先發制人不可信，後手拿捏最緻命

讓我們學習一下，當對手先走時該如何赢得比賽的魔法和數學。

大多數讓兩名玩家或兩支隊伍互相競争的遊戲都要求其中一方先出場。這就産生了内在的不對稱性，于是就産生了一個問題：你應該選擇先出場還是後出場？

大多數人本能地想要先走，這種直覺通常被證明是有效。在常見的雙人遊戲中，如國際象棋或網球，“擲硬币獲勝”并獲得先手的确是一種優勢，雖然這種優勢不算大。但有時讓對方先走會對你更有利。

下面我們将展示三種不同的情況，在這些情況下，被迫移動的遊戲規則會成為一個嚴重的、往往是決定性的劣勢。在國際象棋中，這被稱為“zugzwang”——一個德語單詞，意思是“迫移”（國際象棋中，Zugzwang描述這樣一種情況：無好棋可走，隻能走出對自己不利的一步）。讓我們看看在下面這些場景中，“迫移”的神奇魔力是如何實作的。

謎題1：國際象棋

在1971年的世錦賽候選棋手比賽中，執白棋的美國特級大師鮑比·菲舍爾(Bobby Fischer)和執黑棋的蘇聯特級大師馬克·泰馬諾夫(Mark Taimanov)在第二局比賽中産生了下圖的局勢。這時輪到黑棋移動了，但不幸的是黑棋在“迫移”中輸掉了比賽。現在我們的任務就是解釋為何會出現這樣的結果。

如果我們比較雙方的棋子：白棋有一個象(f5)，黑棋有一個馬(g5)，它們都無法決定勝利。但白棋有一個兵(h5)可以前進到棋盤的頂部，成為後。如果發生這種情況，白棋輕松獲勝。是以黑棋的任務很明确：泰馬諾夫必須拿下白棋的兵，即使這意味着犧牲他的馬。這将導緻平局，是黑棋的最好結果。

乍一看，黑方的馬似乎在奪取白棋的兵時處于有利位置：馬受黑方王(f4)的保護，控制着h7方陣，白棋的兵必須通過這個方陣才能被提升。

現在，“迫移”的“移動義務”準備動手：雖然泰馬諾夫滿足于讓他的馬在g5位置上。但不幸的是，國際象棋的規則要求他必須移動一步他的棋子。如果他移動了他的王，它就不能再保護馬，馬就會死亡，而白方的兵可以自由前進；另一方面，如果他将馬移動到唯一安全的方格f3，然後白方将他的兵推到h6，那麼黑方可以在接下來的移動中将馬移回g5。這可以防止菲舍爾立即将兵推進到h7。但是，這時候白棋同樣可以使用秘密武器“迫移”：他可以等待一步，将他的王滑到g6，此時便又輪到黑棋必須移動了。這樣，泰馬諾夫真的沒有可行的選擇了。

如果黑棋移動王，那麼他的馬就會倒下。如果泰馬諾夫把他的馬移動到f3，白棋的兵前進到h7，遊戲結束。（如果他把他的馬移動到其他地方，白方的象或王就會抓住它，遊戲也就結束了）簡而言之，這就是“迫移”的力量。

不用說，菲舍爾赢了這場比賽。然後在第4場比賽中，他讓塔塔諾夫陷入了一個更複雜的迫移，最終以6-0橫掃了比賽。菲舍爾在1972年擊敗蘇聯特級大師鮑裡斯·斯帕斯基(Boris Spassky)成為世界冠軍，這場比賽被稱為“世紀之戰”。

謎題2：尼姆遊戲

在一個尼姆遊戲（Nim）的衍生遊戲中，兩個玩家A和B，玩一個減法遊戲。B選擇一個起始數字，每個玩家依次減去一個小數字，直到他們的數字為零。在每一輪中，玩家必須至少減去1，最多比目前數字的十位數字多1。是以，如果目前數字在90到99之間，則可以減去10以内的任何數字;如果是80到89，可以減1到9，以此類推。最後，當剩下的數字在1到9之間時，他們每輪隻能減去1。A先走，B從90到99中選擇一個起始數字。玩家在做最後一次減法時失敗。

問題：B應該選擇什麼起始号碼？你能列出全部的“迫移”階梯數嗎？

對于這一問題，我們可以從最小的數開始考慮：

- 如果A輪到1時，就會輸掉比賽。同樣地，由于在個位數中隻能減去1，A在面對3、5、7和9（每次加2）時都會輸。

- 但是A在輪到11時不會輸，因為A在11上可以減去2，把會輸的9給B。但A在輪到15和18（每次加3）時則會輸掉。

- 現在，我們考慮20~30，我們不能再加3了，因為在21，A可以減去3，把會輸的數字18給B，我們必須加4，獲得：22，26。

- 當我們跳到30時，我們必須加上5：31，36。

- 十位數為4時需要加6：42，48。

- 依次排列下去：每進入一個更高的十位數，我們就得再增加1，才能繼續登上“迫移”階梯。

- 整個迫移階梯，從高到低：93、82、72、63、55、48、42、36、31、26、22、18、15、12、9、7、5、3、1。

謎題3：模拟遊戲

模拟遊戲（Sim）是兩個玩家之間的遊戲——我們稱他們為小紅和小藍。這個遊戲如圖所示，由6個點組成，每個點之間用黑線連接配接（在圖論中稱為邊）。每個玩家依次用自己名字的顔色将黑線塗成紅或藍。如果一個玩家的操作導緻任何三個點由相同顔色的邊連接配接，該玩家就輸了。

問：你能描述一下在最短的模拟遊戲中，使玩家處于“對等迫移(reciprocal zugzwang)” （下一個玩家輸）的位置嗎？按順序列出在遊戲中所做的動作。

這裡是一個模拟的局勢，其中的對等迫移位置在九步内達到。

可以産生此局面的操作順序為AB、BE、AC、CE、AD、DE、AF、FE、AE。這樣就剩下6條未着色的邊:BC、BD、BF、CD、CF和DF。将它們中的任何一個塗成紅色或藍色都會出現一個三條邊顔色相同的三角形，如下表所示：

是以，下一個要操作的玩家（在這種情況下的藍色玩家）将處于迫移困境中并輸掉比賽。為了了解我們是如何達到這個情形的，考慮由BACE四個點組成的四邊形。它有兩條相鄰的紅色邊AB和AC，以及兩條相鄰的藍色邊BE和CE。是以不管BC邊 （四邊形的對角線）是什麼顔色，它都會形成一個相同顔色的三角形。你可以把這樣一組缺邊的四個點想象成一個單一的“迫移單元”。在這個位置上有六個這樣的單元，每個單元對應着六條未着色的邊中的一條。

由于不完美的發揮，藍隊在比賽早期就達到了這種情況。在模拟遊戲中，無論前玩家做了什麼，後一名玩家總會有獲勝政策。這裡，我們的政策是避免建立迫移四邊形(zugzwang quadrilaterals)——除非有兩個四邊形的共同邊是沒有顔色的。圖中正好有“6選2”（一共15）條邊，是以第15步（最後一步）總是落在第一個玩家的手上。拉姆齊理論(Ramsey Theory)告訴我們：如果有六個點，那麼至少會有兩個三角形，它們的邊都是相同的顔色。在完美的玩法中，第二名玩家應該能夠将單色三角形的創造推遲到最後一步。這将誘使第一個玩家用最後一條邊形成兩個單色三角形。

編輯：zhenni

轉載内容僅代表作者觀點

不代表中科院高能所立場

編輯：Liu

精彩視訊 不要錯過

2.5個水立方大小，我們在海子山上建伽馬射線巡天裝置

星标關注“中科院高能所”微信公衆号

精彩内容不錯過