[程式] 怎麼判斷五子棋的棋型？

看板GameDesign作者 (LaPass)時間12年前 (2013/10/18 01:11), 編輯推噓3(3推 0噓 27→)
留言30則, 4人參與, 最新討論串1/3 (看更多)
之前寫過傳統的五子棋AI，也就是無禁手、長連算贏這種規則 現在打算加入「超過五子以上不算贏也不算輸」這個規則 正在重寫五子棋的AI 之前想出來的方法是 把二維的五子棋分解成「直橫斜斜」四條線 範圍是落子點向外延伸4個點 然後去查表，查出該落子點的積分 這樣一來，運算速度可以維持常數，實力也不錯 (比我自己還強 orz...) EX: 落 子 ↓ 棋型 ○○○ ○○○○ 活四 ●○○ ○ ○○○ 死四 ○○ ○ 活三 ●○○○○● 沒棋 之前只有9個點，在經過扣除左右互換、敵我顏色對調後 表的大小總共只有1600筆左右 所以我就經過程式大概計算一下棋型，然後由人工效正細節 例如: ● ○○○ ● 程式會認為是活三，但其實是死三 因為多下一顆棋子之後，那一邊就會撞牆，變成單四 像這樣把對照表製作完了之後 就丟進txt檔，然後讓程式去讀取 但是因為多了「超過五子以上不算贏也不算輸」這個規則的關係 邊邊需要多一個點才能判斷是否長連 導致資料的點由9點變成11個點 表的筆數也由1600爆增到66000筆 這實在不是人工能處理的量 所以..... 請問要怎麼讓程式判斷一些詭異的棋型？ 像是： 落子 長連不算 允許長連 ↓ ○○○ ○○ 死三 死四 ○○ ○ ○○ 死三 活三 ○ ○○ ○ ○○ ○ 沒棋 活三 ○ ○○○ ○ 死三 活三 ○ ○ ○○ ○ ○ 沒棋 活三 ● ○○○ ● 死三 死三 ● ○○○ 活三 活三 ● ○○○ ○ 死三 活三 ●○ ○ ○○● 沒棋 死三 請問有沒有什麼建議的判斷方式呢？ 希望能提示一些判斷的方法或是方向 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.41.98.199 ※ 編輯: LaPass 來自: 114.41.98.199 (10/18 01:12)
推
10/18 01:21, , 1F
長連不要用查表呢? 做完積分計算後再多做長連檢測
10/18 01:21, 1F
→
10/18 01:22, , 2F
如果發現這一步下去會變成長連就把積分變成負的
10/18 01:22, 2F
→
10/18 01:23, , 3F
如果最高積分是長連就改成負一 然後往下選用次高積分
10/18 01:23, 3F
→
10/18 01:23, , 4F
複雜度應該還好 盤面積分可以只改變落子點附近
10/18 01:23, 4F
→
10/18 01:31, , 5F
我想想看... 如果能的話是一次到位最好，因為我打算放在網
10/18 01:31, 5F
→
10/18 01:31, , 6F
頁上讓人玩
10/18 01:31, 6F
推
10/18 03:25, , 7F
對每顆棋，抓離它五格遠的位置。那邊有自己的棋，則這個方
10/18 03:25, 7F
→
10/18 03:26, , 8F
向由原來那顆棋開頭的一串棋子在此方向必是死的，這應該可
10/18 03:26, 8F
→
10/18 03:26, , 9F
以篩掉不少吧。
10/18 03:26, 9F
→
10/18 03:27, , 10F
呃，我回文好了。
10/18 03:27, 10F
→
10/18 19:43, , 11F
我玩過AI會逼我黑子一定要下雙三犯規輸的。現在想想真厲害
10/18 19:43, 11F
→
10/18 20:27, , 12F
禁手會讓規則更複雜的說...
10/18 20:27, 12F
推
10/19 00:15, , 13F
其實會讓你禁手輸就AI來講沒有比較厲害啦，不如說除了評分
10/19 00:15, 13F
→
10/19 00:16, , 14F
函數不同以外架構還是完全一樣XD
10/19 00:16, 14F
→
10/19 00:25, , 15F
禁手會讓一維問題變成二維問題啊.... orz
10/19 00:25, 15F
→
10/19 00:26, , 16F
查表對會雙邊比較不敏感，所以要在表上標明這裡有條三、四
10/19 00:26, 16F
→
10/19 00:27, , 17F
，萬一出現有個點下下去會有兩個活三或死四之類的，要特別
10/19 00:27, 17F
→
10/19 00:28, , 18F
處理.... 然後，我之前那個查表AI是根本沒跑遞迴的，把四方
10/19 00:28, 18F
→
10/19 00:29, , 19F
向的分數加起來，下在分數最高的點上就是了。
10/19 00:29, 19F
→
10/19 00:29, , 20F
有禁手就不能這樣了.....
10/19 00:29, 20F
→
10/19 00:35, , 21F
是說整個棋盤的遞迴跑起來的運算真的很恐怖..... 真的.....
10/19 00:35, 21F
→
10/19 00:36, , 22F
每加一層深度的運算量，至少比上層多兩個零
10/19 00:36, 22F
→
10/19 02:06, , 23F
所以會有Alpha–beta pruning演算法囉，減輕一些負擔XD
10/19 02:06, 23F
→
10/19 02:06, , 24F
雖然我不知道你怎麼做的，不過我覺得禁手會讓pruning機率提
10/19 02:06, 24F
→
10/19 02:07, , 25F
高，問題計算量反而變低耶
10/19 02:07, 25F
→
10/19 12:39, , 26F
我的方法就..... 把棋盤上的空白點切分成四個方向，然後查
10/19 12:39, 26F
→
10/19 12:40, , 27F
表啊..... 不是min-max也不是alpha-beta，演算法中沒有嘗試
10/19 12:40, 27F
→
10/19 12:41, , 28F
落子的動作，所以運算量不會隨著可能的落子點增加而增加。
10/19 12:41, 28F
→
10/19 12:43, , 29F
之前用過alpha-beta，原本是想用他來求黑棋必勝，結果算好
10/19 12:43, 29F
→
10/19 12:44, , 30F
久，因為我沒設深度的邊界。
10/19 12:44, 30F
┌┬┬┬┬┬┬┬┬┬┬┬┐ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼●○○○Ｇ┼┼┼┤ ├┼┼┼┼○●┼●┼┼┼┤ ├┼┼┼┼●○●●┼┼┼┤ ├┼┼┼┼○┼┼●┼┼┼┤ ├┼┼┼┼┼┼┼┼●┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ └┴┴┴┴┴┴┴┴┴┴┴┘ 舉例來說，G點的分數可以這樣算 ┌┬┬┬┬┬┬┬┬┬┬┬┐ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼●○○○Ｇ┼┼┼┤ ├┼┼┼┼○●┼●┼┼┼┤ ├┼┼┼┼●○●●┼┼┼┤ ├┼┼┼┼○┼┼●┼┼┼┤ ├┼┼┼┼┼┼┼┼●┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ └┴┴┴┴┴┴┴┴┴┴┴┘ 所以這個點的分數是 「 xooo:o: 」 棋型 連成 死四 分數是 5300 「 xxx:o: 」 棋型 阻擋 活三 1300 「 oo :o: 」 棋型 連成 活三 300 「 :o: 」 無 10 這四個的分數加起來，就是該點的分數 把每個空白點的分數算出來 然後，棋就下在分數最高的地方 沒什麼策略可言，原本也只打算用來當作評價公式 以及alpha-beta的落子優先順序 後來發現..... 好像不用動到alpha-beta 依照這個評價評出來的優先順序，就差不多就已經是很不錯的棋步了 ※ 編輯: LaPass 來自: 114.38.67.101 (10/19 13:17)
‣ 更多 LaPass 的文章
文章代碼(AID): #1IO1f2Az (GameDesign)
‣ 更多 LaPass 的文章
文章代碼(AID): #1IO1f2Az (GameDesign)