第2卷第4期 智能系统学报 Vol.2 Ng 4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 对称无关的模式编码方法在定式学习中的应用 岳鹏，李太华邱玉辉 (西南大学智能软件与软件工程重点实验室，重庆400715) 摘要：计算机围棋中的定式可以从棋谱中学习，采用与模式对称性无关的编码方法可以取得更好的储存效果.这 是一种基于模式的邻近特征轮廓特征和行列特征的模式编码方法，与模式的平移、旋转、翻转及黑白对称性无关 实验结果表明其哈希性能良好，模式间的查找迅速，也可以在官子和死活问题中得以应用. 关键词：计算机围棋：定式 中图分类号：TP181文献标识码：A文章编号：16734785(2007)040092-03 A pattern encoding method independent of symmetry applied in joseki learning YUE Peng LI Tai-hua,QIU Yurhui (The Key Laboratory of Intelligent Software Software Engineering,Southwest University,Chongqing 400715,China) Abstract Joseki can be learned from game records in Computer Go.To more effectively maintain the joseki library,a pattern encoding method independent of symmetry is needed.This is provided by an encoding method is designed based on the pattern's neighbor character,the outline character and the row and col- umn's character.The results show that this method's hashing performance is good,and it rapidly swit- ches between patterns.The method can also be applied to tsumego and yose in Computer Go. Key words :computer Go;joseki 围棋分为布局、中盘、终盘3个阶段.定式是布配置方式，每个位置存在黑子、白子和无子3种可 局阶段对局双方得失相对平衡的走步序列，因开局能.模式具有平移、旋转、翻转及黑白对称性，最坏情 时角部价值最大，所以定式多发生在角部，约20步 况下共有16种对称可能.最简明的模式匹配方法 左右，可以包含脱先(Pass).不同的走步顺序可能导 为：将目标模式于盘面上平移检验是否能与局部完 致同一局面的产生，同一局面的后续走步常常有多 全重合.因为需要考虑选定模式的所有16种可能的 个，所以，定式库可以用有限状态机表示 对称模式，效率欠佳，不拟采用」 经职业棋手的潜心研究，定式已经数以万计，可 为了高效储存定式，处于不同对称状态下的相 以手工输入，但因工作量大有一定的局限性.不过， 同模式应有相同的编码.但传统的Zobrist哈希法 因为职业棋手对局双方常常以定式为基础，可以从 并不具备此特点)，因为其棋盘上每个位置状态对 其对局谱中学习.有时一方走法错误但因发生频率 应不同的随机值，而模式一经对称变换其绝对位置 低，可以在学习的最后阶段予以剔除，当然一些生僻 也变了，这样经异或运算后的哈希值也就不同 但确实可以称为定式的走法也可能会被剔除.为了 针对此，有研究者提出了以下算法：为处理旋 有效储存定式下的特定局面需要一种有效的定式编 转对称性将定式均归一于棋盘某一角，为处理翻转 码方法 对称性将定式中不位于对角线上的第1步翻转于对 1定式的编码 角线同一侧，为处理黑白对称性将定式第1步均变 换为同一颜色.这种处理方法的确解决了Zobrist 将特定局面看作模式，模式即是指特定的棋子 哈希法下的对称性问题，却导致了另一问题：同一局 收稿日期：20060821. 面下的走步历史不同将导致其编码不同.这原本是 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 对称无关的模式编码方法在定式学习中的应用 岳 鹏 ,李太华 ,邱玉辉 (西南大学 智能软件与软件工程重点实验室 ,重庆 400715) 摘 要 :计算机围棋中的定式可以从棋谱中学习 ,采用与模式对称性无关的编码方法可以取得更好的储存效果. 这 是一种基于模式的邻近特征、轮廓特征和行列特征的模式编码方法 ,与模式的平移、旋转、翻转及黑白对称性无关. 实验结果表明其哈希性能良好 ,模式间的查找迅速 ,也可以在官子和死活问题中得以应用. 关键词 :计算机围棋 ;定式 中图分类号 : TP181 文献标识码 :A 文章编号 :167324785 (2007) 0420092203 A pattern encoding method independent of symmetry applied in joseki learning YU E Peng ,L I Tai2hua ,QIU Yu2hui ( The Key Laboratory of Intelligent Software & Software Engineering , Southwest University , Chongqing 400715 , China) Abstract :Joseki can be learned from game records in Comp uter Go . To more effectively maintain t he joseki library , a pattern encoding met hod independent of symmetry is needed. This is provided by an encoding met hod is designed based on t he pattern’s neighbor character , t he outline character and the row and col2 umn’s character. The results show that t his method’s hashing performance is good , and it rapidly swit2 ches between patterns. The met hod can also be applied to tsumego and yose in Comp uter Go. Keywords :comp uter Go ; joseki 收稿日期 :2006208221. 围棋分为布局、中盘、终盘 3 个阶段. 定式是布 局阶段对局双方得失相对平衡的走步序列 ,因开局 时角部价值最大 ,所以定式多发生在角部 ,约 20 步 左右 ,可以包含脱先(Pass) . 不同的走步顺序可能导 致同一局面的产生 ,同一局面的后续走步常常有多 个 ,所以 ,定式库可以用有限状态机表示. 经职业棋手的潜心研究 ,定式已经数以万计 ,可 以手工输入 ,但因工作量大有一定的局限性. 不过 , 因为职业棋手对局双方常常以定式为基础 ,可以从 其对局谱中学习. 有时一方走法错误但因发生频率 低 ,可以在学习的最后阶段予以剔除 ,当然一些生僻 但确实可以称为定式的走法也可能会被剔除. 为了 有效储存定式下的特定局面需要一种有效的定式编 码方法. 1 定式的编码 将特定局面看作模式 ,模式即是指特定的棋子 配置方式 ,每个位置存在黑子、白子和无子 3 种可 能. 模式具有平移、旋转、翻转及黑白对称性 ,最坏情 况下共有 16 种对称可能. 最简明的模式匹配方法 为 :将目标模式于盘面上平移检验是否能与局部完 全重合. 因为需要考虑选定模式的所有 16 种可能的 对称模式 ,效率欠佳 ,不拟采用. 为了高效储存定式 ,处于不同对称状态下的相 同模式应有相同的编码. 但传统的 Zobrist 哈希法 并不具备此特点[ 1 ] ,因为其棋盘上每个位置状态对 应不同的随机值 ,而模式一经对称变换其绝对位置 也变了 ,这样经异或运算后的哈希值也就不同. 针对此 ,有研究者[2 ]提出了以下算法 :为处理旋 转对称性将定式均归一于棋盘某一角 ,为处理翻转 对称性将定式中不位于对角线上的第 1 步翻转于对 角线同一侧 ,为处理黑白对称性将定式第 1 步均变 换为同一颜色. 这种处理方法的确解决了 Zobrist 哈希法下的对称性问题 ,却导致了另一问题 :同一局 面下的走步历史不同将导致其编码不同. 这原本是
第4期 岳鹏，等：对称无关的模式编码方法在定式学习中的应用 ·93· Zobrist哈希法下不存在的问题.如图1所示2个定 有限状态机.因此，特定模式需要和下一走步位置联 式当前局面相同，应该具有相同编码，但因其走步历 系，而二者并无相关性，只能分别储存.如己知目前 史不同，按上述编码方法得到的编码并不一样 编码和完成下一走步后的新编码，如何确定下一走 步位置只能通过搜索可能选点实现.不过可以通过 适当的提示信息大大减少搜索范围，如指明下一走 ⑥ 步位于当前模式掩码的外部或内部第几层上，掩码 向四周扩张一步后的边界称为外部第1层，向内部 区域收缩一步后的边界称为内部第1层，依此类推 经棋谱提取定式后储存于模式库，可以作为走 图1走步历史不同的同一局面 步推荐器使用.当考虑当前棋局状态下某个局部定 Fig.I The same position with different history 式时，按上述编码方法于模式库中找到相应模式，进 故此，提出如下编码方法.模式范围限制在角部 而得到多个可能走步，再根据启发式策略选定其一 10×10区域，用64位(bit)整数表示编码结果，超过 3实验结果及结论 2则取模运算后的结果.首先按以下步骤求得单色 以507局专业棋谱为学习材料提取定式，定式 棋子所构成的棋形的编码：)求得模式邻近特征码 (4):针对每个点求得与之直连的点个数，如果该点 最大走步数为20，并记录其总模式数为27686个、 总编码次数为42691次，重复编码次数为43次，总 位于棋盘边界则再加上基数19，即棋盘规模，并累 编码时间为114797ms,定式库以有限状态机形式 乘；2)求得模式行列特征码(B):求得每行及每列的 棋子至边界的跨度，并累乘；3)求得模式轮廓特征码 储存，平均每步搜索时间为22ms.这种基于模式的 邻近特征轮廓特征和行列特征的模式编码方法与 (C:求得模式掩码所包含的点数，掩码指刚好包含 模式对称性无关，解决了传统编码方法在模式对称 模式所有点的最小矩形区域；4)求得最终模式编码 K=mod(A XB+C,254) 性方面存在的不足，3」，走步历史不同的同一局面 然后按以下步骤求得双色模式的编码：1)求得 的编码也保持一致.其主要缺点在于不能由前后状 某一局面中黑色棋形的模式编码(KB);2)求得白色 态直接确定走步位置，不过可以通过启发式信息减 棋形的模式编码(Kw);3)求得将黑白色视作同一时 少搜索量.其主要优点在于计算简单快速，哈希性能 的单色模式编码(K);4)则最终模式编码即为S= 良好，适用于不同规模的模式；在定式储存方面性能 mod(KB×KwXK,24) 良好，也可以应用于官子模式提取和眼型模式提取 容易验证上述每步均与模式的对称性无关，亦 等方面 与走步历史无关.如图1所示局面的编码均为 参考文献： S=mod(KB XKw×K,24)= m0d(159766479×1416808× [1]ALBERT L.Feature extractions and representation for pattern recognition and the game of Go[D].Graduate 1230201772835,264)= School of the University of Wisconsin,1970. 3483223225763992904 [2]谷蓉，刘学民，朱仲涛，周杰.一种围棋定式的机器学 2应用方法 习方法U].计算机工程，2004,30(6)：142.144 GU Rong,LIU Xuemin,ZHU Zhongtao,ZHOU Jie.A 有限状态机由一组有限数目的状态和其间的转 machine learning method of joseki in Go [J].The Journal 换规则组成.将进行到不同阶段的定式看作状态，将 of Computer Engineering,2004,30(6):142-144. 走步位置看作转换规则即可将多个定式储存于一个 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
Zobrist 哈希法下不存在的问题. 如图 1 所示 2 个定 式当前局面相同 ,应该具有相同编码 ,但因其走步历 史不同 ,按上述编码方法得到的编码并不一样. 图 1 走步历史不同的同一局面 Fig. 1 The same position with different history 故此 ,提出如下编码方法. 模式范围限制在角部 10 ×10 区域 ,用 64 位(bit) 整数表示编码结果 ,超过 2 64则取模运算后的结果. 首先按以下步骤求得单色 棋子所构成的棋形的编码 :1) 求得模式邻近特征码 ( A) :针对每个点求得与之直连的点个数 ,如果该点 位于棋盘边界则再加上基数 19 ,即棋盘规模 ,并累 乘 ;2) 求得模式行列特征码( B) :求得每行及每列的 棋子至边界的跨度 ,并累乘 ;3) 求得模式轮廓特征码 ( C) :求得模式掩码所包含的点数 ,掩码指刚好包含 模式所有点的最小矩形区域 ;4) 求得最终模式编码 K = mod ( A ×B + C ,2 64 ) . 然后按以下步骤求得双色模式的编码 :1) 求得 某一局面中黑色棋形的模式编码( KB) ;2) 求得白色 棋形的模式编码( Kw) ;3) 求得将黑白色视作同一时 的单色模式编码( Kt) ;4) 则最终模式编码即为 S = mod ( KB ×Kw ×Kt ,2 64 ) . 容易验证上述每步均与模式的对称性无关 ,亦 与走步历史无关. 如图 1 所示局面的编码均为 S = mod ( KB ×Kw ×Kt ,2 64 ) = mod (159 766 479 ×141 680 8 × 1 230 201 772 835 ,264) = 3 483 223 225 763 992 904. 2 应用方法 有限状态机由一组有限数目的状态和其间的转 换规则组成. 将进行到不同阶段的定式看作状态 ,将 走步位置看作转换规则即可将多个定式储存于一个 有限状态机. 因此 ,特定模式需要和下一走步位置联 系 ,而二者并无相关性 ,只能分别储存. 如已知目前 编码和完成下一走步后的新编码 ,如何确定下一走 步位置只能通过搜索可能选点实现. 不过可以通过 适当的提示信息大大减少搜索范围 ,如指明下一走 步位于当前模式掩码的外部或内部第几层上 ,掩码 向四周扩张一步后的边界称为外部第 1 层 ,向内部 区域收缩一步后的边界称为内部第 1 层 ,依此类推. 经棋谱提取定式后储存于模式库 ,可以作为走 步推荐器使用. 当考虑当前棋局状态下某个局部定 式时 ,按上述编码方法于模式库中找到相应模式 ,进 而得到多个可能走步 ,再根据启发式策略选定其一. 3 实验结果及结论 以 507 局专业棋谱为学习材料提取定式 ,定式 最大走步数为 20 ,并记录其总模式数为 27 686 个、 总编码次数为 42 691 次 ,重复编码次数为 43 次 ,总 编码时间为 114 797 ms ,定式库以有限状态机形式 储存 ,平均每步搜索时间为 22 ms. 这种基于模式的 邻近特征、轮廓特征和行列特征的模式编码方法与 模式对称性无关 ,解决了传统编码方法在模式对称 性方面存在的不足[ 1 ,3 - 4 ] ,走步历史不同的同一局面 的编码也保持一致. 其主要缺点在于不能由前后状 态直接确定走步位置 ,不过可以通过启发式信息减 少搜索量. 其主要优点在于计算简单快速 ,哈希性能 良好 ,适用于不同规模的模式 ;在定式储存方面性能 良好 ,也可以应用于官子模式提取和眼型模式提取 等方面. 参考文献 : [1 ] ALBERT L. Feature extractions and representation for pattern recognition and the game of Go [ D ]. Graduate School of the University of Wisconsin , 1970. [2 ]谷 蓉 ,刘学民 ,朱仲涛 ,周 杰. 一种围棋定式的机器学 习方法[J ]. 计算机工程 ,2004 ,30 (6) :142 - 144. GU Rong , L IU Xuemin , ZHU Zhongtao , ZHOU Jie. A machine learning method of joseki in Go[J ]. The Journal of Computer Engineering , 2004 , 30 (6) : 142 - 144. 第 4 期 岳 鹏 ,等 :对称无关的模式编码方法在定式学习中的应用 · 39 ·
·94 智能系统学报 第2卷 构建智能平台 打造精品期刊 《智能系统学报》 双月刊 《智能系统学报》由中国人工智能学会与哈尔滨工程大学联合主办，是中国人工智能学会会刊。中国人 工智能学会是我国智能科学技术领域惟一的国家级民间学术团体，隶属于中国科学技术协会。目前，中国人 工智能学会有22个专业委员会和工作委员会，100多位全国著名学者和知名专家担任专业委员会的领导职 务，20多位院士活跃在智能科学技术的各个领域。 《智能系统学报》主要刊登智能科学领域最新的科研成果和高水平学术论文，内容包括人工智能与计算 智能、智能控制与决策、智能信息处理、模式识别、专家系统与知识工程、机器学习与知识发现以及人工心理 与机器情感等。 中国标准连续出版物号：ISSN1673-4785CN23-1538/TP 邮发代号：14-190 订阅价：15元/期，90元/年 通信地址：哈尔滨市南岗区南通大街145号1号楼 邮编：150001 电话：0451-82534001 82518134 网址：http/www.tis.net.cn 电子信箱：tis@vip.sina.com [3 GRA EPEL T.PAC-Bayesian pattern classification with 李太华，男，1974年生，博士研究生，主 kernels:theory,algorithms,and an application to the 要研究方向为多Agent系统，己发表论文2 game of Go[D].Berlin:Technical University of Berlin, 。 Berlin,2002 E mail:catalyst @swu.edu.cn. [4]BALDI P,RALAIVOLA L,WU L.SVM and pattermr enriched common fate graphs for the game of Go[A].Eu 邱玉辉，男，1938年生，博士生导 ropean Symposium on Artificial Neural Networks [C]. 师，中国人工智能学会副会长，主要研究 Bruges,Belgium,2005. 方向为模糊逻辑、多Agent系统、博弈 [5]STOUTAMIRE D.Machine learning,game play,and Go 等，主持主研国家自然科学基金、省市自 [D].Case Western Reserve University,1991. 然科学基金及攻关项目15项，曾荣获曾 作者简介： 宪梓教育基金会三等奖，四川省优秀教 学成果一、二等奖，重庆市优秀教学成果 岳鹏，男，1974年生，博士研究生，主 一等奖，重庆市自然科学奖二等奖，重庆 要研究方向为博弈，已发表论文2篇」 市科技进步二、三等奖.已发表论文18 Email:yappy555 @swu.edu.cn. 0余篇，出版学术专著10余部 E mail yhqiu @swu.edu.cn. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
构建智能平台 打造精品期刊 《智能系统学报》 双月刊 《智能系统学报》由中国人工智能学会与哈尔滨工程大学联合主办 ,是中国人工智能学会会刊。中国人 工智能学会是我国智能科学技术领域惟一的国家级民间学术团体 ,隶属于中国科学技术协会。目前 ,中国人 工智能学会有 22 个专业委员会和工作委员会 ,100 多位全国著名学者和知名专家担任专业委员会的领导职 务 ,20 多位院士活跃在智能科学技术的各个领域。 《智能系统学报》主要刊登智能科学领域最新的科研成果和高水平学术论文 ,内容包括人工智能与计算 智能、智能控制与决策、智能信息处理、模式识别、专家系统与知识工程、机器学习与知识发现以及人工心理 与机器情感等。 中国标准连续出版物号 :ISSN 1673 - 4785 CN 23 - 1538/ TP 邮发代号 :14 - 190 订阅价 :15 元/ 期 , 90 元/ 年 通信地址 :哈尔滨市南岗区南通大街 145 号 1 号楼 邮 编 :150001 电 话 :0451282534001 82518134 网址 :http :/ / www. tis. net. cn 电子信箱 :tis @vip . sina. com [3 ] GRA EPEL T. PAC2Bayesian pattern classification with kernels: theory , algorithms , and an application to the game of Go [ D ]. Berlin : Technical University of Berlin , Berlin , 2002. [4 ]BALDI P , RALAIVOLA L , WU L. SVM and pattern2 enriched common fate graphs for the game of Go[ A ]. Eu2 ropean Symposium on Artificial Neural Networks [ C ]. Bruges , Belgium , 2005. [5 ]STOU TAMIRE D. Machine learning , game play , and Go [D]. Case Western Reserve University , 1991. 作者简介 : 岳 鹏 ,男 ,1974 年生 ,博士研究生 ,主 要研究方向为博弈 ,已发表论文 2 篇. E2mail : yappy555 @swu. edu. cn. 李太华 ,男 ,1974 年生 ,博士研究生 ,主 要研究方向为多 Agent 系统 ,已发表论文 2 篇. E2mail : catalyst @swu. edu. cn. 邱玉辉 ,男 , 1938 年生 ,博士生导 师 ,中国人工智能学会副会长 ,主要研究 方向为模糊逻辑、多 Agent 系统、博弈 等 ,主持主研国家自然科学基金、省市自 然科学基金及攻关项目 15 项 ,曾荣获曾 宪梓教育基金会三等奖 ,四川省优秀教 学成果一、二等奖 ,重庆市优秀教学成果 一等奖 ,重庆市自然科学奖二等奖 ,重庆 市科技进步二、三等奖 . 已发表论文18 0 余篇 ,出版学术专著 10 余部. 49 · E2mail :yhqiu @swu. edu. cn. · 智 能 系 统 学 报 第 2 卷