为 Tic Tac Toe 的极小极大算法找出可能的走法

Question

我决定创建一个 11x11 棋盘的井字游戏，获胜条件是 5 个单元格 X 或 O 连续（垂直、水平或对角线）或当棋盘是已满，即无法向左移动。

我创建了一个 AI 对手，它使用 minimax 算法来找到棋盘上的最佳着法。 minimax（带alpha-beta剪枝）的伪代码如下：

function alphabeta(node, depth, α, β, maximizingPlayer)
    if the game ends:
        return the heuristic value of the current state
    if maximizingPlayer
        v := -∞
        for each possible move in board // notice this
            v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
            α := max(α, v)
            if β ≤ α
              break (* β cut-off *)
        return v
    else
    ....

最初，井字棋盘的大小只有 3x3，这意味着没有多少空单元格可以循环 minimax。但是11x11的板子，有121个cell！

例如，如果第一轮是 X，那么 O 有 120 种可能的移动。 O 将尝试每一步以找到最佳价值，因此函数的运行时间是 120 的阶乘。

我的问题是，我们能否以某种方式减少可能的走法？例如，如果第一个玩家移动到中心的某处，那么我们不需要检查某些角落或边缘单元格的极小值。

Answer 1

如果我对问题的理解正确，Alpha-Beta-Pruning 本身的目的是通过在找到相应的最大值或最小值时停止来减少调查的移动次数。如果这还不够，则需要采用一些启发式方法。这意味着博弈树没有被调查到叶子（上面的伪代码描述没有这样做），而是引入了一些对递归深度的人为限制。如果达到递归深度，如果棋盘未处于终止状态，则必须对其进行启发式评估。

为 Tic Tac Toe 的极小极大算法找出可能的走法

Find possible moves for Tic Tac Toe's minimax algorithm

algorithm

tic-tac-toe

minimax

alpha-beta-pruning