数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

[转载] 棋子游戏

[复制链接]
发表于 2008-9-11 19:07:25 | 显示全部楼层
可以看出2个4先手胜,2个4加1个1先手负。很有可能除去这两个状态后我前面贴出的方法成立,不过现在我还没能够验证
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 19:34:24 | 显示全部楼层
(1, 1, 1)负
(1, 1, 2), (1, 1, 3)胜
(1, 2, 2)的子序列是
(1, 2)胜, (2, 2)负, (1, 1, 2)胜
所以(1, 2, 2)胜
同样(2,2,2)胜
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 19:39:02 | 显示全部楼层
(3, 4)子序列
(2, 4)胜,(1,4)胜,(3,3)胜,(2,3)胜,(1,1,4)负,(1,2,3)负
(1,1,4)子序列
(1,4)胜,(1,1,3)胜,(1,1,2)胜,(1,1,1,2)胜,(1,1,1,1)胜
(1,2,3)子序列
(2,3)胜,(1,3)胜,(1,1,3)胜,(1,2,2)胜,(1,1,2)胜,(1,1,1,2)胜

所以(3,4)胜
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 21:21:53 | 显示全部楼层
综合31# 41# 42# 43# 44#
9是先手负
所以10, 11先手胜
下一个是12
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 07:53:14 | 显示全部楼层
首先我们给一些更加方便的记号,比如
1*2+2*1可以简记为2+2*1(也就是所有1*可以省略),其次2*1也可以写成1*1+1*1=1+1

我们先考虑另外一个问题,其他规则都不变,但是允许拿最后一个子。轮到无子可拿的情况输(也就是拿到最后一颗的赢),对于这个情况,可以分析出一个比较好的结论,记:
s[1]=1
s[2]=2
s[3]=3
s[4]=1
s[5]=4
s[6]=3
s[7]=2
s[8]=1
s[9]=4
s[10]=2
s[11]=6
s[12]=4
s[13]=1
s[14]=2
s[15]=7
s[16]=1
s[17]=4
s[18]=3
s[19]=2
s[20]=1
s[21]=4
s[22]=6
s[23]=7
s[24]=4
s[25]=1
s[26]=2
s[27]=8
s[28]=5
s[29]=4
s[30]=7
s[31]=2
s[32]=1
s[33]=8
s[34]=6
s[35]=7
s[36]=4
s[37]=1
s[38]=2
s[39]=3
s[40]=1
s[41]=4
s[42]=7
s[43]=2
s[44]=1
s[45]=8
s[46]=2
s[47]=7
s[48]=4
s[49]=1
s[50]=2
那么对于一个局面$x_1+x_2+...+x_k$,这个局面的状态数为$s[x_1]^^s[x_2]^^...^^s[x_k]$
一个状态先手负的充要条件是其对应的状态数为0。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 08:20:31 | 显示全部楼层
对于初始局势 1*n ,拿最后子赢的游戏简单的很,只需分为两个等长的序列就行了。但对任意初始局势的判定也挺复杂。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 08:41:26 | 显示全部楼层
两位
9怎么判定的?能给我分析下么?
我怎么看9是输阿?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 08:58:59 | 显示全部楼层
切换到本问题,我们可以知道,除了状态1*1和1*2以外,所有其他状态能够转移到的状态同上面一个问题完全相同。
我们对于某个状态s,记上一个问题中对应的状态数为g(s),这个问题中对应的状态数为f(s)
所以我们知道,如果对于某个状态s,它经过一次变换能够达到的所有不同状态为$s_1,s_2,...,s_h$
如果有$f(s_1)=g(s_1),f(s_2)=g(s_2),...,f(s_h)=g(s_h)$,那么我们必然可以有$f(s)=g(s)$。
而根据经验可以猜测除了少数状态以外,都会有$f(s)=g(s)$,我们的任务就是找出所有$f(s)!=g(s)$的状态s而且计算出其状态值.
第一步我们可以知道
$f(p*1)=0,f(o*1)=1$这两个状态不同于函数g,
所以所有可以到达p*1和o*1的状态都要重新计算状态数,也就是我们还需要计算状态
2+p*1,2+o*1,3+p*1,3+o*1,4+p*1,4+o*1
首先计算$f(2)=1!=g(2)=2$,所以,所有可以到达状态2的也需要重新计算,包括状态
3,4,2+1,2*2
其次计算$f(2+1)=2!=g(2+1)=3$
然后我们可以得到$f(2+p*1)=2!=g(2+p*1),f(2+o*1)=3!=g(2+o*1)$
所以所有可以到达这些状态的也都需要重新计算,也就是
2*2+p*1,2*2+o*1,3+p*1,3+o*1,4+p*1,4+o*1,5+p*1,5+o*1,3+2+p*1,3+2+o*1,4+2+p*1,4+2+o*1
加上前面列出的还需要添加状态3,4,2*2
都要重新计算

下一步需要计算2*2,2*2+o*1,2*2+p*1就是重复25#过程可以得到它们函数值同g函数值相同,所以不需要近一步考虑。
然后下一个需要计算状态3,3+p*1,3+o*1,3+2+p*1,3+2+o*1,根据27#的结果得到
$f(3)=2!=g(3)=3,f(3+p*1)=3!=g(3+p*1)=2,f(3+o*1)=2!=g(3+o*1)$
$f(3+2+p*1)=0=g(3+2+p*1),f(3+2+o*1)=1=g(3+2+o*1)$
也就是只有f(3),f(3+p*1),f(3+o*1)不同于g,为此我们还需要验证所有可以到达状态3,3+p*1,3+o*1的状态,包含状态
4,5,3+1,3+2,4+p*1,5+p*1,4+o*1,5+o*1,2*3+p*1,2*3+o*1,3+2+p*1,3+2+o*1,5,6,5+o*1,6+o*1,5+p*1,6+p*1
其中最大为3的已经验证和g函数相同,因此余下还有状态
4,4+p*1,4+o*1,4+2+p*1,4+2+o*1,5,5+p*1,5+o*1,6,6+p*1,6+o*1
已经得出所有不同项为
$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2$,其余最大数不超过3的都同g相同
然后我们计算状态4,可以到达状态3,2,2+1,1+1;对应f状态值分别为2,1,2,1,所以$f(4)=0!=g(4)=1$
为此我们需要重新计算所有可以到达状态4的状态,包含状态6,5,4+1,4+2
其次计算4+1状态,可以到达状态4,3+1,2+1,2+2*1,3*1,所以对应f值为0,3,2,3,0
所以$f(4+1)=1!=g(4+1)=0$,所以我们需要重新计算6+1,5+1,4+2*1,6,7,4+2,4+3几个状态
4+2*1状态可以到达4+1,3+2*1,2+2*1,2+3*1,4*1,f值分别为1,2,3,2,1;所以得到$f(4+2*1)=0!=g(4+2*1)$
4+3*1状态可以到达4+2*1,3+3*1,2+3*1,2+4*1,5*1,f值分别为0,3,2,3,0;所以得到$f(4+3*1)=1!=g(4+3*1)$
同样可以得到4+o*1可以到达4+p*1,3+o*1,2+o*1,2+p*1,o*1,f值分别为1,2,3,2,1;所以得到$f(4+o*1)=0!=g(4+o*1)$
同样可以得到4+p*1可以到达4+o*1,3+p*1,2+p*1,2+o*1,p*1,f值分别为0,3,2,3,0;所以得到$f(4+p*1)=1!=g(4+p*1)$
到达它们的状态有5,6,5+o*1,5+p*1,6+o*1,6+p*1,7,7+o*1,7+p*1,4+2+o*1,4+2+p*1,4+3+p*1,4+3+o*1,2*4+o*1,2*4+p*1

到次我们已经知道同g不同的状态有
$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2,f(4)=0,f(4+p*1)=1,f(4+o*1)=0$
需要继续计算的状态有
4+2,4+3,4+2+p*1,4+2+o*1,4+3+p*1,4+3+o*1,2*4+o*1,2*4+p*1,5,5+p*1,5+o*1,6,6+p*1,6+o*1,7,7+p*1,7+o*1
我们先查看状态4+2可以到达4,4+1,3+2,2*2,2*2+1,2+2*1,对应f值0,1,1,0,1,3;所以$f(4+2)=2!=g(4+2)$
到达4+2的状态有4+3,2*4,4+2+1,4+2*2,5+2,6+2,7,8
4+2+1可以到达4+2,4+2*1,4+1,3+2+1,2*2+1,2+3*1,2*2+2*1,对应f值2,0,1,0,1,2,0,所以$f(4+2+1)=3!=g(4+2+1)=2$
4+2+2*1可以到达4+2+1,4+3*1,4+2*1,3+2+2*1,2*2+2*1,2+4*1,2*2+3*1,对应f值为3,1,0,1,0,3,1;所以$f(4+2+2*1)=2!=g(4+2+2*1)=3$
同样我们可以得出$f(4+2+p*1)=3!=g(4+2+p*1)=2,f(4+2+o*1)=2!=g(4+2+o*1)=3$
计算4+2*2,可以到达4+2+1,4+2,3+2*2,3*2,3*2+1,2*2+2*1,对应f值3,2,3,2,3,0,所以$f(4+2*2)=1=g(4+2*2)$
类似估计其他4+x*2开头的都应该同g相同了。
其次计算4+3,可以到达4+1,4+2,4+2*1,2*3,3+2,3+2+1,3+2*1,对应f值为1,2,0,0,1,0,2;所以$f(4+3)=3!=g(4+3)$
4+3+1,可以到达4+3,4+2+1,4+2*1,4+3*1,2*3+1,3+2+1,3+2+2*1,3+3*1,对应f值3,3,0,1,1,0,1,3;所以$f(4+3+1)=2!=g(4+3+1)$
类似我们应该可以得到$f(4+3+o*1)=3!=g(4+3+o*1),f(4+3+p*1)=2!=g(4+3+p*1)$
然后查看4+3+2可以到达4+3+1,4+3,4+2*2,4+2+1,4+2+2*1,2*3+2,3+2*2,3+3*1,3+2+2*1对应f值2,3,1,3,2,2,3,3,1;
所以$f(4+3+2)=0=g(4+3+2)$.类似我估计后面的f值都应该同g值会相同了
也就是我们找出了同g值不同的f有

$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2$
$f(4)=0,f(4+p*1)=1,f(4+o*1)=0,f(4+2)=2,f(4+2+p*1)=3,f(4+2+o*1)=2,f(4+3)=3,f(4+3+p*1)=2,f(4+3+o*1)=3$
对于其余的应该有$f(.)=g(.)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 09:05:25 | 显示全部楼层
状态9好像的确是先手输,前面分析还没有完,至少象f(2*4)我也没有分析到,这个计算一下又同g函数不同。不过如果得出f(9)=0,那么9以后的又会一堆同g函数不同,这种方法不能用下去了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-12 09:14:12 | 显示全部楼层
不过感觉我上面的算法可以让计算机来做,那样会好很多,只是需要解决里面一些类似数学归纳法方法的问题
如得出f(2+p*1)=2,f(2+o*1)=3,两者需要互相以对方为基础,而且开始通常需要先计算f(2),f(2+1),f(2+2*1)等,然后再使用归纳法(而且可能少数情况这个规律不一定成立,这时需要多推导几项)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-6-18 11:20 , Processed in 0.078257 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表