c# - 我是否正确地实现了这个 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

有意思的做法，第一次见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 处的最佳 boardScore，但是您没有/使用级别 98..0 中的任何东西，除非没有移动(空)，但是当您注意到自己那部分出了问题。

Tried looking at some pseudo algorithms, but all the seem to return a score. That confuses me, because I don't really want to get a score back, I want to get a Move back.

不过，这就是要走的路。树搜索的主要结果是最佳分支的值。此举本身仅在根级别必不可少。保留它直到您开始实现 alpha/beta，然后您将能够将最好的分支存储在一个表中。

我建议改用普通的 NegaMax，
另见 this SO question .