作者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)