两人轮流从一堆棋子中移除规定数量,无法行动的人结束并判负时,单看剩余棋子总数未必足以判断局面。每堆允许的后续状态,才决定组合后的选择。
先明确输入与规则
本例每次只能选择一堆,并移除集合中某个不超过该堆余量的数量。先给单堆大小零赋状态值零,其他大小的状态值取所有可达状态值中未出现的最小非负整数。两堆组合用两个状态值按位异或,零表示当前方在双方最佳选择下没有必胜走法。
本例的独立记录
每次可移除数量[1, 4, 6],单堆最多十八。堆编号零、一;结束判定是轮到自己时无合法动作则负。
单堆大小 | 状态值 0 | 0 1 | 1 2 | 0 3 | 1 4 | 2 5 | 0 6 | 1 7 | 0 8 | 1 9 | 2 10 | 0 11 | 1 12 | 0 13 | 1 14 | 2 15 | 0 16 | 1 17 | 0 18 | 1 双堆数量 | 异或结果 | 归零走法,依次为堆号、取数、操作后数量 [2, 9] | 2 | [[1, 4, [2, 5]]] [0, 7] | 0 | [] [13, 4] | 3 | [[0, 4, [9, 4]], [1, 1, [13, 3]]] [2, 1] | 1 | [[0, 1, [1, 1]], [1, 1, [2, 0]]] [5, 3] | 1 | [[0, 4, [1, 3]], [1, 1, [5, 2]]] [3, 7] | 1 | [[0, 1, [2, 7]], [1, 1, [3, 6]], [1, 4, [3, 3]], [1, 6, [3, 1]]]
记录中的编号只用来区分本例对象,不应与大小排名或另一组记录的身份混淆。先核对单位和边界,再跟随中间值检查结果。空结果、零值与尚未确定是不同状态;分数保留精确含义,显示小数只为方便阅读。
怎样复算
表格列出单堆状态值和每个双堆局面的全部归零走法。归零是指操作后两个状态值异或为零,并不是把棋子全部取光。非零局面应至少有一条归零走法,零局面则不应存在这种走法。
可以对较小的双堆局面逐层枚举胜负,核对状态值方法的结果。走法列表只说明当前规则下的战略性质,不包含现实奖励或任何金钱行为。实际练习还要检查所取数量是否合法,不能为了让异或归零执行规则之外的移除。
适用条件与限制
这是无随机、无隐藏信息、有限步、双方可做动作相同的抽象谜题。若规则改成最后取走者输,或不同玩家可取数量不同,不能继续直接采用这里的递推和组合判定。
练习时可以一次只改变一个条件,比较差异从哪个步骤开始。若自己的结果不同,先核对是否采用同样的规则,再定位第一个不一致的中间状态,不要只修改最终答案。输入与运算过程需要一起保存,才能判断结论究竟适用于哪一个具体场景。
