查找可能的移動Tic Tac Toe的極大極小算法

Question

我決定創建一個帶有11x11棋盤的Tic Tac Toe遊戲，勝利條件是連續（垂直，水平或對角）5格X或O或當棋盤滿，即沒有可能的移動。

我創建了一個AI對手，它使用minimax算法找到棋盤上的最佳棋步。極大極小（具有α-β修剪）的僞代碼如下：

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

本來，井字棋板的尺寸僅是3×3，這意味着沒有太多的循環極小空單元格。但有了11x11的電路板，就有121個電池！

例如，如果第一輪是X，那麼O有120個可能的移動。 O會嘗試每次移動以找到最佳值，因此該函數的運行時間的階乘爲120.

我的問題是，我們可以以某種方式減少可能的移動？例如，如果第一個玩家在中心的某處移動，那麼我們不需要檢查某個角落或邊緣單元的最小極大值。

Answer 1

如果我正確地理解了這個問題，Alpha-Beta-Pruning本身旨在通過停止查找相應的最大值或最小值來減少調查移動的數量。如果這還不夠，則需要採用一些啓發式方法。這意味着遊戲樹不被調查到樹葉（上面的僞代碼描述沒有這樣做），但是引入了一些關於遞歸深度的人爲約束。如果達到遞歸深度，如果棋盤不處於終端狀態，則棋盤必須進行啓發式評估。