·580· 智能系统学报 第13卷 色棋子的阵型。如图6中黑色二子夹着白色一 此可以把每一个棋谱看作一个DFA。 子。此时，为了阻止黑色棋子布置在白色的对角成 把棋谱表示成一个确定有限自动机，如图8。 方，应将白色棋子下在图6中所示位置进行应对。 年始 -一→0"甲0o"o0一→© 图8使用确定有限自动机识别棋谱过程 Fig.8 Deterministic finite automaton to recognize chess record 图8中，W[gg、Bhh、W[gh、B[hg表示状 态转移条件，W表示白子，B表示黑子，中括号的 字母表示棋子的坐标。 图6对角棋型及其对策 3.2BM模式匹配算法 Fig.6 Contrast form and its tactics BM(Boyer Moore)算法是最为快速的模式匹 5)四子棋型 配算法之一图，因此，本文采用BM算法对棋谱及 四子棋型是指同色四子形成一个方，如图7 当前局面进行模式匹配。待匹配字符串为长度为 中白色的四颗棋子所示。四子棋型是整个战斗阶 n的棋谱T,定义为T[OT[1]T[2]…Tn-2]Tn-1], 段中最强的阵型，褡裢、拉萨等阵型都是由此形 模式串为长度为m的当前局面P,定义为P[O]P[1] 成。一旦己方形成四子棋型，就可以吃掉棋盘上 P[2]…P[m-2]P[m-1],其中，n≥m 对方的任意一子。因此，在布局和战斗阶段，己 “久”棋中，模式匹配算法的伪代码如下： 方要尽力使自己形成四子棋型，阻止对方形成四 private coordinate sgfmatch(inti){ 子棋型。 changtodfa;把棋局的下子顺序变成DFA格式 List<Integer>matches=BoyerMoore.match(strb, st[]),∥使用BM算法对所有存在的棋谱与当前 棋局相匹配 for(Integer integer:matches){ i=str[i].charAt(integer+strb.length()+2)-'a'; j=str[i].charAt(integer+strb.length()+3)-'a'; 图7四子棋型 } Fig.7 Square form /去除所有相匹配的棋局的下子策略 3“久”棋中使用的模式匹配算法 4基于棋型的攻防策略 “久”棋中，布局的质量对胜负影响很大，而以 “久”棋布局阶段的质量对弈棋胜负影响很 棋盘中央对角线为中心的约40步棋的布局几乎 大，棋盘中央对角线附近约40步棋的棋子布局又 决定了整个布局的质量，因此，在布局的前 直接决定一盘棋布局的好坏。战斗阶段，哪一方 40步，使用模式匹配方法进行布局。具体来说， 最先形成褡裢，哪一方就具有明显的赢棋优势。 将录制的300局对弈数据采用SGF格式进行处理 在布局及战斗阶段，好的棋型非常重要。本文设 后，构建棋谱。使用确定有限自动机表示识别棋 计了基于棋型的攻防策略，分别应用于“久”棋布 谱，使用BM字符串匹配算法进行模式匹配。 局及战斗阶段。 由于“久”棋的棋盘与围棋类似，因此借鉴围 4.1基于矩阵的棋型识别方法 棋打谱的方式，仿照SGF的格式，建立“久”棋的 对于上述提出的棋型，本文提出了基于矩阵 棋谱文件。 的棋型识别方法，具体如下。以三角棋型为例， 3.1确定有限自动机识别棋谱及当前盘面 定义矩阵TS如式(1)所示： 棋谱及当前盘面的识别是模式匹配中的重要 环节。确定有限状态机(deterministic finite auto- s=[9 (1) maton,DFA)能够识别字符串，做出接受或者拒绝 式中：0是该位置为空，1是该位置为白棋，2是该 的判断。下棋的若干步之间存在依赖关系，因 位置为黑棋。当前棋局的矩阵TB如式(2)所示。色棋子的阵型。如图 6 中黑色二子夹着白色一 子。此时，为了阻止黑色棋子布置在白色的对角成 方，应将白色棋子下在图 6 中所示位置进行应对。 图 6 对角棋型及其对策 Fig. 6 Contrast form and its tactics 5) 四子棋型 四子棋型是指同色四子形成一个方，如图 7 中白色的四颗棋子所示。四子棋型是整个战斗阶 段中最强的阵型，褡裢、拉萨等阵型都是由此形 成。一旦己方形成四子棋型，就可以吃掉棋盘上 对方的任意一子。因此，在布局和战斗阶段，己 方要尽力使自己形成四子棋型，阻止对方形成四 子棋型。 图 7 四子棋型 Fig. 7 Square form 3 “久”棋中使用的模式匹配算法 “久”棋中，布局的质量对胜负影响很大，而以 棋盘中央对角线为中心的约 40 步棋的布局几乎 决定了整个布局的质量，因此，在布局的 前 40 步，使用模式匹配方法进行布局。具体来说， 将录制的 300 局对弈数据采用 SGF 格式进行处理 后，构建棋谱。使用确定有限自动机表示识别棋 谱，使用 BM 字符串匹配算法进行模式匹配。 由于“久”棋的棋盘与围棋类似，因此借鉴围 棋打谱的方式，仿照 SGF 的格式，建立“久”棋的 棋谱文件。 3.1 确定有限自动机识别棋谱及当前盘面 棋谱及当前盘面的识别是模式匹配中的重要 环节。确定有限状态机 (deterministic finite auto￾maton，DFA) 能够识别字符串，做出接受或者拒绝 的判断[17]。下棋的若干步之间存在依赖关系，因 此可以把每一个棋谱看作一个 DFA。 把棋谱表示成一个确定有限自动机，如图 8。 开始 0 1 2 3 4 结束 W [gg] B[hh] W [gh] B[hg] 图 8 使用确定有限自动机识别棋谱过程 Fig. 8 Deterministic finite automaton to recognize chess record W [ gg]、B[hh]、W [ gh]、B [ hg] 图 8 中 ， 表示状 态转移条件，W 表示白子，B 表示黑子，中括号的 字母表示棋子的坐标。 3.2 BM 模式匹配算法 n T T[0]T[1]T[2]···T[n−2]T[n−1] m P P[0]P[1] P[2]···P[m−2]P[m−1] n ⩾ m BM(Boyer Moore) 算法是最为快速的模式匹 配算法之一[18] ，因此，本文采用 BM 算法对棋谱及 当前局面进行模式匹配。待匹配字符串为长度为 的棋谱 ，定义为 ， 模式串为长度为 的当前局面 ，定义为 ，其中， “久”棋中，模式匹配算法的伪代码如下： private coordinate sgfmatch(inti) { changtodfa;//把棋局的下子顺序变成 DFA 格式 List<Integer> matches =BoyerMoore.match(strb, str[i]); //使用 BM 算法对所有存在的棋谱与当前 棋局相匹配 for (Integer integer : matches) { i=str[i].charAt(integer+strb.length()+2)-'a'; j=str[i].charAt(integer+strb.length()+3)-'a'; } }//去除所有相匹配的棋局的下子策略 4 基于棋型的攻防策略 “久”棋布局阶段的质量对弈棋胜负影响很 大，棋盘中央对角线附近约 40 步棋的棋子布局又 直接决定一盘棋布局的好坏。战斗阶段，哪一方 最先形成褡裢，哪一方就具有明显的赢棋优势。 在布局及战斗阶段，好的棋型非常重要。本文设 计了基于棋型的攻防策略，分别应用于“久”棋布 局及战斗阶段。 4.1 基于矩阵的棋型识别方法 对于上述提出的棋型，本文提出了基于矩阵 的棋型识别方法，具体如下。以三角棋型为例， 定义矩阵 TS 如式 (1) 所示： TS = [ 0 1 1 1 ] (1) 式中：0 是该位置为空，1 是该位置为白棋，2 是该 位置为黑棋。当前棋局的矩阵 TB 如式 (2) 所示。 ·580· 智 能 系 统 学 报 第 13 卷