Правильно ли я реализовал эту минимаксную функцию?

Question

Это для игры в шашки.См. Историю изменений для более старых версий кода.

    private static Move GetBestMove(Color color, Board board, int depth)
    {
        var bestMoves = new List<Move>();
        var validMoves = board.GetValidMoves(color);
        int highestScore = int.MinValue;
        Board boardAfterMove;
        int tmpScore;
        var rand = new Random();

        Debug.WriteLine("{0}'s Moves:", color);

        foreach (var move in validMoves)
        {
            boardAfterMove = board.Clone().ApplyMove(move);

            if(move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any())
                tmpScore = NegaMax(color, boardAfterMove, depth);
            else
                tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth);

            Debug.WriteLine("{0}: {1}", move, tmpScore);

            if (tmpScore > highestScore)
            {
                bestMoves.Clear();
                bestMoves.Add(move);
                highestScore = tmpScore;
            }
            else if (tmpScore == highestScore)
            {
                bestMoves.Add(move);
            }
        }

        return bestMoves[rand.Next(bestMoves.Count)];
    }

    private static int NegaMax(Color color, Board board, int depth)
    {
        var validMoves = board.GetValidMoves(color);
        int highestScore = int.MinValue;
        Board boardAfterMove;

        if (depth <= 0 || !validMoves.Any())
            return BoardScore(color, board);

        foreach (var move in validMoves)
        {
            boardAfterMove = board.Clone().ApplyMove(move);

            if(move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any())
                highestScore = Math.Max(highestScore, NegaMax(color, boardAfterMove, depth));
            else
                highestScore = Math.Max(highestScore, -NegaMax(Board.Opposite(color), boardAfterMove, depth - 1));
        }

        return highestScore;
    }

    private static int BoardScore(Color color, Board board)
    {
        if (!board.GetValidMoves(color).Any()) return -1000;
        return board.OfType<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3));
    }

Я пробую это с глубиной 0, и результаты верны примерно для половины игры, а затем вдруг начинает облажаться.Один из игроков начнет заявлять, что его счет выше, чем он есть на самом деле.Почему это работает только на половину игры?!

Answer 1

Интересный подход, впервые вижу MaxiMax.Но я вижу здесь проблему:

var minMove = GetBestMove(... board.Clone().ApplyMove(move), ...);
float score = ... BoardScore(color, board.Clone().ApplyMove(minMove));

В этом коде move и minMove - это ходы для разных сторон, и все же вы применяете их одинаково на одном уровне здесь.Вторая строка должна выглядеть примерно так:

float score = ... BoardScore(... board.Clone().ApplyMove(move).ApplyMove(minMove));

Конечно, вы можете сохранить и повторно использовать часть board.Clone().ApplyMove(move).

Но тогда вы все равно теряете информацию: на глубине 100 вы отфильтровываете лучшие показатели BoardScore на глубине 99, но у вас нет / не используется ничего с уровней 98..0, кроме случаев, когда не было никакого движения (ноль)но, как вы сами заметили, эта часть идет не так.

Пробовал смотреть на некоторые псевдоалгоритмы, но все, похоже, возвращают счет.Это смущает меня, потому что я не хочу возвращать счет, я хочу вернуть ход.

Тем не менее, это путь.Основным результатом поиска по дереву является значение наилучшей ветви.Сам ход важен только на корневом уровне.Оставьте это, пока не начнете внедрять альфа / бета, тогда вы сможете хранить лучшие ветви в одной таблице.

Я бы посоветовал перейти на обычный NegaMax,
также см. это SOвопрос .

Answer 2

Нашли ошибку: Что может привести к неправильному расчету через некоторое время?

Новый код:

private static Move GetBestMove(Color color, Board board, int depth)
{
    var bestMoves = new List<Move>();
    IEnumerable<Move> validMoves = board.GetValidMoves(color);
    int highestScore = int.MinValue;
    Board boardAfterMove;
    int tmpScore;
    var rand = new Random();

    Debug.WriteLine("{0}'s Moves:", color);

    foreach (Move move in validMoves)
    {
        boardAfterMove = board.Clone().ApplyMove(move);

        if (move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any())
            tmpScore = NegaMax(color, boardAfterMove, depth);
        else
            tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth);

        Debug.WriteLine("{0}: {1}", move, tmpScore);

        if (tmpScore > highestScore)
        {
            bestMoves.Clear();
            bestMoves.Add(move);
            highestScore = tmpScore;
        }
        else if (tmpScore == highestScore)
        {
            bestMoves.Add(move);
        }
    }

    return bestMoves[rand.Next(bestMoves.Count)];
}

private static int NegaMax(Color color, Board board, int depth)
{
    IEnumerable<Move> validMoves = board.GetValidMoves(color);
    int highestScore = int.MinValue;
    Board boardAfterMove;

    if (depth <= 0 || !validMoves.Any())
        return BoardScore(color, board);

    foreach (Move move in validMoves)
    {
        boardAfterMove = board.Clone().ApplyMove(move);

        if (move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any())
            highestScore = Math.Max(highestScore, NegaMax(color, boardAfterMove, depth));
        else
            highestScore = Math.Max(highestScore, -NegaMax(Board.Opposite(color), boardAfterMove, depth - 1));
    }

    return highestScore;
}

private static int BoardScore(Color color, Board board)
{
    if (!board.GetValidMoves(color).Any()) return -1000;
    return board.OfType<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3));
}

Я не уверен на 100%, что это работает отлично. Кажется, он работает для глубины 0, и обычно для глубины 1 ... помимо этого, я понятия не имею, о чем думает компьютер. По-видимому, не очень умно играет.

Редактировать: Запуск этой и максимальной скорости ... Агент NegaMax против Random. NegaMax всегда побеждает. Смотря баллы за появлением "1000". После этого он всегда побеждает в течение нескольких ходов, так что, похоже, все работает, наконец-то!