三堆Wythoff遊戲的冷位置

Wythoff的遊戲是有兩個玩家，在這種情況下，有3堆石頭。每個玩家輪流從堆中取出石塊，如果玩家拿起最後一塊石頭，玩家將獲勝。每回合一名球員可以從一堆中取出N塊石頭，從兩堆中取出N塊石頭，或者從三堆中取出N塊石頭。

獲勝配置是第一位玩家可以強制獲勝的配置。例如，（0,0,13），（0,11,11）和（5,5,5）是獲勝配置，因爲第一個玩家可以立即移除所有寶石。

失敗的配置是第二個玩家可以強制贏得勝利的一種，無論第一個玩家做什麼。例如，（0,1,2）和（1,3,3）都是失敗的配置：任何合法的移動都會給第二個玩家留下勝利的配置。

考慮所有丟失的配置（XI，苡仁，紫），其中xi < =易< =紫< = 100 我們可以驗證Σ（十一+易建聯+ ZI）= 173895這些。

我已經搜索和搜索，但無法弄清楚如何找到所有失敗（冷）職位。通過將座標的二進制值相加來獲得nimnumber，並且如果nimnumber> 0，則它是冷位置。但是我最終得到Σ（xi + yi + zi）> 1mil。任何人都可以幫助我指出正確的方向嗎？

來源

2012-07-19 postelrich

Riotburn，請勾選丹尼斯的迴應，如果它是有用的，或者至少以某種方式迴應他 - 「這只是禮貌！ – halfer 2012-09-29 16:36:12

由於它的功課，我將不會發佈一個完整的解決方案，但這裏有一個技巧：

您已經知道喜< =易< =紫< = 100，那麼配置的數量永遠不會超過2 * 101^3（無論是誰的X2），這不會超過200萬。嘗試製作查找表（例如，isWinningPosition[][][][]，其中isWinningPosition[a][b][c][d]對應於大小爲a，b，c的堆並輪到它）並遞歸。（警告：在您的查找表中的每個條目需要處理true，false，並且not computed三個獨立的東西。）

來源

2012-07-20 21:17:29

感謝您的幫助，儘管對查找表不瞭解。 – postelrich 2012-09-29 23:13:06

三堆Wythoff遊戲的冷位置

回答

相關問題