魔方吧·中文魔方俱乐部

标题: 勇往直前棋 [打印本页]

作者: yzsjw0 时间: 2009-5-2 13:06:05 标题: 勇往直前棋

勇往直前棋：
A和B两人分别有5粒棋子。A棋子可以向右移动，B棋子可以向左移动。每次移动格数不限。但双方棋子不能重合，也不能跳过对方棋子。不能移动者算输。分析一下谁能赢，怎么移动？

附件: 勇往直前棋.JPG (2009-5-2 13:06:27, 16.22 KB) / 下载次数 57
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NDg0Nzd8YWMyZmUzMzZ8MTc0MDYzMDYyMnwwfDA%3D

作者: joey0513 时间: 2009-5-2 13:09:46

這是什麽玩意？還真沒有玩過

作者: q376997368 时间: 2009-5-2 13:10:53

可以反向移动吗？

作者: joey0513 时间: 2009-5-2 13:11:08

雖然還沒想明白，但我覺得還是先走的能贏

作者: xdgtzsyyj 时间: 2009-5-2 13:33:16

我觉得无论谁先走胜率都一样

作者: lulijie 时间: 2009-5-2 14:15:09

先走方必胜，
A1和B1之间共有4格，
A2和B2之间共有5格，
A3和B3之间共有6格，
A4和B4之间共有7格，
A5和B5之间共有8格，
总共有30格，为偶数格。
先走方第一步走偶数格，使得剩下的总格数为偶数，以后对方走奇数格，我方也走奇数格，对方走偶数格，我方也走偶数格，使得剩下的总格数保持偶数。
最后其他三行都无子可走时，你要保证剩下的两行都大于1，
再进行下去，最后必形成2+2的形式，
对方只能走1步，你走另1行的1步，形成1+1，对方再走1步，你走完最后1步，成0+0形式，对方无子可走。
若对方走2步，你也走2步，对方无子可走。
----------------------------------------------------------------
在进行过程中，若剩两行之前，对方若故意造成某行只剩1格，若他走的是奇数格，你就把这格走掉，若他走的是偶数格，不理这1格。若对方再造成另一行仅剩一格，在总行数大于3行之前，不用当心。当仅剩3行时，形成1+1+N 的形式，就走掉N格，成1+1形式。

作者: putibenwushu1 时间: 2009-5-2 14:17:32

楼上专业，这种棋那有的玩？

作者: 骰迷 时间: 2009-5-2 14:19:22

先手必勝，所有情況（除了沒有選擇的情況）都必勝

作者: 魔鱼儿 时间: 2009-5-2 14:25:32

这个应该是先走的胜吧,呵呵,顶

作者: lulijie 时间: 2009-5-2 14:41:01

后走方最顽强的抵抗，是尽量形成1+2+3的形式。
先走方要尽量避免被对方走成1+2+3的形式。
--------------------------------------------------------------------
所以先走方最好让后手方被迫消掉1行，剩3行的时候，要轮到自己走棋。

作者: 骰迷 时间: 2009-5-2 14:41:43

就算是奇數格先手也必勝
除了一開始就是１＋１的局面

作者: lulijie 时间: 2009-5-2 15:13:48

我发现没有相像中那么简单：
1+1
偶数+偶数
奇数+奇数（奇数不等于1）
1+2+3
都是必胜形式。
但以下形式却需要分析：
1+奇数+偶数（奇数大于1，偶数大于2）
   1.轮到你走，你不能把1消掉，否则对方可造成奇数+奇数或偶数+偶数的必胜局面。
   2.你也不能把1+奇数+偶数走成1+奇数+奇数或1+偶数+偶数的局面，否则对方消掉1，成奇数+奇数或偶数+偶数的必胜局面
   3.你只能每次走偶数格，对方每次也最能走偶数格，最后谁先走成1+2+奇数，或1+3+偶数，谁就输。

作者: lulijie 时间: 2009-5-2 15:27:19

对于 1+奇数+偶数（奇数大于1，偶数大于2）的形式
若奇数-偶数=1 是必胜局面
否则就是  必败局面。
比如1+4+5
   1+6+7
   1+8+9
等等都是必胜局面，其他都是必败局面。

作者: lulijie 时间: 2009-5-2 15:44:51

偶数+偶数
奇数+奇数（奇数不等于1）
是必胜局面，我考虑错了。
应该是：
N+M (N=M) 才是必胜局面，
若N<>M，是必败局面。

作者: lulijie 时间: 2009-5-2 17:17:30

楼主的题目确实没有想象中简单：
抛开楼主的具体题目，考虑一般情况。
一、剩两行的情况：
   N+M (N=M)  ，必胜局面，
   N<>M，必败局面。
二、剩三行的情况：
1+2+3 必胜局面
a+b+c （a<=b<=c）
      1. a、b、c至少有两个数相等，必败局面。
      2. a、b、c有1、2、3中的两个数，必败局面。
      3. a=1
                        b为偶数，c等于b+1，必胜局面，
                        否则，必败局面。
      4. a=2
                  。。。。。。好复杂哦！
----------------------------------------------------------------------
最多5行，每行最多空格数位8格。
用倒推的方法推出  （电脑计算）
必胜局面：
11
22
33
44
55
66
77
88
123
145
167
246
257
347
356
1111
1122
1133
1144
1155
1166
1177
1188
1247
1256
1346
1357
2222
2233
2244
2255
2266
2277
2288
2345
2367
3333
3344
3355
3366
3377
3388
4444
4455
4466
4477
4488
4567
5555
5566
5577
5588
6666
6677
6688
7777
7788
8888
11123
11145
11167
11246
11257
11347
11356
12223
12245
12267
12333
12344
12355
12366
12377
12388
13345
13367
14445
14467
14555
14566
14577
14588
15567
16667
16777
16788
22246
22257
22347
22356
23346
23357
24446
24457
24556
24666
24677
24688
25557
25667
25777
25788
33347
33356
34447
34456
34557
34667
34777
34788
35556
35666
35677
35688

[ 本帖最后由 lulijie 于 2009-5-2 19:20 编辑 ]

作者: lulijie 时间: 2009-5-2 19:25:53

因为45678不是必胜局面（即必败局面），相当于对方走成45678必败局面，所以先行方必胜。
查上述结果，先行方把A5走到B5的旁边，消除掉A5B5行，形成4567局面，就成必胜局面，仅此一种必胜走法。

作者: lulijie 时间: 2009-5-2 19:37:58

若一共只有4行，第一行4格，第二行5格，第三行6格，第四行7格，即4567的形式，
那么先行方必败。
所以不能说先行方必胜，而是跟局面有关。

作者: flwb 时间: 2009-5-2 21:16:20

其实就是个NIM题,不过变了个方式。五堆石子，两人轮流取子，一次只能从一堆中取，随便取多少，谁取到最后一颗胜，先手必胜。

作者: xdgtzsyyj 时间: 2009-5-2 21:32:05

原来如此，有意思，这使我想起了2个人在一张桌子上放硬币的胜率问题，先放者必胜

作者: lulijie 时间: 2009-5-2 21:54:26

18楼的类比非常正确，但结论却不对。
比如简单一点：
两堆石子，每堆6个，先取方必败。
三堆石子，一堆1个石子，一堆2个石子，一堆3个石子，先取方也必败。
-------------------------------------------------------------------------
18楼的结论若这么说：5堆石子，各堆石子数相同，那么先取方必胜。才是正确的。

作者: lulijie 时间: 2009-5-2 22:14:02

各堆的石子数如下
66
123
4567
35666
--------------
上述都是先取方必败。
所以先取方必胜还是后取方必胜，与各堆的石子数有关。
具体到怎样的组合是先取方必胜，怎样的组合是后取方必胜，可以用倒推的方法从2堆的结论，推导出3堆的结论，一直往后推导，可推导出4堆得结论，5堆得结论，..........
推导过程可以交给电脑。

作者: 无限正义 时间: 2009-5-3 00:24:44

先手的不会输。后手的不会赢。这游戏小时候在文曲星里好像玩过

作者: kexin_xiao 时间: 2009-5-3 21:28:09

６楼高手啊，学习了！

作者: sokoban 时间: 2009-5-3 21:29:06

这个本质上就是 Nim 游戏吧

作者: 骰迷 时间: 2009-5-3 22:02:56

樓上說得不錯，NIM遊戲就是從幾堆的棋子中取子，本質上一樣

作者: 骰迷 时间: 2009-5-14 19:41:25

星島日報上有ＮＩＭ的介紹與探討，發上來分享

附件: img008.jpg (2009-5-14 19:41:25, 259.79 KB) / 下载次数 33
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTA0OTF8NTgyYTdjNjB8MTc0MDYzMDYyMnwwfDA%3D

附件: img005.jpg (2009-5-14 19:41:25, 413.02 KB) / 下载次数 38
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTA0OTJ8NTRlNzNlMzR8MTc0MDYzMDYyMnwwfDA%3D

作者: 骰迷 时间: 2009-5-14 19:52:30

龍校長所謂輸定局面，是對先手而言的。

附件: img009.jpg (2009-5-14 19:52:30, 354.81 KB) / 下载次数 29
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTA0OTN8YTMzMzIxMGN8MTc0MDYzMDYyMnwwfDA%3D

作者: lulijie 时间: 2009-5-14 21:10:18

龙教授的方法跟我的15楼编程使用的方法是相同的，我的那些必胜局面（你走成这个局面就会必胜）就是龙教授的必败局面。
假设有n堆石子，每堆石子数最多为S颗。
每堆的个数分别是a(1)、a(2)、a(3)......a(n)。从小到大顺序排列。
用a(1)a(2)a(3)......a(n)来表示石子的局面。
已知n堆石子的所有必胜局面。那么可推导出所有的n+1堆的必胜局面。
n+1堆的局面a(1)a(2)a(3)......a(n)a(n+1) 假如无论去掉哪一堆，都无法使形成的n堆局面是必胜局面，且每一堆的数目都无法再少了，那么这个局面就是必胜局面。
----------------------------------------------------
例如每堆石子数最多8个。
那么n=2时的所有必胜局面就是
11，22，33，44，55，66，77，88
那么123，就是必胜局面。因为123无论去掉哪个数（剩下为12，13，23），都形不成必胜局面。且每堆数都无法再减少。比如减少成122，不是必胜局面，因为去掉1，剩下22，是必胜局面。
而134不是必胜局面，尽管无论去掉哪个数，都形不成必胜局面，但4可以减少为2，形成123必胜局面，所以134不是必胜局面。（已知n堆的局面a(1)a(2)a(3)......a(n)是必胜局面，那么另一个n堆局面，与它有n-1堆的石子数都相同，那么它必定不是必胜局面）
依次递推，就推导出我在15楼得到的那些必胜局面。

作者: 骰迷 时间: 2009-5-17 15:14:55

繼續發圖華麗的湊字數

附件: img010.jpg (2009-5-17 15:14:55, 402.89 KB) / 下载次数 27
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTA4Mzd8M2JlMGEyZmJ8MTc0MDYzMDYyMnwwfDA%3D

作者: oboe 时间: 2009-5-19 16:49:41

有个象棋残局有这个思路的.

基本上思路是这样, 红车和黑车都在自己的底线上, 还有红炮和黑炮也是, 还加上了红兵和黑卒.
这三个子都在同一线上,相对的.
如果移开,不和对方子相对,就会被对方将死.
其它的子也不能动, 因为一动就会被对方将死.
结果就是要你计算,双车/双炮/双卒不断地靠近距离.

基本结果是我走一步,你也走一步, 你走二步我也走二步, 你走三步,我只走一步.
先手胜的.

作者: oboe 时间: 2009-5-19 16:51:09

那残局名是叫长亭短亭

引自古代长亭十里短亭五里.
意为走二步, 或者走一步.
你走偶数步,我走奇数步.

[ 本帖最后由 oboe 于 2009-5-19 16:59 编辑 ]

附件: 长亭短亭.jpg (2009-5-19 16:59:52, 23.14 KB) / 下载次数 46
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTExMzF8ZTQ2N2FiMjh8MTc0MDYzMDYyMnwwfDA%3D

作者: zxl0714 时间: 2009-8-28 18:53:03

每一行可以看成一个单独的小游戏，sg( x ) = x，x表示两棋子之间的距离。对于含有五个这样的小游戏而言，SG( ) = sg( x1 ) xor sg( x2 ) xor sg( x3 ) xor sg( x4 ) xor sg( x5 )
对于这种局面的sg值为SG( ) = 4 xor 5 xor 6 xor 7 xor 8 = 8不等于0，因此先手必胜。设4 xor 5 xor 6 xor 7 xor 8 xor k = 0，则k xor 8 = 0，k = 8，找k的最高位在8处，8 xor 8 = 0，只需将第5行的距离变成0即可，这时SG( ) = 4 xor 5 xor 6 xor 7 xor 0 = 0为先手必败

作者: hw294 时间: 2009-8-29 13:01:18

提示: 作者被禁止或删除内容自动屏蔽

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