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