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