minimax递归究竟是如何工作的？

Question

所以我正在寻找一个Tic-Tac-Toe游戏的Mini-max,但是无法理解递归是如何工作的？好的,基本上这里是我的问题:

1. 极小极大如何知道轮到谁了？什么是最好的方式来表明轮到它生成的玩家？
2. 你如何产生可能的动作？
3. 您如何知道何时在终端节点,以及如何生成终端节点？

例如在这个伪代码中

function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
    return the heuristic value of node
? = -?
for child in node: # evaluation is identical for both players
    ? = max(?, -minimax(child, depth-1))
return ?

A node是一块板子吗？并且代码在递归中的深度是多少？还有什么max功能以及从哪里生成节点？

现在,到目前为止,我已经有了创建板的代码:

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

但我怎么知道轮到谁了？我如何为电路板生成子节点？

Answer 1

我们首先以你的tic-tac-toe为例.

• minimax算法最适合玩家轮流转换的游戏,但可以适应玩家每回合可以进行多次移动的游戏.为简单起见,我们假设前者.在这种情况下,您不需要为每个节点存储"X to move"或"O to move",因为这可以通过节点深度的奇偶校验来确定(无论我是偶数步数,还是奇数从顶部开始的步数.
• 从每个位置生成可能的移动需要您知道它的移动(可以像以前那样确定),以及从特定位置移动合法的规则.对于一个简单的游戏像井字棋,给定一个位置,就足够了枚举所有的包括当前位置的副本加上一块新的状态,属于当前播放器,放置在依次对每个空方.对于像奥赛罗这样的游戏,您还必须检查每个位置,以确保它遵循规则,并根据规则的后果更新最终位置(对于奥赛罗,翻转一堆碎片的颜色).通常,从您跟踪的每个有效位置,您枚举新片段的所有可能位置,并检查规则集允许哪些位置.
• 通常,您永远不会生成整个树,因为游戏树大小很容易超过地球的存储容量.您始终设置最大迭代深度.因此,终端节点只是最大深度的节点,或者不存在合法移动的节点(对于井字游戏,每个正方形填充的板).您不预先生成终端节点; 它们在游戏树构建过程中自然生成.Tic-tac-toe很简单,你可以生成整个游戏树,但是不要尝试使用你的tic-tac-toe代码,例如奥赛罗.

看看你的伪代码:

• max(a, b)是任何返回a或更大的函数b.这通常由数学库或类似物提供.
• 这depth是您要搜索的最大深度.
• 您正在计算的启发式值是一些描述电路板价值的数值.对于像井字棋游戏,这是很简单的,你可以枚举整个博弈树,你可以指定1为获胜玩家做了分析,一个板位置-1的,对于其他玩家赢得板位置,以及0任何不确定的立场.一般来说,你必须自己做一个启发式的方法,或者使用一个被广泛接受的方法.
• 您可以在分析期间根据父节点动态生成节点.您的根节点始终是您进行分析的位置.

如果你还没有使用图形或树木,我建议你先这样做; 特别是树原语对于这个问题至关重要.

作为对此线程中的注释的回答,请求确定给定节点的转向的示例,我提供了这个伪Python:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

每个节点都能够跟踪"根"节点的绝对深度.当我们试图确定我们应该如何为下一步行动生成董事会职位时,我们会根据我们的深度(结果self.depth % 2)以及我们先移动的记录来检查其移动情况.