公平组合游戏ICG:
若一个游戏满足:
1. 由两名玩家交替行动;
2. 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
3. 不能行动的玩家判负;
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏,但城建的棋类游戏,比如围棋,就不是公平组合游戏。因为
棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3。
我们来看看什么是nim游戏。
NIM游戏
给定N堆物品,第i堆物品有Ai个。两名玩家轮流行动,每次可以任选一堆,取走任意多个
物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先
是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的
称为先手,第二个行动的称为后手。若在某一局面下无论采取何种行动,就会输掉游戏,称该局面必败。
所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对面面临必败局面,则
优先采取该行动。同时,这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情
况,即两人均无失误,都采取最优策略行动时游戏的结果。
NIM博弈不存在平局,只有先手必胜和先手必败两种情况。
定理: NIM博弈先手必胜,当且仅当 A1 ^ A2 ^ ... ^ An != 0
先手必胜态:可以走到某一个必败状态。
先手必败态:走不到任何一个必败状态。
我们来看一下这个nim游戏:
现在有两堆石子,一堆有3个 、一堆有5个。
先手只需要从最大的一堆中拿走两堆差的个数,后手不管拿多少,先手只需在另一堆中拿走镜像的个数,后手必败。
我们来看一下定理内容:
(1) 所有堆上的石子异或值为零 : 0 ^ 0 ^.......^ 0 = 0;(所有二进制位上 0 / 1 的个数为偶数)
(2) 所有堆上的石子异或值不为零: a1 ^ a2 ^ a3 ^ ......^an != 0
我们只需拿走若干的石子,使得所有堆上的石子异或值为零即可。
那我们需要拿走多少呢:
假设 a1 ^ a2 ^ a3 ^ ai ^ ..... an = x;
x 的最高位的一个1 是 第 k 位 ,则a1 .... an中一定存在且至少一个ai 的的第 k 位 是 1;
那我们只需拿走 ai - (ai ^ x)
那ai 堆上的石子数量变成了 ai - (ai - (ai ^ x)) = ai ^ x;
则 a1 ^ a2 ^ a3 ^ ..... ai^x ^ a(i+1) ^ ......an = x ^ x = 0;
则结得证。
洛谷模板题:【模板】nim 游戏 - 洛谷
加点难度:取火柴游戏 - 洛谷
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int main()
{
cin>>n;
while(n--)
{
int t;
int res = 0;
cin>>t;
while(t--)
{
int x;
cin>>x;
res ^= x;
}
if(res)puts("Yes");
else puts("No");
}
return 0;
}