極小化極大算法

極小化極大算法是一種為具有完全信息的有限兩人零和博弈確定最優博弈策略的算法。

用極小化極大算法計算的策略稱為極小化極大策略。 由雙方玩家的極小極大策略形成的策略對構成納什均衡。

在非零和博弈中，對手的輸不一定與你的贏同時發生，極小化極大算法可能無法提供最佳策略。

極小化極大算法的變體構成了象棋程序等下棋程序的核心元素。 與此同時，計算機計算能力的增強導致即使是象棋這樣復雜的游戲，現在每個人都可以輕松被計算機打敗。

如果玩家 A 獲勝，理想的評分函數會為某個位置分配值 +1，如果玩家 B 獲勝則為 -1，如果平手則為 0。 如果您可以構建從所有游戲位置到xxx深度的搜索樹，那么該算法將玩出完美的游戲。

在幾乎所有其他游戲中，這計算量太大。因此，人們滿足于僅在給定搜索深度（范圍）內構建搜索樹。修改了評估函數，A 的非常好的游戲位置獲得非常高的值， B 的非常好的游戲位置收到非常高的值非常低的值。為了確定值，人們使用啟發式方法進行估計。

該算法從葉子的底部開始，然后上升到根。 在級別 3 中，算法選擇子節點的最小值并將其分配給父節點（已最小化）。 在級別 2 中，xxx的子節點然后被分配給父節點（它被最大化）。 這是交替進行的，直到到達根。 根被賦予xxx子節點的值。

極小化極大算法在要檢查的可能移動數量方面是線性的。 通常，搜索深度越長，所需時間越長。另一方面，搜索結果的質量通常隨著搜索深度的增加而增加（取決于數值評估）。

因此有各種優化的變體，例如

• 可變搜索深度：如果每種游戲情況只有少數可能的移動，例如因為游戲場上只剩下幾塊棋子位于，可以增加搜索深度。
• 動態搜索深度：如果搜索樹中某一點的數值從一級到另一級發生顯著變化，則可以局部增加搜索深度。

存儲先前檢查的位置及其評估可顯著節省時間。 如果從起始位置通過不同的移動序列到達一個位置，則不必每次都搜索整個底層搜索樹。 在實踐中，高效的哈希表通常用于這種存儲。

迭代加深尤其適用于搜索時間有限的情況。 搜索從要檢查的位置開始反復開始，逐漸增加所需的搜索深度。 如果已經檢查過的位置如上所述被保存，那么只有自上次搜索以來已經到達的位置需要用評價函數來評價。 這個過程一直持續到超過可用的搜索時間或獲得“相當不錯”的結果。

如果沒有迭代深度優先搜索，如果超過了時間限制，在最壞的情況下只會檢查一個單一的移動，但這是一個非常大的深度。 下一步可能只需要一次反擊就可以確保獲勝，但一開始就不會嘗試。

為了簡化代碼并能夠以相同的方式對待搜索樹的每個節點，定義每個玩家都試圖為自己獲得xxx結果，即評估函數的xxx值。 為此，后續位置的評估必須乘以 ? 1。 不再需要區分是 A 還是 B 的走法，因此應該計算xxx值或最小值，但在每個位置只計算后續位置的否定評估的xxx值。