Minimax解釋「傻瓜」

我很新的算法，我試圖理解最小極小，我讀了很多文章，但我仍然無法得到如何實現它到井字遊戲python遊戲。你可以試着用一些僞代碼或python代碼儘可能簡單地向我解釋一下嗎？Minimax解釋「傻瓜」

我只需要了解它是如何工作的。我讀了很多關於這方面的內容，並且我理解了基本內容，但是我仍然無法知道它是如何返回移動的。

如果你可以請不要鏈接我的教程和樣本像（http://en.literateprograms.org/Tic_Tac_Toe_(Python）），我知道他們很好，但我只需要一個白癡的解釋。

感謝您的時間:)

2012-05-16 Edoardo Sparkon Dominici

正在做作業嗎？ – Jordan

我仍然在高中......我爲激情學習:) –

「minimax」的想法是，在雙人遊戲中，一個玩家試圖最大化某種形式的分數，另一個玩家試圖將其最小化。例如，在Tic-Tac-Toe中，X的勝利可以被評爲+1，而O的勝利被評爲-1。 X會成爲最大的球員，試圖最大限度地提高最終得分，並且O會成爲最小球員，試圖最小化最終得分。

X被稱爲最大玩家，因爲當它是X的移動時，X需要選擇一個移動來最大化移動後的結果。當O球員時，O需要選擇一個移動，使移動後的結果最小化。這些規則以遞歸方式應用，例如如果只有三個棋盤位置開放，X的最佳表現就是促使O選擇一個價值儘可能高的最小值移動的棋子。

換言之，在博弈論極小極大值V爲一個板位置B定義爲

V(B) = 1 if X has won in this position 
V(B) = -1 if O has won in this position 
V(B) = 0 if neither player has won and no more moves are possible (draw)

否則

V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for X, and it is X's move 
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for O, and it is O's move

x的最優策略是總是從乙移動到Bi使得V（Bi）最大，即對應於博弈理論值V（B），對於O，類似地，選擇最小後繼位置。

但是，這通常不可能在象棋這樣的遊戲中計算，因爲爲了計算遊戲理論值需要枚舉整個遊戲樹直到最終位置，並且該樹通常是非常大的。因此，一種標準的方法就是設置一個「評估函數」，將棋盤位置映射到希望與遊戲理論值相關的分數。例如。在國際象棋程序中，評估函數傾向於給予材料優勢的積極分數，開放列等。最小化算法，它們使評估函數分數最小化，而不是實際（未計算）的棋盤位置的博弈理論值。

minimax的一個重要的標準優化是「alpha-beta修剪」。它給出了與minimax搜索相同的結果，但速度更快。 Minimax也可以按照「negamax」進行鑄造，其中每個搜索級別的分數符號都被顛倒過來。這只是一種實現超級極小的替代方式，但是可以統一處理玩家。其他遊戲樹搜索方法包括迭代加深，證明號碼搜索等。

來源

2012-05-17 15:29:14

感謝您花時間解釋這一點，我搜索了一會兒才找到這篇文章，它有助於瞭解minimax – Rick

極小是探索在兩個玩家的遊戲潛在的移動交替輪流空間的一種方式。你試圖贏得勝利，而你的對手正試圖阻止你贏。

一個關鍵的直覺是，如果它現在輪到你了，那麼保證你獲勝的兩步移動序列沒有用，因爲你的對手不會與你合作。你試圖做出讓你獲勝的機會最大化的動作，並且你的對手進行動作可以最大限度地減少獲勝的機會。

由於這個原因，探索你對你造成傷害的移動分支並不是很有用，或者移動你的對手使得對你有好處。

來源

2012-05-16 22:22:25 recursive

好的......但是我怎樣才能將它應用在一個tic tac toe遊戲中呢？ –

Minimax解釋「傻瓜」

回答

相關問題