作者saltfish (笨魚)
看板GO
標題Re: [新聞] 科學視角解讀 AI3-5年內將贏遍人類棋手
時間Sun Mar 13 10:53:04 2016
: “人機大戰”為什麼選擇圍棋？ 171位數“嚇死你”
: “人機大戰”的興起，最早是1997年，IBM超級電腦“深藍（Deep Blue）” 擊敗了
: 國際象棋大師加里-卡斯帕羅夫。科學界認為，圍棋“人機大戰”可以看成是人工智慧發
: 展具有標誌性的進展。曾經“深藍”的勝利鼓舞了人工智慧研究的士 氣，吸引了投資者
: 對人工智慧的興趣。
: 至於為什麼選擇圍棋，史忠植教授解讀稱：“圍棋之所以很難被人工智慧攻破，戰勝
: 人類高手，就是其可能的組合數異常龐大。至於多麼異常，2016 年1月，普林斯頓的研究
: 人員給出了最新研究結果：對於一個19x19的圍棋棋盤而言，一共有361個位置，而每個位
: 置可以單獨放置黑棋、白棋或者留空，理 論上所有的可能組合是3361種。但根據圍棋規
: 則，不是所有位置都可合法落子，例如在圍棋術語中沒有氣的位置就不能落子。”
: “那麼，排除掉這些不合法的棋局後總共還剩多少種呢？普林斯頓的研究人員給出的
: 19x19格圍棋的精確合法棋局數：
: ‘
: 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
: 。’”
: “171位數！”這個數字比我們地球所有的沙粒數量還要多！比人類已知宇宙的所有
: 星球數量還要多！對比來講，穀歌學習的近萬盤人類棋局是5位 數，谷歌自行對戰的3000
: 萬盤是8位數，而圍棋所有可能的棋局盤數是171位數。如果規避還有可能的重複變化，把
: 大頭去掉，那也是70位數的棋局變化。
錯的
3^361= (黑、白、空) 這個算法對圍棋變化來說 是不對的
3^361 大約等於 1.740897* 10^172 172位數左右
可是圍棋是 黑一子 白一子下
3^361 表示包含了361格 每一格都放黑的 或是每一格都放白的
或是361格全部沒有棋子
在完全不考慮禁手 劫爭的狀況下
圍棋比較接近的變化總數大約是361! = 361*360*359*...*4*3*2*1
=1.43792* 10^768
"768位數" 才是棋盤暴力窮舉還沒砍除garbage node前的大約變化總數
(當然禁手、廢棋可以扣除一大堆變化 劫爭則會增加變化)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.56.242
※ 文章網址: https://www.ptt.cc/bbs/GO/M.1457837586.A.59E.html
→ asglay: 這是論文 可慮的是合法落子跟扣除重複位置 03/13 10:55
→ asglay: 說人家錯之前 可以先看一下人家的論文 03/13 10:55
噓 nnlisalive: 你沒考慮到順序的問題 排列組合請重學 03/13 10:59
→ darkseer: 說真的，我覺得我們要討論數學也要討論些對圍棋高手可能 03/13 11:01
→ darkseer: 有參考價值的，這種末節還是盡量避免佔版面吧@@ 03/13 11:02
→ saltfish: asglay 論文作者沒考慮手順問題 03/13 11:12
→ saltfish: 論文是錯的 03/13 11:13
推 cloudandfree: 這論文真的是錯的 03/13 11:16
→ cloudandfree: 反覆劫爭可能會多上許多變化，例如三劫循環、長生劫 03/13 11:17
→ cloudandfree: 、雙劫…… 03/13 11:17
→ saltfish: nnlisalive 第一手下天元和 第113手下天元 03/13 11:45
→ saltfish: 即使最後盤面完全一樣 它們還是兩盤不一樣的棋 03/13 11:46
→ saltfish: 盤面結果一樣 但手順不同就是不同兩盤棋 03/13 11:49
→ saltfish: 論文計算的盤面數 有些還得黑棋連下3手5手才會達成 03/13 11:51
→ saltfish: 論文是錯得誇張 03/13 11:51
→ asglay: 所以說要看論文囉~ 你說的沒有錯 每個子下的順序不一樣 03/13 12:32
→ asglay: 即使盤面一樣 但還是不一樣的棋 03/13 12:32
→ asglay: 複雜度接近361! 這在演算法裡叫做Game Tree Complexity 03/13 12:35
→ asglay: 問題是這篇論文裡面 它說他們算的是state complexity 03/13 12:36
→ asglay: 也就是不管怎麼下的 我們只看盤面 人家就說他要算這個 03/13 12:37
→ asglay: 有點像是人家說要算1+1=2 你說要算成1*1=1才是對的 03/13 12:39
→ asglay: 變成好像硬要算你自己覺得對的東西 這... 03/13 12:40
→ saltfish: 下圍棋的過程複雜度本來就是 "Game Tree Complexity" 03/13 13:54
→ saltfish: 本來就不該拿state complexity來解釋電腦圍棋的複雜度 03/13 13:56
推 fallcolor: asglay我懂你 不要難過 03/13 13:57