一种围棋定式的机器学习方法
概述1
计算机博弈是人工智能研究的一个重要领域，而计算机
围棋是计算机博弈中极具挑战性的一个分支。在计算机围棋
的发展中，人们对机器学习方法的运用进行过很多研究与尝
试[1~4]。围棋博弈的过程一般划分为个阶段，其中棋局的开3
局部分通常前手左右称为布局，双方互相分割势力范(40)
围。在布局阶段中，有一些经过研究，普遍认为均势的走法
称为定式。
在计算机围棋中引入定式，这是由人类学习过程自然而
来的想法目前最常用的建立定式库的方法是人工录入,, [2,5]。
而事实上，布局阶段中固定性的、带有规律性的走法较多，
是适合于机器学习的；而所谓的定式，也都来源于实际对
弈，可以让机器由学习获得。
文献提出了一种学习定式的基本方法，即记录从空[6]
盘开始在不同棋局中重复出现过在一定范围内完全一致的()
走法，其中，完全一致的范围分别限定为全盘、棋盘和1/21
棋盘考虑旋转与翻折。学习结果与一般概念下的定式还/4()
有较大差距，实战中的使用价值不高，尚处于研究阶段。
与人工录入的定式相比，我们定义的定式更为宽泛，不
但包括大部分传统意义上的定式，还包括了定式的后续变
化，以及对错误走法的应对；与前人通过机器学习获得的定
式[6,7]相比，我们在记录不同棋谱中的重复走法的基础上，
根据对围棋定式的认识，添加了一定约束，使得学习到的定
式更合理，更符合人类的理解，实用性更强。
在计算机围棋博弈系统中，如何正确地应用定式是一直
以来困扰人们的重要问题。涉及定式的围棋博弈系统，一般
都使用模式匹配的方法应用定式和确定着法的其它方式相(
结合，即当前盘面与定式库中定式的前几步一致时，按库)
中定式行棋，若有多种走法时，随机选择[2,5,6]。这种方法不
考虑边和全盘状况，仅根据角部的局部变化选择定式，必然
造成定式应用的呆板无理。文献提出在学习定式时记录[6]
相应的棋局参数，在相同参数下才使用该种定式，其难点在
于简单的棋局参数很难反应出棋局的本质，从而也不能作为
应用定式的判断标准；文献提出了一种利用计算机辅助[7]
人类选择定式的方法，但决策者仍为人类。本文提出了一种
全新的使用组合博弈理论[8]解决定式选择问题的方法。
围棋定式的学习方法2
向职业棋手学习，是提高计算机围棋博弈系统推理水平
的一种有效方法。首先假设，职业棋手包括高段的业余棋(
手走出的每一步棋，相对于计算机围棋博弈系统而言，都)
是正确的走法，都可以作为学习系统的样本。
我们搜集到对局棋谱近NNGS(The No Name Go Server)
局，职业棋手对局棋谱局，构成学习系统丰富20 00014 000
的样本集。
基于对围棋的基本认识，可以认为定式具有以下个特3
征：在实际对局中可以多次复现；复现的区域常常局(1)(2)
限于局部；相对于中盘战斗来说，着法比较固定。(3)
因此，通过机器学习的方法建立定式库是可行的。根据
以上性质，把棋盘×的每个角部看作×的独立棋(1919)1010
局，对其进行规格化处理，即，将每个独立棋局转化到棋盘
的左上角，并保证第步不在对角线上的棋在从左上至右下1(
作者简介：谷蓉－，女，硕士生，主研方向：计算机博弈 (1977)
及模式识别；刘学民，硕士生；朱仲涛，讲师；周杰，副教授
收稿日期：2003-03-05 ： E-mail gurong00@mail.tsinghua.edu.cn
一种围棋定式的机器学习方法
谷蓉 1，刘学民2，朱仲涛2，周杰 1
智能技术与系统国家重点实验室智能信息处理分室，清华大学自动化系，北京；(1. 100084
智能技术与系统国家重点实验室，清华大学计算机科学与技术系，北京2. 100084)
摘要： 提出了一种围棋定式的机器学习方法。利用此方法可实现从棋谱库中自动提取定式并生成定式库。此外，对于棋谱数量较大的情
况，采用分阶段学习方法，提高了学习效率。应用此方法，对局棋谱进行处理，得到定式点个。最后，还给出了种基于组合34 000680 6381
博弈理论在计算机围棋博弈系统中使用定式的方法。
关键词：围棋定式；机器学习；组合博弈理论
A Machine Learning Method of Joseki Database for Computer Go
GU Rong1，LIU Xuemin2，ZHU Zhongtao2，ZHOU Jie1
(1.Division of Intelligent Information Processing, State Key Laboratory of Intelligent Technology and Systems, Department of Automation of
；Tsinghua University, Beijing 1000842.State Key Laboratory of Intelligent Technology and Systems, Department
of Computer Science and Technology of Tsinghua University, Beijing 100084)
【】Abstract A machine learning method of Go joseki for computer Go game system is proposed in this paper. By using this method, various Go joseki can
be automatically extracted from human-played Go game files so as to construct a joseki-tree database. The learning procedure can be separated by several
steps when the learning data set is too large. This approach improves the learning efficiency. 34 000 human-played Go games are processed and 680 638
joseki nodes are created. In addition, a method of how to apply joseki, which is based on combinatory game theory, to computer Go game system is
presented.
【】Key words ；；JosekiMachine learningCombinatorial game theory
第30卷 第6期
Vol.30 № 6
计 算 机 工 程
Computer Engineering
2004年3月
March 2004
·人工智能及识别技术 · 中图分类号： TP311.1 文章编号：1000—3428(2004)06 —0142—03 文献标识码：A
—142—
的对角线上方，具体操作见节。当两盘棋的前面若干步)2.1
着法相同，就可以把它们合并起来，构成树结构，如图所1
示所有的棋谱经过处理可以得到一棵定式树。
图定式树1
定式学习算法2.1
为叙述方便，以下给出几个定义：
定义1 }19,0|{ , <￡= jiPB ji棋盘为格点的集合，
jiP ,其中表示格点。
定义2 |||||| ,, vyuxPP vuyx -+-=格点距离。
定义3 ),( , cPs yx=棋步定义为二元组，即包括格点
BP yx ?, 落子位置及棋子 ()c(黑或白。)
定义4 ),( 1,1 cPs yx= ),( 2,2 cPs vu=棋步，的距离定
|||| ,,21 vuyx PPss =义为棋步对应格点的距离，。
定义5 },0|{ +?== ZnntsS t L棋谱是棋步的集合。
如图将棋盘分为份，左上、右上、左下、右下，分24
4321 ,,, mmmm别记为：
}10,0|{ ,1 <￡= jiPm ji
}100,1910|{ ,2 <￡<￡= jiPm ji
}1910,100|{ ,3 <￡<￡= jiPm ji
}19,10|{ ,4 <￡= jiPm ji
},0|{ +?== ZnntsS t L对于每局棋谱一般可以学习
4321 、J、J、JJ到个定式，以下给出学习算法。4
算法：A
),( , tjit cPs对棋谱中每一步棋，作如下处理：
定式起始点(1)
1, mP ji ?不妨假设
1J 还不存在起始点；1)
ts 4,2 ￡￡ ji位于角上星位及其相邻的个格点之中。2) 9( )
ts ts 1J如果满足条件、，则为定式起始点。 AB
定式后继点(2)
),0( 1dsstiSs tii ￡<￡?" 31 =d如果，满足 ( )
}3,2,1,0{, ?? aaJsi ts aJ aJst ?，则为定式后继，。
1d ts如果距离范围内没有除待考察点外的其它点，则
}min{, tituu sssss =$ 满足 2dss tu ￡如果，且
52 =d }3,2,1,0{, ?? bbJsu ts bJ，，则为定式后( )
bJs t ?继，。
ts如果既不是定式起始点也不是定式后继点，则该步
ts 记为无效点，不在定式问题的考虑之中。
一个棋谱拆分为最多个定式后，则经过规格化，记(3)4
入定式库中。
规格化分为两步：
41 JJ -先将转换到左上角1)
1J ：保持不变；
2J ),18(),( yxPyxP -?：，左右翻转；
3J )18,(),( yxPyxP -?：，上下翻转；
4J )18,18(),( yxPyxP --?：，沿自右上至左下的对
角线翻转。.
第个不在对角线上的棋子若在对角线下方，则2)1
),(),( xyPyxP ? ，这样最好情况下可将定式树缩小为原来
的。1/8
149292 =-+-=AB
图棋盘划分2
结果分析及后处理2.2
经过机器学习，程序从个棋谱中学习到定式点34 000
定式树中的节点个，显然，对于手工输入定式的围()680 638
棋程序是很难达到这一数目的。
定式库在计算机围棋博弈系统中有很多用途。例如，可
以根据当前局面匹配定式库，直接应用定式点；其次，定式
库提供的匹配定式点可作为搜索的候选点，据此可以应用详
尽的搜索算法。常用的搜索算法包括Alpha-Beta Search,
等，它们是死活计算、收官计算的重要Proof Number Search
算法。
图是系统学习到的定式一例，黑至白是常见的小3(a)18
目一间挂定式，对照图棋谱的右下角，我们发现黑至3(b)9
白和棋盘定式周围棋子配置关系紧密，单独走这几步没有14
意义，这并不是我们想要的结果。在图所示定式中，黑3(a)
—143—
至白在棋谱库中出现多次，而黑至白仅出现一次，这18914
正符合前面提到的定式的可复现性——可复现的着法具有推
广意义，是所需的定式，不可复现的着法往往是特定棋局的
特定情况，不具推广意义。据此，对定式库进行后处理。对
每一个定式点，统计有多少棋谱中学到的定式含有这一点，
其数目记为N；有多少棋谱在这一点上脱先，其数目记为
，则脱先率定义为T Ｔ/N。后处理过程中删除定式树中N<2
的节点，这样，像上面黑至白这样的定式点就不会被保914
留。经过后处理，定式点总数削减到约。12 000
(a)
(b)
图定式和棋谱3
分段学习及定式点的表示方法2.3
从上面的结果可以看出，后处理过程删除了％以上90
的定式点，因此，将内存中学习到的定式点经后处理之后再
写入定式库可以节省大量的存储空间。由此也带来了两个问
题：当棋谱数量很多时，内存空间有限，无法一次对所(1)
有棋谱进行处理；所有(2) N 的定式点都被删除，无法和下=1
一批学习到的定式点进行比较。为此，可以采取下面的折中
kSSS ,,, 21 L办法，将棋谱分成若干部分，分阶段处( )
理。在每一阶段学习中，可以认为在定式树中离定式点(N>
越近的点将来成为定式点的可能性越大，为了尽可能保留1)
将来可能成为定式点的点(N> ，处理方法如下：1)
每阶段按照节的算法所述方法学习一部分棋谱(1)2.1A
),,1( kiS i L= ，把它们加入定式库，在后处理中保留 N> 的定1
式点以及T(T 代子孙节点。=5)
kSSS ,,, 21 L重复执行的操作，直到全部完成。再次(2)(1)
对定式树中节点进行处理，删除N＝的节点。1
定式在博弈系统中应用时，需要频繁查找，希望定式树
在内存中占有空间尽可能小。棋盘上每个点的坐标可以用0~
之间的一个整数代表，考虑到棋子的颜色数，每个定式3602
点只需要一个之间的整数就可以表示了。这种表示方0~720
法，相对于传统的表示方法横纵坐标各用一个整数表示，(
棋子颜色用一个整数表示，节省了的内存空间。)2/3
围棋定式的应用3
我们注意到，该算法学习到的定式不仅包括双方互相A
应对的着法，还包括了脱先后的走法，这使得学习到的定式
很容易与组合博弈理论的博弈集合表示相对应[8]。
组合博弈理论由创建J. H. Conway [8,9]。一个组合博
弈是如下形式的有序博弈集合考虑个人完备信息 (game)(2
博弈，结果必有一方胜出即无平局的情况，分别用和代LR
{ }RL GGG |= RL GG 和表博弈双方：，其中也是组合博弈集)
合，分别表示L博弈者或R博弈者在G中走一步后形成的新博
弈。该定义是递归的，空集是定义的基础。最简单的博弈，
就是终局博弈博弈双方都已没有合法的走法，ΦΦ。(){|}=0
博弈集合上定义了两个运算，即“加”运算和“取反”运算：
{ }RRLL GHGHHGHGHG ++++=+ ,|, { }LR GGG --=- |
当先行者必输时，定义博弈值为，0 G ；当=0 L博弈者一
定获胜时，G 其绝对值根据不同的博弈规则定义，能表>0(
示对L的优势；当) R博弈者一定获胜时，G ；当先行者必<0
赢时，G不能确定大小，可记为“”。fuzzy
棋盘上初期可能出现与个角部对应的个定式44
4321 ,,, JJJJ bJJJJG ++++= 4321。定义整盘棋为，
其中b是常数，代表棋盘上非定式的其他部分。定式的选择
问题就是在G上选择一步最有利的着法，算法如下：
算法：B
从盘面的每个角部独立匹配定式库，得到一棵子定式树，代(1)
表当前情况下角部的应对树。应对树的叶节点必须满足两个条件：
脱先条件，有效条件。脱先条件指该节点具有一定的脱先率T/N，
有效条件指该节点在当前盘面下可以走到。将应对树转换成组合博
4321 、J、J、JJ弈理论中的子游戏。
子游戏估值。每个叶节点放到当前棋盘中进行估值，计算每(2)
)(),(),(),( 4321 JCJCJCJC个定式的评价值。注意估值后应对树
一般不会简化成一个简单数。
bJCJCJCJCGC ++++= )()()()()( 4321将子游戏相加。分析在(3) ,G
中选择最优着法。估值后各子游戏结构仍然较复杂，可以使用组合
博弈理论中的相关算法例如温度图分析方法以求得较优解()[9~11]
。
使用这种方法选择定式，不但结合了盘面情况，还考虑
到了先手问题每个子游戏的估值过程不会丢失先手信息。()
结束语4
本文提出了一种计算机围棋博弈系统学习和使用定式的
方法，算法可以从人类棋手的实战棋谱中学习定式，并自A
动建立定式库。基于对算法学习结果的分析，对定式库进A
行后处理，增加统计信息N(重复次数，) T(脱先次数，能有)
效地优化定式树，并能为定式的后续应用提供更多条件。算
法能结合盘面情况应用组合博弈理论选择定式。如要求搜B
索的结果为最优解，在理论上不能保证比传统的Alpha-Beta
算法复杂度低，但可以使用近似算法求得较优解。这Search
在计算机围棋博弈系统的研究中具有很大的实用价值。
下转第页 (173)
—144—
用查看。用户通过交互界面选择设置各种信息的综合检索条
件，限定时间范围、类别、编号和设备台号等结构化信息，
系统对用户输入的数据逐一进行逻辑检查和范围控制，不符
合要求的数据都将给予错误提示，协助用户修改设置。最后
插入关键字和谓词把所有约束条件在规范下组合成一条SQL
完整的查询语句交付执行，返回的结果以图形、列表清单等
不同的形式予以显示。程序算法模型如图所示。3
结束语4
本文提出了将基于令牌总线信息流侦听和主机ARCNET
冗余技术应用于设备生产故障数据监测系统，详尽论述了建
立集散式分层结构的系统各部分程序算法模型的具体思路和
方法。本系统已在中国人民银行某印钞公司成功投入使用，
极大地减少了设备故障停机率，实际运用表明这是一种获取
凹印机设备故障信息，远程实时分析评价设备生产状态的有
效途经，能促进企业设备生产效益得到可靠保障和提高，对
类似设备的故障监测也具有较高的借鉴作用。
参考文献
贾嵘薛惠锋潘泉水电厂闸门群计算机监控系统计算机1 ,, . [J].
工程,2001,27(5):81-82
张剑锋朱永生康荣学等混凝土生产运输浇筑监测子系统的开发2 ,,.
与研制测控技术[J].,2001,20(9):57-60
潘惠勇葛芦生张建培等基于现场总线分布式轧制力信号采集及3 ,,.
故障监测系统华东冶金学院学报[J]., 2000,17(4): 340-343
上接第页(103)
结论4
本文描述了多径源路由测试床的工作并讨论了一些关于
多径源路由的优点与缺点。在运行的时候，我们收集MSR
了一些关于时延和吞吐率的数据。从前面的数据分析，我们
给出了从建设测试床的实践中获得的一些数量的实MSR
例，讨论了协议运行在上的性能并给出了关于性能TCPMSR
方面的有力的实例证明。结果表明在多径上频繁切换会TCP
导致性能下降。
参考文献
1 Perkins C, Royer E. Ad Hoc on Demand Distance Vector (AODV)
Routing. Internet-draft, 1998-11
2 Johnson D, Maltz D. Dynamic Source Routing in Ad Hoc Wireless
Networks. In Imielinski T and Korth H(Editors), Mobile Computing,
Kluwer Academic Publishers, 1996
3 Wang L, Shu Y T, Dong M, et al. Adaptive Multipath Source Routing
in Wireless Ad Hoc Networks. In Proc. IEEE ICC'01, 2001-06: 867
4 Wu Kui, Harms J. Multipath Routing for Mobile Ad Hoc
Networks. Journal of Communications and Networks, 2002, 4(1)
5 Hu Yihchun, Johnson D B. Caching Strategies in On-demand Routing
Protocols for Wireless Ad Hoc Networks.Proceedings of the Sixth
Annual International Conference on Mobile Computing and
Networking (MobiCom 2000), ACM, Boston, MA, 2000-08
6 Maltz D A, Broch J, Johnson D B. Quantitative Lessons from a Full-
scale Multi-hop Wireless Ad Hoc Network Testbed. In Proceedings of
the IEEE Wireless Communications and Networking Conference,IEEE,
Chicago, 2000-09
—173—
图3 车间级监测单元程序算法模型
TCP/IP 协议
车间级监测单元
故障字典
现场监测单元
企业局域网
Winsock 会话
采集故障数据
年度数据备份
过期数据删除
手动数据备份
当前库/历史库
机台对象选择
检索条件设置
起始时间
终止时间
故障类型
故障编号
信息统计
按年统计图表
按月统计图表
按日统计图表
后台打印报表
会话建立
数据年限检查
数据日期检查
当前数据
时间范围选择
信息对象选择
数据再现操作
检索结果
列表清单显示
分析图像显示
设备状态分析
上接第页(144)
参考文献
1 Burmeister J, Wiles J. AI Techniques Used in Computer Go. In: R
Heath, B Hayes, A Heathcote, C Hooker (EDS), Proceedings of the
Fourth Conference of the Australasian Cognitive Science Society,
Newcastle: NSW, 1999
2 Bouzy B,Cazenave T.Computer Go: An AI-oriented Survey. Artificial
Intelligence, 2001, 132(1): 39-103
3 McQuade B.Machine Learning and the Game of Go[Master's Thesis].
Department of Computer Science, Middlebury College, Middlebury,
Vermont, 2001
王鲁明戴汝为在计算机围棋中形象思维的研究自动化学报4 , . . ,
1997, 23(4): 564-566
陈志行电脑围棋小洞天广州中山大学出版社5 . .: , 2000
张玉志计算机围棋博弈系统博士论文北京中国科学院计算6 . []. :
技术研究所 ,1991
7 Steen J V D.A World-wide Go Game Repository. In: Proceedings of
the First International Conference on Baduk, South-Korea: Myongji
University, 2001
8 Conway J H. On Numbers and Games. London: Academic Press, 1976
9 Berlekamp E R,Conway J H,Guy R K.Winning Ways for Your
Mathematical Plays. London: Academic Press, 1982
10 Berlekamp E R, Wolfe D.Mathematical Go: Chilling Gets the Last
Point. MA: A K Peters, Wellesley, 1994
11 Muller M,Berlekamp E,Spight B.Generalized Thermography: Algori-
thms, Implementation, and Application to Go Endgames. Berkeley
University, Technical Report: 96-030, ICSI, 1996
上接第页(158)
3 Jia Chunguang,Tan Ou,Duan Huilong,et al.Medical Imageregistration
Based on Deformable Contour [J].Journal of Computer-aided Design
&Computer Graphics,1999,11 (2 ):115-119
4 Ouyang S,Maynard D E.Phong Shading by Binary Interpolation.
Compute &Graphics,1996,20(6):839-848
5 Zhang Nan,Qin Kaihuai. Image Rendering for Building Cad. CADDM,
1996,6(1)
彭群生真实感图形的计算机生成计算机学报6 .. ,1989,(3 ):226-237
张英杰快速映射技术微电子与计算机7 ..,1994,(4):18-21
亢积真生成真实感图形的四大关键技术计算机应用研究8 ..,1994,
(4):57-59
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
一种围棋定式的机器学习方法
