博弈论入门
Trexmao
·
·
个人记录
0 序
我预判了你的预判。
——鲁迅
我没说过这句话。
——鲁迅
博弈论？很有意思，很有意思。在小时候，吹牛的时候经常要说的一个词语居然就要被我学了吗？感到时光流逝的很快。
开始吧。
1 引入：你喜欢玩游戏？
你肯定听说过这个：
地上有n个石子，两人对弈，每次每人取石子若干。取走最后一颗者胜出。
就算你没玩过，你也肯定在题目里见过。那么，我们今天就研究这个游戏。
2 先来讲一个东西：SG函数
先定义一下必胜态和必败态。
必胜态就是当前这个状态先手无论怎么操作都会赢，必败态则反之。在没有随即条件（色子？硬币？）时且先手和后手都很聪明，那么不存在必胜态和必败态之间的状态。
如果一个游戏有最优策略，则从必败态走到的每一个状态都是必胜态，从必胜态走到的每一个状态都是必败态，无法操作的状态为必败态。
当$SG$函数值为$0$时，当前状态必败；若$SG$函数值$>0$，则当前状态必胜。
# 3 最简单取石子游戏
### 1 简单的大脑分析
题目同上所述，且已知每次最多取$m$个，不能不取，求必胜策略。
我们看，啊，不会啊！
怎么办呢？我们只好用最简单的方案欺骗一下自己。
唔……嗯！我们让$n=m+1$，这个时候先取者必输！
答案出来了，我们自己都开始嘲笑自己，这都要说出来吗？都中学生了，不丢人？我们又进入了思考。
嗯……哦！好像有点头绪！如果我们让剩下的石头对手一次拿不完，两次就能拿完，那么不就可以让对方输了吗？
那么，我们按着这个想法下去，就可以推导出：
当你第一次先手时，马上将剩下的石子个数变为$m+1$的倍数，然后每回合中，如果对手拿了$a$个，那么你就拿$m+1-a$个，那么，你必然会赢。
但是
1. 要求$n≥m+1$，不然就没什么好玩的了。
2. $n$也不能是$k(m+1)\;\;\;\;(k∈N)$！不然，先手就必输了。
注意！当游戏满足上面两条要求并且你和你的对手都知道最优策略时，先手会赢！你可以自己和自己试一下，就知道了。
### 2 简单的数学分析：$SG$函数
我们来分析一下：这个游戏的$SG$函数是什么呢？
我们如果要想赢，那么就不能让现在石子的颗数为$km\;\;(k∈N)$（这个可以从必胜策略里面看出）。
那么，如果$n\;mod\;m=0$,那么先手处于必败态，否则处于必胜态。
因此，我们的$SG$函数就是$n\;mod\;m$。
# 4 $Nim$取石子游戏
> 有$k$堆各$n$个石子，两人轮流从某一堆取石子，每次至少一个，无上限，同一次不能同时取多堆的石头。取走最后一个石子的人获胜，求最优策略。
### 1 该游戏的$SG$函数是什么？
我们现在想证明的是：存在这个最优策略。
设现在第$i$堆中有$a_i$个石子。现在的$SG$函数的值$C=a_1\; xor\; a_2\; xor\; a_3......xor\; a_n$。关于这个函数的证明，请看下面。
### 2 讲另一个东西：$xor$函数
$xor$函数的美妙之处在于：它的逆函数就是它本身。
即在
$$a\;xor\;b=c$$
时，有
$$b\;xor\;c=a$$
和
$$a\;xor\;c=b$$
### 3 言归正传
假设现在状态的$SG$函数和它的后一个状态的$SG$函数相等（那就相当于假设该游戏没有必胜策略），且现在你想要在第$m$堆中取出$x$个石子，那么我们重新定义一个$C'=C\;xor\;a_m$，则
$$C'=a\;xor\;a_1\;xor\;a_2\;......xor\;a_{m-1}\;xor\;a_{m+1}\;xor\;......\;xor\;a_n$$
亦成立。
因为当前状态的$SG$函数和之前状态的$SG$函数相等，且$xor$是自身的逆函数，那么有
$$s\;xor\;a_m=s\;xor(a_m-x)=k$$
，则有
$$a_m=a_m-x$$
，即
$$x=0$$
。因此无法取走棋子，与游戏本身矛盾，因此假设不成立，该游戏有必胜策略。
### 4 必胜策略是什么？
但是你玩的时候，肯定想要赢对不对？因此我们来研究一下必胜策略：
通过上面的证明可以看出，如果一个状态是必败态，那么它的任意一个后继状态都是必胜态。我们的必胜策略就是找出一个方案，使得任何一个必胜态按此方案转化后都是必败态。
考虑一个必胜态的$SG$函数值$s$的二进制形式。因为它不是$0$，那么必然有一个最高位的$1$。又通过$xor$函数的计算规则，可以看出必然有一堆石子数目的二进制形式这一位是$1$。假设是第$k$堆，有$x$个石子。
再假设有一个数$x'=x\;xor\;s$,那么如果用$x'$代替$x$作为第$k$堆的石子数量，则新状态的$SG$函数值
$$s'=a_1\;xor\;a_2\;xor\;......\;xor\;a_{k-1}\;xor\;x'\;xor\;a_{k+1}\;xor\;......\;xor\;a_n$$
则有
$$s'=a_1\;xor\;a_2.....\;xor\;a_{k-1}\;xor\;x\;xor\;s\;xor\;a_{k+1}\;xor\;......\;xor\;a_n$$
又$\because x=a_k \therefore
s'=a_1\;xor\;a_2\;xor\;a_3......a_n\;xor\;s
成立，又\because有
s=a_1\;xor\;a_2\;xor\;a_3\;xor\;......\;xor\;a_n
\therefore
s'=s\;xor\;s=0
因此新状态必然为必败态。
又因为xor的运算法则，所以x'<x，满足游戏要求。
即必胜策略为在第k堆中拿走x-x'个石子。完结撒花泪目。
实验证明，这个最优策略确实可行，即使SG函数是错的，它也成立。
那么，SG函数为什么是对的呢？
5 对于SG函数的证明
回到SG函数的定义：
当SG函数值为0时，当前状态必败，否则必胜。
在这个SG函数中，要使函数值等于零，就让每堆石子数目的二进制形式的每一位上都有偶数个1。
如果实现了这一条件，那么现手的最优策略就是不取。而这又违反了游戏规则。如果取的话，则对手就处于必胜态。
所以可以看出，当该SG函数为0时，现手处于必败态，否则处于必胜态。因此，这个SG函数符合题意。
6 真題の挑戰
现在有5堆石子，数量分别为3,5,7,19,50,甲乙轮流从任一堆中任取（每次只能取自一堆，不能不取），取走最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎么取，只要甲不失误，都能取胜）？如果有，甲第一步应该在哪一堆中取多少？请写出你的结果:____ （2006年普及组问题求解）
看到这道题，我们就可以马上开始计算：
第二问的话，我们看看$32$的二进制形式中，第六位是$1$，和第五堆$50$的最高位相同，那么我们就让第五堆中剩下$32\;xor\;50=18$个石子，那么就是从第五位中拿走$32$个石子就好了。
# 5 休息一下：非考试内容
## 1 开炮问题
这个题目来自于一本挺好的数学书：《Do you feel lucky?》(中文：寻找你的幸运星：概率的秘密）
> 有三个人，分别叫做俄甘姆、格里塞尔达、汉贾。这三个人是原始人，一天到晚吵架。终于有一天，他们忍受不了彼此了，约定在一个平坦的无人的地方用火炮干一架（原始人哪来的火炮我也不知道）。已知俄甘姆几乎百发百中（命中率$99\%$），格里塞尔达能中一半（命中率$50\%$），汉贾几乎怎么都打不中（命中率$1\%$）。为了公平，汉贾先开炮，格里塞尔达次之，俄甘姆最后。求汉贾的最优策略。
这个题目需要你去好好思考。首先说答案：汉贾应该对天开炮。
惊不惊喜？意不意外？想不想知道为什么？
原因就是~~他有很大的机会打不中天空就会打中人~~如果他射的是其他两个人就会陷入危险之中。
如果他去射格里塞尔达，他在格里塞尔达眼中就会更加危险，于是格里塞尔达会来射他。俄甘姆则有很大几率补刀。
如果他去射俄甘姆，格里塞尔达虽然会射俄甘姆，但是你自己想一想，无论俄甘姆有没有死，他都会陷入危险之中。
看懂了吧，这就是博弈论的博大精深。
## 2 真正的博弈论带师：押题之路
### 1 谁？是谁？
无论你采取怎样的策略，你都无法在与€€￡出题人的心理博弈中取胜。
无论你怎么押题，怎么学习，都无法猜中出题人要考什么。这才是真正的大师。
### 2 一些（不适用于信息的）押题技巧
~~益 街 坊~~
1. 你记录一下老师上课讲某个知识点的时间，时间最长的基本上是重点。
2. 书本上根本没有的概念，公式，定义什么的肯定不会是重点。
3. 根据墨菲定律，你不会的基本都是重点。
4. 一些很偏僻又没什么用的常数肯定不要你默写。
5. 书本上用个小框框框起来的要么是重中之重，要么根本没人会考。
6. 剩下的都靠你了。
# 6 鸣谢&后记
学了博弈论以后，**不要**随便和人约架，人家未必按规则来。
参考文献：《信息学奥赛一本通初赛版》、《信息学奥赛金牌导航（初赛篇）》、《Do you feel lucky?》。
感谢我的弟弟不厌其烦地听我解释游戏规则并陪我玩取石子游戏，我发现规律后陪着我让我赢了$20$多盘。~~（为了我弟弟点个赞再走嘛~~