博弈论笔记
博弈论笔记
巴什博弈
Nim游戏
威佐夫博弈
今天讲了三种博弈题型，今天困，老师又说不清楚，听的云里雾里的。
博弈最重要的是局面，局面确定了，输赢也就确定了。
在推导过程中，要标出
必败点一定会输的点
必胜点可以到达必败点的点
由此找规律
巴什博弈
有n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m个。最后取光者得胜。
假设n = m + 1，那么无论如何取，先取者必输。因为先取者无论取多少，后者一次性便可将剩余取完。
胜利法则：若n%（m+1)不等于0，则先手必胜
Nim游戏
有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
Nim游戏是博弈论中比较重要的的，因为很多问题都可以转化成它。有个很重要的结论就是
若A(1) xor A(2) xor … xor A(n)==0 那么必输，否则必胜。
老师上课没讲证明，弄得我一头雾水。。
简易证明如下：
出处：https://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html
今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
设S态为A(1) xor A(2) xor … xor A(n)!=0
T态为A(1) xor A(2) xor … xor A(n)=0
[定理1]：对于任何一个S态，总能从一堆火柴中取出若干个使之成为T态。
证明：
若有n堆火柴，每堆火柴有A(i)根火柴数，那么既然现在处于S态，
c = A(1) xor A(2) xor … xor A(n) > 0;
把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，这与c的第p位就也为0矛盾）。
那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).讲x替换A(t)
A(1) xor A(2) xor … xor x xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n)
= 0
这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。证毕
[定理2]：T态，取任何一堆的若干根，都将成为S态。
证明：用反证法试试。
若
c = A(1) xor A(2) xor … xor A(i) xor … xor A(n) = 0；
c’ = A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = 0;
则有
c xor c’ = A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = A(i) xor A(i’) =0
进而推出A(i) = A(i’)，这与已知矛盾。所以命题得证。
[定理 3]：S态，只要方法正确，必赢。
最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理1，可以把它变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己方控制，对方只能被动地实现由T态转变为S态。故S态必赢。
[定理4]：T态，只要对方法正确，必败。
由定理3易得。
看了半天才有点明白。还有一道拓展，取最后一根火柴的人输。原文里有很严密的分析过程和两道题的对比。并没有完全看懂。
老师找的例题是 高僧斗法
威佐夫博弈
凡是正儿八经的玩意儿都得有个奇奇怪怪的名字。这东西今天让我想了半天。
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这个最大的不同就在于可以两堆同时取。考虑的时候要打表。
首先考虑两堆中有一堆是1的情况，找出必败点。 经过寻找，得出只有1，2时必败
再找有一堆是2的时候，发现无论是多少，只要拿走一些，到达1，2即可，所以必败点1，2
再找有一堆是3的时候，3，4可以分别拿走一个变成1，2.所以必败点3，5 即 3，3+2
再找4： 4，5可以到达1，2；4，6可以到达3，5；必败点4，4+3
再找5 ： 5已经有必败点了，所以跳过
然后6：6，6+4
7：7，4
.……
打表，用大数除以小数，在数据大的时候，比值就是黄金分割的倒数！
黄金分割是个神奇的东西，看起来毫不相关的东西居然有它的身影。pi，e，42……这些数字里有宇宙的奥义，藏着上帝的秘密。
谢谢惠读，笔者水平不入门，还需学习，望多指点