經過足夠長的時間， AlphaGo 的棋譜能收斂到一張上嗎？

11-25

若能的話，能否說明找到了圍棋的必勝策略？
相關問題：
兩個乒乓球機器人對戰，最後球會不會收斂到一個路徑上？ http://www.zhihu.com/question/26008264

根據策梅洛定理（Zermelo"s theorem），若一個遊戲滿足如下條件：

雙人、回合制；
信息完全公開（perfect information）；
無隨機因素（deterministic）；
必然在有限步內結束（finite）；
沒有平局；

那麼先手、後手兩個玩家中必有一者有必勝策略。

圍棋顯然滿足 1、2、3 三個條件。「禁全同」規則保證了 4（注），非整數的貼目規則保證了 5。所以圍棋是存在必勝策略的。

如果 AlphaGo 系列的 AI 足夠強，能找到這個必勝策略，那麼它自我對弈時會發生如下的情況：

如果先手必敗，那麼先手 AI 將直接認輸；
如果先手必勝，那麼先手 AI 將按必勝策略走第一步，然後後手 AI 直接認輸。

如果 AI 尚未找到必勝策略，那麼它的走法將會是有隨機性的 —— 它會在勝率差不多的走法中按一定規則採樣。注意它並不總是走勝率最高的走法，因為這樣就探索不到未知的領域，也就無法學習了。這種隨機性會隨著 AI 越來越接近必勝策略而逐漸減小，如果真正能找到必勝策略，那麼是會收斂的。

註：評論中針對「禁全同」的批評比較激烈。我先承認，我其實不會下圍棋。不過，評論中 @zy RSN 給出了這一條規則的來源：

中國圍棋規則第一章總則第6條，「禁止全局同形」

這條規則並不是全球通用的，所以我的討論也只適用於有這條規則的情形。

0. 十九路圍棋盤，存在一個唯一的正整數X （嚴格起見，應該說非負整數。），使得貼目為X時，黑白均存在必不敗策略。（證明略，參見此答案圍棋有沒有必勝策略？）

雙方不敗策略的總和，就是十九路盤上的最優策略。如果把贏得更多作為次要目標，則此最優策略與貼目值無關。

1、AlphaGo Zero繼續進化，是否會準確地收斂於最優策略，從理論上難以證明。

1.1 誰知道會不會收斂於一個局部極值呢？（斜眼笑）

2、即使確實收斂，需要的時間怕是要到宇宙末日。注意狗蛋Zero的進步曲線，可以用對數函數擬合。ln（x）確實趨近正無窮，可是需要多少時間啊朋友們。

3、換個角度：最優策略容不得半點模糊，而AlphaGo的本質是近似處理問題。新版AlphaGo Zero的神經網路，包含約4000萬個參數。而圍棋總變化數10^170. 用10^7個參數「擬合」 10^170種情況尚遊刃有餘，但最優策略要的不是擬合，是一點不差，毫釐不爽-- 那就無能為力了。這就需要真的把整條遊戲樹都算一遍。

4、我們退一億步說.. 想像一下最優策略真的被搞出來了，真的只是「一張」棋譜嗎？

4.1 七路棋盤的（雙方）最優策略集合都不小。換句話說，在7x7棋盤上，黑白雙方達成盤面九目最優解的變化（且雙方不犯錯）有若干個大類，其中還可以細分。

4.2 十九路棋盤的最優策略集合本身可能就會非常巨大。甚至可能出現，第一步下星或者小目都是最優策略的情況。因此，即使Alpha可以無限時間地進化，達成的最優策略也會是一個變化豐富的集合，而不是一張棋譜。

簡答一下。在棋手開啟上帝模式，自我對弈，允許投降的情況下， @王贇 Maigo 的答案無疑是正確的。即使開啟上帝模式，但如果禁止投降，即使必輸也要下完的話，那麼棋譜不可能收斂到一張上。原因有二，

1. 同優解的存在：這個不需要用特別大的棋盤，看死活題就知道，有很多死活題不止有一個解。在9x9，大局已定的棋盤上(死活題中，黑殺白或者黑求活都已經是只要下對就必然會實現的結果了)，都有同優解的存在，那麼在19x19，局勢還相對而言比較紛繁的情況下，則有更多得多，更複雜得多的同優解。

以比較容易理解的官子來說，棋盤的收尾階段，盤面上仍會留有不少價值相同的官子。你撿了這個，對方撿了那個，雖然最後的結果相同，但盤面和過程是不一樣的

2. 棋局的「最優解」，會因雙方的「共識程度」的不同而有變化。如果雙方存在共識，即我像了解自己一樣地了解你，那麼不考慮過程和盤面外表上的差距，棋局必然只有一個結果，即必敗方敗得最少得那種結果。換言之，同優解的意思無非是，千百萬個同優解，最後必敗方和必勝方的差距是相同的。

但沒有任何一條圍棋規則規定雙方應該具有這種「共識」。那麼，即使是其實明明開了上帝視角的兩個AI在互斗，必敗方也可以下出非常精彩但絕非理論最優解的棋局。

據我所知，到目前為止的AI還善於處其勝而不善於處其敗。處於理論上必敗的局勢下該如何落子，其實是要考慮到人性的。設若有A,B兩種解法，A理論上更優但對對手無法構成任何威脅，雖然如果對手下的全是最優解，則下B輸得更多些，但B在百步之外暗藏殺招，百步之內對手一個落子不慎，必敗方便可以轉為必勝方，在與對手不存在共識的情況下。A,B兩種下法，孰優孰劣？這就要看你的性格了。

而勝方也會出現「我是該冒險爭大勝，還是該下最穩妥的棋」的問題。

換言之，即使雙方都對棋局開啟了上帝模式，但在雙方不具備共識(對對方的情況完全了解)的情況下，棋局是可以下出千百種風格的。

不會。

即使阿狗遍歷所有棋譜，也不會。

目前，日韓規則是黑貼6.5目，中國規則是黑貼3.75子。

日韓規則下，黑棋略好；中國規則下，白棋略好。中國規則曾經是黑貼2.75子，那時候是黑棋明顯好。

我更喜歡中國規則，但我覺得貼3.75子過分了。平衡點或許是黑貼3.25子，但這樣會出現和棋：如果黑白雙方出現一目公氣雙活的情況。

假設規則改成黑貼3.25子，那阿狗遍歷所有棋譜之後，就會停在和棋上。然而，這樣的和棋局面會有很多個，形成同一個局面的過程也未必相同。所以，不會收斂到一張。

不可能的，最優化解在極小概率下也是確定的，計算最優化解需要窮舉，每個原子存儲一個解，需要整個宇宙才能存儲下來，你不可能找到這麼大的存儲，而深度學習神經網路是大概率下的次優化解，是一種擬合，只要人類下了不是高概率的失誤機器就能把握機會。

如我用遺傳演算法來計算大規模優化問題，可以做到優化平均剩餘1%，人工在5%以上，而用最優化演算法可能是千分之一，最理想時為剩餘為零。高維度天文數字時擬合演算法只是逼近最優化解，不會大於最優化解，而最優化解再無優化空間，己經到頂了。

最優化圍棋解，如果是執黑勝，應該是可以讓你無限次悔棋，可以悔n步，但你一樣贏不了。

如果提問是高度發展後的演算法能不能，答案必然是能

如果是現在的阿爾法狗0，那麼答案是不能，它目前是對蒙特卡洛決策樹的模擬，仍然存在非收斂因素以及在可收斂區域的隨機情況

必勝策略是策略集合而不一定是某一具體走法。

我覺得可以先試試13路棋盤，看多久能收斂。

會收斂到下列三種情況之一：

1。比賽開始。黑棋：我輸了。

2。比賽開始。黑棋走了一步。白棋：我輸了。

3。比賽開始。黑棋：和棋嗎？白棋：好噠。

兩台零狗對戰。黑狗下第一個子。白狗長考5秒後投子認輸。

會收斂到「猜先後黑棋認輸」

不會，起碼收斂到4張吧。

不能，因為這個足夠長的時間比宇宙年齡還長長長長長……
首先，早有普林斯頓的研究人員用計算機計算出了19×19圍棋合法棋局數，約等於2.08×10^170。
第二，假設兩個AI每秒可以下一局棋。
然後，一年有3.15×10^7秒，所以兩個AI一年可以下3.15×10^7局圍棋，遍歷所有棋局需要6.6×10^162年。而現在的宇宙年齡不過2×10^10年。
接著，假設我們的科技很牛逼了，可以把宇宙的每個原子做成一個計算機(類似三體的智子，但還差點)，全宇宙也不過10^80個原子，也就是會有5×10^79對AI，他們遍歷所有棋局需要1.32×10^83年。
再接著，我們把宇宙中的所有原子核都拆成夸克，做成AI(比智子還牛！)，把暗能量、暗物質也做成AI，也不過把AI的數量提高了幾個數量級而已(宇宙大部分元素是氫和氦，只有幾個質子、中子，每個質子、中子含三個夸克。宇宙中暗物質、暗能量的總和是普通物質的200倍，因為普通物質只佔總數的0.5％)，最後，需要的時間依然是10^70年數量級以上。

最後，如果我們把所有光子、中微子等輕子都做成AI，大概可以把數量級降到年為單位。(實際上還不夠，宇宙中的光子數是重子數的10^9倍，中微子數也差不多，電子數和質子數應該接近，所以，即使把占最大多數的光子、中微子也做成AI，也不過把時間降到10^60年量級)

所以，這個問題，應該是無解，或者說，不可能做到。
哦，我忘了量子計算機了，如果AI是用它造的，也許希望大一些。不過，即使一秒鐘可以遍歷上萬億種可能的棋局，還是遠遠不夠的。

不知道是不是會收斂到一張上，但是黑棋勝應該肯定的。

此問題低估了數學本身，高估了人或者人工智慧。假如有一個答案，這個答案得出的時間也是凡人難以承受的。

不需要收斂到棋譜那麼多餘吧？收斂的結果：規則確定的情況下，猜先以後，直接就斷勝負了。於是圍棋變成了石頭剪刀布。唉，AI就是這麼無聊。

經過很吵時間，圍棋的棋譜一定會收到一張上。是不是谷歌狗做的就不一定了。

命題:
每一招棋，只對應兩個狀態:
1 接下來我有必勝的招法
2 接下來對方有不敗的招法

為證此命題，只需證明1與2是互為否命題。而這可以用數學歸納法來證明，見《遊戲機實用技術》2003年某期關於人工智慧的論文。

假設你開了上帝視角，也就是說，你通過計算得知了每一招棋是狀態1或者狀態2。那麼，你每次都下狀態1的招法就行了。因為狀態1的招法不一定唯一，所以題主所說的不一定成立。

如果沒有狀態1的招法，那麼狀態2又分為我是否有不敗招法。

可問題是上帝視角能否通過計算開啟?我個人認為是無法的，因為我覺得很難判斷對方有不敗的招法。

Zero應該很接近最優解了。但最優路徑可能有無數個。它找到的是每種局面下的幾種最優下法。總步數在200-400之間，即使每一步取5種最優下法，5^300也是個天文數字。

經過足夠長的時間，會收斂到N張黑白某一方必勝的棋譜上。

目前來看，合理推斷，在中國規則下應該是白必勝。

目前來看，很有可能，N是個很大的數。

目前來看，值得懷疑，「足夠長的時間」好像會長到世界末日。