为Tic Tac Toe的极小值算法找到可能的移动

Question

我决定用11x11的棋盘创建一个井字游戏，获胜条件是连续5个单元格（垂直、水平或对角线），或者当棋盘满了，即没有可能向左移动。

我创建了一个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
    ....

最初，Tic-tac趾板的大小只有3x3，这意味着没有太多的空单元来循环minimax。但在11x11板上，有121个单元！

例如，如果第一圈是X，则O有120个可能的移动。O将尝试每一步以找到最佳的播放值，因此函数的运行时间是120的阶乘。

我的问题是，我们能否减少可能的行动？例如，如果第一个玩家移动到中心的某个位置，那么我们不需要检查某些角或边单元格的极小极大值。

Answer 1

如果我正确理解了这个问题，Alpha-Beta修剪本身旨在通过在找到相应的最大值或最小值时停止来减少所调查移动的数量。如果这还不够，则需要采用一些启发式方法。这意味着博弈树不会一直研究到叶子（上面的伪代码描述没有这样做），而是引入了递归深度的一些人工边界。如果达到递归深度，如果电路板未处于终端状态，则必须对其进行启发式评估。