迷你圍棋之奧妙(四):七路圍棋,不唯一的最優解
七路圍棋在小棋盤圍棋中相當受矚目。雖然它超出了現有計算機的窮舉能力,但人類專家尚能以圍棋知識排除大部分無效的變化,從而以手工研究得到正解。
1977年,部分日本業餘棋手開始組織研究七路棋盤的最優解。1989年,在日本職業棋手工藤紀夫、中山典之的協助下,他們最終得到了黑勝9目(日本規則)的結論。他們的研究發布在《棋道》雜誌上。由於《棋道》雜誌已於1999年停辦,原文難以查證。好在美國圍棋協會電子月刊在1995年轉載並翻譯了日本人的部分研究成果,筆者摘錄部分如下:
在7x7的棋盤上,最優解的前三手是唯一的,如下圖:
接下來的第四手,白A斷和B位扳均可引向黑棋盤面9目的最優結果。我們先看白A斷的變化:
其中,黑13雙、白14立都是官子手筋,不可走錯。至此黑盤面9目。
然後是相對複雜的B位扳。黑棋退是唯一正解,以下又交給白棋A位尖虎和B位連扳兩個選項,見下圖。
若白棋走A位尖虎,則黑棋打吃、白棋粘。接下來黑棋又有兩種選項,A粘或B拐。
若黑A粘,則棋局簡化,直線走向結局。黑勝9目。
B位拐則更複雜。
黑5的退讓要緊。若黑棋一毛不拔,走在10位立,則白棋可以在左下連扳做劫,黑棋劫材不利。右圖中,白12利用黑棋氣緊的弱點扳入,迫使黑棋退讓。最終結果也是盤面9目。
最後講最複雜的連扳。
白連扳以後,黑2打是唯一正解;走3位打吃則不可能贏9目。黑2打、白3接以後,黑共有四種可行的走法,均引向盤面9目的結果。本文僅摘錄黑A的變化,余者請讀者自行研究。
結果不出所料,黑勝9目。
請讀者注意,以上的研究均基於日本規則。若是採用中國規則,能夠達到盤面9目的最強變化還要增加一些分支,比如下圖:
按照日本規則,黑棋盤面8目。按中國規則,黑棋29子,白棋20子,黑勝9子。黑棋多出了收後的一子,因此盤面8目的棋在中國規則下同樣是黑勝9子。
2015年前後,中國職業棋手李喆在時越、尹航等棋手的協助下,獨立完成了對7路棋盤正解的進一步研究,成果《七路棋盤最優解》發布在《圍棋天地》2015年第20期上。李喆的文章中共研究了八十一個變化圖,比日本棋手的研究更加細緻。除了驗證最優貼目9目的結論之外,李喆還提到了一個全新的關鍵分支,如下圖:
白棋二路尖虎時,黑棋可以選擇不打吃、單拐。白12一路扳挑起劫爭,最終仍是黑勝9目。
七路盤看似不大,但求正解的技術難度遠超已知最難的死活題。已有的結論相當可靠,但不能保證沒有遺漏有意義的變化。嚴格的證明或須引入巧妙設計的程序輔助檢驗。
到達最優解的路徑遠遠不止一條。結合日本棋手和中國棋手的研究,主要的分支共有八條。每一條分支中,黑白雙方都沒有給對方佔便宜的機會,都走出了最強手段。而且,對於每條主要的分支,或改變無關緊要的手順,或是走一個先手交換,會引出一些不改變最終結果的次要分支。因此,七路棋盤上的最優解不唯一,而是一個包含很多道路的解集。如果採用中國規則代替日本規則,則這個解集就更大了。
正如李喆所言,研究七路盤最優解給我們的啟發之一是,圍棋盤上的最優解遠遠不是唯一。也許有一天,圍棋上帝會告訴我們十九路棋盤的最優貼先,比如說7目。考慮十九路棋盤的狀態空間複雜度(10^170 對比10^22)和遊戲樹複雜度(10^600 對比 10^35),對比七路棋盤,我們不難推出,十九路棋盤上到達這個最優結果、盤面7目的路線會有億億…億條。其中每一條路線,黑白雙方都沒有犯哪怕一個小錯。
AlphaGo經過訓練會變得越來越強。有些人擔心,若給AlphaGo足夠的時間,她會最終收斂到唯一的最優解,終結圍棋。通過上面的分析,我們可以下結論,這樣的擔心完全是杞人憂天(此處 @王贇 Maigo @柯靈 (#滑稽) )。事實上,AlphaGo在布局階段的選擇引入了很大比例的隨機因素,會在兩個差不多好的選項之間投硬幣。AlphaGo的開發者知道,兩個AlphaGo認為差不多好的選項,在圍棋上帝的眼裡可能就是一樣好。
換句話說,即使在神眼裡,圍棋也是個有趣的遊戲。
本系列第二、三部分(3-6路棋盤)暫不發布,請讀者諒解。
推薦閱讀:
※FPGA是否已經奪得人工智慧硬體領域霸主地位?
※探索路人能聽得懂的深度學習(視頻更新中)
※想輕鬆復現深度強化學習論文?看這篇經驗之談
※Ian Goodfellow談GANs論文評審:有這些跡象的論文要懷疑
※[直播] 負基礎入門Python系列:Python之禪