4

So I was looking up Mini-max for a Tic-Tac-Toe Game, but couldn't understand how the recursion worked? Okay, so basically here are my questions:

  1. How does minimax know whose turn is it? Whats the best way to indicate the player whose turn it is generating?
  2. How do you generate possible moves?
  3. How do you know when you are at a terminal node, and how do you generate the terminal nodes?

For example in this Pseudo-code

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 is a board correct? And is the depth how many plies the code has to go down in recursion? Also what is the max function and where are the nodes being generated from?

Now, so far I have this code for creating a board:

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

But how would I know whose turn is it? And how do I generate the child nodes for the board?

4

3 回答 3

5

我们将首先以您的井字游戏为例。

  • 极小极大算法最适合玩家交替回合的游戏，但也适用于玩家每回合可能进行多次移动的游戏。为简单起见，我们假设前者。在这种情况下，您不需要在每个节点上存储“X 移动”或“O 移动”，因为这可以通过节点深度的奇偶性来确定（无论我是偶数步还是奇数步数，从顶部开始）。
  • 从每个位置生成可能的移动需要您知道它是谁的移动（可以像以前一样确定），以及从特定位置开始合法移动的规则。对于像井字游戏这样的简单游戏，给定一个位置，枚举所有状态就足够了，这些状态包括当前位置的副本加上一个属于当前玩家的新棋子，依次放置在每个空方格上。对于像奥赛罗这样的游戏，你还必须检查每个位置以确保它遵循规则，并根据规则的后果更新最终位置（对于奥赛罗，翻转一堆棋子的颜色）。一般来说，从您跟踪的每个有效位置，您都会枚举一个新棋子的所有可能位置，并检查规则集允许哪些位置。
  • 一般来说，你永远不会生成整棵树，因为游戏树的大小很容易超过地球的存储容量。您始终设置最大迭代深度。因此，终端节点只是处于最大深度的节点，或者是不存在合法移动的节点（对于井字游戏，每个方格都填满的棋盘）。您不会事先生成终端节点；它们是在游戏树构建过程中自然生成的。Tic-tac-toe 非常简单，您可以生成整个游戏树，但不要尝试使用您的 tic-tac-toe 代码，例如 Othello。

查看您的伪代码：

  • 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）的奇偶性和我们对谁先走的记录来检查它是由谁走的。

于 2012-07-28T19:32:03.273 回答
2

1）极小极大如何知道轮到谁了？指示正在生成轮到的玩家的最佳方式是什么？

你有这个depth论点。如果深度是偶数，则轮到一名玩家，如果深度为奇数，则轮到另一名玩家。

2）你如何产生可能的动作？

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

3）你怎么知道你什么时候在终端节点，你如何生成终端节点？

终端节点是某人获胜的节点。您通过递归生成它们。每个递归调用都应该被赋予棋盘的当前状态。我猜那是你的伪代码中的nodeandchild参数。因此，如果在那种情况下有人赢了，那就是终结，否则你尝试所有合法的动作并递归。

于 2012-07-28T19:33:49.883 回答
2

我可以提供一些关于您正在寻找什么的想法，因为我为井字游戏编写了一个极小极大算法。

直接回答您的问题：

  1. 我的极小极大算法没有确定这一点。它接受了一个参数，该参数决定了算法使用的是哪个玩家。

  2. 知道玩家要移动，循环通过棋盘上的所有空白方格，并为每个方格生成一个节点，其中包含当前玩家在该方格中的令牌。从那里递归地进行。

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

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

  • 输入：要移动的玩家，以及棋盘的状态。
  • 找出黑板上剩下的所有空格。
    • 使用玩家在该空间中的移动生成一个新棋盘。
    • 如果游戏结束，则生成一个包含游戏结果的节点。
    • 否则，运行算法，传入另一个玩家和新棋盘，并生成一个包含对手理想移动结果的节点。
  • 确定哪个节点（移动）会导致最好的最坏情况。
  • 输出：最好的棋步，以及从中得到的游戏结果信息。
于 2012-07-28T19:44:37.227 回答