algorithm - 三堆 Wythoff 博弈的 Cold Positions

Question

这是硬件:

Wythoff 的游戏有两个玩家，在这个例子中有 3 堆石子。每个玩家轮流从堆中取出石头，如果玩家捡起最后一 block 石头，则玩家获胜。每个回合玩家可以从一堆中取出 N 颗石子，从两堆中取出 N 颗石子，或者从所有三堆中取出 N 颗石子。

获胜配置是第一个玩家可以强制获胜的配置。例如，(0,0,13)、(0,11,11) 和 (5,5,5) 是获胜配置，因为第一个玩家可以立即移除所有棋子。

失败的配置是第二个玩家可以强制获胜的配置，无论第一个玩家做什么。例如，(0,1,2) 和 (1,3,3) 是输配置:任何合法的移动都会为第二个玩家留下获胜配置。

考虑所有丢失配置 (xi,yi,zi)，其中 xi <= yi <= zi <= 100。对于这些，我们可以验证 Σ(xi+yi+zi) = 173895。

我找了又找，但不知道如何找到所有亏损(冷)头寸。通过对坐标的二进制值求和得到 nimnumber，如果 nimnumber > 0 则它是冷位置。但我最终得到了 Σ(xi+yi+zi) > 100 万。谁能帮我指出正确的方向？

Answer 1

由于是作业，我不会发布完整的解决方案，但这里有一个提示:

你已经知道 xi <= yi <= zi <= 100，所以配置的数量永远不会超过 2*101^3(轮到谁的 x2)，这不会超过200万。尝试制作一个查找表(例如，isWinningPosition[][][][] 其中 isWinningPosition[a][b][c][d] 对应于一堆大小a,b,c 然后轮到 d) 并递归。 (注意:查找表中的每个条目都需要将 true、false 和 not computed 作为三个独立的事物来处理。)