Re: [問卦] 世界三大棋種哪個最難？

看板Gossiping作者derekhsu (華麗的天下無雙)時間5年前 (2020/11/15 20:08)推噓10(10推 0噓 6→)

留言16則, 14人參與討論串2/6 (看更多)

※ 引述《kamelot ()》之銘言： : 世界三大棋種， : 西洋棋，象棋與圍棋， : 最近剛學了西洋棋入門， : 感覺有一堆盤面要記， : 圍棋則是聽說變化最多 : （人類已經輸給AI） : 象棋....我只會玩暗棋。 : 到底世界三大棋種哪一個最難精通？當然是圍棋，毫無疑問。棋類這種雙人有限回合制競賽其決定複雜度的因子就是其可能的狀態種類，也就是說，棋盤各種棋子與位置的組合會有幾種可能性。另外一個因素就是狀態有沒有重複的可能性，上面這三種棋裡面，狀態都是可重複的，例如圍棋中的劫。舉一個沒有重複可能性的棋類，就是五子棋，無論如何下，棋盤與棋子的狀態在一局遊戲內都不會重複。在處理沒有重複可能性搜尋問題的時候，使用的是樹搜尋(tree search)，而在有重複可能搜尋問題時使用的是圖搜尋(graph search)。處理搜尋問題時最簡單的作法是暴力破解法(brute force)，就是將每個狀態進入下一狀態對於勝利的機率影響全部視為相同，然後探索每一個可能的狀態。在搜尋空間很小的狀況下，這個方法能找到全部的解法。那麼，這個問題就等於被破解，因為所有的可能性，所有的變化都已經被探索過了。在早期運算速度還沒有那麼快的時候，象棋跟西洋棋都無法透過純粹的暴力破解法找到所有可能，要其他變形的方式，更有效率地搜尋可能狀態，但是隨著deepblue這種超級電腦算力的出現，找到所有的答案變得可能。 Deep Blue當時的計算能力有多強？他可以在每秒計算2億步，在三分鐘內計算500億個位置，Deep Blue當時根本不是用AI打敗卡斯帕洛夫，Deep Blue是靠算力直接計算出標準答案，棋王勝利的機會根本是0，因為所有的可能性都被Deep Blue全部計算完畢。連MIN-MAX演算法都用不上。象棋的計算複雜度高於西洋棋，因為不管是地圖，棋子數量與種類都比西洋棋多，但這些以現在電腦的能力都可以暴力破解。但圍棋的計算需要的是天文數字，是真正的「天文數字」，暴力破解只有在圍棋的殘局階段因為可探索狀態變少才有效果。開局階段的計算量對圍棋來說是天文數字，所以傳統圍棋AI才會使用人類棋譜作為開局。以人類棋手來說，圍棋的規則最簡單，所以上手也最為容易，但是精通反而越難，因為能推算的深度太淺了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.104.72.167 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1605442113.A.0C7.html

推

cattgirl

11/15 20:09, 5年前 , 1^F

11/15 20:09, 1^F

→

showdoggy

11/15 20:10, 5年前 , 2^F

11/15 20:10, 2^F

推

touurtn

11/15 20:11, 5年前 , 3^F

11/15 20:11, 3^F