作者Baseba11 (背濕霸壹壹)
看板GO
標題Re: [問題] 九路圍棋該貼多少目合理，甚至是十九路 …
時間Sun Jun 26 17:46:05 2011
其實我不知道為什麼只要討論到AI就一定有人要提窮舉
事實上考慮一下圍棋的規則 我們就可以發現一個很明顯的現象
當一串棋子被提吃之後所形成的空 除非只有一目
否則很明顯的這塊空可以再被填入棋子
再考慮最極端的例子 整個盤面除了一個點之外被其中一個顏色填滿
下一手就只有 1.吃掉全部的祺 2.pass 3.認輸
如果選擇1.這時後會發現盤面上的情況回到跟第一手的情形一樣
如果又考慮三劫的問題又更複雜了
所以窮舉圍棋的走法是不可能展開成一個有限的 沒有迴圈的分支樹
結論是不論原原po說得哪一種算法都有點問題
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.202.44
1F：推 ddavid:在有嚴謹規則下可以有限，如下不完的三劫會被給和局，不會 06/26 17:58
2F：→ ddavid:無限往下展開。 06/26 17:59
3F：→ ddavid:就算你很刻意的使用排滿剩一眼→被吃掉，每次都把眼排在不 06/26 18:00
4F：→ ddavid:同的地方或排的順序不同，但這個排法的可能性終究是有限的 06/26 18:01
5F：→ ddavid:，所以在同型反覆的規則下終究會撞到同型同手順就是，也一 06/26 18:02
6F：→ ddavid:樣沒有無限展開......，雖然那會是很變態大的樹就是（會比 06/26 18:02
7F：→ ddavid:(n^2)!還遠大就是，可能大略是(2*(n^2)!)!這個等級XD 06/26 18:03
這樣的樹好像有迴圈 如果又考慮同棋形下雙方的提子數
則可以展開成沒有迴圈 但是單一棋形下有無限個分支
所以還是窮舉不完所有的情況 剛剛吃飯的時候想到的
以前曾經想做一個窮舉機器人 做了很久之後才發現這個蠢問題 :S
※ 編輯: Baseba11 來自: 140.114.202.44 (06/26 18:30)
8F：推 kohttp:同型重覆的判斷,不用其中每一步順序都一樣 06/26 23:02
9F：→ kohttp:只要計算總盤面變化數再補上前一手如果是提劫的位置 06/26 23:03
10F：→ kohttp:此數字將小於3^(全盤點數) 因為要扣掉死子未提的盤面 06/26 23:06