4

这是一个跳棋游戏。查看旧版本代码的修订历史。

    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，并且在大约一半的比赛中得分是正确的，然后突然之间它开始搞砸了。其中一名球员将开始宣称他的分数高于实际分数。为什么只能玩半场？！

4

2 回答 2

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 的最佳 boardScore，但您没有/使用级别 98..0 中的任何东西，除非没有移动（空），但正如您注意到的那样部分出错。

尝试查看一些伪算法，但似乎都返回了分数。这让我很困惑，因为我真的不想拿回一个分数，我想拿回一个 Move。

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

我建议切换到常规的 NegaMax，
另请参阅这个 SO question。

于 2010-09-04T07:57:01.043 回答
0

发现错误：什么可能导致它在一段时间后开始计算错误？

新代码：

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 agent vs Random。NegaMax 总是赢。查看出现“1000”的分数。在那之后他总是在几回合内获胜，所以它看起来确实奏效了，终于！

于 2010-09-06T19:52:47.647 回答