※ 本文為 terievv 轉寄自 ptt.cc 更新時間: 2014-01-14 23:34:06
看板 Gossiping
作者 標題 Re: [問卦] 圍棋有最佳解嗎?
時間 Tue Jan 14 17:53:55 2014
※ 引述《kiwibee (奇異蜜蜂)》之銘言：
: 圍棋的下法雖然億萬種組合
: 但有沒有可能找到最佳解
: 就像圈圈叉叉那樣
: 當然圈圈叉叉的組合太少了
肯定是有，圍棋被分類為「二人零和有限確定完全情報遊戲」。
凡是屬於這種分類的遊戲，
已經被證明出一定會有最佳解，
也因此在雙方都下最佳解走法時，
只會有三種情況：
1. 先手必勝
2. 後手必勝
3. 必定平局
看起來像是廢話，但若不符合二人零和有限確定完全情報遊戲定義，
就不會有所謂的必勝或必定平局的情況。
至於它的定義是：
1. 二人：遊戲者為兩個人
2. 零和：最終結果的總和利得必然為零。例如勝者為1、敗者為-1、平局為0
3. 有限：變化數有其極限。雖然圍棋變化數是天文數字，但仍有極限
4. 確定：沒有偶然或機率的要素混入
5. 完全情報：場上資訊完全公開，沒有隱藏資訊。所以像有手牌之類的遊戲就不算。
因為圍棋屬於此類遊戲，所以必然有最佳解，
只是變化太過天文數字，料想不太可能被找出來。
之前將棋電王戰，職業棋士被電腦痛電，
有人擔心將棋會不會所有變化都被找出來，從而使這遊戲變得無趣。
但有教授計算，目前去串連超高效能電腦，
理論上一秒鐘大概可以計算出350億手，
不過用這速度去跑將棋的所有變化（10的220次方），
需要花費上9.1× 10^201年
等於不可能。
而圍棋的變化更是高達10的360次方左右，又遠比將棋誇張太多，
所以雖然理論上一定存有最佳解，但有生之年應該是看不到才是。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.187.212
推 :量子電腦表示:1F 01/14 17:55
推 :專業推2F 01/14 17:55
推 :而且被證明先手必勝也沒差 只要再貼目就好了3F 01/14 17:55
推 :好專業!!4F 01/14 17:55
推 :快推 免得被發現我看不懂5F 01/14 17:56
→ :第一手 ５之五6F 01/14 17:58
→ :照電腦的研發速度 應該不用太久就會找到了7F 01/14 17:58
推 :P,NP,NP-hard,NP-complete8F 01/14 17:59
推 :圍棋的每一步都是零和的嗎? 感覺很多棋步很難定義阿9F 01/14 17:59
推 :有沒有可能下的人誤以為對自己有利 實則不利?10F 01/14 18:00
推 :人類自尊心問題罷了 19*19要10^202年那就算9*9的圍棋啊11F 01/14 18:00
→ :等到19*19十分鐘算得出來 那就改成30*30的圍棋啊
→ :等到19*19十分鐘算得出來 那就改成30*30的圍棋啊
推 :你淫惹13F 01/14 18:01
推 :對奕只有2人 不是利即弊 所以原PO說的應該沒錯14F 01/14 18:02
推 :我也這麼覺得15F 01/14 18:03
推 :強，推16F 01/14 18:04
→ :圍棋不是有'劫'嗎?17F 01/14 18:04
→ :361階乘>>>>>10的360次方 沒那麼少18F 01/14 18:05
其實我也不知道怎麼計算，是參考我查到的資訊http://www.hummingheads.co.jp/reports/series/ser03/131128.html
コンピュータ囲碁 仕組み｜人間VSコンピュータ 10番勝負！ 囲碁対決・第1回｜連載｜HH News & Reports｜ハミングヘッズ 派手な演出で注目を集めてきたコンピュータ将棋だが、囲碁も実力は玄人はだしのレベルになった。人間とコンピュータの対決、囲碁編初回は「モンテカルロ法」との出会い。 ...
→ :有生之年看不到吧 量子電腦出來也頂多降幾個維度19F 01/14 18:07
→ :10的700次方蠻接近的 目前工程不可能解決的數字20F 01/14 18:07
噓 :人家諾貝爾獎得主都說這是有問題的遊戲惹21F 01/14 18:07
推 :真的是非利即弊嗎嗎?22F 01/14 18:07
推 :諾貝爾獎得主不知道業餘幾d? 人家怎麼說你怎麼信?23F 01/14 18:08
→ :其他棋都有擒王的目的 子的差異也很明顯 西洋棋不會去24F 01/14 18:10
推 :除了計算力外 我覺得關鍵是定義一手棋的好壞25F 01/14 18:10
→ :量子電腦表示：26F 01/14 18:11
→ :即使樹狀圖無限爆開也得知道走哪條是好的吧27F 01/14 18:11
推 :怎麼可能沒有意外, 棋手翻桌~!!!!28F 01/14 18:11
→ :處理王已被吃的棋局 光這樣就能讓電腦少處理很多東西29F 01/14 18:11
→ :就是難以估算落子後的利弊平衡 才會疑慮圍棋是否真的零30F 01/14 18:12
→ :和 但如同前面人所說,高階電腦還不到 知道的只剩上帝..
→ :和 但如同前面人所說,高階電腦還不到 知道的只剩上帝..
→ :撲子/循環劫這些考慮下去 可下的方式應該不止361階乘32F 01/14 18:14
推 :所以圍棋零和是很肯定的事嗎?33F 01/14 18:14
推 : 簡化到圈圈叉叉就可以理解了34F 01/14 18:15
→ :非利即弊聽起來很合理 但還是覺得蠻難接受的35F 01/14 18:15
→ :沒錯 就像考試看到絕對的字眼都要警惕一樣36F 01/14 18:16
→ :去查一下零和的定義不就知道了 你只看原po那句才會有疑問37F 01/14 18:17
推 :等量子電腦出來就知道了 一台效能快上兆倍38F 01/14 18:17
→ :但隨便玩過什麼棋類 應該都會有同感 除非長照之類無意39F 01/14 18:17
→ :西洋棋 皇后從頭到尾都很重要 圍棋 有塊地可能前期才有40F 01/14 18:17
→ :這是經濟學賽局的一個定理阿 可是有要每步零和嗎?41F 01/14 18:18
非常不好意思，後來我重新去查一下資料，發現我看太快，誤解了它對零和解釋的意思。
確實的定義應該還是要回到最終比賽結果為零和來看，
而非每手一定都要零和。
已經對上面的說明做出修正，謝謝指正，不好意思造成大家的誤解。
推 :其它棋類沒必要窮舉"所有變化"啊, 可能有一大半都剪掉了42F 01/14 18:19
→ :用 後期沒作為 你要怎麼界定何時才會沒有用呢?43F 01/14 18:19
→ :義的步數 但是圍棋每步都一定有意義 它真的最難44F 01/14 18:19
→ :然後這雖然沒證出來45F 01/14 18:19
→ :每步零和沒什麼問題阿 只是你看不出來 你下的這步究竟對誰有46F 01/14 18:20
→ :利
→ :利
→ :另外這明顯先手是必勝的遊戲48F 01/14 18:20
→ :每步零和這講法根本沒有聽過阿
→ :每步零和這講法根本沒有聽過阿
→ :圍棋的變化太多, 非現在架構的電腦所能負荷, 只能等未來50F 01/14 18:21
→ :很明顯阿 所以有貼目阿51F 01/14 18:21
→ :比較有趣的問題是現在的貼目是最佳的嗎?52F 01/14 18:21
推 :所以先手要貼回幾目才公平是個好問題...53F 01/14 18:23
→ : 不知道 因為沒下過圍棋XD54F 01/14 18:23
→ :不過對於每步零和這問題沒影響 只是勝機往何方傾倒的問
→ :不過對於每步零和這問題沒影響 只是勝機往何方傾倒的問
推 :貼目有半目鐵定不公平 一定先手雙方和局才是最佳解56F 01/14 18:26
→ :先手或被貼目都是對結果為有利(天平傾向)57F 01/14 18:26
→ :象棋也是紅方(先下)有利 但我還是一直被黑方幹掉XD||
→ :他就是在每一手都把勝機慢慢奪回去
※ 編輯: NewYAWARA 來自: 61.227.187.212 (01/14 18:35)→ :象棋也是紅方(先下)有利 但我還是一直被黑方幹掉XD||
→ :他就是在每一手都把勝機慢慢奪回去
推 :第一手天元60F 01/14 18:31
噓 :QB這時冒出來天元對嗎ww?61F 01/14 18:35
→ :靠夭啦=_=
→ :靠夭啦=_=
推 :看到修正了 害我剛才食不下嚥XDD63F 01/14 18:37
推 :好像也沒差 因為我以為是每手都會影響賽果的零和64F 01/14 18:39
推 :賽果零不零和規則定了就定了阿 好奇的是每一手要怎麼定65F 01/14 18:45
→ :義 還能判斷出每手是零和的
→ :義 還能判斷出每手是零和的
→ :我無法判斷每一手的零和傾向(對賽果) 但我認為一定有67F 01/14 18:49
→ :因為圍棋不會出現無意義來回的步數 他是定死的
→ :如果真的算出圍棋每一落子的傾向 電腦全面贏人不遠了XD
→ :因為圍棋不會出現無意義來回的步數 他是定死的
→ :如果真的算出圍棋每一落子的傾向 電腦全面贏人不遠了XD
→ :先從3X3 4x4 5x5去推算是不是先手先贏這點70F 01/14 18:56
→ :能不能有結果呢
→ :能不能有結果呢
推 :我自己有在下棋 有些棋步在當下真的不會知道他之後的效72F 01/14 19:03
→ :用有多大 或者說很多實地和外勢的取捨很模糊
→ :會有蠻多看似無意義或是先損後賺的棋步
→ :中盤以後或是收官我相信很有可能給出每步棋的效用
→ :但我的想像裡 佈局中要去評判這個不太容易
→ :用有多大 或者說很多實地和外勢的取捨很模糊
→ :會有蠻多看似無意義或是先損後賺的棋步
→ :中盤以後或是收官我相信很有可能給出每步棋的效用
→ :但我的想像裡 佈局中要去評判這個不太容易
推 :這是一個npc的問題 (?77F 01/14 19:16
推 :Quantum computer 用下去.....78F 01/14 19:38
推 :只會有3^361種.大約10^172,很多是禁著跟不可能的結果79F 01/14 20:25
→ :算這個不用考慮到手順
→ :算這個不用考慮到手順
推 :可以先找出3*3 4*4的最佳解 變化不是無窮的81F 01/14 20:41
→ :應該是NPC問題吧 跟數獨一樣82F 01/14 20:52
推 :10^172次方 我是覺得能寫的出來就有機會破啦83F 01/14 20:57
→ :總比一些無限次方好多了 而且科技進步速度沒人料的到
→ :總比一些無限次方好多了 而且科技進步速度沒人料的到
推 :3^361種....node和edge不一樣85F 01/14 22:07
→ :但是電腦的能力也是一直變強...86F 01/14 22:34
→ :CPU運算的能力已經到了一個瓶頸了87F 01/14 22:43
--
※ 看板: terievv 文章推薦值: 0 目前人氣: 0 累積人氣: 1796
※ 本文也出現在 1 個隱藏看板
※ 本文也出現在 1 個隱藏看板
回列表(←)
分享