博弈论算法的实现

一个游戏满足：

由两名玩家交替行动

在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关

不能行动的玩家判负

则称该游戏为一个公平组合游戏。

尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件2和3。

题目描述

给定nn堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。

操作步骤：

1. 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
2. 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。

必胜状态和必败状态

在解决这个问题之前，先来了解两个名词：

必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。

必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

结论

假设nn堆石子，石子数目分别是a1,a2,…,ana1,a2,…,an，如果a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，先手必胜；否则先手必败。

证明

操作到最后时，每堆石子数都是00，0⊕0⊕…0=00⊕0⊕…0=0

在操作过程中，如果 a1⊕a2⊕…⊕an=x≠0a1⊕a2⊕…⊕an=x≠0。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0。

证明：不妨设x的二进制表示中最高一位1在第k位，那么在a1,a2,…,ana1,a2,…,an中，必然有一个数aiai，它的第k为时1，且ai⊕x<aiai⊕x<ai，那么从第ii堆石子中拿走(ai−ai⊕x(ai−ai⊕x)个石子，第ii堆石子还剩ai−(ai−ai⊕x)=ai⊕xai−(ai−ai⊕x)=ai⊕x，此时a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0。

在操作过程中，如果 a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0，那么无论玩家怎么拿，必然会导致最终异或结果不为00。

反证法：假设玩家从第ii堆石子拿走若干个，结果仍是00。不妨设还剩下a′a′个，因为不能不拿，所以0≤a′<ai0≤a′<ai，且a1⊕a2⊕…⊕a′⊕…⊕an=0a1⊕a2⊕…⊕a′⊕…⊕an=0。那么(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0，则 ai=a′ai=a′，与假设0≤a′<ai0≤a′<ai矛盾。

基于上述三个证明：

1. 如果先手面对的局面是a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，那么先手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0。如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
2. 如果先手面对的局面是a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0，那么无论先手怎么拿，都会将局面变成a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，那么后手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0。如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。

c++代码

#include
#include
using namespace std;
/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ … ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ … ^an ≠ 0
*/
int main(){
int n;
scanf(“%d”, &n);
int res = 0;
for(int i = 0; i < n; i++) {
int x;
scanf(“%d”, &x);
res ^= x;
}
if(res == 0) puts(“No”);
else puts(“Yes”);
}