об алгоритме AlphaBeta

Question

Я испытал алгоритм AlphaBeta со своим старым шахматным движком, и теперь я пытаюсь написать новый движок, и я вижу, что алгоритму встречаются бета-сокращения, но, по моему мнению, этого никогда не должно быть, если я не использую суженный окно. Я ошибся ? Я использую int.MaxValue для бета-версии и -int.MaxValue для альфы, так что может привести к отключению бета-версии?

Редактировать:

Полный код здесь.

    public Result Search(int maxDepth)
    {
        int alpha = -int.MaxValue, beta = int.MaxValue, ply = maxDepth;
        var bestLine = new Stack<Move>();

        var score = AlphaBeta(alpha, beta, ply, bestLine);

        return new Result(score, bestLine);
    }
    int AlphaBeta(int alpha, int beta, int ply, Stack<Move> bestLine)
    {
        if (ply <= 0) return Evaluation.Evaluate(Board);
        var moves = Board.GenerateMoves();
        foreach (var move in moves)
        {
            Board.MakeMove(move);

            eval = -AlphaBeta(-beta, -alpha, ply - 1, bestLine);

            Board.TakeBackMove(move);

            if (eval >= beta)
            {
                return beta;
            }
            if (eval > alpha)
            {
                alpha = eval;
                if (ply == 1) bestLine.Clear();

                bestLine.Push(move);
            }
        }
        return alpha;
    }
}

Answer 1

Обратите внимание, что в вашей рекурсии вы передаете параметры в обратном порядке:

eval = -AlphaBeta(-beta, -alpha, ply - 1, bestLine);

В обратном порядке, как они объявлены:

int AlphaBeta(int alpha, int beta, int ply, Stack bestLine)

Таким образом, они меняют роли на каждом слое.Альфа может быть обновлена, и это эквивалентно уменьшению беты на более глубоких уровнях дерева.

Для меня это выглядит странным сочетанием Альфа / Бета и Негамакс, так как оба игрока пытаются уменьшить счет,который отрицается на каждом уровне.

Answer 2

ОК, вы правы в отношении MinValue / MaxValue.

Я немного устала от NegaMax и AlphaBeta, но когда я вижу

   if (eval >= beta)
   {
       return beta;
   }
   if (eval > alpha)
   {
   }

Вы тестируете > для обоих пределов, это не так

Редактировать: Кажется, это просто проблема именования / понимания.Ваш AlphaBeta() метод может быть назван более точно NegaMaxWithAlphaBeta().Из-за чередующихся ролей альфа и бета в NegaMax именование этих параметров не совсем совпадает с MiniMax.

Я вижу, что алгоритмы сталкиваются с бета-отключениями, но, по моему мнению, этого никогда не должно происходить

Да, это должно произойти.И это только бета-отсечение на равных уровнях.На нечетных уровнях if (eval >= beta) проверяет альфа-отсечку.

, если я не использую суженное окно.

Я думаю, что вы используете сужающееся окно альфа / бета.

Но, возможно, этот ответ поможет вам лучше объяснить вашу проблему.