分支因子和深度

Question

問題

一個簡單的兩個玩家的遊戲涉及了一堆ñ火柴，誰擁有交替兩歲 球員。在每一回閤中，玩家從堆中移除1， 2或3個火柴棒。刪除最後的 火柴的玩家會失去遊戲。

A）什麼是遊戲樹的分枝因子和深度（給出一個用N來表示的一般解）？搜索 空間有多大？

B）遊戲中有多少獨特的狀態？對於大N來說，可以做些什麼來使搜索更有效率？

回答

A）我說的分支因子是3，但我有道理，是因爲球員可能永遠只能去除高達3場比賽，這意味着我們的樹通常會有三個孩子。關於深度的第二部分，我不確定。

B） N×2其中N是剩餘匹配的數量。我不確定我們如何才能使搜索更高效？也許推出Alpha-beta修剪？

Answer 1

- 答： 對於深度，試想一下最長的遊戲應該是什麼樣子。這是由兩名球員組成的遊戲，每回合只消除1場比賽。由於有n個匹配，所以這樣的遊戲需要n圈：樹的深度爲n。

B： 只有2 * N個狀態，每個狀態都可以從3個狀態更高的火柴桿計數中訪問。由於比賽的數量必然隨着比賽的進行而下降，所以可能狀態的圖是DAG（有向無環圖）。因此，動態編程方法可以分析這個遊戲。最後，您會看到最佳移動僅取決於N mod 4，其中N是剩餘匹配的數量。

編輯：N mod 4的證明主意： 每個職位都是失敗或獲勝的位置。失去位置是一種情況，無論你玩什麼，如果你的對手打得最好，你都會輸。同樣，獲勝位置是一種情況，如果你打正確的動作，對手就不會贏。 N = 1是一個失敗的位置（根據遊戲的定義）。因此，N = 2,3,4是贏得的位置，因爲通過消除適當數量的比賽，你使對手處於輸球位置。 N = 5是一個失敗的位置，因爲無論您刪除了多少可接受的匹配項，您都會將對手放在勝利的位置。 N = 6,7,8是獲勝位置......你明白了。

現在它只是使這種證明正式：假設N是一個失敗的位置當且僅當N mod 4 = 1。如果這是真的，直到一個整數k，你可以證明這是k+1。正如我們前面所展示的那樣，它的確是高達k = 4。再次發生，任何N都是如此。

Answer 2

任何時候遊戲的狀態都可以通過輪到誰以及每個玩家持有的比賽數來描述。在n次移動之後，有3^n個可能的歷史記錄，但是對於大的n，可能的狀態少於3^n個，因此，例如，您可以通過識別您即將遇到的狀態來節省時間，爲之前制定了一個價值。

另請參閱https://en.wikipedia.org/wiki/Nim - 如果這是Nim或各種Nim，則已經制定了有效的策略。