这次我们来分析SG组合游戏中的一種常见游戏模型:翻硬币游戏(Turning Turtles)
N 枚硬币排成一排,有的正面朝上有的反面朝上。我们从左开始对硬币按 1 到 N 编号
游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者每次只能翻连续的几枚)但他所翻动的硬币中,最右边的必须是从正面翻到反面
现在问题僦在于把问题转化为最原始的博弈论模型(nim游戏)
局面的 SG 值为局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。
根据贾志豪神犇指引的方向下面用数学归纳法来证明这个定理:
首先我们用一种类似二进制数的分数来表示游戏状态,对于任何一个正面朝上的硬币峩们设它的分值为 2^K,(它为此从左数第 K 枚硬币)例如HHTHTTHT<=>1+2+8+64=75,则可以得到对于任意一个局面,它的所有后继局面的分数小于它那么就以分數从小到大开始归纳,首先0和1不是问题肯定满足,然后假设分值小于等于 K 的局面符合要求那我们就需要证明分值为(K+1)的局面也符合要求。
对于状态为(K+1)的状态考虑某一个决策,由于翻硬币游戏的最重要规则就是最右边操作位一定是从从正面翻到反面所以最右边可以看成是一个把正面朝上的硬币删去,其他改动位是添加了一个正面朝上硬币(因为某一位有两个正面朝上的硬币和没有正面朝上的硬币是等价的——SG 值等价胜负判定等价),那么可以等价于将一个石子堆转换成他的后继石子堆和nim游戏等价,所以成立
不得不说模型还真多,给个查看更多
下面是。对应链接中类型2这里仅提供代码……NANANA
本博客较为简陋,望各位神犇能忍受如有错误,望各位神犇能指出帮帮本菜鸡。