為什麼說多數棋類遊戲先手有必勝/必不敗策略？

如果一個博弈（遊戲）滿足如下條件，那麼先手和後手其中至少一方有必不敗或者必勝策略：

2.遊戲必然在有限步內結束。（這點保證了遊戲不會進入一個循環而導致沒有勝負）

3.雙方（或多人）擁有整局遊戲的任何信息。（即，完美信息博弈）

4.沒有任何運氣成分。（就是說，你能夠完全地料到你進行了某行動之後，整個遊戲會發展成為怎樣的局面）

比如五子棋就是一個滿足上述條件的遊戲：

1.執黑執白雙方輪流落子。

2.722步內必分出勝負。（或者平局）

3.沒有任何信息是被隱藏的。

4.落子即為一步行動，指哪落哪。（手滑不算）

但是撲克牌不滿足上述條件。

1.幾人輪流出牌。

2.54步內分出勝負。

3.別人的牌你是看不到的，有信息隱藏。

4.出牌雖然是自己能完全決定的，但是發牌不是。

這個是博弈論的一條定理策梅洛定理，最先由他在1913年證明。但是無奈，在策梅洛定理_百度百科上沒有見到通俗易懂的證法。（事實上截止到筆者寫這段文字的時候，還沒有添加證明）並且知乎上似乎也偶有人詢問，於是我在下面給出一種該定理通俗易懂的證明方法。

我們先考慮下面這個例子：

兩個人甲和乙玩遊戲，從甲開始從1輪流報數，每個人可以報1個，2個，或者3個。第二個人接著上一個人報的最後一個數的下一個數開始報。先報到6的人輸。例：甲報1，2。乙報3，4，5。甲報6，甲輸。問甲有必勝策略嗎？

答案是，甲有必勝策略。

甲只需一開始報1，之後不管乙報多少，甲都報到5。這樣最後乙只能報6然後輸掉比賽。

我們不妨將部分遊戲流程繪製如下：

藍色箭頭表示甲的回合，紅色則表示乙的。文字分別是兩人可能的行動。甲一開始只報1的情況沒有列出來。

我們將輸掉遊戲的箭頭上標上點：藍色的點代表甲贏，紅色的點代表乙贏：

我么發現，有的時候，比如最上面那種情況，甲只能報6然後輸掉比賽。

這種時候，我們認為乙報5的時候，甲已經輸掉了比賽。

即，如果甲沒有選擇只能行動至紅色的點（乙贏），那麼甲已經輸了。

所以，我們將這種「單行線」之前也染上色：

注意此情況：

因為在甲報4之後，是乙的行動回合，所以如果有紅色的點，那麼乙一定會行動至紅色的點（甲輸）。所以，當有一個點和箭頭同色時，箭頭來源的那個點也是這個顏色的。

將圖中所有情況標上有顏色的點：

此時，我們能夠看到：只要甲不報1，那麼乙就報到5，隨後甲輸掉遊戲。可見，只要甲報1，那麼不管乙報幾個數，甲都報（4-乙報的數字個數）個數，保證報到5，隨即乙報6輸掉比賽。

此為甲的必勝策略。

其實說到這兒，命題已經證明完成了。由題給信息，我們總能找到這樣一個「樹」，從「根」開始，每條有色「邊」代表不同玩家的不同行動，最後會在有限的「深度」和「度」內結束。在「葉節點」處，染上代表勝負的顏色，然後依據上述規律依次將其「父節點」染上相應的顏色。最終，在「根」上也染上相應的顏色，代表了誰有必勝/必不敗策略。

p.s.筆者在查閱資料中發現，中國象棋居然也符合規律。（比賽中規定，六十步不失子判和）也就是說，中國象棋也必然會在先手和後手之中的一者有必勝或必不敗策略。太可怕了。

最後，不關注一發嗎？

推薦閱讀：