我在洛谷的第一篇article

· · 算法·理论

博弈论

目录链接

NiM游戏：

   给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把
   一堆取光，但不能不取。取走最后一件物品者获胜。 两人都采取最优策略，问先手是否必胜
  我们把这种游戏称为NIM博弈，把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第
  二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。所谓采取最
  优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，
  这样的局面被称为必胜。我们讨论的博弈问题一般只考虑理想情况，因为NIM博弈不存在平局，只有先手必
  胜和先手必败两种情况。

定理：NIM博弈先手必胜，当且仅当A1^A2^...^An!=0

注：“^”是异或

证：

定义：

在双方足够聪明的前提下：

先手必胜状态：可以走到某一个必败状态

先手必败状态：走不到任何一个必胜状态

先考虑必胜态怎么必胜：

假设A1^A2^...An=k,且k的最高位为第p位,那么至少存在一个Ai,满足Ai的第p位是1,那么我们只需要让Ai异或上k（其中Ai>=k）即： A1^A2^...^Ai^k^...An=k^k=0

由于Ai的第p位是1,所以Ai异或k肯定是减少了(合理的判定)。 异或完后,所有石子的异或和就变成了0，也就是必败态，所以一开始的状态为必败态。

再考虑必败态为什么必败：

由于此时异或和为0,不管怎么拿，拿完之后肯定不为0,也就是说,这个状态只能转移到必胜态,那么这个状态就是必胜态了。

例题P2197

【模板】Nim 游戏

题目描述

甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 n 堆石子（每堆石子数量小于 10^4），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n 堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 T （T\le10），表示有 T 组数据

接下来每两行是一组数据，第一行一个整数 n，表示有 n 堆石子，n\le10^4。

第二行有 n 个数，表示每一堆石子的数量.

输出格式

共 T 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。

样例 #1

样例输入 #1

2
2
1 1
2
1 0

样例输出 #1

No
Yes

一道经典例题,代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int t,n,a,sum;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n;
        cin>>a;
        sum=a;
        for(int i=2;i<=n;i++){
            cin>>a;
            sum=sum^a;
        }
        if(sum==0){
            cout<<"No"<<endl; 
        }
        else{
            cout<<"Yes"<<endl;
        }
    }
}

公平组合游戏ICG

     若一个游戏满足：
     1.由两名玩家交替行动；
     2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
     3.不能行动的玩家判负；
     则称该游戏为公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分
     别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3.

有向图游戏

    给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向
    边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。任何一个公平组合游戏都可
    以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到
    达的下一个局面连有向边。

Mex运算

    设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
    mex(S)=min(x),x属于自然数，且x不属于S

SG函数

    在有向图游戏中，对于每个节点x,设从x出发共有k条有向边，分别到达节点y1,y2,...,yk.
    定义SG（x）为x的后继节点y1,y2,...,yk的SG函数值构成的集合再执行mex运算的结果，即：
    SG(x)=mex({SG(y1),SG(y2)...SG(yk)})