AlphaGo兩次提前30分鐘確信必勝，殘局計算能力的差距或是關鍵
按：作者李理，出門問問NLP工程師。
（via wildfirepr.com）
比賽之前根據論文裏的技術來分析AlphaGo能否戰勝李世乭，我們可能太過關注深度神經網絡而忽視了MCTS的重要性，尤其是它在殘局裏的重要性。前天比賽結束後我們重新審視了AlphaGo的兩大核心技術，認為殘局是AlphaGo制勝的關鍵。昨天晚上看到新聞説AlphaGo在比賽結束前就確認了必勝的結果，更加證實了這個想法可能是對的，所以想把這個觀點分享出來。
下面是具體的內容：
經過第二局比賽之後，我已經變得悲觀了。因為我覺得在殘局的計算能力上人類與AlphaGo的差距太大了。
1. 上帝眼中的圍棋
從數學上來講，圍棋有個最優的走法，也就是用mini-max搜索到遊戲結束時的一條最優路徑（也許有多條，但至少有一條），然後就能知道最優的情況下黑棋勝白棋多少目（也許是白棋勝黑棋？直覺上和經驗上來説黑棋先手是佔優的，但是好像也沒有誰證明過這個問題？），那麼黑棋對白棋的貼目就應該是這個最優值。
2. AlphaGo的殘局計算
和人類相比，AlphaGo的殘局計算有點太Bug了。
比如説AlphaGo可以計算出最後50步棋（這裏只是假設的步數，而且MCTS不是完全搜索所有可能，而是根據先驗概率和搜索結果調整策略，搜索“重要”的子樹），而人類只能計算最後30步棋。那麼即使在第50步的時候人類選手領先10目（已經去掉貼目），那麼也只是説人類在100%精確地走好每一步的時候才能勝。但是圍棋很複雜，也許走第50步時走個次優的走法，領先就變成了8目，如果再走得緩一點，可能就只領先6目了。而因為人類只能計算最後30步棋，那麼這50-31步的一點點失誤可能都會造成最終的失利。
當然我對圍棋不懂，也許圍棋沒有想象的複雜，它的估值函數還是比較平滑的，或者在這50-31步中大部分局面都很容易直接找到最優解，但是某些局面就困難一些（也就是關鍵的點）。但是我覺得這樣的關鍵點還是很多的，因為圍棋和象棋不同，圍棋隨便挪動一個棋子，對全局都是有影響的。象棋雖然在某些特殊情況下一個棋子的位置會影響最後的勝負，但是大部分局面下走一步閒棋影響都不大，尤其是雙方棋子較少的中殘局。
比如説人類高手的判斷局面的準確率是AlphaGo的90%（90%能不計算憑“感覺”直接找到當前局面的最優解，1是AlphaGo的準確度，上帝可能是2？），那麼20步全部正確的概率只有0.12（相對於Alphago來説）。如果兩個人殘局的計算能力差太遠，而且積累的優勢不是太多的話，除非碰到的殘局很簡單，第50步-31步憑感覺就能找到最優解（或者次優解與最優解的差別很小，但感覺上圍棋不像象棋。象棋如果優勢，比如比對方多兩個兵，那麼走一兩步緩手（只要別太差，讓人吃子了），最終還是很可能會贏（當然也有某些特殊的局面必須要走的精確）。但圍棋如果稍微幾個緩手，優勢就丟了很多。
3. AlphaGo的開局呢？
這其實和人類的搜索有些類似：比如當前局面下有10種走法，我們根據好壞(alphago是rollout Policy，這個需要非常快）給它計算一個概率，比如0.4，0.3，0.1，.....，那麼它就會以較大的概率選擇0.4的走法來嘗試，當然也有0.3的概率走第二個。之後每一步都是一樣的方法選擇走法直到遊戲結束，然後就能判斷這個遊戲結束局面的準確值。比如我方勝利了，那麼就會backup回去，讓我們下次選擇0.4的概率更大一點，也許變成了0.45，0.28， 0.09，...。經過大量的模擬，我們就能知道選擇第一個走法的是否“好”。
這兩個得分value network（評估局面）和rollout（蠻力計算）是加權平均起來的，論文裏好像説最優值是0.5？也就是兩個因素都很重要。
所以可以看出，越到後面殘局，變化就越少，模擬的步數也越少，就越準確。而開局的話rollout肯定不準，那麼更多的是靠人類高手棋譜對局學出來的“大局觀”，而越到後面計算就越準了，它就起主要作用了（那理論上是不是兩者的權重動態調整會更好？）
所以我覺得AlphaGo的開局在上帝看了應該也是挺弱的，也許上帝在它下了一步之後就呵呵一笑：你輸了1目棋了。
4. 那人類的開局呢？
我覺得人類超一流的高手可能比AlphaGo強那麼一點點（畢竟AlphaGo只是用大量一流高手的對局），但是在上帝看來可能比隨機下棋只是好那麼一點點。所以經常會出現這樣的情況：這個佈局之前很流行，大家都認為很好，但過了若干年後又認為不好了。
5. 人類/機器是怎麼自學提高自己呢？
理論上如果計算和存儲資源足夠，比如最後10步可以精確計算，那麼我們就可以存儲所有10步之內結束的局面的結果（有點像殘局庫），但是這個局面太多，只能用一個模型來“壓縮”這些結果，提取一些重要的feature來代表局面，這些feature可能就是我們説的勢啊，厚薄等等（當然也可能機器學到的feature完全不同）。假設這個模型能99%的準確率預測最終得分。然後再計算11步的所有局面（用的是模型來打分，因此準確率99%），然後又得到更多的訓練數據，重新調整模型，這個時候可能就只有98%的準確率了（因為局面變多），再加上之前累計的誤差，總的準確率是99% * 98%，...，然後不斷的反向傳播到開局。如果這麼一算，我們開局第一步能算準的概率基本就是0了。
所以我們人類這麼幾千年這樣學習得出的一些經驗會經常被推翻，幾十年前認為好的開局可能現在認為不好，但過幾十年可能又認為好。説白了就是我們離上帝的距離有些太遠。
6. AlphaGo強在哪？
從上面的AlphaGo原理的分析來看，AlphaGo比人類強的也只是在計算力上面，但是圍棋的分支因子太大，步數又多，而且估值函數太複雜，所以只能在殘局上體現出計算力的優勢。而開局甚至中局計算力都不行，因此早期基於mini-max(alpha-beta)的搜索根本不行，後來出現了MCTS，但開局和中局虧得太多，所以基本沒到殘局就遊戲結束了。
AlphaGo的特點是開局和中局模擬人類，從上帝的角度來説不一定好，但是至少在人類高手看來還可以（即使會下一些人類認為“業餘”的走法，但也不至於太離譜），只要不在殘局前崩盤，輸得不太多，那麼殘局它總是能追回來。
7. MCTS和深度神經網絡(CNN)哪個重要？
因為深度神經網絡非常火，大家可能覺得它是AlphaGo能贏的關鍵，其實我覺得不是這樣。
根據Tian yuandong和AlphaGo的論文，如果不做任何搜索，只是根據“棋感”（其實就是估值函數），CNN最好能達到KGS 3d的水平，我估計也就業餘1段的水平。而MCTS算法在沒有Value Network的情況下在9*9的棋盤上能戰勝人類高手，其實這也間接印證了AlphaGo在殘局的實力是搜索(計算）起重要作用。原來基於搜索的軟件在開局和中局就崩盤或者虧太多了，所以就不能體現搜索的優勢了，另外AlphaGo使用了Value Network，這保證即使搜索有一些小問題，從人類學來的棋感也能保證不至於偏差太大。
AlphaGo的特點是：開局和中局依靠人類的棋譜學習棋感（可以理解為背棋譜，不過比死記硬背好一點，有一定的泛化能力），然後殘局的計算能力碾壓人類，就好像以前的李昌鎬，前面看不出什麼好來，但官子你就是下不過他，沒辦法，不服不行。
8. AlphaGo能成為圍棋上帝嗎？
我認為AlphaGo離上帝（最優解）其實還是差得老遠的，尤其是開局和中局。其實這也間接的説明人類在開局上其實也離最優解差得太遠。人類幾千年也下不了多少盤棋（而且水平越差的人的棋對整個人類圍棋沒有太大幫助），我們認為一個開局是否好，只能更加水平相似的高手下這個佈局的勝率來推測它的好壞。但如果我們在最後50步的時候誤差就很大，那麼往前傳播時積累的誤差就更大了，我們可能經常忽略了一個看起來不好的走法，而這個走法可能就是“支持”這個開局的關鍵。
當然AlphaGo的殘局比人厲害，那麼就可以通過自己對弈來學習，然後往前傳播誤差。
因此如果人類不能解決NP問題，不能提出計算能力超過圖靈機的計算模型，那麼人類製造的機器也是不太可能解決這個問題的（當然這只是我的直覺，不知道能不能數學上證明）。不過即使這樣，能製造和人類一樣，雖然質不能超越人類，但量能超越人類的機器也是很有意義的。
9. 怎麼能驗證你的這些看法？
新聞説AlphaGo提前30分鐘認為自己必勝，這是個很強有力的證據，我們看看30分鐘還有多少棋，可以估算AlphaGo自認為能算準多少步。
那麼作為人類選手，應該怎麼和AlphaGo下棋呢？
我覺得可以試試的策略就是中前期利用自己超一流的棋感儘量佔優，然後殘局導向簡單變化的局面。開局不要被怪招嚇到，我們認為是弱手就要嚴厲打擊，我覺得機器的開局不怎麼樣。當然我不懂圍棋，只是從程序員的角度的個人看法。
資料來源：雷鋒網
作者/編輯：Ticwear
（via wildfirepr.com）
比賽之前根據論文裏的技術來分析AlphaGo能否戰勝李世乭，我們可能太過關注深度神經網絡而忽視了MCTS的重要性，尤其是它在殘局裏的重要性。前天比賽結束後我們重新審視了AlphaGo的兩大核心技術，認為殘局是AlphaGo制勝的關鍵。昨天晚上看到新聞説AlphaGo在比賽結束前就確認了必勝的結果，更加證實了這個想法可能是對的，所以想把這個觀點分享出來。
下面是具體的內容：
經過第二局比賽之後，我已經變得悲觀了。因為我覺得在殘局的計算能力上人類與AlphaGo的差距太大了。
1. 上帝眼中的圍棋
從數學上來講，圍棋有個最優的走法，也就是用mini-max搜索到遊戲結束時的一條最優路徑（也許有多條，但至少有一條），然後就能知道最優的情況下黑棋勝白棋多少目（也許是白棋勝黑棋？直覺上和經驗上來説黑棋先手是佔優的，但是好像也沒有誰證明過這個問題？），那麼黑棋對白棋的貼目就應該是這個最優值。
2. AlphaGo的殘局計算
和人類相比，AlphaGo的殘局計算有點太Bug了。
比如説AlphaGo可以計算出最後50步棋（這裏只是假設的步數，而且MCTS不是完全搜索所有可能，而是根據先驗概率和搜索結果調整策略，搜索“重要”的子樹），而人類只能計算最後30步棋。那麼即使在第50步的時候人類選手領先10目（已經去掉貼目），那麼也只是説人類在100%精確地走好每一步的時候才能勝。但是圍棋很複雜，也許走第50步時走個次優的走法，領先就變成了8目，如果再走得緩一點，可能就只領先6目了。而因為人類只能計算最後30步棋，那麼這50-31步的一點點失誤可能都會造成最終的失利。
當然我對圍棋不懂，也許圍棋沒有想象的複雜，它的估值函數還是比較平滑的，或者在這50-31步中大部分局面都很容易直接找到最優解，但是某些局面就困難一些（也就是關鍵的點）。但是我覺得這樣的關鍵點還是很多的，因為圍棋和象棋不同，圍棋隨便挪動一個棋子，對全局都是有影響的。象棋雖然在某些特殊情況下一個棋子的位置會影響最後的勝負，但是大部分局面下走一步閒棋影響都不大，尤其是雙方棋子較少的中殘局。
比如説人類高手的判斷局面的準確率是AlphaGo的90%（90%能不計算憑“感覺”直接找到當前局面的最優解，1是AlphaGo的準確度，上帝可能是2？），那麼20步全部正確的概率只有0.12（相對於Alphago來説）。如果兩個人殘局的計算能力差太遠，而且積累的優勢不是太多的話，除非碰到的殘局很簡單，第50步-31步憑感覺就能找到最優解（或者次優解與最優解的差別很小，但感覺上圍棋不像象棋。象棋如果優勢，比如比對方多兩個兵，那麼走一兩步緩手（只要別太差，讓人吃子了），最終還是很可能會贏（當然也有某些特殊的局面必須要走的精確）。但圍棋如果稍微幾個緩手，優勢就丟了很多。
引用所以如果殘局計算力差太多的話，前中盤有差不太多的話，那麼人類是不太可能勝利的。
3. AlphaGo的開局呢？
引用AlphaGo的計算有兩個關鍵，一個是Value Network，也就是給定一個局面，不計算，直接判斷它的好壞（也就是上帝的視角來看，大家都下得完美，黑棋能比白棋多/少多少目），另外一個就是通過不斷的蒙特卡羅模擬比賽到遊戲結束(rollout)。
這其實和人類的搜索有些類似：比如當前局面下有10種走法，我們根據好壞(alphago是rollout Policy，這個需要非常快）給它計算一個概率，比如0.4，0.3，0.1，.....，那麼它就會以較大的概率選擇0.4的走法來嘗試，當然也有0.3的概率走第二個。之後每一步都是一樣的方法選擇走法直到遊戲結束，然後就能判斷這個遊戲結束局面的準確值。比如我方勝利了，那麼就會backup回去，讓我們下次選擇0.4的概率更大一點，也許變成了0.45，0.28， 0.09，...。經過大量的模擬，我們就能知道選擇第一個走法的是否“好”。
這兩個得分value network（評估局面）和rollout（蠻力計算）是加權平均起來的，論文裏好像説最優值是0.5？也就是兩個因素都很重要。
所以可以看出，越到後面殘局，變化就越少，模擬的步數也越少，就越準確。而開局的話rollout肯定不準，那麼更多的是靠人類高手棋譜對局學出來的“大局觀”，而越到後面計算就越準了，它就起主要作用了（那理論上是不是兩者的權重動態調整會更好？）
所以我覺得AlphaGo的開局在上帝看了應該也是挺弱的，也許上帝在它下了一步之後就呵呵一笑：你輸了1目棋了。
4. 那人類的開局呢？
我覺得人類超一流的高手可能比AlphaGo強那麼一點點（畢竟AlphaGo只是用大量一流高手的對局），但是在上帝看來可能比隨機下棋只是好那麼一點點。所以經常會出現這樣的情況：這個佈局之前很流行，大家都認為很好，但過了若干年後又認為不好了。
5. 人類/機器是怎麼自學提高自己呢？
理論上如果計算和存儲資源足夠，比如最後10步可以精確計算，那麼我們就可以存儲所有10步之內結束的局面的結果（有點像殘局庫），但是這個局面太多，只能用一個模型來“壓縮”這些結果，提取一些重要的feature來代表局面，這些feature可能就是我們説的勢啊，厚薄等等（當然也可能機器學到的feature完全不同）。假設這個模型能99%的準確率預測最終得分。然後再計算11步的所有局面（用的是模型來打分，因此準確率99%），然後又得到更多的訓練數據，重新調整模型，這個時候可能就只有98%的準確率了（因為局面變多），再加上之前累計的誤差，總的準確率是99% * 98%，...，然後不斷的反向傳播到開局。如果這麼一算，我們開局第一步能算準的概率基本就是0了。
所以我們人類這麼幾千年這樣學習得出的一些經驗會經常被推翻，幾十年前認為好的開局可能現在認為不好，但過幾十年可能又認為好。説白了就是我們離上帝的距離有些太遠。
6. AlphaGo強在哪？
從上面的AlphaGo原理的分析來看，AlphaGo比人類強的也只是在計算力上面，但是圍棋的分支因子太大，步數又多，而且估值函數太複雜，所以只能在殘局上體現出計算力的優勢。而開局甚至中局計算力都不行，因此早期基於mini-max(alpha-beta)的搜索根本不行，後來出現了MCTS，但開局和中局虧得太多，所以基本沒到殘局就遊戲結束了。
AlphaGo的特點是開局和中局模擬人類，從上帝的角度來説不一定好，但是至少在人類高手看來還可以（即使會下一些人類認為“業餘”的走法，但也不至於太離譜），只要不在殘局前崩盤，輸得不太多，那麼殘局它總是能追回來。
7. MCTS和深度神經網絡(CNN)哪個重要？
因為深度神經網絡非常火，大家可能覺得它是AlphaGo能贏的關鍵，其實我覺得不是這樣。
根據Tian yuandong和AlphaGo的論文，如果不做任何搜索，只是根據“棋感”（其實就是估值函數），CNN最好能達到KGS 3d的水平，我估計也就業餘1段的水平。而MCTS算法在沒有Value Network的情況下在9*9的棋盤上能戰勝人類高手，其實這也間接印證了AlphaGo在殘局的實力是搜索(計算）起重要作用。原來基於搜索的軟件在開局和中局就崩盤或者虧太多了，所以就不能體現搜索的優勢了，另外AlphaGo使用了Value Network，這保證即使搜索有一些小問題，從人類學來的棋感也能保證不至於偏差太大。
AlphaGo的特點是：開局和中局依靠人類的棋譜學習棋感（可以理解為背棋譜，不過比死記硬背好一點，有一定的泛化能力），然後殘局的計算能力碾壓人類，就好像以前的李昌鎬，前面看不出什麼好來，但官子你就是下不過他，沒辦法，不服不行。
8. AlphaGo能成為圍棋上帝嗎？
我認為AlphaGo離上帝（最優解）其實還是差得老遠的，尤其是開局和中局。其實這也間接的説明人類在開局上其實也離最優解差得太遠。人類幾千年也下不了多少盤棋（而且水平越差的人的棋對整個人類圍棋沒有太大幫助），我們認為一個開局是否好，只能更加水平相似的高手下這個佈局的勝率來推測它的好壞。但如果我們在最後50步的時候誤差就很大，那麼往前傳播時積累的誤差就更大了，我們可能經常忽略了一個看起來不好的走法，而這個走法可能就是“支持”這個開局的關鍵。
當然AlphaGo的殘局比人厲害，那麼就可以通過自己對弈來學習，然後往前傳播誤差。
引用但是由於這個問題本質是NP的，即使它用了MCTS的方法來避免“明顯不好”的走法。但是由於圍棋的複雜性，可能某個“看起來不好”的走法可能恰恰是一個關鍵的勝負手呢？另外根據之前的分析，即使每步都能99%的準確，那麼往前推100步準確的可能性也基本是0了。
因此如果人類不能解決NP問題，不能提出計算能力超過圖靈機的計算模型，那麼人類製造的機器也是不太可能解決這個問題的（當然這只是我的直覺，不知道能不能數學上證明）。不過即使這樣，能製造和人類一樣，雖然質不能超越人類，但量能超越人類的機器也是很有意義的。
9. 怎麼能驗證你的這些看法？
新聞説AlphaGo提前30分鐘認為自己必勝，這是個很強有力的證據，我們看看30分鐘還有多少棋，可以估算AlphaGo自認為能算準多少步。
引用方法一，看接下來3盤棋，如果都是人類覺得李世乭走得還可以或者稍微領先，最後都翻盤，那麼就是一個證據。
方法二，人類和AlphaGo下開局和中局，然後到了AlphaGo認為可以比較準確計算的時候讓它來評估好壞。
方法三，找一盤人類認為可以但是被翻盤的局面，然後人類和AlphaGo換個顏色來下，如果還是AlphaGo獲勝，那麼也是一個證據。
方法四，看AlphaGo對自己的打分，是不是有出現過認為自己落後，後來又領先。
那麼作為人類選手，應該怎麼和AlphaGo下棋呢？
我覺得可以試試的策略就是中前期利用自己超一流的棋感儘量佔優，然後殘局導向簡單變化的局面。開局不要被怪招嚇到，我們認為是弱手就要嚴厲打擊，我覺得機器的開局不怎麼樣。當然我不懂圍棋，只是從程序員的角度的個人看法。
資料來源：雷鋒網
作者/編輯：Ticwear