取数游戏

phileas

一维的容易很多，不过仍然不存在一个漂亮的公式。

取数会把原来连续的一段数字分成两段，相当于两个子游戏。所以仍然可以用处理nim类问题的一般方法。求得前100项为：

0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7,4,0,1,1,2,0,3,
1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,8,1,1,2,0,3,1,1,0,3,3,2,
2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,

程序如下：

import java.util.BitSet;

public class X
{
    public static void main(String[] args)
    {
        int[] nim = new int[100];
        nim[0] = 0;
        nim[1] = 1;
        nim[2] = 1;

        for (int i = 3; i < nim.length; i++)
        {
            calculate(i, nim);
        }

        for (int i = 0; i < nim.length; i++)
        {
            System.out.print(nim + ",");
        }
    }

    private static void calculate(int i, int[] nim)
    {
        BitSet handleSet = new BitSet();

        handleSet.set(nim[i-2]);
        handleSet.set(nim[i-3]);
        int n = i-3;
        for (int index = 0; index <= n/2; index++)
        {
            handleSet.set(nim[index] ^ nim[n-index]);
        }

        nim = handleSet.nextClearBit(0);
    }

}

phileas

单纯要知道先手胜还是后手胜的话：0表示先手败，非0表示先手胜。

这些数值本身的作用是用来递推的。2楼也已经说了，一次取数，可以把原来的游戏变成
1. 子游戏n-2
2. 子游戏n-3
3. 子游戏1和子游戏n-4；子游戏2和子游戏n-5。。。

所以，递归定义nim(n)如下：
1. nim(0)=0
2. 当nim(0),...,nim(k)都已经定义，定义集合G(k+1) = {nim(k-1), nim(k-2), nim(1) 异或 nim(k-3), nim(2) 异或 nim(k-4),...}
3. 定义nim(k+1) = min {x | x >= 0 且 x不属于G(k+1)}

然后这个取数游戏就变成那个经典的取石子游戏了，仍然是用两进制解决。

编程计算上述函数是容易的，但是不存在一个很漂亮的公式来描述这个函数。

有了这个函数，可以很容易解决多堆数字的情况，比如，三堆数字分别有2个，3个，5个，这种情况是先行必败，因为1异或2异或3 = 0

[ 本帖最后由 phileas 于 2009-10-10 21:17 编辑 ]

phileas

18，先手拿成12,3，后手如何应对？

phileas

原帖由 lulijie 于 2009-10-10 23:52 发表
回7楼：
   后手应成  3 ,10

回10楼：先手应2,3,5。

phileas

通过状态转换来计算当然是可以的，但是这样计算量比较大，实际上就是穷举。

对于一般的两人博弈游戏，每步只有有限多种选择，有限步后必然结束，结束后必然能判定输赢（即不存在和棋）。那么根据博弈论的基本定理，任一个初始状态，必然有一个人存在必胜策略。

如果加上限制条件：对于任何状态，两人可供选择的下法是相同的；那么所有这样的游戏都可以等价于一个经典的nim取石子游戏。本游戏正是如此。

这个定理的价值在于，母游戏的nim值等于所有子游戏的nim值的异或。这样，虽然仍然需要编程计算，但计算量比较小。

对于二维的隔空棋，也是可以运用这个定理的。但是由于二维情况下无法很容易的把母游戏转化成多个子游戏，所以即使使用该定理，计算量仍然很大，作用不明显。

phileas

我把前20项的nim值重新贴一下，有兴趣的朋友可以用8楼的列表验证一下，是否先手必败的充要条件是nim值的异或=0。

nim(1)=1,nim(2)=1,nim(3)=2,nim(4)=0,nim(5)=3,
nim(6)=1,nim(7)=1,nim(8)=0,nim)9)=3,nim(10)=3,
nim(11)=2,nim(12)=2,nim(13)=4,nim(14)=0,nim(15)=5,
nim(16)=2,nim(17)=2,nim(18)=3,nim(19)=3,nim(20)=0,
==============================================
随便验证两个：
2,7：nim(2)异或nim(7) = 1异或1 = 0
1,3,5：nim(1)异或nim(3)异或nim(7) = 1异或2异或3 = 0

phileas

对于拿到最后一个算输的问题，其一般解法见：
http://bbs.mf8-china.com/viewthr ... page%3D1&page=2
15楼