【算法基础】博弈论入门：基础博弈论模型与SG函数基础详解（洛谷 P2197 C++代码）
博弈论是算法竞赛里一个很重要的考点。但如果没有具体了解过解决博弈论的工具和方法，面对此类问题还是会很容易束手无策。
下面我们先可以看一道具体的题目：有一堆石头数量为 8 ，双方每次都可以拿取最多 3 颗石头，至少要拿一个石头，当一个人无法再拿石头的时候则输。假设双方都会做出最优选择，其中一方先手，他最后是会输还是赢？
我们稍作尝试就能很容易发现解法。我们首先要承认一点的是，如果双方都会做最优选择，那任何一种状态都会是先手必胜或者先手必败其中一种，则有如下推理。
显然如果石头数量为 1,2,3 这种情况下先手必胜；如果数量为 4 ，我们取 1 则剩 3，取 2 则剩 2 ，取 3 则剩 1 ，此时到对方他必定全部取走石头，那我们先手必败；如果数量为 5 ，我们取 1 剩下 4，取 2 剩下 3 ，取 3 剩下 2 ，但我们会做出最优选择，取 2 和 3 对方都会全部拿走那我们就输了，而取 1 剩下 4 ，那又回到数量为 4 的状态了，我们刚刚已经知道状态为 4 则必输，所以我们当然会直接取 1 让对方输，此时先手必胜。以此类推到数量为 8 ，很好发现每个数量的石头状态规律如下。以 N 代表先手必胜（必胜态），以 P 代表先手必败（必败态）。
其实很好发现规律，如果石头数量为 n ，每次最多可以拿 m 个石头，则n%(m+1)=0 时是必败态，反之为必胜态。这就是最简单基础的博弈论模型：巴什博弈（Bash Game）。
但是，现实情况题目往往不会给我们这么简单的博弈模型，会更加复杂难懂。我们如果每次都推导每一种情况的必胜态必败态，不仅麻烦几乎做不到，而且大部分情况我们无法总结出来一个类似巴什博弈一样的公式规律。所以，我们需要一个专门解决博弈论问题的工具：SG函数。
在说明SG函数之前，我们还需要了解 mex 计算。mex 计算的大致定义就是对于数字 $A_1$,$A_2$, ... ,$A_n$ ，mex{$A_1$,$A_2$, ... ,$A_n$} 的值就是这些数字里没有出现的最小非负整数。比如 mex{1,3,4}=0 ，mex{0,1,3,5}=2 ，mex{0,2,3,4}=1。
而SG函数值的定义是：对于当前情况 A 的 SG 值为 SG(A) ，且通过操作可以去到情况 $A_1$,$A_2$, ... ,$A_n$ ，则 SG(A)=mex{SG($A_1$),SG($A_2$), ... ,SG($A_n$)}。最重要的一点是，经过验证，SG函数值是与必胜态和必败态相关的：对应当前情况 A ，如果 SG(A)=0 ，则 A 此时为必败态，反之则是必胜态。证明过程比较抽象且繁琐，所以我们只用记住结论，懂得利用SG函数来推导博弈必败必胜态即可。
SG函数的计算很可能一时间难以理解，下面我通过对刚刚的巴什博弈的简单计算SG 值来让大家熟悉这个计算过程。
首先，可以肯定的是 SG(0)=0 ，即对于 0 颗石头，先手就拿不了了则必败，为必败态。随后如下：
1颗石头：SG(1)=mex{SG(0)}=1
2颗石头：SG(2)=mex{SG(0),SG(1)}=2
3颗石头：SG(3)=mex{SG(0),SG(1),SG(2)}=3
4颗石头：SG(4)=mex{SG(1),SG(2),SG(3)}=0
5颗石头：SG(5)=mex{SG(2),SG(3),SG(4)}=1
6颗石头：SG(6)=mex{SG(3),SG(4),SG(5)}=2
7颗石头：SG(7)=mex(SG(4),SG(5),SG(6))=3
8颗石头：SG(8)=mex{SG(5),SG(6),SG(7)}=0
可以发现，我们刚刚总结的规律n%(m+1) 其实本质上还是 SG 值，只是在 SG 值中找出了规律而已。
到现在，想必大家已经掌握了计算 SG 函数值来判断必胜必败态了。我们接下来可以看一个也比较经典的模型：尼姆博弈（Nim Game）。洛谷题目链接：P2197 【模板】Nim 游戏 - 洛谷
看完这个题目其实可以发现，这道题的主要让人无从下手的是它这次不止有一堆石头了，而是 n 堆，可我们只知道怎么分析一堆的局面（类似巴什博弈）， n 堆的状态简直太复杂了，我们直接对整体石头进行计算 SG 值无法得出答案。
所以，我们首先要知道一个结论：对于由 n 个互不关联的子博弈组成的整体博弈，这 n 个子博弈的 SG 值的异或和即是整体博弈的 SG 值。由此判断整体的 SG 值即可，而互不关联，则是子博弈两两 SG 值互不影响。显而易见，对于一堆石头的 SG 值，肯定不会影响另一堆，因为每次取石头只能在同一堆取，所以在这题尼姆博弈中，我们只需要计算单独每一堆石头的 SG 值，再计算其异或和，就能得到答案了。
而单堆石头的 SG 值也很好算。假设石头有 n 颗，由于是可以取任意颗石头，所以可得
SG(0)=0
SG(1)=mex{SG(0)}=1
SG(2)=mex{SG(0),SG(1)}=2
SG(3)=mex{SG(0),SG(1),SG(2)}=3
······
SG(n)=mex(SG(0),SG(1),SG(2),...,SG(n-1))=n
最终能发现，每堆石头的 SG 值其实就是它本身石头数量。知道了 SG 值，我们再进行异或和，就能得到总博弈的 SG 值，可以判断是否能必胜了。具体代码很简单。
#include <bits/stdc++.h> using namespace std; using ll=long long; int t; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>t; while(t--) { int n; cin>>n; int ans; cin>>ans; for(int i=2;i<=n;++i) { int t; cin>>t; ans=ans^t;//计算异或和 } //判断总博弈的SG值 if(ans) cout<<"Yes\n"; else cout<<"No\n"; } }所以，了解了 SG 值，我们就有办法去具体有思路地分析博弈论题目，而不是每次无头苍蝇一般随意分析各种情况，最后搞得晕头转向。希望大家通过本文能基本入门博弈论，懂得利用 SG 函数来分析。