博弈论入门——Nim游戏引入

说实话,我真的对这个游戏看得是一脸懵逼,因为(我太弱了)我没有明白一些变量的意思,所以一直很懵,现在才明白,这让我明白博弈论(还可以骗钱)博大精深;

以下是我自己思考的过程,也许不严谨,但是最终明白了.

这里只是粗略地介绍Nim游戏,一个入门博客,以来更好地进入SG函数(因为我才刚学

游戏简介

　　背景故事我就不说了,直接介绍游戏规则.

　　有n堆物品,每堆有$a_{i}$个物品,两个玩家每次可以任选一堆挑出任意整数个物品(可以整堆取完),但不能不取,取走最后一个物品的为胜者.

　　这个游戏历史久远,曾用来赌钱,但是被一位数学家用二进制求解,得到了先手必胜和先手必败理论,于是这个游戏也就GG了;

游戏套路

　　假如有3堆物品,它们的个数分别是6,4,2,那么两个玩家都选择最优策略,那么先手胜还是后手胜? (例题(竟然还蓝了))

　　答案是后手胜.(这个可以自己推一下)

　　这里引入一个概念:有向图游戏;

　　有向图游戏

　　　　我们定义一个游戏的初始状态为起点,向所能到达的所有状态连边,通过不断向下延展,得到必胜点(就是到这个点是胜利的情况)和必败点(这其实是我自己的理解)

　　考虑将${6,4,2}$这个集合作为起点,然后向所有状态连边;但是显然状态太多,我们无法完全枚举;

　　考虑终点,必然是${0,0,0}$,此时集合的异或和显然是0.

　　那么我们定义每一堆剩余的个数为$A_{i}$,我们通过推论可以得到:初始状态集合异或和为0时必败,反之必胜.

　　为什么会得到这个结论?

游戏思考

　　考虑将开始时集合中的数换成二进制,即${110,100,010}$,最后状态也换成二进制,我就不再写出来了.

　　我们倒着推,最终解异或和为0,那么必然是从异或和非0的状态转移过来的.

　　证明

　　　　如果$A_{1} Xor A_{2} Xor A_{3} ...Xor A_{i}... Xor  A_{n}=0$,那么其中$A_{i}$是从$A_{i}^{‘}$转移过来的,假设$A_{1} Xor A_{2} Xor A_{3} ...Xor A_{i}^{‘}... Xor  A_{n}=0$,

　　　　根据异或运算得到,$A_{i}=A_{i}^{‘}$,根据游戏规则,每个玩家必然至少要取1个物品,与规则矛盾,假设不成立,结论成立.

　　所以考虑采取这样一个策略,如果我们开始时异或和不为0,那么我们策略是轮到对手时,让他得到$A_{1} Xor A_{2} Xor A_{3} ...Xor A_{i}... Xor  A_{n}=0$.

　　那么必败节点必定到对方手中,我们需要证明一下我们一定能实现这个策略

　　证明

　　　　假设此时集合异或和为x,此时最大数为$A_{i}$,那么我们可以让$A_{i}$变成$A_{i} Xor x$,这样异或和就又为0了.

　　　　显然,$A_{i} > A_{i} Xor x$,所以我们可以让$A_{i}$变成$A{i}Xor即可,那么一定可以实现这个策略.

　　但是如果我们开始时异或和为0,对方也可以反过来利用这个策略,让我们陷入必败场面.

　　结论再次强调一遍:初始状态集合异或和为0时必败,反之必胜.

　　(以上证明单纯自己类似口述,没有按照严格的证明格式,请多谅解)

游戏反思

　　我们学习的是思维方式,而不单单是结论,所以我们反思一下我们做了什么

　　1.首先分析了模型,概括出每种情况的集合,构造了一个有向图游戏;

　　2.我们思考了每个点的转移方式.并分析了必败点的特点,发现一些特别的转移情况.

　　3.我们更加深入的思考了转移情景,并证明了策略的正确性.

　　4.算法实现(这里没有摆出);

　　根据这个思路,也许会对以后有帮助,SG函数和Mex运算将会在之后讲到(博主还在努力的学T_T)

原文：https://www.cnblogs.com/waterflower/p/11366144.html