擊敗一個極小極度對手

Question

我必須創建一個AI，它必須與其他AI進行競爭。

兩個AI都將在相同的硬件上運行，具有相同數量的處理時間和內存。我知道對手AI將使用alpha beta修剪的minimax算法。

現在我的問題是 - 有什麼辦法打這樣的對手？如果我自己使用minimax - 那麼AI就完全預測對方的動作，並根據遊戲的固有屬性（首先移動勝利等）來解決遊戲。

明顯的解決方案是以某種方式進一步提前考慮可能的更好的評估方法 - 因爲處理器時間是相同的，我無法評估更大的深度（假設相反的AI代碼被同等優化）。我可以使用預先計算的樹來獲得額外的優勢，但是如果沒有超級計算機，我當然無法「解決」任何不平凡的遊戲。

在故意挑選一個非最佳節點（如alpha beta將會修剪的節點）時是否有一些價值？這可能會對對手造成CPU時間損失，因爲他們必須返回並重新評估該樹。它會對我造成懲罰，以及我不得不評估最小最大樹+ alpha測試版，以查看哪些節點alpha beta會修剪而不會獲得任何直接益處。

針對這種對手進行優化的其他策略是什麼？

Answer 1

首先，在選擇非最佳遊戲方面沒有任何價值。假設你的對手將會打出最佳狀態（這是超級極小號搜索的一個基本假設），那麼你的對手將會採取一種行動來利用這個錯誤。一個好的遊戲引擎會有一個散列反駁表條目，其中包含對你的錯誤的反制動作，所以你可以通過瘋狂的舉動來獲得時間。製作不好的動作可以讓電腦對手更快找到。

用像奧賽羅這樣的遊戲來實現的關鍵是，你不能確定什麼是最佳的舉動，直到遊戲後期。這是因爲搜索樹幾乎總是太大而無法全面搜索所有贏得的或失去的位置，因此極小極小組無法確切地告訴您哪些移動會導致勝利或失敗。您只能啓發式地決定停止搜索的位置，隨意調用這些節點的「終端」，然後運行一個評估函數來猜測某個頭寸的贏/輸潛力。

評估函數的工作是評估一個職位的價值，通常使用靜態指標，可以在沒有進一步搜索遊戲樹的情況下進行計算。棋子數量，位置特徵，殘局桌球基礎，甚至是對手心理都可以在這裏發揮作用。您對評估功​​能的智能越強，通常發動機的性能越好。但靜態評估的重點在於取代那些成本太高的搜索。如果你的評估函數做得太多或者效率太低，它可能會比獲得相同信息所需的遊戲樹搜索慢。知道在評估函數中放什麼以及何時使用靜態評估而不是搜索是編寫好遊戲引擎的很大一部分。

Answer 2

有很多方法可以通過AB修剪來提高標準極小極大值。例如，殺手啓發式試圖改善秩序的動作，因爲AB的效率在有序移動的情況下更好。

有關AB上不同搜索增強和變體的大量信息可在chessprogramming.wikispaces.com找到。