人工智慧/搜尋/對抗搜尋/極小極大搜尋

極小極大搜尋以其在計算所有資訊都可用的雙人遊戲中最佳行動的有效性而聞名，例如棋盤遊戲或井字棋 (Muller, 2001)。它包括遍歷一棵樹，該樹捕獲了遊戲中所有可能的行動，其中每個行動都以一方的得失來表示。因此，它只能用於在零和遊戲中做出決策，在一方獲勝的博弈中，另一方必敗。理論上，這種搜尋演算法基於馮·諾依曼的極小極大定理，該定理指出，在這些型別的遊戲中，總存在一組策略，導致雙方獲得相同的值，並且由於這是可以預期獲得的最佳值，因此應該採用這組策略 (Kulenovic, 2008).

描述

第一步是根據玩家 1 的效用給每個節點一個值。這些值源自終端節點的值，每個終端節點都代表遊戲結束。樹的每一層交替進行玩家 1 的行動（她試圖最大化自己的分數）和玩家 2 的行動（他試圖最小化玩家 1 的分數以破壞她的成功）。如果終端節點上方的層代表玩家 2 可能的行動，那麼節點的值將是其子節點中值的最低值，即最小值。另一方面，如果這一層代表玩家 1 可能的行動，那麼其節點的值將是其子節點中值的最高值。最後，一旦所有節點都被分配了值，玩家 1 就可以做出決定，她只需選擇會導致最高值的行動 (Russell & Norvig, 1995)。圖 1 說明了此過程。

,

圖 1 : 為節點分配值並決定最佳行動。

虛擬碼

此虛擬碼改編自 Russell 和 Norvig (1995) 提供的版本。

function minimaxDecision (game)
	for each possible move in game
		moveValue = minimaxValue(state, game)

	return move with highest value

function minimaxValue (state, game)
	if terminal node
		return utility

	if player 1's turn
		return highest value of children

	if player 2's turn
		return lowest value of children

複雜性、缺點和未來方向

這種搜尋的一個缺點是，它假設對手將以有效地最小化你的收益並最大化其自身收益的方式行動。但是，如果你的對手是非理性的、初學者或容易犯錯的人類，這將不成立。在某些情況下，最好賭一把，並希望你的對手不會注意到微妙的反擊 (Moore & Knuth, 1975)。

此外，表示像井字棋這樣簡單遊戲的行動並不困難，但是對於像棋盤遊戲這樣的遊戲，表示所有可能的行動在計算上會變得非常昂貴。因此，程式設計師通常依靠進一步的演算法來縮小搜尋範圍，例如 alpha-beta 剪枝 (Moore & Knuth, 1975)。這包括當確定一個節點的值不可能高於相鄰節點的值時停止計算該節點的效用。有關稱為 min/max 近似的另一種方法，請參閱 Rivest (1988)。

縮減搜尋空間的另一種方法是隻到某個深度，將該級別的行動視為臨時的終端節點，並使用啟發式方法確定其值。但是，在需要長期規劃的情況下，這仍然有問題 (Sadikov & Bratko, 2006)。但是，透過尋找遊戲中穩定的階段並將這些階段用作中間終端節點，這種方法可以變得更加可行 (Scheucher & Kaindl, 1989)。儘管有這些技術，但關於在如此複雜的情況下使用極小極大搜尋是否真正有效存在爭議 (Sadikov et al., 2005)。

最後，本節僅討論了下一個狀態完全由參與者行動決定的遊戲。極小極大搜尋的最終領域是涉及機會的遊戲，例如西洋雙陸棋和撲克 (Hauk et al., 2006)。

參考文獻

• Hauk, T., Buro, M., & Schaeffer, J. (2006). Rediscovering *-Minimax Search. In Computers and Games (pp. 35-50). Berlin: Springer-Verlag.
• Knuth, D. E., & Moore, R. W. (1975). An Analysis of Alpha-Beta Priming. Artificial Intelligence , 6 (4), 293-326.
• Kulenovic, M. R. (2008). Game Theory . Retrieved March 8, 2009, from University of Rhode Island Department of Mathematics: http://hypatia.math.uri.edu/~kulenm/mth381pr/GAMETH/gametheory.html
• Muller, M. (2001). Global and Local Game Tree Search. Information Sciences , 135, 187-206.
• Rivest, R. L. (1988). Game Tree Searching by Min/Max Approximation. Artificial Intelligence , 34, 77-96.
• Russell, S. J., & Norvig, P. (1995). Artificial Intelligence: A modern approach . Upper Saddle River, New Jersey: Prentice-Hall.
• Sadikov, A., & Bratko, I. (2006). Learning long-term chess strategies from databases. Machine Learning , 63, 329–340.
• Sadikov, A., Bratko, I., & Kononenko, I. (2005). Bias and pathology in minimax search. Theoretical Computer Science , 349, 268 – 281.
• Scheucher, A., & Kaindl, H. (1989). The reason for the benefits of minimax search. Proceedings IJCAI-89 , 322–327.