简单的博弈总结

2022-04-27

如题目＞▽＜

巴什（巴适）博弈

特征

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

结论

1 2	// 等于零先手负，大于0先手胜 int res = n % (m + 1);

尼姆博弈

特征

有n堆若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，最多不限，最先取完着胜。

结论

// 所有堆的物品的数量异或起来是0，先手必败。
int n;
cin >> n;
int res = 0;// 结果为零先手输
forn (i, 0, n) {
    int x;
    cin >> x;
    res ^= x;
}

SG函数

q有向图游戏

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

定理

(1)有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
(2)有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

有向图游戏的和

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和（因此我们可以把nim博弈和bash博弈杂交一起）

时间复杂度

最多100堆石子，记忆化搜索每个状态计算一次，一个状态最多k个后继状态，sg计算次数最多为1e4次，所以总时间复杂度不超过1e6,O(mk)，m为每堆的石子个数

int s[1100], sg[MAX];// s为每堆可以去的石子数， sg[i]为第i堆游戏的结果
int k;// 可以取得石子数
int SG(int x)  //用记忆化搜索来求SG值
{
    if (sg[x] != -1)  //保证每个状态只会被算一次，避免了时间复杂度为指数级别
        return sg[x];
    //用一个哈希表来存当前局面所能到达的局面
    set<int> st;
    for (int i = 0; i < k; i++)  //遍历可以取的石子数
    {
        if (x >= s[i])
            st.insert(SG(x - s[i]));  //把这个状态加进去并且求这个状态的SG值
    }
    //找到当前最小的自然数
    for (int i = 0;; i++)
        if (st.count(i) == 0)  //当前状态中没有i，所以最小的自然数就是它了
            return sg[x] = i;
}
int main() {
    memset(sg, -1, sizeof(sg));  //不需要多次初始化sg，因为x值相等对应的SG值是一定的
    int ans = 0;
    for(int i=0;i<n;i++)// n堆
    {
        int x;
        cin>>x;
        ans^=SG(x);
    }
    if(ans)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}