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

StackOverflow https://stackoverflow.com//questions/11703846

题

所以我正向TIC-TAC-TOE游戏查找MINI-MAX，但无法理解递归的工作方式？好的，所以基本上是我的问题：

  1. Minimax如何知道谁的转弯是什么？什么是表示转弯它正在生成的玩家的最佳方式？
  2. 如何生成可能的移动？
  3. 您如何知道何时在终端节点时，以及如何生成终端节点？

    4. 例如在这个伪代码中

    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 α
    .

    一个node是一个正确的电路板？并且是代码在递归中缩小的潜力的深度？还有什么是生成的世代odeTagcode函数，以及从哪里生成的节点？

    现在，到目前为止，我有这个代码创建一个板：

    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];
};
    .

    但我怎么知道谁的转弯是谁？以及如何为板生成子节点？

有帮助吗？

解决方案

我们将首先使用您的TIC-TAC-TOE作为示例。

  • 一个最小的算法最适合玩家交替转弯的游戏，但可以适应玩家每圈可以多次移动的游戏。为了简单起见，我们将假设前者。在这种情况下，您不需要将“X X移动”或“O才能移动”，因为可以通过节点深度的奇偶校验（无论是偶数步数，还是奇数从顶部的步数）。
  • 从每个位置产生可能的移动需要您知道它是（可以像以前确定的）的移动，以及来自特定位置的法律移动规则。对于一个简单的游戏，如TIC-TAC-TOE，给定一个位置，它足以枚举由当前位置的副本组成的所有状态，属于当前播放器，依次放置在每个空方块。对于像OTHELL这样的游戏，您还必须检查每个展示位置，以确保它遵循规则，并根据规则的后果更新最终位置（对于奥赛罗，翻转一堆颜色的颜色）。一般来说，从您跟踪的每个有效位置，您枚举新一块的所有可能放置并检查规则集是否允许哪些位置。
  • 一般来说，您从不生成整个树，因为游戏树大小可以很容易地超越地球的存储容量。您始终设置最大的迭代深度。然后，终端节点只是在最大深度处的节点，或者没有存在合法动作的节点（对于Tic-Tac-Toe，一个带有每个方形填充的电路板）。您不会事先生成终端节点;他们在游戏树施工期间自然地生成。 TIC-TAC-TOE很简单，你可以 can 生成整个游戏树，但是不要尝试使用您的TIC-TAC-TOE代码。奥赛罗。

查看您的伪代码：

  • max(a, b)是返回a或b的任何函数。这通常由数学库或类似的。
  • depth是您将搜索的最大深度。
  • 您计算的启发式值是一些描述板的值的数值值。对于像TIC-TAC-TOE这样的游戏，这很简单，您可以枚举整个游戏树，您可以指定用于为播放器进行分析的播放器的电路板位置，为另一个获胜的板位置的板位置指定1播放器和生成的任何不确定位置的-1。一般来说，你必须自己做出一个启发式，或者使用众所周心的人。
  • 根据其父节点，在分析期间，您可以在飞行中生成节点。您的根节点始终是您正在进行分析的位置。

如果你还没有使用图形或树木，我建议你先这样做;尤其是树原语是基本这个问题。

作为该线程中发表评论的答案，要求确定其适用于给定节点的示例，我提供此伪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)
.

每个节点都能够跟踪其从“根”节点的绝对深度。当我们尝试确定我们应该如何生成下一步移动的董事会职位时，我们检查它是基于我们深度的奇偶校验的移动（世代odicetagcode的结果）以及我们首先移动的记录。

其他提示

1）Minimax如何知道它的转弯是什么？什么是指示它的播放器的最佳方法是生成的？

您拥有该属性icetagcode参数。如果深度甚至，那么它是一个玩家的转弯，如果它是奇怪的话，那么它是另一个玩家的转弯。

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

使用游戏规则。在Tic Tac Toe中，可能的移动装置将一个人的标记放入自由池中。

3）您如何知道何时处于终端节点，以及如何生成终端节点？

终端节点是某人赢得的节点。您通过递归生成它们。每个递归调用应给出电路板的当前状态。我猜这是伪代码中的depth和node参数。所以如果在那种情况下，有人赢了，那么它的终端，否则你会尝试所有法律动作和反复生命。

我可以提供一点想法，即您正在寻找什么，因为我为TIC-TAC-TOE写了一个Minimax算法。

直接回答您的问题：

  1. 我的最小算法没有确定。它接受了一个参数，确定算法使用哪个播放器使用。

  2. 了解播放器移动，循环通过板上的所有空白方块，以及每一个，在该方形中使用当前播放器的令牌生成一个节点。递归地从那里进行。

  3. 我使用了一个返回一个值的函数，该值指示游戏是否结束，以及是否是绘制或胜利。

    4. 我的基本算法是这样做的：

    • 输入：播放器移动，以及板的状态。
    • 在电路板上找到剩下的所有空格。
      • 通过玩家在该空间中的移动中生成一个新电路板。
      • 如果游戏结束，则会通过游戏结果生成节点。
        • 否则，否则，运行算法，传入另一个播放器和新板，并在对手的理想移动结果中生成一个节点。
    • 确定哪个节点（移动）导致最佳最坏情况。
    • 输出：最佳举动，以及关于游戏结果的信息。
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top