抓石子争单双博弈题
此题原来是一堆。改编成三堆，增加了难度：有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 编辑 ] 原来看到过好像有必胜方法的。。。。。。 写了个程序，确实是先手必胜，第一步可以在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） 这个问题规模很小，只有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 = y
break
else:
mem = 'lose'
return mem
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 编辑 ] 谢谢LS！不过，我看不懂。我只学过一点BASIC语言。这个是C语言吧？ 这个是Python写的，用C的话要考虑太多与问题无关的东西。 用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 即先行方必得偶数。
说明偶数胜，则先行方胜，奇数胜则先行方败。
f(27,24,27)=1，说明先行方必得奇数。
所以若结果偶数胜，那么 (27,27,27)---->（27,24,27）就能胜利。
而(27,27,27)所能演变的所有其他结果f(a,b,c)都等于2，所以其他取法都不能取得胜利。
而若结果为奇数胜，那么后行方必得到奇数结果，所以先行方必败。 f(6,3,4)=3
说明无论是奇数胜还是偶数胜，先行方必败。
页:
[1]
2