作者indium111 (原子核的奧秘)
看板GO
標題Re: [好文推薦] 這兩盤棋 沒人會比李世石做得好
時間Fri Mar 11 21:12:59 2016
※ 引述《nnlisalive (nnlisalive)》之銘言：
: ※ 引述《raiderho (冷顏冷雨)》之銘言：
: : 依本文說法，AlphaGo的臭棋 (人類認定) 有三種可能性，而且都已經發生了：
: : 其一，在電腦判定的獲勝機率已經非常高時，
: : 不同下法對機率的影響會鈍化，可能只是99.9%與99.91%的差別而已，
: : 而算法設計可能會讓非最佳解更容易被隨機挑到。
: : 這種非最佳解，就是真正的臭棋 (邏輯上為嚴格劣勢策略)。
: : 然而，若以上敘述為真，當電腦下出明顯臭棋時，電腦應該已經大幅佔優了。
: : 相反的，情勢還在膠著時，下錯會讓獲勝機率大幅降低，
: : 臭棋被挑中的機率近乎為零，這時，我們會看到非常緊繃的對局。
: : 這一點呼應「遇強則強，遇弱則弱」。
: : (最後一句不是指李和樊的差距，因為電腦棋力這幾個月增加不少)；
: 我覺得要從程式碼方面下手了
: 首先就是阿發狗所謂的"勝率"是怎計算出來的?
: 不外乎用盤面上所得到的資訊轉換成數據
: 再代入勝率函數得到每一點的勝率
: 那這個函數適用於任何盤面嗎? 沒有任何邏輯漏洞和盲點?
: 算出來的勝率沒有誤差? 如果有個點勝率是70%
: 具體來說應該是下了這個點跑到結束N次 有0.7*N次會贏
: 但明明就還沒下完 也不知道對方會怎下
: 所以只要能騙過電腦 讓他一直下到誤判勝率的棋
: 阿發狗就會輸到怎死的都不知道了
: 問題是要怎騙過阿法狗?
: 我 不 知 道 !
以前的圍棋程式所用的蒙地卡羅演算法
它的原理簡單的說
就是在目前的棋盤上，下了某一子之後
隨機開始落子，直到最後一子結束
最後判斷是黑勝還是白勝
之後重複N次的隨機落子，然後看這N次裡面，黑勝幾次，白勝幾次
這樣就可以判斷下這一子的勝率為何
當然我們知道，黑白相互交錯隨機落子，變化總共有361!=10^768
就算是雙方各下100步之後的情勢，也還有161!=10^286
基本上都是超級天文數字，電腦不可能做全部的隨機事件
所以電腦基本上只能做到有限的N次隨機次數
基本上圍棋盤面的真正變化次數跟電腦運算可隨機的次數差距越小
獲得的機率數值就越可能接近正確值
https://youtu.be/KMkjtZtGBsE
(網路有用蒙地卡羅法求π，看完大概就可以了解以上這段)
所以以前的圍棋程式
在初期布局的時候常會下出讓人類覺得很可笑的布局
越到後面變化越少時，則正確率越高
AlphaGO當然是超級進化版
它利用了類神經網路的學習，參考了人類棋譜
並自己跟自己對下累積了數千萬盤棋
練出了所謂的"直覺"，可以把一些荒謬的落子排除掉
(例如第一手八七這種荒謬的棋步)
大幅度減少了隨機事件，使得演算法推估勝率能更為準確
真正理論上的「圍棋上帝」是使用窮舉法的暴力演算
其運算變化是個天文數字，依照目前的電腦是辦不到的
所以AlphaGo絕對不是「圍棋上帝」
不過也不要因此小看了AlphaGo
簡單的問題讓大家想想吧
A=(10^768- 10^265)/(10^768)
A這個數字我們都知道不是100%，但它跟100%有什麼不一樣?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.134.57.127
※ 文章網址: https://webptt.com/m.aspx?n=bbs/GO/M.1457701983.A.E5D.html
※ 編輯: indium111 (220.134.57.127), 03/11/2016 21:16:04
1F：推 birdy590: 其實這後面的技術並不困難, 接下來幾年不是不可能出現 03/11 21:18
2F：→ birdy590: 超車的...(會有多少人做這個畢業呢?) 03/11 21:18
3F：→ aaaba: 技術多困難不談，消化數據沒個像樣的硬體會等死人 03/11 21:21
4F：推 birdy590: 已經很多大公司在投資啦, 其實人事成本比硬體貴呢 03/11 21:23
5F：→ milkdragon: 1. 你略過了最重要的搜尋步驟(tree search); 2. 模擬 03/11 21:24
6F：→ milkdragon: 棋局並非隨機落子，若無圍棋知識輔助，局勢評估必定不 03/11 21:24
7F：→ milkdragon: 準確 03/11 21:24
AG當然不是純粹的蒙地卡羅法，不然早就被電爆了
8F：→ birdy590: 標準的 MCTS 是隨機落子沒錯, 但是這樣同樣很沒有效率 03/11 21:25
9F：→ birdy590: 在這裡引進神經網路評估函數很高明, 太瞎的棋直接先跳過 03/11 21:25
10F：推 sck921: 可是「直覺」有沒有可能排除掉真正的好棋？ 03/11 21:26
你這個問題大概只有真正的「圍棋上帝」可以回答
大家愛講的第一手天元，或許是步妙手也說不定
11F：→ birdy590: 所以幾個網路的訓練很重要, 從這裡也不難理解 03/11 21:28
12F：→ sck921: 我把直覺假設成人類的棋感，那電腦會犯和人類一樣的錯嗎？ 03/11 21:28
13F：→ birdy590: 為什麼在領先的狀況特別容易下出臭棋(OS: 還是贏你管我) 03/11 21:28
14F：→ birdy590: 這裡的"直覺"只影響評估順序而已, 時間內有算到就不會漏 03/11 21:29
※ 編輯: indium111 (220.134.57.127), 03/11/2016 21:29:52
15F：推 liaon98: 單純用蒙地卡羅法的話 之前的軟體就這樣 只能到業餘4 5段 03/11 21:29
16F：→ milkdragon: 原po描述的只是「蒙地卡羅法」，只是MC，不是MCTS 03/11 21:34
17F：→ milkdragon: 這跟AG用什麼方法無關，因為你說的是「以前的程式」 03/11 21:36
我開頭的時候就說這是以前的演算法啊
因為要回答前面的人所問的勝率是如何計算的
※ 編輯: indium111 (220.134.57.127), 03/11/2016 21:38:09
18F：→ birdy590: 其實後面的原理跟電腦棋類剛開始的時候一樣沒有變過 03/11 21:36
19F：→ birdy590: 當然還是要建決策樹, MCTS 只是維護這棵樹的方法而已 03/11 21:37
20F：→ birdy590: 在這之前只有 alpha-beta pruning, 這用在圍棋上不能看 03/11 21:38
21F：→ birdy590: 在這之前電腦西洋棋/象棋也已經開始用 heuristic search 03/11 21:40
22F：→ birdy590: 來減少計算量, 所以現在連手機上棋力都可以強到不行 03/11 21:41
23F：→ indium111: 以後alphago的後代裝進手機也不是什麼問題 03/11 21:43
24F：→ birdy590: 圍棋的空間太大 想縮到這種程度恐怕有點困難 XD 03/11 21:44
25F：→ indium111: 到時候可能要禁止圍棋選手外出上廁所和散步了 03/11 21:44
26F：推 lwei781: 手機可以雲端啊 03/11 22:46
27F：推 bearching: 雲端運算應該可以辦得到? 03/11 23:16
28F：→ indium111: 不要小看電腦硬體進步速度，你手中的iphone 6就比打敗 03/11 23:31
29F：→ indium111: 當年西洋棋王的深藍電腦還快了 03/11 23:32