西洋棋軟體大勝 - 西洋棋

這是舊消息了，不過還是PO一下自己的心得。
最近人類高手Michael Adams(世界第六，外號spider，擅長佈陣)
和電腦高手Hydra(一秒想2*10^8個node)有一場較量，比六局，
結果人類慘敗(只和了一局，其他全敗)。

我算了一下電腦的深度和思考精確度，感到非常訝異，計算如下：

已知 1s 想 2*10^8 nodes
先估 1 ply 平均只想 5 nodes
=> 10 plies 則是約 10^7 nodes
=> 12 plies 約需 1.22s
=> 152.6s 可想 15 plies
(其實還要乘上 (1+1/5+1/25...)=5/4，即約 191s ~= 3m11s )

接近hydra的用時(2h 想 40 步，一步 3m)
而且可以利用對手的時間偷想，如果猜對對方的下一著棋，則可以得到兩倍的時間，
如果猜中的機率是1/2，則等於 3h 想 40 著，1 著就有 4.5 m 可想。但有風險，
所以還是想 3m 就好。

1 ply 平均只想 5 nodes 這已經很厲害了
(30~40個可能性它只挑5個看就知道其他不用看了)(不過當然還是和人類沒得比)，
但是hydra絕對不只想 14 plies。我看到它有一步棋至少要想 14 plies 才有把握下
(match 5 的 Re6)，而且一般GM也不只想 14 plies，而hydra比GM更會算。
所以如果 1 ply 只想 4 nodes(haha這個好算)：

=> 10 plies 則是 4^10 ~= 10^6 nodes
=> 14 plies 則是 256*10^6 nodes
=> 約需 1.28s(秒殺 14 plies!)
=> 17 plies: 160s
=> 再乘1.33: 約 213s = 3m33s

但在我感覺 16~17 plies 應該也不是什麼難事‥‥
試試 20 plies 是怎麼達成的吧‥‥
假設 1 ply 只想 3 nodes(!)：

=> 18 plies 需要 387420489 nodes
=> 但其實要想(再乘1.5) 581130733.5 nodes
=> 約 2.9s
=> 所以其實可以再想 4 plies：3m55s

所以大概可想 21~22 plies‥‥

天哪，這真是太可怕了‥‥可怕之處不在於想多少plies，
可怕之處在於對nodes選擇的精確‥‥
居然只想3~4個可能性而已！！(再次強調，再怎麼樣也沒有人類準！！)

而且 1s 要想 2*10^8 nodes，以 2GHz 的機器來說，1 node 只用到10個指令，
一定要用assembly！而且不可以只有一個CPU！
平均每個棋子的分數計算應該用很少的指令就夠了吧，
主要的指令是在處理亂七八糟的局勢判斷。


唉，我看象棋的日子也不遠了(許x川皮繃緊一點)，大家來下圍棋吧‥‥

後記：好像太扯了‥‥坦白說，想 20 plies 真的是太強了，人類應該連和棋都很難。
目前應該是想5 nodes，然後利用對方思考的時間偷想，
並且根據目前所剩時間來決定下一步的用時，所以也許可以接近 16~17 plies。

其實硬體上DEEP BLUE就已經很強了，hydra厲害的地方該在於更大的開局資料庫、
更強的殘局(六盤中有幾盤是電腦靠殘局墊人類‥‥真慘)、更精準的盤面分析。
我覺得人類快要看不懂電腦下的棋了‥‥

--