Nim游戏博弈

本文主要是介绍Nim游戏博弈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Nim游戏的概述：

还记得这个游戏吗？
给出n列珍珠，两人轮流取珍珠，每次在某一列中取至少1颗珍珠，但不能在两列中取。最后拿光珍珠的人输。
后来，在一份资料上看到，这种游戏称为“拈（Nim）”。据说，它源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。后来流传到高级人士，则用便士（Pennies），在酒吧柜台上玩。
最有名的玩法，是把十二枚便士放成3、4、5三列，拿光铜板的人赢。后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5，就能稳操胜券了，游戏也就变得无趣了。于是大家就增加列数，增加铜板的数量，这样就让人们有了毫无规律的感觉，不易于把握。
直到本世纪初，哈佛大学数学系副教授查理士•理昂纳德•包顿（Chales Leonard Bouton）提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则。
一般规则是规定拿光铜板的人赢。
它的变体是规定拿光铜板的人输，只要注意某种特殊形态（只有1列不为1），就可以了！
有很多人把这个方法写成计算机程序，来和人对抗，不知就理的人被骗得团团转，无不惊叹计算机的神奇伟大。其实说穿了，只因为它计算比人快，数的转化为二进制其速度快得非人能比，如此罢了。
（以上来自K12教育论坛）

Nim游戏的数学理论论述：

Nim游戏是博弈论中最经典的模型，它又有着十分简单的规则和无比优美的结论
Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。

定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。
按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。

以Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠定义证明一下(3,3)是一个P是一个P是一个P-position。首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只要找到一个是P-position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局面(0,1)是N-position），所以(1,3)也是N-position。同样可以证明(2,3)是N-position。所以(3,3)的所有子局面都是N-position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且仅当这两堆石子的数目相等”。

根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP或者记忆化搜索的方法以提高效率。但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,...,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1*a2*...*an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法。

直接说结论好了。

(Bouton's Theorem)：对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。

怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。

根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题： 1、这个判断将所有terminal position判为P-position；2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；3、根据这个判断被判为P-position的局面无法移动到某个P-position。

第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。

第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

第三个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。

根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。

（以上来自百度百科）

Nim游戏的形象具体论述：

Nim取子游戏是由两个人面对若干堆硬币（或石子）进行的游戏。设有k>=1堆硬币，各堆分别含有N ₁，N ₂，……N _K枚硬币。游戏的目的就是选择最后剩下的硬币。游戏法则如下：

1．两个游戏人交替进行游戏（游戏人I和游戏人II）；

2．当轮到每个游戏人取子时，选择这些堆中的一堆，并从所选的堆中取走至少一枚硬币（游戏人可以取走他所选堆中的全部硬币）；

3．当所有的堆都变成空堆时，最后取子的游戏人即为胜者。

这个游戏中的变量是堆数k和各堆的硬币数N ₁，N ₂，……N _k。对应的组合问题是，确定游戏人I获胜还是游戏人II获胜以及两个游戏人应该如何取子才能保证自己获胜（获胜策略）。

为了进一步理解Nim取子游戏，我们考查某些特殊情况。如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N ₁和N ₂。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N ₁！=N ₂，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N ₁= N ₂，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。

现在我们如何从两堆的取子策略扩展到任意堆数中呢？

首先来回忆一下，每个正整数都有对应的一个二进制数，例如：57 ₍₁₀₎ à 111001 ₍₂₎ ，即：57 ₍₁₀₎=2 ⁵+2 ⁴+2 ³+2 ⁰。于是，我们可以认为每一堆硬币数由2的幂数的子堆组成。这样，含有57枚硬币大堆就能看成是分别由数量为2 ⁵、2 ⁴、2 ³、2 ⁰的各个子堆组成。

现在考虑各大堆大小分别为N ₁，N ₂，……N _k的一般的Nim取子游戏。将每一个数N _i表示为其二进制数（数的位数相等，不等时在前面补0）：

N ₁= a _s…a ₁a ₀

N ₂= b _s…b ₁b ₀

……

N _k= m _s…m ₁m ₀

如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：

a_s+ b_s + … + m_s 是偶数

……

a₁+ b₁+ … + m₁是偶数

a₀+ b₀ + … + m₀是偶数

于是，我们就能得出获胜策略：

游戏人I能够在非平衡取子游戏中取胜，而游戏人II能够在平衡的取子游戏中取胜。

我们以一个两堆硬币的Nim取子游戏作为试验。设游戏开始时游戏处于非平衡状态。这样，游戏人I就能通过一种取子方式使得他取子后留给游戏人II的是一个平衡状态下的游戏，接着无论游戏人II如何取子，再留给游戏人I的一定是一个非平衡状态游戏，如此反复进行，当游戏人II在最后一次平衡状态下取子后，游戏人I便能一次性取走所有的硬币而获胜。而如果游戏开始时游戏牌平衡状态，那根据上述方式取子，最终游戏人II能获胜。

下面应用此获胜策略来考虑4-堆的Nim取子游戏。其中各堆的大小分别为7，9，12，15枚硬币。用二进制表示各数分别为：0111，1001，1100和1111。于是可得到如下一表：

	2³ = 8	2² = 4	2¹ = 2	2⁰ = 1
大小为7的堆	0	1	1	1
大小为9的堆	1	0	0	1
大小为12的堆	1	1	0	0
大小为15的堆	1	1	1	1

由Nim取子游戏的平衡条件可知，此游戏是一个非平衡状态的取子游戏，因此，游戏人I在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法有多种，游戏人I可以从大小为12的堆中取走11枚硬币，使得游戏达到平衡（如下表），

	2³ = 8	2² = 4	2¹ = 2	2⁰ = 1
大小为7的堆	0	1	1	1
大小为9的堆	1	0	0	1
大小为12的堆	0	0	0	1
大小为15的堆	1	1	1	1

之后，无论游戏人II如何取子，游戏人I在取子后仍使得游戏达到平衡。

同样的道理，游戏人I也可以选择大小为9的堆并取走5枚硬币而剩下4枚，或者，游戏人I从大小为15的堆中取走13枚而留下2枚。

归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。

(以上转自Rainco_shnu的百度空间)

下面写点自己的东西:

如果Nim游戏中的规则稍微变动一下,每次最多只能取K个,怎么处理?

方法是将每堆石子数mod (k+1).

最近看《编程之美》一书，感叹思维之妙，不过看过之后又在很多数学方面的书里面找到了同样的解法例如《组合数学》、《图论导引》等，之后才知道其实很多书上的算法都是源自数学、图论、博弈论知识，同时也一直有一种感觉：未来是数据的天下，同时也是数学威力大大展现的时候。

在《编程之美》1.11~1.13中讲的都是NIM游戏。所以在网上查查资料，汇总如下，以备review。

给出n列珍珠，两人轮流取珍珠，每次在某一列中取至少1颗珍珠，但不能在两列中取。最后拿光珍珠的人输。后来，在一份资料上看到，这种游戏称为“拈（Nim）”。据说，它源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。后来流传到高级人士，则用便士（Pennies），在酒吧柜台上玩。最有名的玩法，是把十二枚便士放成3、4、5三列，拿光铜板的人赢。后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5，就能稳操胜券了，游戏也就变得无趣了。于是大家就增加列数，增加铜板的数量，这样就让人们有了毫无规律的感觉，不易于把握。直到本世纪初，哈佛大学数学系副教授查理士•理昂纳德•包顿（Chales Leonard Bouton）提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则。一般规则是规定拿光铜板的人赢。它的变体是规定拿光铜板的人输，只要注意某种特殊形态（只有1列不为1），就可以了！

Nim游戏的数学理论论述：

(Bouton's Theorem)：对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。

Nim游戏的形象具体论述：

1．两个游戏人交替进行游戏（游戏人I和游戏人II）；

2．当轮到每个游戏人取子时，选择这些堆中的一堆，并从所选的堆中取走至少一枚硬币（游戏人可以取走他所选堆中的全部硬币）；

3．当所有的堆都变成空堆时，最后取子的游戏人即为胜者。

现在我们如何从两堆的取子策略扩展到任意堆数中呢？

现在考虑各大堆大小分别为N ₁，N ₂，……N _k的一般的Nim取子游戏。将每一个数N _i表示为其二进制数（数的位数相等，不等时在前面补0）：

N ₁= a _s…a ₁a ₀

N ₂= b _s…b ₁b ₀

……

N _k= m _s…m ₁m ₀

a_s+ b_s + … + m_s 是偶数

……

a₁+ b₁+ … + m₁是偶数

a₀+ b₀ + … + m₀是偶数

于是，我们就能得出获胜策略：

游戏人I能够在非平衡取子游戏中取胜，而游戏人II能够在平衡的取子游戏中取胜。

	2³ = 8	2² = 4	2¹ = 2	2⁰ = 1
大小为7的堆	0	1	1	1
大小为9的堆	1	0	0	1
大小为12的堆	1	1	0	0
大小为15的堆	1	1	1	1

	2³ = 8	2² = 4	2¹ = 2	2⁰ = 1
大小为7的堆	0	1	1	1
大小为9的堆	1	0	0	1
大小为12的堆	0	0	0	1
大小为15的堆	1	1	1	1

之后，无论游戏人II如何取子，游戏人I在取子后仍使得游戏达到平衡。

同样的道理，游戏人I也可以选择大小为9的堆并取走5枚硬币而剩下4枚，或者，游戏人I从大小为15的堆中取走13枚而留下2枚。

这里我认真查了查异或运算的性质和应用。之前只知道X XOR X =0。异或是自己的逆运算。现在给你2n+1个正整数，其中有n对数和1个单独的数，（这里规定一对数的意思是这两个数相等），然后让你设计一种算法，把这个单独的数给找出来，要求时间复杂度为O(n)，那么就可以使用异或运算因为连续异或的结果与运算数的顺序无关，所以所有的对数异或之后都是0，之后的异或则可以直接找出单独的数。异或还可以在磁盘损坏之后推算出其数据。XOR 满足消去率。同时在交换两个数的时候不需要使用传统的引用传递而是通过^符号进行。位运算的功能确实强大啊。

转自：http://blog.csdn.net/ingwfj/article/details/52481349

1.7　例子：Nim游戏

2012-10-08 08:36:02 我来说两句

收藏我要投稿

本文所属图书 > 组合数学（原书第五版）

本书系统地阐述组合数学基础、理论和方法，侧重于组合数学的概念和思想，论述了鸽巢原理、排列与组合、二项式系数、容斥原理及应用、递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计、图论、有向图... 立即去当当网订购

下面我们追溯组合数学在数学娱乐中的起源并研究一下Nim3这个古老的游戏来结束本章的介绍。这个游戏的解取决于奇偶性（parity），这是在组合数学中解决问题的一个重要概念。之前在研究棋盘的完美覆盖时利用了一个简单的奇偶论断，当时我们指出一个棋盘为了有多米诺骨牌的完美覆盖就必须有偶数个方格。

Nim是一种两个人玩的游戏，玩家双方面对一堆硬币（或者石头或者豆粒）。假设有k≥1堆硬币，每堆分别有n1,n2,…,nk枚硬币。这一游戏的目标就是取得最后一枚硬币。游戏的规则如下：

（1)玩家轮番出场（我们称第一个取子的玩家为Ⅰ，而第二个玩家为Ⅱ）。

（2)当轮到一个玩家取子时，他们都要从选择的硬币堆中至少取走一枚硬币。（这位玩家也可以把所选硬币堆的硬币都取走，于是剩下一个空堆，这时它“退出”。）

当所有硬币堆都空了的时候，游戏结束。走最后一步的玩家，即取走最后一枚硬币的玩家获胜。

在这个游戏中的变量是堆数k和堆中的硬币数n1,n2,…,nk。我们要问的组合问题是确定是第一个玩家胜还是第二个玩家胜1，以及这位玩家为了获胜应该如何取子，也就是获胜策略。

为了进一步理解Nim游戏，下面我们考虑一些特殊的情况2。如果一开始就只有一堆硬币。那么玩家Ⅰ取走所有硬币就可以获胜。现在假设k=2，且分别有n1枚和n2枚硬币。玩家Ⅰ是否可以获胜不取决于n1，n2具体是多少，而是取决于它们是否相等。假设n1≠n2。玩家Ⅰ可以从大堆中取走足够多的硬币以便对于玩家Ⅱ来说，剩余两堆的大小相同。现在，当轮到玩家Ⅰ时，他可以模仿玩家Ⅱ的取子方式。因此，如果玩家Ⅱ从一堆中取走了c枚，那么玩家Ⅰ则从另一堆中取走相同数目的硬币。这样的策略保证玩家Ⅰ可以获胜。如果n1=n2，那么玩家Ⅱ通过模仿玩家Ⅰ的取子方式而获胜。因此，我们就完全解决了2堆的Nim游戏的取子问题。下面是2堆Nim游戏的一个例子，其堆的大小分别是8和5：

上述解决2堆Nim游戏的想法是用某种方式取子使得剩余两堆的大小相同，这一想法可以推广到任意k堆的情况。玩家获胜的洞察力来自于二进制整数的概念。回想一下，每一个正整数n都可以表示成二进制数字，其方法是反复减去一个不超过这个数的2的最大幂。例如，为了将十进制数57表示成二进制数，我们观察到

因此

57表示成二进制数是

111001

二进制数的每一个数字不是0就是1。第i个位置上的数字对应于2i，称为第i(i≥0)位3。对于每一堆硬币，对应于它的基数2，我们可以认为它是由2的幂的子堆组成的。因此，53枚硬币的一堆硬币是由下面的子堆组成的：25，24，22，20。对于2堆Nim游戏，各种大小的子堆总数只能是0，1或2。具有特定大小的子堆正好有一个当且仅当这两堆的大小不同。换句话说，各种大小的子堆总数是偶数当且仅当这两堆大小相同，即当且仅当玩家Ⅱ在这场Nim游戏中获胜。

下面考虑有大小分别为n1，n2,…,nk的一般的Nim游戏。把每一个数字ni表示成二进制数：

　?
（通过在数前补0，可以假设所有堆的大小都是有相同位数的二进制数。）我们称一个游戏是平衡的(balanced)，指的是各种大小的子堆数是偶数。因此一个Nim游戏是平衡的当且仅当

若一个Nim游戏不是平衡的，则称它为非平衡的（unbalanced）。我们说第i位是平衡的，指的是和ai+bi+…+ei是偶数，否则就是非平衡的。因此，若一个游戏是平衡的，则它在各个位上都是平衡的，而对于非平衡游戏来说，至少存在一个非平衡位。

于是我们有下面的陈述：

玩家Ⅰ能够在非平衡Nim游戏中获胜，而玩家Ⅱ则能够在平衡Nim游戏中获胜。

为了理解上述的结论，我们扩展2堆Nim游戏中使用的策略。假设这个Nim游戏是非平衡的。设最大不平衡位是第j位。于是，玩家Ⅰ以某种方式取走硬币给玩家Ⅱ留下一个平衡游戏。他的作法是：选出一个第j位上是1的堆，并从中取走一定数目的硬币使得剩下的游戏是平衡的（参见练习题32）。无论玩家Ⅱ怎样做，他都不得不又给玩家Ⅰ留下一个不平衡的游戏，玩家Ⅰ又把这个游戏变成平衡游戏。如此这般继续下去就可以保证玩家Ⅰ获胜。如果这个游戏开始时就是平衡游戏，那么玩家Ⅰ第一次取子使其变成不平衡游戏，此时轮到玩家Ⅱ采用平衡游戏的策略。

例如，考虑一个4堆Nim游戏，其堆的大小分别是7，9，12，15。这些堆的大小的二进制数表示分别是0111，1001，1100和1111。用2的幂的子堆表示，我们得到

这个游戏中第3位、第2位和第0位是不平衡的。玩家Ⅰ可以从大小为12的堆中取走11枚硬币，留下1枚硬币。因为1的二进制数字是0001，此时这个游戏是平衡的。或者玩家Ⅰ也可以从大小为9的堆中取走5枚硬币，留下4枚，或者从大小为15的堆中取走13枚硬币，留下2枚硬币。

3　Nim来自于德语的Nimm!，意思是取!
1 发挥聪明才智。
2 这是一般情况下要遵守的重要原则:为了加深理解和更加直观，先考虑较小或特殊的情况，然后再尝试着拓展你的思路去解决更一般的问题。
3 位（bit）一词是binary digit的简写。

转自：http://www.cnblogs.com/easonliu/p/4472541.html

[hihoCoder] 博弈游戏·Nim游戏

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

今天我们要认识一对新朋友，Alice与Bob。
Alice与Bob总是在进行各种各样的比试，今天他们在玩一个取石子的游戏。
在这个游戏中，Alice和Bob放置了N堆不同的石子，编号1..N，第i堆中有A[i]个石子。
每一次行动，Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗，至多取出这一堆剩下的所有石子。
Alice和Bob轮流行动，取走最后一个石子的人获得胜利。
假设每一轮游戏都是Alice先行动，请你判断在给定的情况下，如果双方都足够聪明，谁会获得胜利？

提示：Nim?!

输入

第1行：1个整数N。表示石子堆数。1≤N≤100
第2行：N个整数，第i个整数表示第i堆石子的个数A[i]，1≤A[i]≤10000

输出

第1行：1个字符串，若Alice能够获胜输出"Alice"，否则输出"Bob"

样例输入

3
3 2 1

样例输出

Bob

这一次我们讲的是一个古老而又经典的博弈问题：Nim游戏。

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：
1、两名选手；
2、两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3、游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4、若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：
P-position：在当前的局面下，先手必败。
N-position：在当前的局面下，先手必胜。

他们有如下性质：
1.合法操作集合为空的局面是P-position；
2.可以移动到P-position的局面是N-position；
3.所有移动都只能到N-position的局面是P-position。

在这个游戏中，我们已经知道A[] = {0,0,...,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A[1]*A[2]*...*A[N]。并且每一次的状态转移很多。
虽然耗时巨大，但确实是一个可行方法。

当然，我们这里会讲这个题目就说明肯定没那么复杂。没错，对于这个游戏有一个非常神奇的结论：

对于一个局面，当且仅当A[1] xor A[2] xor ... xor A[N] = 0时，该局面为P局面。

对于这个结论的证明如下：
1. 全0状态为P局面，即A[i]=0，则A[1] xor A[2] xor ... xor A[N] = 0。
2. 从任意一个A[1] xor A[2] xor ... xor A[N] = k != 0的状态可以移动到A[1] xor A[2] xor ... xor A[N] = 0的状态。由于xor计算的特殊性，我们知道一定有一个A[i]最高位与k最高位的1是相同的，那么必然有A[i] xor k < A[i]的，所以我们可以通过改变A[i]的值为A[i]'，使得A[1] xor A[2] xor ... xor A[i]' xor ... xor A[N] = 0。
3. 对于任意一个局面，若A[1] xor A[2] xor ... xor A[N] = 0，则不存在任何一个移动可以使得新的局面A[1] xor A[2] xor ... xor A[N] != 0。由于xor计算的特殊性，我们可以知道，一定是存在偶数个1时该位置的1才会被消除。若只改变一个A[i]，无论如何都会使得1的数量发生变化，从而导致A[1] xor A[2] xor ... xor A[N] != 0。
以上三条满足ICG游戏中N,P局面的转移性质，所以该结论的正确性也得到了证明。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, p, a;
 5 
 6 int main() {
 7     while (cin >> n) {
 8         for (int i = 0; i < n; ++i) {
 9             cin >> a;
10             if (i == 0) p = a;
11             else p ^= a;
12         }
13         if (p == 0) cout << "Bob" << endl;
14         else cout << "Alice" << endl;
15     }
16     return 0;
17 }