第7卷第3期 智能系统学报 Vol.7 No.3 2012年6月 CAAI Transactions on Intelligent Systems Jun.2012 D0I:10.3969/i.issn.16734785.201110005 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120518.0845.002.html 采用时间差分算法的九路围棋机器博弈系统 张小川，唐艳，梁宁宁 (重庆理工大学计算机科学与工程学院，重庆400054) 摘要：围棋机器博弈是机器博弈中重要的分支之一，其庞大的博弈空间给机器博奔研究者带来了巨大挑战.目前 围棋机器博弈多采用静态估值搜素与蒙特卡洛树搜索，故将时间差分算法引入至九路围棋机器博弈系统中，提出基 于时间差分算法的围棋机器博弈系统模型，该博弈系统具有一定的自学习能力，能在不断的对弈中逐步提高博弈能 力.通过与采用B搜索算法的博弈系统进行实际对弈，证明了该方法的可行性： 关键词：机器博弈；九路围棋：围棋机器博弈；时间差分算法 中图分类号：TP31文献标志码：A文章编号：1673-4785(2012)03027805 A 9 x 9 Go computer game system using temporal difference ZHANG Xiaochuan,TANG Yan,LIANG Ningning (College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400054,China) Abstract:Computer Go is an important branch of computer games and presents great challenges to computer game researchers due to its need for huge game space.Presently,the static evaluation method and the Monte-Carlo tree search method are widely used in Go computer games.In this paper,a temporal difference algorithm was intro- duced to the 9 x9 Go computer game system which gave it self-learning capability,thereby improving the game lev- els as a result of the continuous training.Through playing chess with a system which adopts an a-B algorithm,the new method was proven to be effective. Keywords:computer game;9x9 Go;Go computer game;temporal difference 近年来人工智能是信息科学中重要的热点研究标解.因此，本文尝试将时间差分法引入至围棋机器 领域之一，其相关算法、技术及研究成果正被广泛运博弈，将博弈系统看成一个具有自我学习能力的围 用于各行业，如军事、心理学、智能机器、商业智能 棋人工生命体或围棋智能体，它能在不断的博弈过 等.机器博弈是人工智能研究的重要分支，而围棋机 程中提高自己的博弈能力.借助计算机C语言，实 器博弈是机器博弈的热点问题之一，其庞大的搜索 现了该围棋机器博弈系统，并且通过博弈实战验证 空间和较高的复杂度，使其在机器博弈中有着重要 了该方法的有效性和可行性 的研究价值. 目前，围棋机器博弈中常采用的博弈算法有B 1时间差分算法 剪枝搜索算法1、模式匹配231和UCT算法4等.围 1.1强化学习 棋机器博弈相对于六子棋、象棋等其他棋类博弈拥 强化学习(reinforcement learning,RL)较其他常 有更大的搜索空间和更高的复杂度，当采用αβ等传 用的机器学习算法，如神经网络、决策树等，在博弈 统搜索算法时，会在时间有限情况下无法搜索到目 系统中有着独特优势.该方法通过不断的试探与环 境进行交互，根据试探所得到的反馈来决定下一动 收稿日期：2011-10-17. 网络出版日期：201205-18 基金项目：重庆市敕委科研项目(KJ120824):重庆市自然科学基金资 作选取，不同于传统的监督学习.监督学习需要一个 助项目(2007BB2415). 教师信号来告诉智能体怎样选取动作，并给出好坏 通信作者：张小川.E-mail:cqpczxe@163.com. 程度的评价标准，而强化学习则是通过环境反馈来
第3期 张小川，等：采用时间差分算法的九路围棋机器博弈系统 ·279· 评价采取某动作的好坏51.图1简单描述了强化学 Q(s,a)←-Q(s,a)+ 习中智能体与环境的交互过程（其中s为智能体当 n(r++y maxQ(s,+)-Q(s:,a)).(3) 4+1 前所处的环境状态)· 式中：η为更新因子，随时间的增加逐渐减小；Y为 折扣率，0≤y
280 智能系统学报 第7卷 系到棋子被提的可能性和地盘的占有率 法应用在围棋机器博弈中，则此时需解决的问题转 2.2系统动作 化为求合适的动作， 围棋每走一步都有相应的说法，即术语，而常用 2.3动作奖励 的围棋术语有很多，如“拆”、“飞”、“长”、“立”、 当尝试动作a时，系统会获得一个奖励r.,并且 “尖”、“扳”、“接”、“断”、“挖”、“夹”、“托”、“虎”和 在围棋机器博弈中这样的奖励是确定的.在实际的 “刺”等21.若将每一种下法作为一种动作，则系统 博弈过程中，奖励跟下棋后棋盘位置的静态值、己方 动作数量会过大而使算法失去实用性，这需要将术 棋子总数与对方棋子总数、是否吃子与被吃、气微薄 语归类，也就是划分基本动作，下面以“扳”和“挖” 的数目等信息有关例如，当落下某棋子时，使得某 为例说明其归为哪一基本动作，如图2所示，未标号 串棋的气数减少（甚至为1），这样很有可能在对方 棋子为已下棋子，标号棋子为欲下棋子 下一手棋或后几手的时候提掉整个串，这样的下子 动作将会得到较少的奖励（甚至为负）.基于这样的 情况，下面给出动作奖励规则： ra=S。+Sm+Ln+S1: (6) 式中：S,为棋盘棋子位置的静态分值，S。为己方棋 (a)扳 )挖 (c尖 (d跳 子总数与对方棋子总数的差值，L为吃子与被吃子 图2围棋的一些着法 数的差值，S,为对方气为1的棋子数目与己方气为 Fig.2 Some actions in Go 1的棋子数目的差值。 由图2可知，“扳”和“挖”均可看作在己方棋子 的“尖”或“跳”位置上下棋，若选取“扳”和“挖”中 3实验 离棋子1位置最近的己方棋子则为“尖”，采用此归 3.1生成训练集 类方法，选取如下四大类下法作为基本动作：“拆”、 “飞”、“尖”和“长”，如图3所示 当Q(s,a)值（即状态-动作值）很大时，用表格 等手段存储，则表格的尺寸会非常大，这使得搜索空 间也增大.为此，在基于时间差分算法的围棋机器博 弈系统中，采用人工神经网络作为回归器，此时以 s、a.作为网路输入，Q(s,a)值为网络输出，如图4 (a)拆1和拆2 (b)飞1和飞2 所示 棋谱 训练 (c)尖 (d) 文件网络 图3四大基本动作 Fig.3 4 Basic actions expQ(s,a)rTT凵人 P(als)= 选取 由此可得到动作的形式化描述集A,具体形式 之exp[Q(s,b)yTT 动作a 如下： 图4采用神经网络的时间差分算法 A={ActionType）,(ActionDirection）f; Fig.4 The flow chart of the application of temporal ActionType =extend1,entend2,knimovel,kn- difference using neural networks imove2,diamove,nobi; 由于人工神经网络为监督学习方法，因此需要 ActionDirection ={up,down,left,right,to- 训练集TS.故本文首先将棋谱文件导入至博弈系统 pright,botright,topleft,botleft. 中，按照棋谱文件下棋，根据式(3)计算Q(s,a) 式中：动作集A由动作类型和方向参数2个参数组 值，式(3)中需要用到的奖励r。则由式(6)得到，再 成.动作类型有6种，分别为“拆1”、“拆2”、“飞 将s,、a、Q(s,a,)存储至系统中得到样本集TS(表1 1”、“飞2”、“尖”和“长”.“拆1”、“拆2”、“尖”和 给出样本集TS中10个训练样本).其中折扣率y “长”的方向参数为上下左右4个，“飞1”和“飞2” 取0.5,7取0.4，η随时间逐渐减小，每次减小 的方向参数为上下左右和右上、右下、左上、左下8 0.0012.需注意的是，由于围棋博弈空间巨大，故训 个.6种动作组合一起，共32个动作.将时间差分算 练时需要相当数量的样本才能达到训练效果，本文
第3期 张小川，等：采用时间差分算法的九路围棋机器博弈系统 ·281· 选取的样本数为4000. 时，博弈智能体在博弈初期发挥较好，搜索时间短， 表1TS样本集中的10个样本 能为后面棋局摆一个良好阵形，但当进入至中局和 Table 1 10 samples of TS sample set 终局时，进攻能力减弱，系统处于劣势 Q(s,a） 将引入时间差分算法的CQUTG0-2与采用aB 880682780 (0,14) 0.237247 算法的CQUTG0-1对弈100盘，其中CQUTG0-2执 381395919 (0,2) 0.517648 黑和执白各50盘，其对弈结果如图5所示.由此可 见在采用时间差分算法后，博弈系统的博弈能力较 347699070 (10,11) -0.083999 之前有所提高。 402741079 (12,10) -0.093058 60 820219960 (12,12) 0.472617 709852749 (12,11) 0.451825 袋 0 15 514998196 (6,5) -0.387498 COUTGO-1 CQUTGO-2 105471686 (11,10) 0.519132 图5C0LUTG0-1与C0UTG0-2对弈的结果 1016084926 (9,11) 0.501035 Fig.5 The game results of CQUTGO-1 and CQUTGO-2 56907172 (13,3) 0.506086 3.4结果分析 3.2 仿真Q(s,a,)值与选取动作 在基于人工神经网络的时间差分算法中，神经 本文采用BP神经网络，网络输入层有9个节 网络的各个方面均对算法在九路围棋机器博弈系统 点，由系统状态集S={Sn,S。,S,0n,0.,0}、表示动 的应用效果产生影响，包括样本集、神经网络结构和 作位置的x和y,以及用哈希值存储的整个棋盘表 训练次数 示s组成，隐藏层4个节点，输出层1个节点.初始 1)样本集的选取.在实际博弈过程中，同一系 训练时网络权值随机赋值，学习率α取0.5，学习精 统状态下有多种动作可供选择.采用棋谱文件导人 度0取0.0001.BP神经网络根据前向传播输出原 至系统中，便于样本提取并可按不同对手选择不同 理，利用误差反向传播修改权值和阈值.在学习过程 的棋谱文件.但棋谱文件中出现棋盘状态相同的次 中，可将每一个或一定数量的棋谱文件视为学习的 数较少，会降低样本集学习价值，影响学习效果.有 一个停顿.训练好神经网络后，保留修改好的权值和 的学者在选取样本集时采用随机扩展方法，以产生 阈值等参数 在数量和质量上均可观的样本集3] 训练结束后，就可进行对弈，在博弈时将提取到 2)神经网络结构.采用神经网络仿真Q(s,a) 的棋盘状态s,和搜索到的所有合法动作a,输入至 值时，网络输出则直接为相应的s、a,的Q(s,a,) 9×4×1的BP神经网络中，得到Q(s,a)值.然后 值.故网络结构直接影响Q(s,a,)值，也就直接影响 把当前所有合法动作a,所对应的Q(s1,a:)值都求 动作的选取和博奔的决策.选取9个棋盘特征作为 出来，之后便采用式(4)的方法选取动作a,其中式 网络输人，但事实上这样并不能完全描述整个棋盘 (4)中温度变量T的初值为500，在博弈过程中逐渐 状态.例如可将气为1、气为2的棋子数作为棋盘特 减小（每次减小1），从而达到从知识的探索过渡到 征时，当气为1时很可能被提掉，当气为2时，可以 知识的利用.当T值减小到一定程度时则实现知识 形成真眼， 利用，P(als)值大的动作更容易被选取到.此时本 3)训练次数.在神经网络中，网络训练次数也 文采用轮盘赌的方式，生成一个p(0
282. 智能系统学报 第7卷 于围棋博弈的复杂度较高，因此为了提高算法实时 based on immune clustering[J].Journal of Harbin Engi- 性，采用此类模型时将系统状态统计为6个状态因 neering University,2007,28(4):423-428. 素向量，下棋动作划分为6类.这样便简化了系统状 [7]BAE J,CHHATBAR P,FRANCIS J T,et al.Reinforce- 态和动作.虽然该方法能提高算法实时性，但其也存 ment learning via kernel temporal difference[C]//Proceed- ings of the Annual International Conference of the IEEE En- 在不足，无法清晰划分动作和系统状态.而且系统状 gineering in Medicine and Biology Society.Boston,USA, 态和动作的划分直接影响人工神经网络结构，进而 2011：5662-5665, 影响模拟结果.本文后期研究工作的方向是在保证 [8]SUTTON R S.Leaming to predict by the methods of tempo- 算法实时性的前提下，如何划分系统的状态和动作 ral difference[J].Machine Learning,1988,3(1):9-44. 而现阶段围棋机器博弈大都采用蒙特卡洛算法，后 [9]KAELBLING L P,LITTMAN M L,MOORE A W.Rein- 期亦可考虑与其结合来提高算法的有效性。 forcement leaming:a survey[J].Journal of Artificial Intel- ligence Research,1996,4:237-285. 参考文献： [10]阿培丁.机器学习导论[M].范明，昝红英，牛常勇，译 [1]张聪品，刘春红，徐久成.博弈树启发式搜索的aB剪枝 北京：机械工业出版社，2009：372-390. 技术研究[J].计算机工程与应用，2008,44(16)：54- [11]SUTTON R S,BARTO A G.Reinforcement learning:an 55,97. introduction M].Cambridge,USA:The MIT Press, ZHANG Congpin,LIU Chunhong,XU Jiucheng.Research 1997. on alpha-beta pruning of heuristic search in game-playing [12]聂卫平，冯大树.聂卫平围棋道场[M].北京：北京体育 tree[J].Computer Engineering and Applications,2008, 大学出版社，2004. 44(16):54-55,97. [13]徐长明，马宗民，徐心和，等.面向机器博弈的即时差分 [2]刘知青，李文峰.现代计算机围棋基础[M].北京：北京 学习研究[J1.计算机科学，2010,37(8)：219-224. 邮电大学出版杜，2011：6380. XU Changming,MA Zongmin,XU Xinhe,et al.Study of [3]GELLY S,WANG Yizao,MUNOS R,et al.Modification of temporal difference learning in computer games[J].Com- UCT with patterns in Monte-Carlo Go[R/OL].[2011-10- puter Science,2010,37(8):219-224. 15].http:/219.142.86.87/paper/RR6062.pdf. 作者简介： [4]GELLY S,WANG Yizao.Exploration exploitation in Go: 张小川，男，1965年生，教授，中国人 UCT for Monte-Carlo Go[C/OL].[2011-10-15].http:// 工智能学会机器博弈专业委员会副主 wenku.baidu.com/view/66c2edd6b9f390f76c61bc0.html. 任.主要研究方向为人工智能、人工生 [5]张汝波，周宁，顾国昌，等.基于强化学习的智能机器人 命、计算机软件等.主持国家级、省部级 避碰方法研究[J].机器人，1995,21(3)：204-209. 项目6项，横向项目30余项，曾获重庆 ZHANG Rubo,ZHOU Ning,GU Guochang,et al.Rein- 市自然科学奖1项、科技进步奖1项，重 forcement learning based obstacle avoidance leaming for in- 庆市教学成果奖1项.主编教材3部，发表学术论文50余篇. telligent robot[J].Robot,1995,21 (3):204-209. [6]沈晶，顾国昌，刘海波.基于免疫聚类的自动分层强化学 唐艳，女，1987年生，硕士研究生， 习方法研究[J].哈尔滨工程大学学报，2007,28(4)： 主要研究方向为计算智能与智能软件。 423-428 SHEN Jing,GU Guochang,LIU Haibo.Hierarchical rein- forcement learning with an automatically generated hierarchy