抓石子争单双博弈题

钟七珍

此题原来是一堆。改编成三堆，增加了难度：
　　有A、B、C三堆石子，每堆的数量均为27个。两人轮流取石子，每次可取走的数为：A组1-3颗，B组1-4颗，C组1-5颗。但每次取石子时，只能在一堆里面取，不能同时取两堆或三堆。石子全部取完后，以总数为双数者获胜。问：应该先取还是后取才能获胜？取的过程中又应该怎样应对？

　　若将此题作一般化设置：
　　有A、B、C、……共n堆石子（n≥2），每堆的数量分别为N1、N2、N3、……、Nn，Ni可以任意或相等，且总数：N总＝N1+N2+N3+……+Nn 是奇数。两人轮流取石子，，每次至少取一颗，最多可取：A堆M1颗，B堆M2颗，C堆M3颗……Mn颗，Mi可以任意或相等。但每次取石子时，只能在一堆里面取，不能同时取两堆或两堆以上。石子全部取完后，以拿取石子总数为双数者获胜。问：应该先取还是后取才能获胜？取的过程中又应该怎样应对？
　　又：若把以拿取总数为双数者获胜，改为以拿取总数为单数者获胜，又该怎样取？

　　此题目与本版置顶的《分珍珠》一题相似，但取胜条件由“谁取得最后一颗”改为“谁取得的总数为双数”，难度似乎增加了一点。

[ 本帖最后由 钟七珍 于 2011-9-12 11:27 编辑 ]

jinlijie

原来看到过好像有必胜方法的。。。。。。

yq_118

写了个程序，确实是先手必胜，第一步可以在B里取3个。

钟七珍

关于此题，人工智能编程网友改编了一个简化版。我与他对了一局，并有一些讨论。实录如下（括号中是我的编辑按语）：

钟七珍 40楼
7楼的简化版：
　　有A、B、C三堆石子，每堆的数量 la，lb，lc 个。两人轮流取石子，每次可取走的数为：A组1-3颗，B组1-4颗，C组1-5颗。但每次取石子时，只能在一堆里面取，不能同时取两堆或三堆。石子全部取完后，以总数为双数者获胜。现出3题，问：先者赢还是输？如果赢的话，第一步怎样拿？
　　题2：4 5 6
　　题3：4 6 7
　　题4：7 7 7
望各位指教！
———————————————————————————————————
　　题２和题３，我得出的解是先行者胜。题４还未思考出应对策略。
2011-09-10 20:16

钟七珍 43楼
试一下吧，就题2。怎么样？
2011-09-11 01:48

人工智能编程0 44楼
好吧！@钟七珍
2011-09-11 11:43

钟七珍 46楼
44楼先行！（各人一先。下一局我先）
2011-09-11 11:54

人工智能编程0 47楼
好！题2：我先下，当中拿掉2。
4 3 6
r：2 z：0
z:拿
2011-09-11 11:59 （钟按：当他先手拿成 4 3 6 后，我就知道他胜了）

钟七珍 48楼
4 3 5
r：2 z：1
r:拿
2011-09-11 12:04

人工智能编程0 49楼
4 2 5
r：3 z：1
z:拿
2011-09-11 12:12 （钟按：这一步，他可以拿成 4 3 0，这样，胜负立判，赢得更快。还有，我发现他应对慢，我就怀疑他是用电脑编程在与我对局）

钟七珍 50楼
3 2 5
r：3 z：2
r:拿
2011-09-11 12:14

人工智能编程0 51楼
3 1 5
r：4 z：2
z:拿
2011-09-11 12:20

钟七珍 52楼
3 1 4
r：3 z：3
r:拿
2011-09-11 12:21

钟七珍 53楼
更正：
3 1 4
r：4 z：3
r:拿
2011-09-11 12:22

人工智能编程0 54楼
3 0 4
r：5 z：3
z:拿
2011-09-11 12:24

钟七珍 55楼
你赢了！　　
看来确实是先拿者胜。
2011-09-11 12:27

人工智能编程0 56楼
引用 钟七珍 (55楼) 你赢了！　　 看来确实是先拿者胜。
是先拿者胜的。
2011-09-11 12:29

钟七珍 57楼
但我没有找到数学分析方法，与二进制分析挂不上钩？望老师赐教！
2011-09-11 12:31

人工智能编程0 58楼
我也不会2进制方法，但是我知道2进制方法肯定存在，能解数量上亿的棋局。
2011-09-11 12:35

钟七珍 59楼
哦。那你是针对具体题目，每一步用电脑编程应对的吗？
2011-09-11 12:38

人工智能编程0 60楼
我是用电脑硬算的，数据小点还行，数据一大就玩完。。。
两进制解法数量能到大上亿，几乎无限。。。

我不会，但是我知道肯定存在。。。
2011-09-11 12:50

钟七珍 61楼
所以，７楼的三道题目用电脑编程易解，而１楼的三堆27颗解起来就难了！
　　找出通解，尚须时日。
　　继续努力！互勉！
2011-09-11 13:00

人工智能编程0 62楼
好！
2011-09-11 13:11

(原帖见：http://tieba.baidu.com/p/1196491373）

yq_118

这个问题规模很小，只有27^3=19683。用递归轻松搞定。 调用 s(27, 27, 27, 0) 返回的是 (27, 24, 27)，表示第一步在B里取3个，以后根据对手的决策反复调用s就行了。

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

复制代码

[ 本帖最后由 yq_118 于 2011-9-11 20:40 编辑 ]

钟七珍

谢谢LS！不过，我看不懂。我只学过一点BASIC语言。这个是C语言吧？

yq_118

这个是Python写的，用C的话要考虑太多与问题无关的东西。

lulijie

用f(a,b,c)表示A堆为a，B堆为b，C堆为c时，先行方取石子最后能取得的结果。
f(a,b,c)=0    表示先行方必得到偶数结果
f(a,b,c)=1    表示先行方必得到奇数结果
f(a,b,c)=2    表示奇偶结果由先行方决定
f(a,b,c)=3    表示奇偶结果由后行方决定
-------------------------------------------------------------
电脑编程（我用的是VB6.0，楼主要的话可以向我索取），f(27,27,27)之内的所有结果见附件。
下面摘取其中的部分结果。
f(4,5,6)=2
f(4,6,7)=2
f(7,7,7)=2
说明楼主后来举的三个简单些的题目，无论最后是偶数胜还是奇数胜，都是先行方胜。
而f(27,27,27)=0    即先行方必得偶数。
说明偶数胜，则先行方胜，奇数胜则先行方败。

答案.rar (16.48 KB, 下载次数: 6)

2011-9-11 22:37:13 上传

下载次数: 6

lulijie

f(27,24,27)=1，说明先行方必得奇数。
所以若结果偶数胜，那么 (27,27,27)---->（27,24,27）就能胜利。
而(27,27,27)所能演变的所有其他结果f(a,b,c)都等于2，所以其他取法都不能取得胜利。
而若结果为奇数胜，那么后行方必得到奇数结果，所以先行方必败。

lulijie

f(6,3,4)=3
说明无论是奇数胜还是偶数胜，先行方必败。