本篇文章，将讨論動态博弈裡一類有趣的遊戲策略——必勝/敗策略。

首先，動态博弈是指參與人的行動有先後順序，而且行動在後者可以觀察到行動在先者的選擇，并據此作出相應的選擇。

典型的例子是下棋（如象棋、圍棋、跳棋等）。下棋有兩個博弈參與者，一人一步，遊戲規則和每一步的信息都是完全公開的，且無任何運氣成分，遊戲的所有可能局面有限且遊戲規則已決定遊戲會在有限步内結束。然後，策梅洛定理（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，必敗态

綜上，當

時，乙（後手）必勝；否則甲（先手）必勝。

可見，在沒有規則補償的情況下，此類遊戲（大多數），先手具有先發優勢。

轉載内容僅代表作者觀點

不代表中科院物理所立場

來源：新東方智慧學堂

編輯：荔枝果凍

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!