博弈论1：拿走游戏（take-away game）

假设你和小红打赌，玩“拿走游戏”，输的人请对方吃饭....

你们面前有21个筹码，放成一堆；每轮你或者小红可以从筹码堆中拿走1个/2个/3个；第一轮你先拿，第二轮小红拿，你们两个人交替进行;拿走筹码堆中最后的一个的人赢得游戏。

是不是摩拳擦掌可以开始玩啦？你拿了两个，小红拿了三个...作为观众的我开始记录你们每轮交替拿走后，筹码堆中剩余筹码的数量（黑色代表你拿走之后的筹码剩余数，红色则代表小红拿走之后的）：

19；16；15；12；11；8；6；4；2；0

omg,小红拿走了最后一个筹码（她拿完后剩余筹码数变成0）。小红完美获胜！

输了游戏的你得请吃饭了....（顺便请下我)bushi)

下次还玩吗？

我偷偷告诉你，这个游戏有“必胜策略”。

请带着耐心往下看。

（碎碎念：第一部分“无偏组合游戏”的定义会有些枯燥，如果只想看制胜策略的话，可以跳过第一部分，直接看第二部分）

目录

一、无偏组合游戏（impartial combinational games）

1.组合游戏特点：

2.无偏游戏特点

3.组合游戏定义

二、拿走游戏的“制胜策略” 

1.逆向推理（反向归纳法）（难推）

2.P&N positions解法（推荐）

---

一、无偏组合游戏（impartial combinational games）

拿走游戏属于一种无偏组合游戏，所以下面先介绍无偏组合游戏。

1.组合游戏特点：

设定如下：

• 两个玩家，I与II
• 完整信息(perfect information)
• 没有随机性（no chance move)
• 要么赢，要么输

比如开头的拿走游戏，就是你与小红两个玩家，你们都能看到场上的筹码和对方每轮的动作，你们一旦确定拿走几个筹码，就一定能拿走几个筹码；最后不可能平局，总会有个人拿走最后一个筹码，成为赢家，而另一个人成为输家。

2.无偏游戏特点

要求：

• 在每个位置，对于玩家I和玩家II的行动是同等的。也就是说，两个玩家的可选策略是相同的，且游戏的状态仅依赖于当前配置，而与玩家的身份无关。（比如上面提到的拿走游戏，不会因为你是小红还是小明，你是玩家I还是玩家II而影响策略）

有偏游戏则与无偏游戏的要求相反。（比如一些英雄游戏，你们的角色会影响你们的策略）

3.组合游戏定义

同时满足下列条件的游戏称作组合游戏：

• 两个玩家，I与II
• 一套通常有限的可能位置（positions）
• 游戏规则指定了两个玩家的合法行动；若规则对于两个玩家没有差别，则为无偏游戏，反之为有偏游戏。
• 玩家I和II交替行动
• 抵达其中一个位置时，游戏结束，同时下一个玩家无法行动。一般(normal)游戏规则是，最后一个完成行动的玩家获胜；misère(不幸）游戏规则相反，最后一个完成行动的玩家输掉游戏。
• 如果游戏永远不结束，陷入了平局(draw),必须要增加额外条件（也就是增加Ending Condition),来终结平局，评出胜负。
• 无论两个玩家怎么行动，最终游戏都能在有限步内结束

二、拿走游戏的“制胜策略” 

1.逆向推理（反向归纳法）（难推）

19；16；15；12；11；8；6；4；..

回顾最开始你与小红的游戏过程，其实小红把筹码拿到只剩4个的时候，你就能意识到无论如何自己都输了。如果自己拿走1个，那么还剩3个；拿走2个剩2个；拿走3个剩1个。而无论自己拿走多少，剩的1/2/3个小红都能一次性全部拿走，取得游戏胜利。

于是逆向推理一下，如果自己想要赢，需要走到“4”的位置，也就是拿完筹码还剩4个。

我们要想拿完筹码还剩4个，出发点就得是5/6/7(也就是小红拿完后剩余的筹码数量）。

为了让小红拿完后还剩5/6/7,小红开始拿的时候就还得剩8个.....

我们把拿完就必胜的位置定义成“P-positions”,可以发现P-positions有：4,8,12,16,20.也就是说，只要你拿完了还剩4个或8个或其他P位置，只要你按制胜策略继续走下去，就一定能赢。

2.P&N positions解法（推荐）

P位置，即positions that are winning for the Previous player (the player who just moved)，拿完走到这个位置的玩家获胜。

N位置，即 winning for the Next player to move，拿完之后走到这个位置，你的对手玩家（也就是下一轮行动的玩家）会获胜。

要想赢拿走游戏，我们只需要四个步骤：

 1）标记终点为P位置。（本游戏中，0为P位置）

2）有路径可以抵达P位置的标记为N位置。（1，2，3都可以抵达0，故1，2，3都为N）

3）只能到达N位置的标记为P位置。（4只能到达1，2，3，故4为P）

4）重复2）3）直至游戏中所有有限可达位置都被标记为P&N。

本游戏标记下来就是：

位置：0  1  2  3  4  5  6  7  8  9  10  11  12 13 14  15  16  17  18  19  20  21

P/N:    P N N  N  P N  N N  P  N  N   N    P N   N    N    P  N   N    N    P    N 

于是你可以总结规律（注意，不同游戏规则下这个规律不一样）：

P位置是4k;N位置是4k+1， 4k+2，4k+3.你需要努力走到4k的位置。

怎么证明你找到的规律是正确的？

1）证明终点是P点（即走到终点一定能获胜）

2）证明任何N点都能走到P点（对应4k+1， 4k+2，4k+3，我们拿走1/2/3个筹码一定能走到4k） 

3) 证明任何P点都只能走到N点（对于4k,走不到4k的位置，只能走到4k+1或4k+2或4k+3的N位置）

学会了吗~学会了拿14个筹码，每次只能拿走1/3/4个筹码试一试哟~