Re: [問題] alphago已經超越樹狀圖設者?

[F23ko (名無乚)]

: 樹狀圖設計者-->硬體
: 現代AI-->軟體
: 除非妳要探討的是
: 普通軟體+極限硬體 vs 大幅優化軟體+普通電腦
: 那就需要實際數值了，需要更專業的人來解答

我把我前一篇的概念，用簡單易懂的方式再說一次好了

順便讓大家都能挑戰一下樹狀圖設計者

樹狀圖設計者下圍棋能不能下贏 AlphaGO 我不確定

但是乘法問題，只要計算程式是用暴力法計算的話，我敢保證人類一定算的贏

也讓大家體驗一下「演算法」 vs 「硬體計算能力」的差異在哪裡



舉例來講，一方通行講的

1*10 = 10 用 1+1+1+1+1+1+1+1+1+1=10 來計算

我出個數學題目，大家來算一算：

1*1000000000=?



我寫一段程式，用 1+1+1... 的形式，來算這個問題
  sum = 0
  startT =Time.now
  for i in 1..1000000000
      sum+=1
  end
  endT =Time.now
  puts sum
  puts endT- startT 


程式語言是 Ruby

雖然Ruby在執行速度上很悲劇

跟 java c++ javascript(用V8) 比起來，慢了兩個零到四個零的倍數

但是Ruby計算天文數字不需要去處理溢位

所以選她來寫這段程式

http://f23.tw/F7uX.jpg

而且在這個例子中，語言不是問題



1*1000000000=? 的問題

我相信大家應該都在1秒內就算出來了

如果再把寫答案的速度算進去，算10秒好了

再怎麼樣都是30秒內的事情吧？




但那程式在我自己的電腦上的計算結果，卻是

  1000000000
  56.562931939

程式算了大約56.56秒

你沒看錯，就是花了 56.56 秒

雖然每台電腦運算時間會不同

但計算時間基本上都會跟數字大小成正比


也就是說，只要在

  for i in 1..1000000000 

後面再多加一個零，計算時間會暴增10倍

如果你的電腦太快，你可以多加幾個零，直到你算題目的速度比電腦快為止

即使你用的電腦是樹狀圖設計者

也一樣可以找到一個夠大的數字，讓樹狀圖設計者算的比你慢




相關的理論的關鍵字，是「時間複雜度」

有興趣的人可以去 wiki 一下


樹狀演算者的暴力算法，是 O(n)，意思是計算時間與數字大小成正比

人類計算計算 1*n，是 O(1)，意思是不管數字大小，計算時間都一樣


由此可推論

像剛剛那個題目，一定有個數字，可以讓樹狀圖設計者算輸人類



至於 樹狀演算者 vs AlphaGO 下圍棋誰會贏

這很難回答，因為樹狀演算者的計算能力是未定值

而圍棋的複雜度是固定數值

在有一方是未知數的狀況下，這個問題不會有答案



但如果是像作者一味的強調樹狀設計者的運算能力

還特別強調使用用暴力運算的話

我很肯定樹狀設計者在基本的計算問題上

都會輸給一台個人電腦



: 普通軟體+極限硬體 vs 大幅優化軟體+普通電腦
演算法是「方向」的問題

計算能力是「力道」的問題

方向不對，自然要花很大的力氣才能做到同樣的事情

甚至完全做不到

就像是門版上寫「推」的門，硬是要用拉的去開，的那種感覺



在小問題上，不會有太大的差距

但問題一大，硬體頂多加速幾千到幾萬倍

演算法可以讓「運算時間與數字大小成正比」變成「常數」

就像是上面我舉的例子

  1*10000000000000000000 = ?

這一題用我電腦以及剛剛那隻程式，要算大約 1500 年

但是人類算這個問題，還是一樣，不到一分鐘



--


                       我... 我一點都不糟糕啦！>///<


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.87.115
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1457687940.A.79D.html
推 LABOYS: 很久沒看到你，一來就好認真啊 XDD
推 xji6m3vm0: 好吧..我覺得我發的文有點偏了..
→ xji6m3vm0: 會用暴力運算舉例的原因是這樣好懂..
→ xji6m3vm0: 作者可沒設定只能暴力運算阿
推 GOBS: ag的設計師有說 他會自動放棄推演中出現一定劣勢的棋路
→ GOBS: 光是這點就屌打暴力算法了 能適時放棄代表有更多時間去處理
→ GOBS: 有機會贏的棋路
→ xji6m3vm0: 會提那個是因為作者設定的運算能力太瞎了用暴力都會贏
→ F23ko: to xji6m3vm0: 癥結點就在這裡啊，作者強調了暴力運算的能
→ F23ko: 力，還寫出模擬所有空氣分子之類的東西，就會讓人以為樹狀
→ GOBS: 看第二場就知道 右上角ag放棄六顆黑子 剛開始賽評還以為他下
→ GOBS: 錯 結果算出來去搶中間賺更多
推 orze04: 要國中生理解蒙地卡羅 AB剪枝太過份了
→ F23ko: 只會用暴力運算啊。實際上的狀況會是，一個問題大到不行，
→ F23ko: 行，又極度優化演算法之後，還是需要大量的運算能力，才會
→ F23ko: 丟去給超級電腦算的。
→ miname: 拜託不要來亂了 O(n)算暴力解啊
推 zizc06719: 結果你標題一點都不重要啊XD 你只是想點出演算法的重要
→ zizc06719: 性
推 iamnotgm: 講真的和馬自己都沒搞清楚暴搜是怎麼回事我們在這裡都是
→ iamnotgm: 喇低賽阿w
推 kinuhata: 我看河馬自己也搞不清楚這些東西 否則也不會寫出一堆可
→ kinuhata: 笑的物理概念
→ F23ko: 是不是暴力要看狀況啦 有些優化解法都已經是 O(N*logN)了呢
推 reinhert: 如果複雜度只有O(n)都還算好，最怕的就是O(n^m)這種啊
推 LayerZ: 可是AlphaGo主要是屬於類神經網路類型，最重要的部分就是
→ LayerZ: 學人類如何避免暴力解法
→ LayerZ: 雖然跟這篇已經沒啥相關了XD
→ dreamnook: 推樓上...
推 Entropy1988: 蒙地卡羅或AB剪枝 其實國中生也可以略懂耶
→ Entropy1988: 寫科幻小說被要求要對題材有所掌握是當然的，不過我
推 agreerga: 所以AG可以秒達這則運算嗎XD
→ agreerga:           答
→ agreerga:             答
→ Entropy1988: 不會期待作者一定毫無破綻。比較讓我注意的是他周遭
推 tsubasawolfy: AG後期也會轉向窮舉吧 這樣比較節省時間
→ tsubasawolfy: 你看第二場最後都是 30秒下一目y
→ Entropy1988: 沒有人幫他審稿嗎，針對科學的部分？
→ tsubasawolfy: 反正接近收尾 變化小就可以用暴力法 這種彈性才好
推 GOBS: ag會窮舉阿 可是中盤窮舉絕對不是好事 真的到收官時窮舉比
→ GOBS: 較穩
→ gmoz: 沒有優化才會用1+1的方式去解乘法吧XDDD
→ LayerZ: 那你要如何讓AI自己去找1+1以外的算法XD
推 reinhert: AlphaGO演算法就擺在那邊不會變，但當展開空間越少就越
→ reinhert: 有可能接近窮舉法
推 Edaw: https://www.zhihu.com/question/39905662
→ gmoz: 你在設計AI的時候就會考慮進去啦
→ Edaw: 就文中所提的P_human()與P_human_fast()阿!
推 tsubasawolfy: 和馬寫魔禁好像是高中的時候...
→ LayerZ: 你的回答是指人類優化，但是要如何讓人類優化以外自己去找
→ Edaw: 0.3ms與2us的差距
推 BanJarvan4: ag會學習吧 第一次很爛 但會越算越快
→ gmoz: 我只是覺得舉例問題，基礎運算不用AI一般編譯器就有優化XD
→ gmoz: 以這篇精神能找類似的例子不會多 就算有我覺得也是慢慢會解
→ LayerZ: 人家是舉例咩 = =
→ gmoz: 但是當你很難舉出真的例子，就知道其出現的機率了
→ LayerZ: 不，舉1+1是因為他是極簡化的例子而以阿~_~
→ gmoz: 就算是真的1+1+1 真的很笨，弄成類似MAP/REDUCE去跑也會很快
→ F23ko: 演算法真的很常遇到，我上次做的是搜尋，你可以想像是，從
→ gmoz: 限定問題領域再限定解法 = 人類一定贏，我覺得已經偏掉了www
→ F23ko: 一堆文章，大概幾千萬字中去尋找特定的字，我程式下去，一
→ gmoz: 我覺得解答就存在河馬他的理工腦的程度啦XD
→ F23ko: 小時多.... 結果換用 Suffix Tree 的方式，億開始先掃過一
→ Entropy1988: 傳奇的熱膨脹也是高中寫的嗎？
→ F23ko: 次全部文章，之後搜尋，都不用一秒結果就出來了。
→ gmoz: 對阿w 一定要先建個索引吧 至少有個inverted index也好
→ gmoz: AI自行找演算法的功力 其實進步很快了 阿法狗也會自己找解法
→ F23ko: 電腦充其量只是工具，至少目前都還只是工具，跟電腦起競爭
→ oread168: 電腦很笨R
→ gmoz: 同意找演算的功力這部分目前還是人類還是屌打的
→ F23ko: 心態太奇怪了。該競爭的對象是把計算方式寫出來的工程師
推 Edaw: 平行運算也要看問題的平行度  首先計算1*100000000000透過
→ Edaw: map/reduce計算  要有人類快也要有相應的超級多硬體成本
→ gmoz: 應該說是 "計算方式寫出來後讓他自己去長的AI"
→ Edaw: 這硬體成本本身要跟問題複雜度同個數量集  且前提是此問題要
→ Edaw: 可適用於平行
→ gmoz: 所以討論到這個就偏掉啦  要提提不完 何況河馬的理工程度
→ gmoz: 對設定上面 我們根本沒辦法得知太多XDDD
→ Edaw: 而且若是1*100000000000 = 1+1+...+1的問題  人類是O(1)
→ Edaw: 你用map/reduce也僅能得到O(logn)吧!
→ Edaw: 每個CU都只運算1+1一次可以把運算量減半
→ Edaw: 第二個問題變2+2+..+2  高度會是O(logn)
→ Edaw: 代表要算logn次
→ Edaw: 次與次之間因有相依性所以無法透過平行去做優化  再多硬體都
→ Edaw: 沒軟用
推 gmoz: 搞不好學園都市有999999999PHz的CPU啊XD
推 Entropy1988: ↑一直想提的一件事就是 先把性能參數喊出來就輸了
推 pusufu: 可是人類會少寫好幾個0
→ Entropy1988: 因為喊出來以後，就可以說它在什麼條件下會輸。反之
→ Entropy1988: ，若一直沒喊出來，就可以無限膨風，立於不敗之地。
推 cangming: 窮舉法遇到連續函數就gg了 更不要講機率性運算 是不可能
→ cangming: 的事
推 Seeker7: 和馬可能連國中理化都有問題，別要求太多了XD
推 crazylin924: 快推 不然別人以為我看不懂
推 bitcch: 我覺得和馬搞不清楚硬體跟演算法的差異
推 Dkuei: 我怎麼覺得ai 討厭複雜度有點怪 類神經的複雜當你決定完結
→ Dkuei: 構後就固定了