minimax中MIN的最優值

Question

在minimax算法中，第一個玩家最佳地玩，這意味着他想要最大化他的分數，第二個玩家試圖最小化第一個玩家的獲勝機會。這是否意味着第二位玩家也能夠以最佳方式贏得比賽？試圖選擇一些路徑來減少第一個玩家獲勝的機會也意味着要贏得勝利？

我其實是想從TopCoder的解決這個任務：EllysCandyGame

我不知道我們是否能在這裏適用極大極小算法。但我不知道第二位球員是否會盡量減少第一位球員的成績，同時他也會以最佳狀態進行比賽。如果可能的話，我還想要一個正確性的數學證明。這種「最佳發揮」的說法讓我很困惑，如果有一些總體想法，我想就如何處理這類問題提出一些建議。謝謝。

Answer 1

是的，你可以在這裏使用minimax算法。

問題說明說遊戲的勝者是「遊戲結束時糖果更多的女孩」。因此，您可以使用的一個合理得分功能是第一名和第二名球員所持有的糖果數量的差異。

這是否意味着第二位玩家還能以最佳方式贏得比賽？

是的。當您評估MIN級別時，MIN玩家將始終選擇MAX玩家得分最低的路徑。

注意：如果您從該玩家在該回閤中移動的角度評估每個節點，並在不同級別之間轉換分數，則MIN和MAX級別都可以使用相同的代碼實現。如果分數是糖果數量的差異，你可以簡單地在兩個水平之間進行否定。

試圖選擇一些路徑，以最大限度地減少第一個玩家的獲勝機會也意味着嘗試贏？

是的。第二個球員正在努力減少第一個球員的分數。一個合理的得分功能會讓第一個球員的失分比分數低。

我想知道我們是否可以在這裏應用minimax算法。

是的。如果我已經正確地閱讀了這個問題，那麼關卡的數量將等於盒子的數量。如果框的數量沒有限制，則需要使用n-move lookahead，將minimax樹中的節點評估爲最大深度。遊戲的

Answer 2

性質：

• 在每個點，也有移動（採摘的非空框之一）
• 有限數量的後遊戲結束一個有限的，明確定義的數移動（當所有框都爲空時）

因此，搜索樹由有限數量的葉子組成。你是對的，通過應用Minimax，你可以找到最好的舉措。

請注意，您只需在最終位置評估遊戲（當沒有更多的移動時）。那時，只有三個結果：第一位選手贏了，第二位選手贏了，或者是平局。

請注意，標準Minimax算法與概率無關。 Minimax算法的結果決定了雙方的完美表現（假設雙方都沒有犯錯誤）。

順便說一句，如果你需要改進搜索算法，一個安全和簡單的優化是應用Alpha Beta pruning。