Альфа-бета-метод обрезки корней

Я пишу простой игровой движок, который может играть в такие игры, как шахматы и шашки, и я не уверен, правильно ли я реализую корневой метод альфа-бета-функции. Это обычная функция:

double AlphaBeta(GameState gameState, int depth, double a, double b)
    {
        if (depth == 0 || gameState.IsOver)
            return Evaluate(gameState);

        var moves = gameState.GetMoves();
        var bestValue = double.MinValue;
        foreach (Move move in moves)
        {
            double value = -AlphaBeta(gameState.MakeMove(move), depth - 1, -b, -a);
            bestValue = Math.Max(value, bestValue);
            a = Math.Max(value, a);
            if (a >= b)
                break;
        }
        return bestValue;
    }

Здесь метод Evaluate всегда возвращает значение с точки зрения игрока, у которого есть ход, а MakeMove возвращает копию исходного состояния игры со сделанным ходом. Но я не уверен, что делать с корневой функцией. Это то, что у меня есть прямо сейчас:

Move AlphaBetaRoot(GameState gameState, int depth)
    {
        var moves = gameState.GetMoves();
        moves = moves.OrderBy(o => AlphaBeta(gameState.MakeMove(o), depth - 1, double.MinValue, double.MaxValue)).ToList();
        return moves[0];
    }

Кажется, пока это работает отлично (я тестировал это с помощью 3x3 Tic Tac Toe), но не делает никакой обрезки для корневого узла. Поэтому я подумал, может быть, это должно быть больше похоже на это:

Move AlphaBetaRoot2(GameState gameState, int depth)
    {
        double a = double.MinValue;
        double b = double.MaxValue;

        var moves = gameState.GetMoves();
        Move bestMove = null;

        foreach (Move move in moves)
        {
            var value = -AlphaBeta(gameState.MakeMove(move), depth - 1, -b, -a);
            if (value >= a)
            {
                a = Math.Max(value, a);
                bestMove = move;
            }
            if (a >= b)
                break;
        }
        return bestMove;
    }

Но я просто не могу заставить это работать, и я не знаю, что делать. Что бы я ни менял, в итоге я получаю что-то, что играет непонятными или проигрышными ходами.

Хотя в Интернете есть много литературы и вопросов по Alpha-Beta Pruning, я ничего не нашел о том, как реализовать корневой метод. Так что буду признателен за любую помощь.


person Terry Anderson    schedule 09.12.2016    source источник
comment
Когда я писал что-то подобное для соединения четырех, я должен был принять во внимание глубину (предпочтительнее меньшее количество ходов до победы), и когда есть несколько одинаково лучших ходов, я случайным образом выбирал один. stackoverflow.com/questions/36792847/   -  person juharr    schedule 09.12.2016
comment
В реальной реализации у меня тоже есть случайность, если все ходы равны; это делает игры намного менее скучными. Однако я не думаю, что это что-то добавит к вопросу. Однако имеет смысл отдавать приоритет победам за меньшее количество действий, я собираюсь это проверить.   -  person Terry Anderson    schedule 09.12.2016
comment
См.: stackoverflow. ком/вопросы/3884793/. Вы, вероятно, хотите double a = -double.MaxValue;   -  person Jeff Y    schedule 10.12.2016
comment
@JeffY Это на C#, поэтому я не думаю, что это применимо здесь; но тем не менее было интересно узнать, так как я тоже использую Java и раньше о ней не слышал.   -  person Terry Anderson    schedule 10.12.2016