我如何从 TicTacToe 中的 Min Max 中提取出我的最佳动作？

Question

        int minmax(Board game, int depth)
        {
            if (game.IsFinished() || depth < 0)
                return game.Score(game.Turn);

            int alpha = int.MinValue + 1;
            foreach (Point move in game.Generate_Moves())
            {
                Board currentBoard = game;
                currentBoard.Do_Move(move); 

                alpha = max(alpha, -minmax(currentBoard, depth-1));
                currentBoard.Undo_Move(move);
            }

            return alpha;
        }

问题是，这个小函数告诉我游戏是赢、输还是平，但我怎样才能获得使我获胜的棋步呢？我的 Point 类是一个简单的类，有 2 个坐标 X、Y，我想得到一个点的答案，这样我以后就可以说类似 game.Do_Move(myPoint) 的内容。

如果某些函数不明显：

game.IsFinished() - 如果赢/输/平局则返回 true，否则

返回 game.Score(turn) - 返回 -1/ 0/1，如果玩家的下一步行动是输/平/赢

game.Generate_Moves() - 返回包含可用动作的列表

game.Do_Move() - 将移动应用到游戏中的无效

game.Undo_Move() - 不言自明

Answer 1

如果在游戏树的根节点上调用的 minimax 函数返回选择的移动和分数就足够了。对于游戏树的所有其他节点，该函数只需要返回分数。因此，通常的方法是实现两个略有不同的极小极大函数 - 查看注释#2对此 NegaMax 框架的描述。
应用于您的 minimax 接口，您将具有以下附加功能：

int minimaxWithMove(Board game, int depth, Point& choosen)
{
    assert (!game.IsFinished() && depth > 0); // not possible at root node
    int alpha = int.MinValue + 1;
    foreach (Point move in game.Generate_Moves())
    {
        Board currentBoard = game;
        currentBoard.Do_Move(move);
        int score = -minmax(currentBoard, depth-1);
        if (score > alpha)
        {
            alpha = score;
            choosen = move;
        }
    }
    return alpha;
}

请注意，我已删除对 Undo_Move 的调用，因为不需要它，因为您在每次迭代中都会复制 game 。

Answer 2

您需要应用 极小极大定理。

您基本上必须制作一个博弈树，其中的每个节点这棵树是一个棋盘位置，每个孩子都是合法移动的结果。叶子节点（游戏结束的地方）将根据 game.score() 获得分数，一个玩家试图沿着通向高分的路径选择移动，而另一个玩家则尝试选择迫使低分的移动分数。该定理将帮助您了解如何严格应用该想法。