Grundy博弈编程

在两位选手面前放着一堆东西,譬如说一堆铜币.第一位选手把原堆分成不相等的两堆.然后每个选手轮流地这样做,即当轮到某一方分时他把已被分的任一堆再分成不相等的两堆.博弈这样一直进行下去,直到每一堆都只乘下一个或两个铜币为止.这时按规则博弈已经不可能继续玩下去了,哪个选手首先遇到这种情况就算输了.

要求用prolog语言，不会的话给出一个好的算法也可以。
最后能：对任意一个N值，判断先手必胜或后生必胜，电脑充当必胜者，和人分币。

表一：

东西个数－－－输者（A为当前走者）
1 －－－－－A
2 －－－－－A
3 －－－－－B
4 －－－－－B
5 －－－－－A
6 －－－－－B
7 －－－－－B
8 －－－－－A
9 －－－－－B
…………………
…………………
发现规律了。比如有10个东西的时候，是先走的输还是后走的输啊？
10＝8＋2＝9＋1＝3＋7＝4＋6＝5＋5
存在（8，2）这样的一对，使得下一个行动的agent无论选择8或者2都是自己输（即A输）。那么当前的agent肯定应该选择这样的路径。
所以对于任何一个N值就可以用这个方法判断先走输还是后走输（使用递归函数，prolog不会哈，不过用lisp容易实现）。

最先走的我们叫它为竞争者1，后面的叫做竞争者2。

具体走法可以这么实现，为什么10个的时候一定是后走的输掉呢？因为先走的“竞争者1” ，它一定会选择最有利于自己的一步，使得无论 “竞争者2” 无论怎么走，都一定会输。他一定要把10分为8和2两堆。这样 “竞争者2” 选择的时候，就会发现，根本没有一条能够走向获胜的道路，因为8和2对应的都是A，也就意味着这种情况下参与竞争的竞争者一定会输。竞争继续下去……此时无论 “竞争者2” 怎么分，分得的结果对（a，b）中一定存在上表中对应的是B输的，此时正是 “竞争者1”(作为A)走，按照上面的过程，寻找（a，b）对，使得a,b都对应“竞争者2”输（对应“竞争者2”输也就是表中值对应A），由上面的推理可以知道一定有这样的一对。

另：由上面分析也可以看出来，这个游戏对于先走后走的人并不公平，所以即便不用保证每次都获胜，只要是每次我先走，也一般都是我赢。

int is-first-win(int n){
   int i=1;
   if(n==1||n==2)return 0;
   for(i=1;i<=n/2;i++){
     if(!is-first-win(i)&&!is-first-win(n-i))return 1;
   }
   return 0;
}

动态规划+hash f[i]表示当m=i的时候该决策的人的输赢状态。 1.i*9>=n f[i]是1 （必胜） 2.i*9<n  如果f[i*j]都是1  f[i]=0（必败） 反之f[i]=1 所以可用记忆化搜索求f[1] 其值为1就是nic胜 反之susan 由于n要到2^31-1所以下标会爆，但考虑到m在任何时候的质因数只能是2、3、5、7，所以m的实际可能取到的数值是很少的，故可用hash解决。 注意f数组的初值，赋为0和1之外的值