› 看板 GameDesign 關於我們 聯絡資訊
作者LaPass (LaPass)
看板GameDesign
標題[程式] 怎麼判斷五子棋的棋型？
時間Fri Oct 18 01:11:27 2013
之前寫過傳統的五子棋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)
推 elfkiller:長連不要用查表呢? 做完積分計算後再多做長連檢測 10/18 01:21
→ elfkiller:如果發現這一步下去會變成長連就把積分變成負的 10/18 01:22
→ elfkiller:如果最高積分是長連就改成負一 然後往下選用次高積分 10/18 01:23
→ elfkiller:複雜度應該還好 盤面積分可以只改變落子點附近 10/18 01:23
→ LaPass:我想想看... 如果能的話是一次到位最好，因為我打算放在網 10/18 01:31
→ LaPass:頁上讓人玩 10/18 01:31
推 ddavid:對每顆棋，抓離它五格遠的位置。那邊有自己的棋，則這個方 10/18 03:25
→ ddavid:向由原來那顆棋開頭的一串棋子在此方向必是死的，這應該可 10/18 03:26
→ ddavid:以篩掉不少吧。 10/18 03:26
→ ddavid:呃，我回文好了。 10/18 03:27
→ KanoLoa:我玩過AI會逼我黑子一定要下雙三犯規輸的。現在想想真厲害 10/18 19:43
→ LaPass:禁手會讓規則更複雜的說... 10/18 20:27
推 ddavid:其實會讓你禁手輸就AI來講沒有比較厲害啦，不如說除了評分 10/19 00:15
→ ddavid:函數不同以外架構還是完全一樣XD 10/19 00:16
→ LaPass:禁手會讓一維問題變成二維問題啊.... orz 10/19 00:25
→ LaPass:查表對會雙邊比較不敏感，所以要在表上標明這裡有條三、四 10/19 00:26
→ LaPass:，萬一出現有個點下下去會有兩個活三或死四之類的，要特別 10/19 00:27
→ LaPass:處理.... 然後，我之前那個查表AI是根本沒跑遞迴的，把四方 10/19 00:28
→ LaPass:向的分數加起來，下在分數最高的點上就是了。 10/19 00:29
→ LaPass:有禁手就不能這樣了..... 10/19 00:29
→ LaPass:是說整個棋盤的遞迴跑起來的運算真的很恐怖..... 真的..... 10/19 00:35
→ LaPass:每加一層深度的運算量，至少比上層多兩個零 10/19 00:36
→ ddavid:所以會有Alpha–beta pruning演算法囉，減輕一些負擔XD 10/19 02:06
→ ddavid:雖然我不知道你怎麼做的，不過我覺得禁手會讓pruning機率提 10/19 02:06
→ ddavid:高，問題計算量反而變低耶 10/19 02:07
→ LaPass:我的方法就..... 把棋盤上的空白點切分成四個方向，然後查 10/19 12:39
→ LaPass:表啊..... 不是min-max也不是alpha-beta，演算法中沒有嘗試 10/19 12:40
→ LaPass:落子的動作，所以運算量不會隨著可能的落子點增加而增加。 10/19 12:41
→ LaPass:之前用過alpha-beta，原本是想用他來求黑棋必勝，結果算好 10/19 12:43
→ LaPass:久，因為我沒設深度的邊界。 10/19 12:44
┌┬┬┬┬┬┬┬┬┬┬┬┐ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼●○○○Ｇ┼┼┼┤ ├┼┼┼┼○●┼●┼┼┼┤ ├┼┼┼┼●○●●┼┼┼┤ ├┼┼┼┼○┼┼●┼┼┼┤ ├┼┼┼┼┼┼┼┼●┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ ├┼┼┼┼┼┼┼┼┼┼┼┤ └┴┴┴┴┴┴┴┴┴┴┴┘ 舉例來說，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)