Facebook 田淵棟:第四局AlphaGo 敗招的分析 ( 附前3場比賽勝率分析)
按:本文作者田淵棟,已獲授權。
第四局李世石的78手L11挖被大家譽為“神之一手”,在DarkForest的策略網絡輸出裏排第31位,而J11靠排第10位。因此我覺得可能是AlphaGo沒有算到這一步。如果對方下了一手機器沒算到的棋,則蒙特卡羅(MCTS)搜索樹會清空,然後重新開始搜索,不應該會太快做出結論。李喆六段告訴我K10這一手是秒下,那有可能是時間管理子系統在搜索樹清空時有程序上的漏洞,因此過早地將搜索結果返回了。MCTS在一開始搜索的時候,因為模擬次數不夠多,每步的勝率方差非常大,所以返回一個不夠好的着法如K10是很正常的(在DarkForest裏面這着排在前四)。這個比較容易修正。
另一種可能是,AlphaGo的估值網絡出了問題。因為估值網絡的權重是0.5,而不管快速走子從一個局面開始重複了多少次,它的權值也是0.5。對於一個局面,估值網絡只得到一個數,而從這個局面往下走子,走多後會得到很多個數,統計上應該更為重要,但是AlphaGo不是這樣想的,兩邊各自算得勝率後直接對半平均了。所以如果估值網絡對某個局面得到的結果不對,則會極大地影響對該局面的勝率估計。注意這裏得到很多個數的原因是按照文章,葉結點在積累了一定盤數後(40)才展開,而不是第一次訪問就展開,以提高DCNN的效率。DarkForest沒有用到估值網絡,在L11的挖之後正確地返回了L12和L10這兩個應手,據李喆六段説,都是正確的應手,這間接支持了這個推斷。AlphaGo在87手之後才意識到自己已經大大落後,可能也是由於同樣的問題,比如説把右邊的黑大龍看成活的。
那為什麼估值網絡會出問題呢?可能是用於訓練估值網絡的自學習(Self-Play)的樣本分佈有盲點。為了提高樣本生成速度,AlphaGo的自學習樣本是通過用兩個純粹的DCNN互搏來生成的(完全沒有搜索),而DCNN下出來的棋因為是純模式識別,一個大問題是死活不正確,經常是在死棋裏面下子。如果黑白兩方都犯了死活不分的毛病,然後一方比如説白僥倖勝了,那估值網絡就會認為方才白的死棋局面是好的。這樣估值網絡就會染上同樣毛病,在中盤複雜的對殺局面中判斷失誤。若是這種情況就不好處理,AlphaGo下一局可能還會有同樣的問題。這裏可以看到,電腦本身也不是靠窮舉來下棋的,圍棋畢竟太複雜,每一步都要剪枝,離當前局面近的仔細剪(用DCNN),離當前局面遠的快速剪(快速走子),直到終局得到勝負為止。剪枝的好壞直接關係到棋力的高低,DCNN只是一個有大局觀的非常好的剪枝手段,它的盲點也會通過敗着反映出來。
關於DCNN+MCTS打劫。首先因為MCTS是全局估計分數的,劫爭本身和其它局面在程序看來沒有本質區別,都只是一步棋而已。劫的特殊性在DarkForest上表現為碰到有劫可提的情況時,DCNN經常會以非常高的概率(0.8以上)返回提劫這一手。可能的原因是,劫點是作為單獨的特徵輸入的,所以DCNN學習到了它和輸出(提劫)的強關聯性。這樣在MCTS搜索時會強烈偏向這一手。這在很多情況下是正確的,但有時劫很小可以不予理會,或者碰到兩個或者多個劫需要放棄一個,那“遇劫必提”的偏向性就會給搜索帶來麻煩。有時連環劫電腦反覆提就是這個原因。AlphaGo可能會有這個問題,或者是反向的問題(比如説提劫概率很小),這樣在下棋時大家就會感覺到它在避免開劫,或者在含劫的變化中計算失誤。
關於地平線效應(Horizon Effect)。國象的AI裏面會有這個效應,比如説只搜索10步,計算到別人的後被自己的後吃了結束,然後用簡單的加和法估計下盤面發現自己多個後特別爽,覺得這個分支特別好。其實再往下走一步自己的後也被別人吃了,或者掉入陷阱,這樣就誤算盤面價值。但是圍棋因為每次模擬都是走到底的,可能前30步是用DCNN,之後就是用快速走子,雖然走子質量上有差距,但是大方向上不會錯,所以地平線效應在某種程度上是減弱了。而且這次AlphaGo的失誤在20步以內,應該還在DCNN的範圍裏面,所以地平線效應的可能性比較低。
應大家要求,這裏放Game3的勝率,李世石毫無機會。
Game4的還沒空全跑,以下是關鍵的一段。注意DarkForest只是5d,所以沒有及早看出來黑掛了也是正常的。
編者一起放上作者的DarkForest對AlphaGo和李世石前兩局每步的勝率估計:
首先説明一下每個數據點是DF在當前局面下給出最優應手,同時給出的勝率。這個最優應手和選手的應手不一定一樣。如果大家要看DF給的應手,可以下載以下兩個文件:
yuandong-tian.com/win_rate1.txt
yuandong-tian.com/win_rate2.txt
資料來源:雷鋒網
作者/編輯:小芹菜
第四局李世石的78手L11挖被大家譽為“神之一手”,在DarkForest的策略網絡輸出裏排第31位,而J11靠排第10位。因此我覺得可能是AlphaGo沒有算到這一步。如果對方下了一手機器沒算到的棋,則蒙特卡羅(MCTS)搜索樹會清空,然後重新開始搜索,不應該會太快做出結論。李喆六段告訴我K10這一手是秒下,那有可能是時間管理子系統在搜索樹清空時有程序上的漏洞,因此過早地將搜索結果返回了。MCTS在一開始搜索的時候,因為模擬次數不夠多,每步的勝率方差非常大,所以返回一個不夠好的着法如K10是很正常的(在DarkForest裏面這着排在前四)。這個比較容易修正。
另一種可能是,AlphaGo的估值網絡出了問題。因為估值網絡的權重是0.5,而不管快速走子從一個局面開始重複了多少次,它的權值也是0.5。對於一個局面,估值網絡只得到一個數,而從這個局面往下走子,走多後會得到很多個數,統計上應該更為重要,但是AlphaGo不是這樣想的,兩邊各自算得勝率後直接對半平均了。所以如果估值網絡對某個局面得到的結果不對,則會極大地影響對該局面的勝率估計。注意這裏得到很多個數的原因是按照文章,葉結點在積累了一定盤數後(40)才展開,而不是第一次訪問就展開,以提高DCNN的效率。DarkForest沒有用到估值網絡,在L11的挖之後正確地返回了L12和L10這兩個應手,據李喆六段説,都是正確的應手,這間接支持了這個推斷。AlphaGo在87手之後才意識到自己已經大大落後,可能也是由於同樣的問題,比如説把右邊的黑大龍看成活的。
那為什麼估值網絡會出問題呢?可能是用於訓練估值網絡的自學習(Self-Play)的樣本分佈有盲點。為了提高樣本生成速度,AlphaGo的自學習樣本是通過用兩個純粹的DCNN互搏來生成的(完全沒有搜索),而DCNN下出來的棋因為是純模式識別,一個大問題是死活不正確,經常是在死棋裏面下子。如果黑白兩方都犯了死活不分的毛病,然後一方比如説白僥倖勝了,那估值網絡就會認為方才白的死棋局面是好的。這樣估值網絡就會染上同樣毛病,在中盤複雜的對殺局面中判斷失誤。若是這種情況就不好處理,AlphaGo下一局可能還會有同樣的問題。這裏可以看到,電腦本身也不是靠窮舉來下棋的,圍棋畢竟太複雜,每一步都要剪枝,離當前局面近的仔細剪(用DCNN),離當前局面遠的快速剪(快速走子),直到終局得到勝負為止。剪枝的好壞直接關係到棋力的高低,DCNN只是一個有大局觀的非常好的剪枝手段,它的盲點也會通過敗着反映出來。
關於DCNN+MCTS打劫。首先因為MCTS是全局估計分數的,劫爭本身和其它局面在程序看來沒有本質區別,都只是一步棋而已。劫的特殊性在DarkForest上表現為碰到有劫可提的情況時,DCNN經常會以非常高的概率(0.8以上)返回提劫這一手。可能的原因是,劫點是作為單獨的特徵輸入的,所以DCNN學習到了它和輸出(提劫)的強關聯性。這樣在MCTS搜索時會強烈偏向這一手。這在很多情況下是正確的,但有時劫很小可以不予理會,或者碰到兩個或者多個劫需要放棄一個,那“遇劫必提”的偏向性就會給搜索帶來麻煩。有時連環劫電腦反覆提就是這個原因。AlphaGo可能會有這個問題,或者是反向的問題(比如説提劫概率很小),這樣在下棋時大家就會感覺到它在避免開劫,或者在含劫的變化中計算失誤。
關於地平線效應(Horizon Effect)。國象的AI裏面會有這個效應,比如説只搜索10步,計算到別人的後被自己的後吃了結束,然後用簡單的加和法估計下盤面發現自己多個後特別爽,覺得這個分支特別好。其實再往下走一步自己的後也被別人吃了,或者掉入陷阱,這樣就誤算盤面價值。但是圍棋因為每次模擬都是走到底的,可能前30步是用DCNN,之後就是用快速走子,雖然走子質量上有差距,但是大方向上不會錯,所以地平線效應在某種程度上是減弱了。而且這次AlphaGo的失誤在20步以內,應該還在DCNN的範圍裏面,所以地平線效應的可能性比較低。
應大家要求,這裏放Game3的勝率,李世石毫無機會。
Game4的還沒空全跑,以下是關鍵的一段。注意DarkForest只是5d,所以沒有及早看出來黑掛了也是正常的。
編者一起放上作者的DarkForest對AlphaGo和李世石前兩局每步的勝率估計:
首先説明一下每個數據點是DF在當前局面下給出最優應手,同時給出的勝率。這個最優應手和選手的應手不一定一樣。如果大家要看DF給的應手,可以下載以下兩個文件:
yuandong-tian.com/win_rate1.txt
yuandong-tian.com/win_rate2.txt
資料來源:雷鋒網
作者/編輯:小芹菜