博弈论拓展式解题（高深的博弈论不）

本篇文章，将讨论动态博弈里一类有趣的游戏策略——必胜/败策略。

首先，动态博弈是指参与人的行动有先后顺序，而且行动在后者可以观察到行动在先者的选择，并据此作出相应的选择。

典型的例子是下棋（如象棋、围棋、跳棋等）。下棋有两个博弈参与者，一人一步，游戏规则和每一步的信息都是完全公开的，且无任何运气成分，游戏的所有可能局面有限且游戏规则已决定游戏会在有限步内结束。然后，策梅洛定理（Zermelo's theorem）告诉我们：这类游戏先行或后行方当中必有一方有必胜或必不败的策略。

下面简单证明策梅洛定理。为方便计，对游戏的所有可能状态（是指游戏进行到某一步时的局面，包括下一步轮到谁）染色，如果某一状态已经判定先手胜则该状态染黑，同理先手负则该状态染白。

如果某一状态是先手方行动且它的所有后继状态（即下一步的状态）都是白色，则这一状态染白。——你的回合但当你所有可能的下一步都会走到必败情形时，你已经输了。

如果某一状态是先手方行动且存在它的某一个后继状态是黑色，则这一状态染黑。——你的回合且当你有一种方法能走到必胜情形时，你已经赢了。

如果是后手方行动，同上。

此局先手（红）下一步无论怎么走，后继状态都是白色（输）

当以上染色结束后，考虑哪些未被染色的状态。如果该状态是先手方行动，根据以上染色规则，因为该状态胜负未分，必存在后继状态，且不能有一个黑色，且不能都是白色。所以它的所有后继状态中必存在一个未染色的状态。先手为了不输，故会选择从一个未染色状态转移到另一个未染色状态。对于后手同理。

所以，初始状态要么染黑要么染白，若未染色，则先后手都会选择从一个未染色状态转移到另一个未染色状态，从而在未染色状态之间循环直到有限步内结束。

总结一下：

1. 没有平局，每个游戏局面要么是必胜态，要么是必败态；

2. 一个状态是必败态，当且仅当它的所有后继状态都是必胜态；

3. 一个状态是必胜态，当且仅当它的后继状态存在一个必败态。

必胜策略的核心本质是：理清必胜态和必败态，并构造必胜态与必败态之间的状态转移。

下面选取一些著名游戏的例子来说明如何构建必胜/败策略。为了方便，去掉可能出现平局的游戏。

Bash Game

有n枚棋子甲乙轮流拿，每次只能拿1~m枚，谁拿到最后一枚棋子算胜。若甲先拿，问：谁有必胜策略？

当1≤n≤m时，甲（先手）必胜；

当n=m 1时，甲（先手）不管拿几枚，乙（后手）都可以在下一次全拿完，即甲行动的所有后继状态都是乙必胜，所以甲（先手）必败；

当n=m 2时，甲（先手）只要拿1枚后，就可以让乙先手并面临n=m 1的情形，即甲行动的某一个后继状态都是乙必败，所以甲（先手）必胜；

当m 2≤n≤2m 1时，甲（先手）只要拿n-m-1枚后，都可以让乙先手并面临n=m 1的情形，所以甲（先手）必胜……

递推规律已经很明显了，当(m 1)|n时，乙（后手）必胜；否则甲（先手）必胜。

如果把问题改为“谁拿到最后一枚棋子算输”，其他均不变。同样分析不难得到当(m 1)|(n-1)时，乙（后手）必胜；否则甲（先手）必胜。

该问题很常见，也可以用“取余制胜法”解决，但理清必胜态与必败态之间的状态转移能更直达本质，且能分析更广泛的问题，比如下一个问题。

有n枚棋子甲乙轮流拿，每次只能拿1枚、3枚、4枚或者5枚，谁拿到最后一枚棋子算胜．若甲先拿，问：谁有必胜策略？

因为不能拿2枚，常用的方法失效了，故我们继续考虑状态转移。

当n=1,3,4,5时，甲（先手）必胜；当n=2时，甲（先手）必败；

当n=6时，甲（先手）只要拿4枚后，就可以让乙先手并面临n=2的情形，所以甲（先手）必胜；

当n=7时，甲（先手）只要拿对应的5枚后，同上，所以甲（先手）必胜；

当n=8时，甲（先手）不管是拿1,3,4,5枚后，乙先手面临剩下的7,5,4,3枚，都是先手必胜，即甲行动的所有后继状态都是乙必胜，所以甲（先手）必败；

当n=9时，甲（先手）只要拿1枚后，乙先手并面临n=8的情形，所以甲（先手）必胜；

当n=10时，甲（先手）不管是拿1,3,4,5枚后，乙先手面临剩下的9.,7,6,5枚，都是先手必胜，即甲行动的所有后继状态都是乙必胜，所以甲（先手）必败……

递推规律还不太明显，大家可以自己再多写几个看看规律，最后的结论是，当8|n或8|(n-2)时，乙（后手）必胜；否则甲（先手）必胜。

如果把问题改为“谁拿到最后一枚棋子算输”，其他均不变。同样分析不难得到当8|(n-1)或8|(n-3)时，乙（后手）必胜；否则甲（先手）必胜。

该问题无法用“取余制胜法”解决，但仍可以用状态转移解决，而下一个动态取子问题则更能说明状态转移这种研究方法的适用广泛性。

有n枚棋子甲乙轮流拿，每次拿的不能超过现有棋子数的一半。谁没有办法拿谁就算输。若甲先拿，问：谁有必胜策略？

当n=1时，甲不能拿超过0.5枚，甲（先手）必败；

当n=2时，甲可以拿1枚，则甲（先手）必胜；

当n=3时，甲只能拿1枚，乙先手并面临n=2的情形，所以甲（先手）必败；

当n=4,5,6时，甲只要对应拿1,2,3枚后，乙先手并面临n=3的情形，所以甲（先手）必胜；

当n=7时，甲不管是拿1,2,3枚后，乙先手并面临n=6,5,4的情形，所以甲（先手）必败；

当n=8时，甲可以拿1枚，乙先手并面临n=7的情形，所以甲（先手）必胜……

递推规律仍不太明显，大家可以自己再多写几个看看规律，最后的结论是，当n=2^k-1(k∈N )时，乙（后手）必胜；否则甲（先手）必胜。

下一个问题将更加复杂。

甲乙二人进行如下游戏：在桌子上放着一堆石子，二人轮流执步，甲先行，执步者每步必须将每堆颗数多余1颗的石子都分成两个较小的堆。

若谁在执步后能使得每堆石子都仅有1颗谁就获胜．若开始时有n(n≥2)枚棋子，对每种情况讨论甲乙的胜负情况。

为方便叙述，以下的必胜态和必败态只针对于先手。

枚举发现2枚必胜，3枚必败。

4可分成1、3，后继3枚是必败态，则4枚必胜。

5可分成2、3，因为每个堆数大于1的堆都要分，所以后继只能分成1、1、1、2（不考虑次序，下同），这个状态是必胜态，所以2、3是必败态，则5枚必胜。

6可分成3、3，后继只能分成1、2、1、2，这个状态是必胜态，所以3、3是必败态，则6枚必胜。

7有3种分法：

若分成1、6，后继6枚是必胜态，则该分法7枚败；

若分成2、5，后继为1、1、2、3时是必败态，所以2、5是必胜态，则该分法7枚败；

若分成3、4，后继为1、2、1、3时是必败态，所以3、4是必胜态，则该分法7枚败。

综上，7枚必败。

8可分成1、7，后继7枚是必败态，则8枚必胜……

于是发现两点：

1、2^k-1(k≥2) 为必败态，其余情况均为必胜态；

2、只需要考虑每个状态中最多棋子个数。

记每个状态中最多棋子个数为该状态名。

思考状态转移：因为2^k-1(k≥2)状态为必败态，所以考虑一个必败态2^k-1→必胜态→必败态2^(k-1)-1的转移回合。

该过程分为两步，第一步是必败态的后继，需要考虑所有分法，第二步是必胜态的后继，只需考虑存在一种分法。即对于2^k-1状态的任何一种分法，后继总存在一种分法使得分后为2^(k-1)-1状态。

首先因为每堆都会被分，所以其实除了最大的堆，其余小堆怎么分对后续的过程往往没有影响。因为每次分割，所有不为1的堆数都会减小，不妨设最大堆的A的堆数为x，其余某个小堆B堆数为y 。

第一步无论怎么分，A堆分后的较大堆的堆数不少于(x 1)/2， 堆分后的较大堆的堆数不超过y-1；第二步存在一种分法：把 堆分后的较大堆分成两堆，其中保证一堆的堆数不少于(x-1)/2，如果能继续分的话，把堆分后的两部分各自分成两堆，其中保证分后的两堆的堆数均不超过y/2。

因为y<x，所以(y/2)≤(x-1)/2

即B堆分两次后的所有堆的堆数，均不大于A堆分两次后的最大堆的堆数。

所以一回合后，一定有方法保证小堆分完后的最大堆也不超过最大堆分完后的最大堆。

结论：只需要考虑每次分完后最大堆的棋子数。

对于2^k-1的状态，先手不论怎么分，最大堆在分割后的最大堆一定在2^(k-1)~2^k-2之间，记为m，则下一个人面对最大为m的状态，可以将其分为

两堆。

于是先手再次拿到2^(k-1)-1的状态，以此循环．所以此为一个必败态→必胜态→必败态的转移。

直到k=3时，此时2^(3-1)-1=3，必败态

综上，当

时，乙（后手）必胜；否则甲（先手）必胜。

可见，在没有规则补偿的情况下，此类游戏（大多数），先手具有先发优势。

---

转载内容仅代表作者观点

不代表中科院物理所立场

来源：新东方智慧学堂

编辑：荔枝果冻

,