游戲AI如何下棋：從Minimax到Alpha-Beta剪枝

游戲AI的決策邏輯和普通搜索完全不同。你不是在找一條路徑，而是在走一步棋的同時，對手正想方設法堵死你。這種對抗性讓游戲決策需要一套獨特的結構。

在游戲搜索中，每一步都會創造一個新狀態。但和簡單的尋路不同，下一個狀態不完全由你控制——對手也在選擇。所以算法必須回答一個關鍵問題："如果對手也下得最好，我的最佳走法是什么？"這就是Minimax的核心思想。

一個基礎的游戲決策流程是這樣的：當前棋盤狀態→可能的走法→對手的回應→評估各個局面→選擇最優走法。Minimax用數學語言表達了這個直覺：MAX玩家試圖最大化分數，MIN玩家試圖最小化分數，最終決策假設雙方都以最優策略對弈。所以游戲AI不只是選一個好棋，而是要選一個能扛住對手最佳反擊的棋。

從實現層面看，Minimax是一個遞歸函數。它接收當前狀態、搜索深度、以及當前是最大化方還是最小化方。如果狀態是終局或深度歸零，就調用評估函數返回分數。如果是最大化方的回合，遍歷所有可能走法，遞歸調用Minimax獲取對手回合的分數，取最大值返回。最小化方則相反，取最小值返回。這樣，對抗性決策就被轉化成了一個遞歸搜索問題。

舉個具體例子。假設一個簡單的棋盤游戲，你有三個選擇：A看起來當下最好，B平平無奇，C有點冒險。一個樸素的AI可能會選A，因為當前盤面分數最高。但Minimax會問更深的問題："我選A之后，對手能做什么？"如果A讓對手下一步就能獲勝，那它其實是個陷阱。Minimax通過向前看避免了這種錯誤。

這就是樸素選擇和Minimax的關鍵區別。樸素選擇只評估當前這一步，忽略對手的最佳回應，容易掉進明顯的陷阱。Minimax則評估未來狀態，假設對手最優對弈，選擇在最壞情況下結果仍然最好的走法。它不是"選分數最高的棋"，而是"選最壞結果中最好的那個"。

但在真實游戲中，博弈樹會爆炸式增長，不可能搜索到終局。這時就需要在有限深度停止，用啟發式函數估計局面價值。評估函數可能考慮子力優勢、棋盤控制、王的安全、機動性、威脅程度等因素。啟發式不保證絕對正確，但給搜索提供了實用的評分規則，讓游戲搜索變得可行。

即便如此，Minimax的效率仍有瓶頸。Alpha-Beta剪枝由此誕生——它能在不改變結果的前提下，剪掉大量無需搜索的分支，讓游戲AI在有限時間內看得更深、算得更準。