极小极大递归是如何工作的？

Question

极小极大递归是如何工作的？

4

所以我在查找Tic-Tac-Toe游戏的Mini-max算法时，无法理解递归是如何工作的？好的，基本上这是我的问题：

Mini-max算法如何知道轮到谁下棋？最好的方法是什么来指示生成下棋者的轮次？
如何生成可能的移动方案？
如何知道何时到达终端节点，以及如何生成终端节点？

例如，在这个伪代码中：

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 α

节点是一个棋盘，对吗？深度是代码要递归下降多少个杆位？ 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];
};

但是我怎么知道该轮到谁了？以及如何为棋盘生成子节点？

- Rivasa

前两个问题与极小化极大算法无关，而是与您正在查看的特定游戏即井字棋及其实现细节有关。 - Rndm

好的，但我只是在寻找一般的想法。 - Rivasa

你还没有准备好解决这个问题。试着做一些更简单的事情吧。 - ddyer

2

哎呀，感谢你的信任。我先做了一些简单的东西，所以才转向极小化算法。 - Rivasa

3个回答

2

1) minimax如何知道轮到哪个玩家？最好的方式是什么来指示生成轮到哪个玩家？

您有一个名为depth的参数。如果深度为偶数，则轮到一个玩家，如果深度为奇数，则轮到另一个玩家。

2) 如何生成可能的移动？

使用游戏规则。在井字棋中，可能的移动意味着将自己的标记放入空闲单元格。

3) 如何知道您处于终端节点，并如何生成终端节点？

终端节点是某个人赢得了游戏的节点。通过递归生成它们。每个递归调用应该给出棋盘的当前状态。我猜这是您伪代码中的node和child参数。因此，如果在那种情况下有人赢了，那么它就是终端，否则您尝试所有合法的移动并进行递归。

- MvG

如何计算特定深度的终端节点值。比如，我有一个深度值为10的树，其中有两条完整路径，一条是某人赢了，另一条是不完整的路径。在这种情况下，我该如何计算所有节点的终端值。谢谢。 - Anish

@Anish：我会说，在终端节点，获胜者的身份是该节点的价值，根据游戏规则可能附带一些分数。对于非终端节点，您需要递归计算其价值。 - MvG

2

我可以提供一些关于你所寻找的信息，因为我曾经为井字棋编写过一个极小化极大算法。

直接回答您的问题：

我的极小化极大算法没有确定这一点。它接受一个参数，确定了算法使用哪个玩家。
知道要移动的玩家后，在棋盘上循环遍历所有空白格子，对于每个空白格子，在该格子中生成带有当前玩家标记的节点，然后从那里递归进行。
我使用了一个函数来返回一个值，该值指示游戏是否结束以及是否是平局或赢了。

我的基本算法是这样的:

输入：要移动的玩家和棋盘状态。
查找棋盘上所有剩余的空白格子。
- 在该空白格子中生成玩家的新棋盘。
- 如果游戏结束，生成带有游戏结果的节点。
- 否则，运行算法，传入另一个玩家和新棋盘，并生成对手理想移动的结果节点。
确定哪个节点（移动）导致最佳的最坏情况。
输出：最佳移动以及有关游戏结果的信息。

- Kendall Frey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- atomicinf · Accepted Answer

我们先以你的井字棋为例。

- 极小极大算法最适合玩家轮流行动的游戏，但可以调整为玩家每回合可进行多个移动的游戏。我们为简单起见假设为前者。在这种情况下，你不必在每个节点上存储“X要走”或“O要走”，因为可以通过节点深度的奇偶性（我距离顶部是偶数步还是奇数步）来确定。 - 从每个位置生成可能的移动需要知道谁要走（可以像之前一样确定），以及特定位置的合法移动规则。对于像井字棋这样简单的游戏，给定一个位置，只需枚举所有状态，其中包括当前位置的副本加上新的棋子，这些棋子属于当前玩家，并依次放置在每个空方格中。对于像黑白棋这样的游戏，您还必须检查每个放置是否遵循规则，并根据规则的后果更新最终位置（对于黑白棋，翻转一堆棋子的颜色）。通常，从您正在跟踪的每个有效位置开始，您会枚举所有可能放置新棋子的位置，并检查哪些位置符合规则集。 - 一般来说，您永远不会生成整个树，因为游戏树大小很容易超过地球的存储能力。您始终设置最大迭代深度。然后，终端节点是最大深度处的节点，或者没有合法移动存在的节点（对于井字棋，是一个每个方格都填满的棋盘）。您不会预先生成终端节点；它们在游戏树构建期间自然生成。井字棋足够简单，可以生成整个游戏树，但不要尝试将井字棋代码用于例如黑白棋之类的游戏。 - 查看您的伪代码：

max（a，b）是返回a或b中较大值的任何函数。这通常由数学库或类似库提供。

深度是您将搜索的最大深度。

您正在计算的启发式值是描述棋盘价值的某个数值。对于像井字棋这样简单到可以枚举整个游戏树的游戏，您可以将赢得分析的玩家的棋盘位置指定为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的结果）和我们谁先移动的记录来检查轮到谁移动了。