博弈论初步

零.前言

​ 想到一些很棒的台词来着。

「白，我们总是在开始游戏前就获胜。」-空《游戏人生》

「世界如此单纯，没有赢不了的比试，努力的话怎么都有可能，世界单纯明了，胜利、失败、平局，那是愚蠢的小孩子所想过的事」-利库《游戏人生zero》

一.什么是博弈论

​ 简要来说，就是智商爆表的人尝试在游戏开始之前就结束这个游戏。并寻找到其方法（像我这种从五子棋到围棋，斗地主到英雄联盟一个都玩不好的是不是不该学这个啊），前提是这个游戏公平。

二.巴什博弈

​ 这种事最初的模型（连我都能会），给你n个石子，每次可以取 k 个（0<k<x)，交替行动，不能行动者判负，那么若\(x|n\),则先手必败，否则先手必胜。

​ 首先在没有平局的游戏里，我们要明白一个事实，非必胜，则必败。（见 零.前言），那么来看看在这个博弈中，我们是如何取胜的。策略只有一个。

跟着对方取，使得和为x

动动脑筋就知道为什么可行了哦。

三.尼姆博弈

​ 哎呀其实我也不太明白这个东西，乱写吧。有 n 堆石子，这次可以在任意一堆中随便取，交替行动，无法行动者判负。建立模型吧，首先假设个数分别为 \(a_1,a_2...a_n\) 如此。那么想像现在我输了，那么摆在我面前的是一个怎么样的死局？答：均为0。这里使用异或（别问我为什么用就对了），令\(k=a_1 xor \;a_2\;xor\;...a_n\),显然此时 k 为 0.

那么不止这一种情况会使得 k=0 ，则有推论，在一个 k=0的情况中，你已经输了。那么如何证明呢？首先 你的下一步一定会使得 k!=0

假设下一步 \(a_1\)处取走了 x，（a几都一样），则 \(k'=(a_1-x)xor\; a_2\;xor\;..a_n\; xor\;a_1\; xor \;a_1\)\(=(a_1-x)xor\;a_1!=1\)

那么又考虑到你的对手是一群魔鬼，并早已洞悉了推论，则他们会想方设法使你的上一步无效化，面临同样危险的局面，那么他们又会如何出手呢？

手上有一个k，从它的二进制可以看到一个最高位1，这个1存在的根源必定是某一个数\(a_i\),此时我们只要让\(a_i\)变换为\(a_i\;xor\;k\),就达到了目的

那么可否变换呢？答案是可以。因为消掉了一个最高位，所以变换之后会更小，符合规则。

四.SG函数

​ 它，是一个工具，是博弈论向前一大步的一个美妙的工具。首先定义一个函数 mex(S),为集合 S 中未出现的最小非负整数。然后给出\(SG(x)=mex(SG(y)),x->y\),那么这么定义有什么用呢？

• \(SG(终点)=0\)
• \(SG(x)=0\)，败

为什么这么设计能行我目前还没有想清楚，不过他是对的。且当操作随意(>1)时\(SG(x)=x\)

五.SG定理

​ 看到上面最后一句话的时候，可能有人会有一些想法。是否尼姆博弈可以看作使用SG函数来进行计算的呢？如此是否能探寻到一些规律性的东西？

​ 那么SG定理出现了，其表述为：一个游戏的SG值为其子游戏的SG异或和。

如此便能将大游戏化成小游戏来解决问题，至于合理性我还没想好。（将就看看吧）