看板 Gossiping作者 NewYAWARA (朝霞之前奏)標題 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
推 ckgegg:量子電腦表示:1F 01/14 17:55
推 fireda:而且被證明先手必勝也沒差 只要再貼目就好了3F 01/14 17:55
推 anddy:好專業!!4F 01/14 17:55
→ HAIWEI:照電腦的研發速度 應該不用太久就會找到了7F 01/14 17:58
推 dacapo:P,NP,NP-hard,NP-complete8F 01/14 17:59
推 howard50b:圍棋的每一步都是零和的嗎? 感覺很多棋步很難定義阿9F 01/14 17:59
推 MicroB:人類自尊心問題罷了 19*19要10^202年那就算9*9的圍棋啊
等到19*19十分鐘算得出來 那就改成30*30的圍棋啊11F 01/14 18:00
推 Emerson158:對奕只有2人 不是利即弊 所以原PO說的應該沒錯14F 01/14 18:02
→ TheBeast:361階乘>>>>>10的360次方 沒那麼少18F 01/14 18:05
其實我也不知道怎麼計算，是參考我查到的資訊
http://www.hummingheads.co.jp/reports/series/ser03/131128.html
或許是作者的計算也有錯...
→ blackwindy:有生之年看不到吧 量子電腦出來也頂多降幾個維度19F 01/14 18:07
→ TheBeast:10的700次方蠻接近的 目前工程不可能解決的數字20F 01/14 18:07
噓 h4k:人家諾貝爾獎得主都說這是有問題的遊戲惹21F 01/14 18:07
推 thudadai:諾貝爾獎得主不知道業餘幾d? 人家怎麼說你怎麼信?23F 01/14 18:08
→ ringtweety:其他棋都有擒王的目的 子的差異也很明顯 西洋棋不會去24F 01/14 18:10
推 howard50b:除了計算力外 我覺得關鍵是定義一手棋的好壞25F 01/14 18:10
→ PSRY:量子電腦表示：26F 01/14 18:11
→ howard50b:即使樹狀圖無限爆開也得知道走哪條是好的吧27F 01/14 18:11
→ ringtweety:處理王已被吃的棋局 光這樣就能讓電腦少處理很多東西29F 01/14 18:11
→ Emerson158:就是難以估算落子後的利弊平衡 才會疑慮圍棋是否真的零和 但如同前面人所說,高階電腦還不到 知道的只剩上帝..30F 01/14 18:12
→ joumay:撲子/循環劫這些考慮下去 可下的方式應該不止361階乘32F 01/14 18:14
推 blasy: 簡化到圈圈叉叉就可以理解了34F 01/14 18:15
→ howard50b:非利即弊聽起來很合理 但還是覺得蠻難接受的35F 01/14 18:15
→ jtch:去查一下零和的定義不就知道了 你只看原po那句才會有疑問37F 01/14 18:17
推 liaon98:等量子電腦出來就知道了 一台效能快上兆倍38F 01/14 18:17
→ Emerson158:但隨便玩過什麼棋類 應該都會有同感 除非長照之類無意39F 01/14 18:17
→ ringtweety:西洋棋 皇后從頭到尾都很重要 圍棋 有塊地可能前期才有40F 01/14 18:17
→ JamesChen:這是經濟學賽局的一個定理阿 可是有要每步零和嗎?41F 01/14 18:18
非常不好意思，後來我重新去查一下資料，發現我看太快，
誤解了它對零和解釋的意思。
確實的定義應該還是要回到最終比賽結果為零和來看，
而非每手一定都要零和。
已經對上面的說明做出修正，謝謝指正，不好意思造成大家的誤解。
推 birdy590:其它棋類沒必要窮舉"所有變化"啊, 可能有一大半都剪掉了42F 01/14 18:19
→ ringtweety:用 後期沒作為 你要怎麼界定何時才會沒有用呢?43F 01/14 18:19
→ Emerson158:義的步數 但是圍棋每步都一定有意義 它真的最難44F 01/14 18:19
→ jtch:每步零和沒什麼問題阿 只是你看不出來 你下的這步究竟對誰有利46F 01/14 18:20
→ JamesChen:另外這明顯先手是必勝的遊戲
每步零和這講法根本沒有聽過阿48F 01/14 18:20
→ birdy590:圍棋的變化太多, 非現在架構的電腦所能負荷, 只能等未來50F 01/14 18:21
→ jtch:很明顯阿 所以有貼目阿51F 01/14 18:21
→ JamesChen:比較有趣的問題是現在的貼目是最佳的嗎?52F 01/14 18:21
推 thudadai:所以先手要貼回幾目才公平是個好問題...53F 01/14 18:23
→ Emerson158: 不知道 因為沒下過圍棋XD不過對於每步零和這問題沒影響 只是勝機往何方傾倒的問54F 01/14 18:23
推 sixersai:貼目有半目鐵定不公平 一定先手雙方和局才是最佳解56F 01/14 18:26
→ Emerson158:先手或被貼目都是對結果為有利(天平傾向)
象棋也是紅方(先下)有利 但我還是一直被黑方幹掉XD||他就是在每一手都把勝機慢慢奪回去57F 01/14 18:26
※ 編輯: NewYAWARA 來自: 61.227.187.212 (01/14 18:35)
推 QBey:第一手天元60F 01/14 18:31
推 Emerson158:好像也沒差 因為我以為是每手都會影響賽果的零和64F 01/14 18:39
推 howard50b:賽果零不零和規則定了就定了阿 好奇的是每一手要怎麼定義 還能判斷出每手是零和的65F 01/14 18:45
→ Emerson158:我無法判斷每一手的零和傾向(對賽果) 但我認為一定有因為圍棋不會出現無意義來回的步數 他是定死的
如果真的算出圍棋每一落子的傾向 電腦全面贏人不遠了XD67F 01/14 18:49
→ ironkyoater:先從3X3 4x4 5x5去推算是不是先手先贏這點
能不能有結果呢70F 01/14 18:56
推 howard50b:我自己有在下棋 有些棋步在當下真的不會知道他之後的效用有多大 或者說很多實地和外勢的取捨很模糊
會有蠻多看似無意義或是先損後賺的棋步
中盤以後或是收官我相信很有可能給出每步棋的效用
但我的想像裡 佈局中要去評判這個不太容易72F 01/14 19:03
推 lwei781:Quantum computer 用下去.....78F 01/14 19:38
推 stupidgod08:只會有3^361種.大約10^172,很多是禁著跟不可能的結果算這個不用考慮到手順79F 01/14 20:25
推 kiwibee:可以先找出3*3 4*4的最佳解 變化不是無窮的81F 01/14 20:41
推 swatch44:10^172次方 我是覺得能寫的出來就有機會破啦
總比一些無限次方好多了 而且科技進步速度沒人料的到83F 01/14 20:57
→ CCWck:但是電腦的能力也是一直變強...86F 01/14 22:34
→ mike0327:CPU運算的能力已經到了一個瓶頸了87F 01/14 22:43
--