点和框游戏的 Java minimax

Question

我正在尝试实现一个使用 Minimax 进行点和框游戏的 AI (http://en.wikipedia.org/wiki/Dots_and_Boxes)

这是我目前所拥有的:

    public Line makeMove(GameState gs) {
    if (gs.getRemainingLines().size() == 1) {
        return gs.getRemainingLines().get(0);
    }

    if (gs.getPlayer() == 1) {
        int minscore = -1;
        GameState g = gs.clone();
        Line lnew = null;
        List<Line> l = gs.getRemainingLines();
        for (Line l2 : l) {
            g.addLine(l2);
            if (evaluate(g) > minscore) {
                minscore = (evaluate(g));
                lnew = l2;
            }
        }
        return lnew;
    } else {
        int maxscore = 999;
        GameState g = gs.clone();
        Line lnew = null;
        List<Line> l = gs.getRemainingLines();
        for (Line l2 : l) {
            g.addLine(l2);
            if (evaluate(g) < maxscore) {
                maxscore = (evaluate(g));
                lnew = l2;
            }
        }
        return lnew;
    }

}

但是，它一直返回 null 并且我认为我没有正确地实现 minimax。任何人都可以给我一些指示。

getRemainingLines() 返回仍然可能的移动列表。

evaluate() 返回一个整数值。

Answer 1

我想建议您完全重构您的代码。查看您的代码(以及为什么这里没有很多响应)的问题在于它难以遵循且难以调试。例如，什么是 gs.getRemainingLines 以及它的具体作用是什么？ (为什么保留行而不是所有合法行？)

但是，通过一些简化，找出正在发生的事情并进行修复会容易得多。

在抽象层面上，minimax 就是这个过程:

float minimax_max(GameState g)
{
    if (g is terminal or max depth reached)
        return eval(g);

    float bestVal = -inf;
    bestMove = null;

    moves = g->getLegalMoves();
    for (m : moves)
    {
        ApplyMove(m);
        if (g->nextPlayer == maxPlayer)
            nextVal = minimax_max(g);
        else
            nextVal = minimax_min(g);
        if (nextVal > bestVal)
        {
            bestVal = nextVal;
            bestMove = m;
        }
        UndoMove(m);
    }

    return bestVal;
}

最后我没有展示如何获得/使用最后一步，但这并不难。您还需要另一个用于 minimax_min 的过程，或者您可以将 if 语句放入代码中。

如果您查看您的代码，您会发现您编写的代码与此接近，但是您在代码中留下了很多游戏特定的细节。但是，您不必考虑这些事情就可以让 minimax 正常工作。

特别是，如果您为 GetMoves()、ApplyMove()、UndoMove() 提供函数，则大多数游戏都可以进行抽象推理，以及评估状态的 eval()。 (进一步的搜索增强功能需要更多的功能，但这会让您走得更远。)

您可能希望以这种方式重构的一些原因:

• 您现在可以分别测试 minimax 和您的其他代码。

• 您可以通过验证是否生成了所有合法移动以及在应用移动后您是否具有正确玩家下一个移动的合法状态来测试您的点和框代码。 (您可以播放和撤消长序列的随机移动，以帮助验证您之后总是回到开始状态。)

• 您可以轻松地针对各个状态测试您的评估函数，以确保其正常工作。 (在实践中，您通常无法搜索到游戏结束来确定获胜者。)

• 您可以通过使用简单的评估函数和测试来测试 minimax 是否做出了正确的移动。 (例如，如果您更喜欢边缘移动，单层搜索应该返回边缘移动)

• 其他人可以更轻松地阅读您的代码。我们可以查看每段代码，看看它本身是否正确，而不必将特定于游戏的实现细节混合到特定于 minimax 的细节中。

• 如果您可以正确应用和撤消移动，则无需复制游戏状态。这将使代码更加高效。

虽然您可以尝试在不重构的情况下修复您的代码(例如，只需找到它返回 null 的第一个位置，这将指出您的错误所在)，但从长远来看，如果没有这些，您的代码将很难调试和改进变化。