【算法基础】博弈论入门：基础博弈论模型与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%(m1)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)}12颗石头SG(2)mex{SG(0),SG(1)}23颗石头SG(3)mex{SG(0),SG(1),SG(2)}34颗石头SG(4)mex{SG(1),SG(2),SG(3)}05颗石头SG(5)mex{SG(2),SG(3),SG(4)}16颗石头SG(6)mex{SG(3),SG(4),SG(5)}27颗石头SG(7)mex(SG(4),SG(5),SG(6))38颗石头SG(8)mex{SG(5),SG(6),SG(7)}0可以发现我们刚刚总结的规律n%(m1) 其实本质上还是 SG 值只是在 SG 值中找出了规律而已。到现在想必大家已经掌握了计算 SG 函数值来判断必胜必败态了。我们接下来可以看一个也比较经典的模型尼姆博弈Nim Game。洛谷题目链接P2197 【模板】Nim 游戏 - 洛谷看完这个题目其实可以发现这道题的主要让人无从下手的是它这次不止有一堆石头了而是 n 堆可我们只知道怎么分析一堆的局面类似巴什博弈 n 堆的状态简直太复杂了我们直接对整体石头进行计算 SG 值无法得出答案。所以我们首先要知道一个结论对于由 n 个互不关联的子博弈组成的整体博弈这 n 个子博弈的 SG 值的异或和即是整体博弈的 SG 值。由此判断整体的 SG 值即可而互不关联则是子博弈两两 SG 值互不影响。显而易见对于一堆石头的 SG 值肯定不会影响另一堆因为每次取石头只能在同一堆取所以在这题尼姆博弈中我们只需要计算单独每一堆石头的 SG 值再计算其异或和就能得到答案了。而单堆石头的 SG 值也很好算。假设石头有 n 颗由于是可以取任意颗石头所以可得SG(0)0SG(1)mex{SG(0)}1SG(2)mex{SG(0),SG(1)}2SG(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 lllong long; int t; int main() { ios::sync_with_stdio(false); cin.tie(0); cint; while(t--) { int n; cinn; int ans; cinans; for(int i2;in;i) { int t; cint; ansans^t;//计算异或和 } //判断总博弈的SG值 if(ans) coutYes\n; else coutNo\n; } }所以了解了 SG 值我们就有办法去具体有思路地分析博弈论题目而不是每次无头苍蝇一般随意分析各种情况最后搞得晕头转向。希望大家通过本文能基本入门博弈论懂得利用 SG 函数来分析。