抓石子争单双博弈题

lulijie

f(a,b,c)=0    表示先行方必得到偶数结果
f(a,b,c)=1    表示先行方必得到奇数结果
f(a,b,c)=2    表示奇偶结果由先行方决定
f(a,b,c)=3    表示奇偶结果由后行方决定
-----------------------------------
递推方法的思路：
f(0,0,0)=0
(a,b,c)---->(x,y,z)
若所有能演变的(x,y,z)中，f()值都等于0或2(至少有一个值为0),那么f(a,b,c)=(a+b+c) mod 2   
若所有能演变的(x,y,z)中，f()值都等于1或2(至少有一个值为1),那么f(a,b,c)=(a+b+c-1) mod 2
若所有能演变的(x,y,z)中，f()值至少有一个为0，且至少有1个为1),那么f(a,b,c)=2
若所有能演变的(x,y,z)中，f()值至少有一个为3，那么f(a,b,c)=2
若所有能演变的(x,y,z)中，f()值都等于2，那么f(a,b,c)=3

钟七珍

先生的几篇回帖，本人受益不少。尽管有些内容还不明白，尚须时间消化。
f(a,b,c)=0（或等于1，2，3）是如何算出来的？比如一堆时，f(a)=？ 或两堆时，f(a,b)=？
望先生不吝指教！

lulijie

比如初始，(0,0,0)
那么先行方只能拿到0个，即必拿到偶数，所以f(0,0,0)=0
------------------------------------------------------------------------------
1: 下面递推f(1,0,0)
(1,0,0)只能变为(0,0,0)
面临(0,0,0)局面的是对方，它只能拿到偶数，所以面临(1,0,0)的先行方必拿到奇数。    （1+0+0） mod 2=1
所以f(1,0,0)=1
同理 f(0,1,0)=1;f(0,0,1)=1
------------------------------------------------------------
2:下面递推f(2,0,0)
(2,0,0)可变为(1,0,0)，（0,0,0）
因为f(1,0,0)=1,f(0,0,0)=0
所以先行方即可以使对手面临必奇局面(1,0,0),也可以让对手面临必偶局面(0,0,0),
也就是说自己拿奇数还是偶数由自己决定，所以f(2,0,0)=2
--------------------------------------------------------------------------------
3:下面递推f(3,0,0)
(3,0,0)可变为(2,0,0)，(1,0,0),（0,0,0）
因为f(2,0,0)=2,f(1,0,0)=1,f(0,0,0)=0,所以f(3,0,0)=2
   如果结果偶数胜，那么先行方需---->(1,0,0)才能胜，
   如果结果奇数胜，那么---->(0,0,0)才能胜。
   无论哪种情况都不能---->(2,0,0)，因为这样取奇取偶由对方决定了。
-------------------------------------------------------------------------------------------
4.下面递推f(4,0,0)
(4,0,0)可变为(3,0,0),(2,0,0),(1,0,0)，变不了(0,0,0）,因为m=3.
因为f(3,0,0)=2,f(2,0,0)=2，f(1,0,0)=1
所有先行方只有---->(1,0,0)一条路，即对手必奇，那么自己也必奇。   (4+0+0-1) mod 2=1
不能---->(3,0,0)或(2,0,0)，否则奇偶由对手决定了。
---------------------------------------------------------------------
依此类推......
(1,1,0)
因为f(0,1,0)=1,f(1,0,0)=1
所以，f(1,1,0)=((1+1+0-1) mod 2)=1
------
(2,1,0)
因为f(1,1,0)=1,f(0,1,0)=1,f(2,0,0)=2
所以，f(2,1,0)=((2+1+0-1) mod 2)=0
........

lulijie

只要把递推的思路编程，递推过程交给电脑就万事大吉了，不过要把结果记录下来，否则白干。

钟七珍

　　返回去看了一下我发的只抓一堆石子的帖子http://bbs.mf8-china.com/viewthr ... &extra=page%3D1，发现参与讨论的也是上面两位老师yq_118和lulijie。
　　我把两位老师发的几段帖子转过来，也许有助于此题的讨论：
　　yq_118：
“假设每次可以取1~4个，
6*n+1个硬币，先手不能保证取偶数个。其它情况先手一定能取到偶数个。
6*n+3，6*n+5个硬币，先手不能保证取奇数个。其它情况先手一定能取到奇数个。”
　　lulijie：
“对于每次拿1-m个：
那么若m为偶数，那么被m+2除，余1为必奇局面(即先行方必拿到奇数个硬币)，余0和余m-1为必偶局面，余其它为必胜局面（即奇偶由先行方决定）。
若m为奇数，那么被2m+2除，余1和余m+1为必奇局面，余m+2和余0为必偶局面，余其它为必胜局面。”
　　lulijie：
“必奇局面：先行方必拿到奇数个硬币。
必偶局面：先行方必拿到偶数个硬币。
必胜局面：先行方可自行决定拿奇数个硬币还是拿偶数个硬币。
------------------------------------------------------------------------
硬币总数为N，每次取1-m个硬币。
m为偶数：       必奇局面 N mod (m+2)=1
                         必偶局面 N mod (m+2)=0 或 m+1
                         必胜局面 剩下的都是
m为奇数：        必奇局面 N mod (2m+2)=1或m+1
                         必偶局面 N mod (2m+2)=0或m+2
                                                 必胜局面 剩下的都是”

lulijie

楼主把题目改成了没有确切数值的一般情况，电脑编程最怕这个情况。
解决这种题目的方法：
1. 先让电脑计算出一大堆结果来，然后人脑去分析出规律。
2. 直接用人脑，寻找规律。（电脑在这方面不如人脑）

钟七珍

谢谢lulijie老师的指教！大概基本明白了。

钟七珍

看了13楼之后，再返回去看11楼，这才看懂。
惊叹lulijie老师是怎样分析出：
f(a,b,c)=0    表示先行方必得到偶数结果
f(a,b,c)=1    表示先行方必得到奇数结果
f(a,b,c)=2    表示奇偶结果由先行方决定
f(a,b,c)=3    表示奇偶结果由后行方决定　　这四种状态判断的！

钟七珍

用递推的方法，虽然麻烦，且没有一个简捷的公式计算，但毕竟是找到了一条至胜的道路！

yq_118

稍加修改就能推广到一般的情况。
根据题目的要求调用solver，返回一个求解器。
调用求解器，第一个参数为一个向量，表示各堆的石子数，第二个参数表示奇偶性，0为偶，1为奇。
返回'lose'表示输了，否则返回一个向量表示决策。

1. #!/usr/bin/python3 -i
   
2. 
   
3. 
   
4. def solver(*m):
   
5.     n = len(m)
   
6.     mem = {((0,) * n, 0): 'win',
   
7.            ((0,) * n, 1): 'lose'}
   
8. 
   
9.     def adj(x):
   
10.         for i in range(n):
    
11.             y = list(x)
    
12.             for y[i] in range(max(0, x[i] - m[i]), x[i]):
    
13.                 yield tuple(y)
    
14. 
    
15.     def rec(x, parity):
    
16.         if (x, parity) not in mem:
    
17.             q = (sum(x) + parity + 1) % 2
    
18.             for y in adj(x):
    
19.                 if rec(y, q) == 'lose':
    
20.                     mem[(x, parity)] = y
    
21.                     break
    
22.             else:
    
23.                 mem[(x, parity)] = 'lose'
    
24.         return mem[(x, parity)]
    
25. 
    
26.     return rec
    
27. 
    
28. 
    
29. s = solver(3, 4, 5)
    
30. print(s((27, 27, 27), 0))

复制代码

[ 本帖最后由 yq_118 于 2011-9-12 13:14 编辑 ]