魔方吧·中文魔方俱乐部

标题: 抓石子争单双博弈题 [打印本页]

作者: 钟七珍 时间: 2011-9-1 00:49:12 标题: 抓石子争单双博弈题

此题原来是一堆。改编成三堆，增加了难度：
　　有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 时间: 2011-9-1 14:06:50

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

作者: yq_118 时间: 2011-9-2 13:02:47

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

作者: 钟七珍 时间: 2011-9-11 15:03:20

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

钟七珍 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 时间: 2011-9-11 19:48:04

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

#!/usr/bin/python3 -i
def solver(a_max, b_max, c_max):
mem = {(0, 0, 0, 0): 'win',
(0, 0, 0, 1): 'lose'}
def adj(a, b, c):
return ([(i, b, c) for i in range(max(0, a - a_max), a)] +
[(a, i, c) for i in range(max(0, b - b_max), b)] +
[(a, b, i) for i in range(max(0, c - c_max), c)])
def rec(x):
if x not in mem:
p = ((sum(x) + 1) % 2,)
for y in adj(*x[:3]):
if rec(y + p) == 'lose':
mem[x] = y
break
else:
mem[x] = 'lose'
return mem[x]
return lambda a, b, c, p: rec((a, b, c, p))
s = solver(3, 4, 5)
print(s(27, 27, 27, 0))

复制代码

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

作者: 钟七珍 时间: 2011-9-11 20:19:09

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

作者: yq_118 时间: 2011-9-11 20:43:18

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

作者: lulijie 时间: 2011-9-11 22:37:13

用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)

附件: 答案.rar (2011-9-11 22:37:13, 16.48 KB) / 下载次数 6
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTU4NzY2fDUzYTBjMDRmfDE3NDAxNjIwODB8MHww

作者: lulijie 时间: 2011-9-11 22:45:19

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

作者: lulijie 时间: 2011-9-11 23:02:04

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

作者: lulijie 时间: 2011-9-11 23:36:37

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

作者: 钟七珍 时间: 2011-9-12 01:30:09 标题: 回复 11# 的帖子

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

作者: lulijie 时间: 2011-9-12 10:52:02

比如初始，(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 时间: 2011-9-12 10:57:43

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

作者: 钟七珍 时间: 2011-9-12 10:59:35

　　返回去看了一下我发的只抓一堆石子的帖子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 时间: 2011-9-12 11:38:00

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

作者: 钟七珍 时间: 2011-9-12 11:43:32 标题: 回复 13# 的帖子

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

作者: 钟七珍 时间: 2011-9-12 11:57:46

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

作者: 钟七珍 时间: 2011-9-12 12:03:44

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

作者: yq_118 时间: 2011-9-12 13:02:20

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

#!/usr/bin/python3 -i
def solver(*m):
n = len(m)
mem = {((0,) * n, 0): 'win',
((0,) * n, 1): 'lose'}
def adj(x):
for i in range(n):
y = list(x)
for y[i] in range(max(0, x[i] - m[i]), x[i]):
yield tuple(y)
def rec(x, parity):
if (x, parity) not in mem:
q = (sum(x) + parity + 1) % 2
for y in adj(x):
if rec(y, q) == 'lose':
mem[(x, parity)] = y
break
else:
mem[(x, parity)] = 'lose'
return mem[(x, parity)]
return rec
s = solver(3, 4, 5)
print(s((27, 27, 27), 0))

复制代码

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)