必勝策略，圍棋之道

　　在職業圍棋圈，一部分棋手自稱「求道派」。「道」者，終極真理是也。與「棋道」如影隨形，「圍棋上帝」、「圍棋之神」也是棋手和棋迷常掛在嘴邊的兩個概念。在上一章節我們講到，圍棋之多變如恆河沙數，非人力所能及。思及此，棋迷朋友可能會詰問，圍棋的終極真理是否存在，「圍棋上帝」到底會怎樣下棋。筆者將在本文解答這兩個問題。（本文部分內容參考了筆者的其它回答）

1、小學生的遊戲

　　圍棋，終究還是個遊戲。欲知圍棋之道，我們可以先從研究一個簡單的遊戲入手。搶三十，一個酒桌上的小遊戲，也是一道小學奧數題。它的規則是這樣的：

　　甲和乙從1開始輪流報數，每次可以報1、2或3個數。比如甲報1,2；乙報3,4,5，甲報6，乙報7,8. 報出「30」這個數字的玩家獲勝。

　　搶三十的訣竅，說來也不難，只需用到一點逆向思維。如果甲想搶到30，一定不能以29收尾，否則乙下回合可以直接搶到30。同理，甲也不能以28或27收尾，不然乙也能直接搶到30. 不過，若是甲以26收尾，則乙在下一回合必然搶不到30. 不僅如此，乙下一回合必然以27,28,29三者之一收尾。這樣一來，輪到甲的時候，甲必然能搶到30. 因此，甲搶到26就可以保證獲勝。同理，想要搶到26，甲必須搶到22、18、14、10、6、2. 我們以下圖示意：

　　以紅色的30為最終目標，橙色的26、22等數是兵家必爭之地，而白色的27、28、29等數，只能過站，不可以停留。甲玩家只需一路佔領2、6、10、14、18、22、26這一串等差數列，即可將勝利收入囊中。

小結一下。搶三十這個遊戲，先手方（即先報數的甲玩家）有必勝策略，而且可以用數學語言精確地描述：先手方先報1,2；之後，若後手方報n個數（n=1,2或3），則先手方立即回以4-n個數。最終，先手方總能搶到30.

　　在博弈論（Game Theory）中，數學家把像22、26這些遊戲中的「兵家必爭之地」，稱作必勝局面（Winning Position）。換句話說，搶到必勝局面的一方，即可穩操勝券。相應的，像27,28,29這樣的節點，在此停留就會失敗，被稱為必敗局面 （Losing Position）.

　　這個策略說來容易，卻隱藏著許多變化。舉個例子。甲報1,2，乙報3,4；這是一個回合。每一個回合，甲都會佔領一個新的必勝節點。七個回合結束以後，甲才能搶到30. 每一個回合中，乙可以報一個、兩個或三個數，各有三種選擇。根據乘法原理，六個回合中，乙共有3*3*3*3*3*3*3=3^7=2187種策略的組合。只不過，乙的變化再多，也逃不出甲的手掌心。

　　那麼，如果甲和乙搶的不是三十，而是每次可以報1-299個數字，報出1,000,000者為勝呢？依樣畫葫蘆，我們仍可以為先手方找到必勝策略：先手方只需先報100。然後，若後手方報n個數（n=1,2,...,299），先手方立即回以300-n個數。先手方總能搶到100,400,700,1000,...999700,1000000這一串數，即「必勝節點」，從而獲勝。

　　我們來看這一套必勝策略包含的變化。後手方每次有299種選擇，先手方每次也只有一種回應。3330個回合之後，先手方就能獲勝。因此，總變化數是299^3330。數字雖大，終究有限。因此，這個無聊的遊戲，就算是上帝來和筆者玩，只要筆者拿到先手，就輸不出去。這就是搶三十這類遊戲的「終極真理」了。

2、完全信息遊戲與策梅洛定理

　　搶三十這一類遊戲，我們能夠運籌帷幄、立於不敗之地的關鍵是，我們知道對手所有可能的選擇，我們了解遊戲中所有的信息。像這樣的遊戲，我們稱之為完全信息遊戲 (Perfect Information Game) 【反例：鬥地主不是完全信息遊戲，因為看不到對手的牌】。另一方面，搶三十也是一個有限遊戲（Finite Game），即它總是在有限個回合內完成。對於所有的完全信息有限遊戲，我們都可以畫出它們的遊戲樹 （Game Tree）。就像圖論中的樹一樣，一個完整的遊戲樹包含有一個起始節點，代表遊戲中某一個局面，接著下一層的子節點是原來父節點局面下一步的各種可能性，以此類推。遊戲樹逐層擴展，直到遊戲結束。

　　上圖是搶三十遊戲樹的一部分。19這個節點只與20、21、22這三個節點連接，意味著若甲報出19，則乙只能報到20、21或22. 其它節點間的連接關係同理。

　　搶三十遊戲相對簡單，在於它只有一個終局局面，或者說遊戲樹的末端節點，也就是30。我們很容易從這唯一的最終節點逆推出必勝策略。但是對於擁有不止一個終局局面的遊戲，推理最優策略就不那麼容易。這時，就輪到遊戲樹出場亮相了。接下來，我們再介紹一個遊戲為例。

　　井字棋 (Tic-Tac-Toe)，又稱XO棋，是一種簡單的棋。對局雙方輪流在3x3的棋盤上落子，在橫、豎或對角線方向上連成三個的一方獲勝。如下圖，是從空枰開始的井字棋遊戲樹。

　　如果能完整地畫出一個遊戲的遊戲樹，那麼我們就像掌握了搶三十的秘笈一樣，只需按圖索驥。比如說，對於井字棋遊戲的一個殘局，下圖的遊戲樹給出了雙方所有的應對可能性。

　　此殘局的初始局面，由畫「X」一方先行。X方有三種選擇，而每一種選擇下，O方也有兩種應對。標有藍色分數的棋局是終局節點，+1表示X方獲勝，-1表示O方獲勝，0表示平局。很明顯，X方不能選擇棋盤右邊的兩個點，否則O方可以一擊絕殺。因此，X方只能走在棋盤左邊。這樣一來，即使O方選擇正確，X方也能保證平局。遊戲樹第二層和第三層的部分節點標有黑色數字。這些節點並非終局，但我們可以簡單推理出雙方都走對情況下的棋局結果，標上+1，-1或0。同理，我們可以逐層往上標記，直到殘局的初始局面，也就是遊戲樹的起始節點。圖中，起始節點的值是0，因此我們得到結論，此殘局若雙方應對無誤，結果是平局；X方應走在棋盤左中的一點。

更進一步，如果我們畫出井字棋的完整遊戲樹（如上圖），我們就可以用同樣的方法，逆推出遊戲樹中每一個節點最終會走向何種結果，最終推出雙方的最優策略，以及在最優策略下誰勝誰負。事實上，如果從空枰開局，雙方不犯錯的情況下，井字棋會以平局收場。

所有的二人完全信息有限遊戲，如果沒有運氣成分（例如飛行棋擲骰子），在理論上我們都可以用同樣的方法，畫出遊戲樹，從結果逆推到開局。數學家恩斯特·策梅洛（Ernst Zermelo）將這個結果總結為策梅洛定理（Zermelos Theorem），表述如下：

　　若二人完全信息有限遊戲不涉及隨機成分，則要麼先行方有必勝策略，要麼後行方有必勝策略，要麼雙方均擁有必不敗策略（即若雙方都不犯錯，遊戲將會是平局）。

　　策梅洛定理的嚴格證明，其實和前文井字棋部分所述類似。在確定遊戲樹之後，從所有終局局面出發，可以推斷出任意局面的勝負性（即此局面何方有必勝策略，或者雙方均有不敗策略），直至初始局面。在數學上，這種推理的方法，被稱為反向數學歸納法（Backward Induction）。

　　策梅洛定理適用於大部分為人熟知的棋類遊戲，比如國際象棋、五子棋、黑白棋、西洋跳棋等，但不適用於涉及運氣成分的飛行棋，也不適用於多方混戰的中國跳棋。

3、圍棋，有限遊戲？

　　讀到這裡，性急的讀者可能已經脫口而出，「那麼，圍棋當然也適用策梅洛定理，一定存在某一方的必勝策略嘛」。且慢。圍棋確實符合「二人」、「完全信息」、「無隨機因素」這三個特點，但「有限」這個性質，我們暫時還得打個問號。

有記載的職業棋局，最長手數記錄是414手（林修平VS陳禧一），超過了圍棋盤交叉點的總數361個。但這並不是一局圍棋長度的上限。能夠無限進行下去的棋局，其實在職業比賽中已經出現過多次。比如下圖，古力和李世乭在2012年三星杯32強雙敗淘汰賽首輪的一局。

由於棋盤右方罕見的四劫循環，本局被判「無勝負」，雙方重賽。注意，本局的結果是「無勝負」，而不是和棋（平局）。「無勝負」隱含的意思是，這盤棋可以無限進行下去。在規則沒有禁止的情況下，黑白雙方將反覆提四個劫，循環往複。

對應到圍棋的遊戲樹中，多劫循環是一種循環(loop)結構。

比如，在上圖中，節點1-2-5和節點2-3-4-5分別構成循環。循環使得策梅洛定理中的反向歸納法失效，不適用於有循環的遊戲。

好在，現行中國圍棋規則在原則上禁止多劫循環，也包括長生等其他特殊的循環棋型。

• 中國圍棋競賽規則（2002年版）
• 第一章 總則
• 第6條 禁止全局同形
• 著子後不得使對方重複面臨曾出現過的局面。

本條規則有時簡稱「禁全同（SuperKo）」或「禁同形」。在部分比賽中，禁全同規則並未得到嚴格執行。本章節剩餘的部分，我們仍基於嚴格的禁全同規則來討論。在嚴格禁同的情況下，循環不復存在。即使局面再多，一盤棋也不能無限進行下去。

綜上所述，禁全同的圍棋是有限遊戲，適用策梅洛定理。取決於貼先的不同，黑方或白方之一肯定有必勝或不敗的策略。現行中國規則，黑貼3又3/4子，杜絕了和棋的可能性。因此，黑方或白方之一肯定有必勝策略。如果採用舊時的不貼目規則，允許和棋，則要麼黑方有必勝策略，要麼白方有必勝策略，要麼雙方均有必不敗策略。

4、存在而不可知的必勝策略

也許思維活躍的讀者還有疑問。黑白雙方之一有必勝策略，這個回答並不令人滿意。想必讀者更關心的問題是，到底是黑棋必勝，還是白棋必勝。前文介紹的搶三十，變化不少，但掌握規律以後沒有任何難度，因為先手方有一個簡單易行的必勝策略。無禁手的五子棋倒是很複雜，但資深愛好者大多也知道花月局加蒲月局可以保證黑方必勝。

圖註：五子棋花月開局。其後變化雖複雜，但黑方總有確定獲勝的路線。

　　但是圍棋呢？我們在前一章節介紹了圍棋變化總數之多。既然如此，找出一個具體的必勝策略，可行嗎？事實上，吳清源不能，柯潔不能，甚至AlphaGo也不能。就算是棋藝已臻化境的AlphaGo，距離圍棋之神還遠得很。如果找不出具體的必勝策略，怎麼敢打包票說要麼先手必勝，要麼後手必勝？

　　數學上，能夠證明存在，而構造不出一個具體例子的概念，實在太多太多。我們把這樣的證明叫作「非構造性證明（Non-constructive Proof）」。接下來，我們將介紹一個數學遊戲，並以此進一步展示非構造性證明。

　　A、B兩人進行這樣一個數學遊戲：在黑板上輪流寫下1到2000中的任意一個整數（含邊界，A先寫），但不能寫下任何黑板上已存在的數的因子。

　　因為一共只有兩千個數可以寫，所以這個遊戲不會無限進行下去，符合策梅洛定理的應用條件。換句話說，要麼A有必勝策略，要麼B有必勝策略。問題來了，誰有必勝策略呢？

　　答案是先手方，A有必勝策略。

證明：

　　考慮一種新的遊戲：A、B在黑板上輪流寫下2到2000中的任意一個整數（含邊界，A先寫），但不能寫下任何黑板上已存在的數的因子。在這個遊戲中誰有必勝策略？

　　如果A有必勝策略，那麼A在原遊戲中也採用這個策略。注意，1在以後的過程中再也不能寫上了（因為它是任何數的因子）。由於在新遊戲中A有必勝策略，所以在原遊戲中，A有必勝策略。

　　如果B有必勝策略，那麼A在原遊戲中先寫上1。這就相當於構建了上述新遊戲，B是新遊戲中的A，A是新遊戲中的B。由於在新遊戲中B有必勝策略，所以在原遊戲中，A有必勝策略。

　　綜上所述，A有必勝策略。

　　上述證明過程中並沒有找出具體的必勝策略，但是仍然證明了A有必勝策略，乃是非構造性證明的一個良好範例。注意到，「如果B有必勝策略」一段，假設了一個後手方的必勝策略，然後再交給原遊戲中的先手方A使用。這種證明方法，在博弈論中被稱為「策略複製論證（Strategy-stealing argument）」。對於具有對稱性的遊戲，策略複製論證總能證明先手方不敗、

　　用相似的思路，我們可以證明，無貼目的圍棋，執黑一方有必不敗策略。不過，我們需要特別小心，無貼目圍棋的對稱性非常微妙。為此，我們需要引用部分中國圍棋規則的條文作為預備知識：

中國圍棋競賽規則（2002年版）

第一章 總則

第7條 終局

　　1、棋局下到雙方一致確認著子完畢時，為終局。

　　2、對局中有一方中途認輸時，為終局。

　　3、雙方連續使用虛著，為終局。

第9條 計算勝負

　　著子完畢的棋局，採用數子法計算勝負。將雙方死子清理出盤外後，對任意一方的活棋和活棋圍住的點以子為單位進行計數。

　　雙方活棋之間的空點各得一半。

　　棋盤總點數的一半180.5點為歸本數。一方總得點數超過此數為勝，等於此數為和，小於此數為負。

　　現在我們可以正式開始證明了。

　　根據策梅洛定理，無貼目的圍棋，要麼黑方有保證不敗的策略，要麼白方有必勝策略。假設白方有必勝策略的，將此策略記為S。

　　對此，黑方可以在第一手使用虛著（即停一招）。現在棋盤為空枰，輪白方落子，相當於雙方交換了先手。即白方變為先手方，黑方變為後手方。

　　若白方在棋盤任意位置落子，則黑方可以複製前文假設後手方存在的必勝策略S，獲得勝利，黑勝。

　　若白方同樣選擇虛手，則雙方連續虛著。按照規則第7條第3款，棋局終止，計算勝負。按規則第9條，雙方各得空枰的一半，平局。

　　綜上，假設的後手方必勝策略S不存在，因此先手方（黑方）不敗。

注意：這不是模仿棋。

5、最優貼目值

　　當然，即使沒有數學證明，不貼目的圍棋不公平，也是顯而易見的。在近代日本，黑棋屬於下手，用來平衡與上手的實力差距。現行中國規則，黑棋須貼先3又3/4子，以平衡先手優勢。貼先小數部分的3/4子杜絕了和棋的可能。在排除和棋之後，黑白雙方有且只有一方存在必勝策略。額外的貼先破壞了對稱性，策略複製論證法不再成立。因此，僅從數學上，我們無從得知黑方必勝還是白方必勝。我們可以確定無誤的是，存在一個最優貼目值（Game Theory Value），記作X，滿足以下性質：

1. X是一個非負整數（腳註：此處的貼目值按數目法定義，如X=7目。如果用中國規則的貼子，則X的小數部分可以是1/2，比如X=3又1/2子。）；
2. 貼目值為X時，先後手雙方均存在不敗策略；即雙方都不犯錯，結果是和棋；
3. 貼目值大於X時，後手方有必勝策略；
4. 貼目值小於X時，先手方有必勝策略。

　　這幾條性質非常直觀，證明起來也不困難，我們交給讀者思考。

　　在小棋盤上，最優貼目值並不難確定。比如，對於二路(2x2)棋盤，X=0.

　　對於五路及以下的小棋盤，計算機窮舉即可證明最優貼目值。但七路及以上的圍棋，變化已經極多，超過了計算機目前的窮舉能力。七路棋盤，圍棋手有比較深入的研究。上世紀八十年代，日本的一些圍棋愛好者與工藤紀夫等職業棋手合作，完成了七路棋盤最優解的研究。2015年，李喆等職業棋手也獨立完成了相似的研究。他們的結論完全一致——七路盤，9目是最優貼目值。

（圖註：七路盤最優解一變）

　　基於圍棋知識的研究雖然沒有窮舉所有變化，但也足夠有說服力。換句話說，知道了最優貼目值，等價於知道了空枰開局時雙方的最優策略。這在博弈論中被稱為弱解構（Weak solution）. 對應地，強解構（Strong solution）需要知道從任何局面開局時雙方的最優策略。而像十九路盤上無貼目的棋局，我們只知道何方有不敗策略，而不知怎麼走棋才能不敗，這種情況被稱為超弱解構（Ultra-we ak solution）。

　　小棋盤的最優解，棋手的研究也就到此為止了。即使是被普遍視作小朋友入門用的九路圍棋，其變化之多也遠遠超出了職業棋手的研究能力；當然，更是遠遠超出計算機的窮舉能力。在前面章節提過，十九路圍棋的變化數相比於九路圍棋，何止幾何級增長。從而，尋找最優策略是一件遙不可及的任務。換句話說，我們也無從得知最優貼目值是多少。貼3又3/4子規則下，我們連何方有必勝策略都不知道，也就是連超弱解構都做不到。

　　唯一的安慰是，人類發明的人工智慧，為我們掀開了真理的一角。AlphaGo在2017年5月公布的自戰50局，白方贏得其中38局，勝率76%。因為AlphaGo的水平極高，我們可以據此認為，貼3又3/4子的棋局對白方有利。這和近年來職業棋手在大貼目對局下的感受、實際勝負統計相符。筆者在此下一個模糊的結論：十九路圍棋，最優貼目值X很可能小於7目半（3又3/4子）。

6、圍棋之道

　　本章寫到這裡，沒有討論任何圍棋的技術，圍棋之道卻已呼之欲出。

　　道，即為終極真理，就是掌握一切。

　　在搶三十遊戲中，終極真理就是先搶到26,22等一系列關鍵數字。對於七路圍棋，職業棋手對於種種變化詳盡的研究，基本上揭示了七路圍棋的終極真理。

　　十九路圍棋的終極問題是，最優貼目值是多少。解決最優貼目值問題，意味著了解空枰開局時雙方的最優策略。用我們剛剛提到的術語，叫做弱解構圍棋。

　　如果要求更高一點，希望知道所有奇形怪狀局面下的最優策略，即強解構圍棋，這是圍棋上帝乾的活。

　　這就是棋道了。

　　十九路圍棋之道，和七路圍棋之道，看上去只是複雜程度的區別。不過，其變化總數跨度之大，量變引發了質變。我們已經掌握了七路圍棋的幾乎所有變化，卻永遠不可能掌握十九路圍棋的所有變化。

　　前文提到，十九路圍棋盤的所有合法局面數，10的170次方。比較一下，西洋跳棋的合法局面數，10的20次方，在近年被弱解構。國際象棋的合法局面數，約10的50次方，弱解構遙遙無期。目前最牛的超級計算機，中國的神威·太湖之光，每秒運算次數10的17次方。通過窮舉的方式破解圍棋，我們一台需要每秒運算次數10的165次方的計算機。

　　10的165次方，這不是人類的領域。這是神祇，或者外星人的領域。

　　「棋道一百，我只知其七。」藤澤秀行名譽棋聖之言，曾被認為是自謙。然而，人類已經了解的圍棋，從比例上來看，遠遠不及變化總數的百分之七，誠為滄海一粟。

　　即使如此，人類也從未放棄對棋道的追求。從圍棋十訣到AlphaGo，我們集跬步而成千里。也許有一天，劉慈欣《詩云》中無所不能的李白文明，帶著量子存貯器中收集的《真·圍棋10的170次方變化大全》來和地球人對弈，人類的ZetaGo也能勝天半子。就像祁同偉，哦不，《天局》中的渾沌那樣。