我是否正确实现了这个极小化极大化函数？

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的方法，得分在游戏的前半段是正确的，但突然间就开始出现错误。其中一个玩家会宣称他的得分比实际高。为什么只有前半段游戏有效呢？！

- mpen

---

现在这是一个最大化问题。对于对手，你需要瞄准最小分数。此外，您最好不要使用浮点数，而是可以使用整数，其值乘以2（浮点数速度较慢且不精确）。 - Imre L

@lmre：我没想到使用浮点数会有太大的影响，但如果运行了几十亿次，它可能会累加起来。 - mpen

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，但除了当没有移动（null）时，您不会在98..0级别中使用任何东西，但正如您自己注意到的那样，这一部分出错了。

尝试查看一些伪代码，但它们似乎都返回一个分数。这让我感到困惑，因为我真的不想得到一个分数回来，我想得到一个移动。

不过，这是正确的方法。树搜索的主要结果是最佳分支的值。移动本身只是在根级别上才是必要的。等到开始实现alpha/beta时再考虑它，那时您将能够在单个表中存储最佳分支。

我建议切换到常规NegaMax，还可以参见此SO问题。

- H H

---

在这段代码中，move和minMove是不同方向的移动，但你却在这里同等地应用它们。它应该是为了找出针对对手的最佳移动，然后计算当前玩家的得分，如果对手做出了好的决策，那么分数会变低……但是我最大化了这个得分……是否意味着我 实际上 假设了玩家会做出错误的决策，因为我最大化的是错误的东西？明天我有机会时会看一下NegaMax。谢谢。 - mpen

但是你仍然会失去信息：在深度100处，你过滤掉了深度99中的最佳boardScore，但你没有使用来自级别98..0的任何东西。-- 最终得分不是我关心的吗？假设两个玩家都做出最佳移动，你想要最大化最终状态，而不是中间的任何东西？ - mpen

你的 Move 类实际上是一个完整的 Branch 吗？ - H H

我正在使用您的倒计时深度，从您的代码中可以看出您没有使用终止状态值。 - H H

不过，一个“移动”基本上只有起始和结束位置，以及进行移动的棋子的颜色。 - mpen

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));
}

我并不完全相信这个程序能够完美地工作。它似乎可以在深度为0时正常运行，并且通常在深度为1时也能正常运行...但是在深度超过1之后，我不知道计算机在想什么。它似乎还没有表现出超级智能的水平。

编辑：以最大速度运行此程序... NegaMax代理与随机代理对战。NegaMax总是获胜。观察“1000”出现的次数，他总是在几轮之后获胜，所以它最终似乎确实能够正常工作了！

- mpen