張貼日期：Feb 22, 2018 10:18:7 AM

小弟從大學時期開始參與遊戲測試，尤其是桌上遊戲的測試。說到遊戲測試，很多人會疑惑說，這工作到底是在做什麼？跟數學又有什麼關係？以上兩個問題，我想可以用下面的這句話來回答：

我可以用數學告訴你，你的遊戲爛掉了！

案例一：如果註定和局，那我幹嘛還要玩啊？

我們先從一個經典的『爛掉的』遊戲開始：圈圈叉叉（tic-tac-toe）。根據美國桌遊公信網 BoardGameGeek，圈圈叉叉的名次是第 14923 名，在所有有評分的遊戲中 敬陪末座。要論爛掉的遊戲，恐怕很難比這個爛。

為什麼這個遊戲會『爛掉』？首先呢，我們可以把整個遊戲的可能發展全部畫出來：(下圖好像沒有畫出先手選擇邊緣的中間的可能)

https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Tic-tac-toe-full-game-tree-x-rational.jpg/1280px-Tic-tac-toe-full-game-tree-x-rational.jpg

請留意上圖中的有色圈圈：

▎藍色圈圈是雙方最後平手的狀態。

▎如果一個棋盤狀態會保證最後進入平手，讓我們稱它為『必和態』。

▎你可以檢查一下圖中的所有紅圈圈都是『必和態』。

所以簡單來說，不論先手（Ｘ）怎麼下，後手（Ｏ）只要確保自己選擇紅色圈圈的這些『必和態』，就能夠遊戲最後和局。結果就是，圈圈叉叉，必和。

既然還沒玩都知道一定和局，那我幹嘛還要花時間玩…拿個第14923名，也只是剛好而已。

這個分析『狀態』的手法可以擴及到很多狀況，讓你甚至不用摸到遊戲就可以告訴對方：你的遊戲爛掉了。這邊給大家一個真實範例做練習：有一位我的設計師朋友，他有一天問我以下這個規則：

甲乙兩人玩一個有九個 3x3 棋盤的圈圈叉叉。輪到一方時，他選擇一個棋盤，並在其中一個空格中寫上他的符號。每個棋盤皆以一般的三連線決定勝負。當有人在其中五個棋盤獲勝時獲勝。

我一秒鐘就回答對方說：你的遊戲爛掉了，這遊戲『必和』。

在這邊給大家想一想，為什麼？

案例二：如果註定會輸，那我幹嘛還要玩啊？

必和遊戲是問題，必輸遊戲也是個問題。

如果我老早就知道我一定輸了，我到底為什麼還要玩這遊戲？

這裡以一個經典的拈（Nim）遊戲做範例：

有 2018 顆石頭。甲乙兩人輪流從剩下的石頭中，取走 1~3 顆石頭。取到最後一顆石頭的人贏。

在前面的圈圈叉叉中，我們觀察『必和態』；在這裡，我們改觀察可以保證的『必勝態』。概念很簡單：

▎首先，如果你取完後剩下 0 顆石頭，那表示你贏了，所以 0 是一個『必勝態』。

▎然後注意到，如果你取完後剩下 4 顆石頭，那你一定可以取到最後一顆：對方取 1 你取 3，對方取 2 你取 2，對方取 3 你取 1。

換言之，剩 4 顆是個可以保證進入剩 0 顆狀態的『必勝態』。

▎同樣的道理，當你取完後剩 8 顆，你就可以保證下一輪你可以取完剩4 顆，所以剩 8 顆也是『必勝態』。依此類推，顯然所有 4 的倍數都是『必勝態』。

這表示 2016 = 4 x 504 是一個必勝態！所以，先手只要取走 2 顆，之後照上面的策略，保持他取完後的顆數都是 4 的倍數，他就一直處於『必勝態』。換言之，先手必勝。

以上是個很簡單的歸納推論。用同樣的概念，你可以推廣到複雜不少的遊戲，在這邊提供給大家一個複雜許多的拈遊戲問題，有興趣的人可以試試看：

（2015年阿根廷數學奧林匹亞，第二級，第三題）

有100! = 1x2x3x…x100 顆石頭。甲乙兩人輪流進行回合。輪到一方時，他必須選擇一個正整數 y，滿足以下條件：

1. y 必須小於或等於目前剩下的石頭數量；

2. y 最多只能有 9 個相異質因數。

選定後，他從剩下的石頭中取走 y 顆。取到最後一顆石頭的人贏。

試問：誰有必勝法？

大絕招：Zermelo’s Theorem

但其實，如果你不想做以上的分析，這邊提供給你一個大絕招。Zermelo定理證明了，如果滿足下列條件，則要不就是有某方必勝，否則就必和：

1. 兩人棋局 : 甲乙雙方交互下。

2. 遊戲是完全資訊（Perfect Information）: 所有事情都攤在陽光下，沒有像橋牌手牌那種你會看不到的東西。

3. 沒有隨機性（No Randomness）: 不會有中途要你丟個骰子之類的。

4. 遊戲的總回合數有上限N。

圈圈叉叉跟拈都很明顯滿足以上條件。對於圈圈叉叉，最差下 9 手遊戲一定會結束；對於前面的拈遊戲，最差 2018 回合一定會把石頭拿光。

證明手法其實非常單純

對著回合數上限 N 做數學歸納法。若 N=1，甲下一手就分勝負了，很明顯是必勝或必和。而若 N=n 時定理成立，則當 N=n+1 時，你只要考慮甲先下一手後，對於乙就是個上限 n 回合的遊戲，再套用歸納假設就可以了。細節不難，各位可以自行試試。

值得注意的是，Zermelo 當初證明的結果更強，他允許最後一條從『回合數有上限』放寬成『總盤面數有上限』。舉例來說，雖然西洋棋的回合數理論上可以到無限大（因為你可以同一顆棋子往復走），但可能的盤面數卻是有限的（因為你就有限多顆棋子排在有限多的棋盤格中），因此，還是存在必勝或必和法。同樣的，圍棋的回合數理論上也可以到無限大（因為有個叫三劫循環以及一個叫長生劫的鬼東西），但可能的盤面數仍然是有限的（畢竟就19 x 19 的棋盤，每個位置黑棋、白棋或沒棋三種可能）。

總結來說

Zermelo 大大告訴我們，你就不用煩惱了，有限的棋盤，有限的棋子，沒有隨機性或隱藏資訊，就別想繞過必勝必和地獄。

所以有限賽局一定沒救…真的嗎？

以上我們說明了，現在常見的圍棋、西洋棋、象棋、將棋等一干棋等，通通都有人必勝或是必和。這樣看起來，我們貌似沒有任何棋好下了？

那倒未必。

因為就遊戲設計的觀點，關鍵不在是否必勝必和，而在人類看不看得出來必勝必和啊！

你看，雖然我們有大絕招 Zermelo’s Theorem，但這定理也只告訴你一定會是某人必勝或必和。它可沒有告訴你是誰必勝或是必和，也沒告訴你要怎樣下才必勝。

Zermelo’s Theorem 是個存在性定理，只告訴你最佳策略存在，可沒告訴你最佳策略是啥。

今天要是遊戲是像前面的圈圈叉叉或是拈遊戲，簡單到可以很快看出誰必勝以及如何必勝，那這遊戲才是爛掉。如果今天存在最佳策略，但人類薄智薄能看不出來，那對於人類而言，這遊戲依然是玩得動的。

奇雞連連 (2004 年 Arets Spel 最佳兒童遊戲)

舉個例子，圈圈叉叉爛掉了，但是大家可以去看看一個叫奇雞連連的桌遊，它是圈圈叉叉的推廣，然後看看你能不能講出誰必勝或必和。

所以，即便知道圍棋有某方必勝，我們可不知道是哪一方，也不知道怎樣下才會必勝。別說我們人類不知道了，連 Alpha Go Zero 都不知道啊！

因此，我們應該還可以下圍棋下滿久的，大家不用急著把家裡的圍棋棋盤丟掉。