勇往直前棋

yzsjw0

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

zxl0714

每一行可以看成一个单独的小游戏，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为先手必败

oboe

那残局名是叫长亭短亭

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

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

oboe

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

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

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

骰迷

繼續發圖華麗的湊字數

lulijie

龙教授的方法跟我的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楼得到的那些必胜局面。

骰迷

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

骰迷

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

骰迷

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