Я правильно внедрил эту функцию MiniMax?

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

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

Новый код:

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 ... за пределами этого, я понятия не имею, что думает компьютер. До сих пор не играет супер разумно.

Редактировать: Запуск этой и максимальной скорости ... Агент негамакса VS Random. Негамакс всегда выигрывает. Наблюдение за баллами для вхождений «1000». После этого он всегда выигрывает в нескольких оборотах, поэтому он, кажется, работает, наконец!

Answer 2

Интересный подход, первый раз, когда я вижу 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 вы отфилировали лучший настольный вал на глубине 99, но у вас нет / не используйте что-либо с уровня 98,0, за исключением случаев, когда не было движения (NULL), но, как вы заметили, что Часть идет не так.

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

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

Я бы советую перейти на обычный негамакс,
также см Это так вопрос.