博弈问题简介

所讨论的博弈问题满足以下条件：

玩家只有两个人，轮流做出决策

游戏的状态集有限，保证游戏在有限步后结束，这样必然会产生不能操作者，其输

对任何一种局面，胜负只决定于局面本身，而与轮到哪位选手无关

一般称满足以上条件的游戏称为ICG，比如我们将要讨论的Nim游戏。作为一个对比，我们平时玩的象棋就不属于ICG，因为它不满足第三条。

ICG具有两个状态，我们称为必胜态和必败态，他们的关系：

后继状态能达到必败的状态为必胜态

所有后继状态都不为必败态，则其为必败态

第二条也可以换一种说法：后继状态都是必胜态，则其为必败态。所以我们可以看出一个状态不是必胜态，就是必败态。

只要是双方共用状态（合法的决策完全相同）的对弈游戏，其中一方肯定有必胜策略。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
这种分析方法有一种很形象的名字叫做Strategy-stealing，它的另一个经典例子是Chomp游戏。上面所举的例子都是双方共用状态的游戏（ICG游戏），因此至少有一方存在必胜策略。对于其它一些非ICG游戏，我们也可以用类似的方法证明后手不可能有必胜策略（但在这里并不能说明先手一定必胜）。比如对于井字棋游戏，假设后手有必胜策略，那先手就随便走一步，以后就装成是后手来应对。如果在哪一步需要先手在已经下过子的地方落子，他就再随便走一步就是了。这种证明方法成立的前提就是，多走一步肯定不是坏事。事实上，对于所有这种“多走一步肯定不是坏事”的且决策对称的游戏，我们都可以证明后手是没有必胜策略的。

取石子游戏NIM

取石子游戏是一个古老的博弈游戏，发源于中国，它是组合数学领域的一个经典问题。它有许多不同的玩法，基本上是两个玩家，玩的形式是轮流抓石子，胜利的标准是抓走了最后的石子。

玩家设定：先取石子的是玩家A，后取石子的是玩家B。

经典的三种玩法

一、巴什博奕(Bash Game)，有1堆含n个石子，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个。取走最后石子的人获胜。

二、尼姆博奕(Nimm Game)，有k堆不同数目石子，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限。取走最后石子的人获胜。

三、威佐夫博奕(Wythoff Game)，有2堆各不同数目个石子，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取1个，多者不限。取走最后石子的人获胜。POJ1067

平衡状态的概念：

引入一个概念，平衡状态，又称作奇异局势。当面对这个局势时则会失败。任意非平衡态经过一次操作可以变为平衡态。每个玩家都会努力使自己抓完石子之后的局势为平衡，将这个平衡局势留给对方。因此，玩家A能够在初始为非平衡的游戏中取胜，玩家B能够在初始为平衡的游戏中取胜。