第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<1,保证返回的奖励为有限的. 回报r,a 对于动作的选取，在知识量少的初期，可以在所 有动作中随机选取，可看作“探索”.但也不希望一 智能体 动作a 环境 直探索下去，故探索到一定时，需利用当前所学知 识.为此采用一个温度变量T来实现从探索到利用 图1强化学习中智能体与环境交互过程 知识的转移，下面给出加入温度变量时选择动作a Fig.1 The agent and the environment interaction process in reinforcement learning 的概率0： 如果将强化学习应用到围棋机器博弈中，博弈 P(als)=_exp[Q(s,a)/T] (4) 程序变成具有一定智能的决策者，而围棋棋盘就被 ∑exp[Q(s,b)/T] 看作博弈环境.当博弈双方产生新着法时，围棋棋盘 当T很大时，所有概率趋近于相等，此时进行 的状态就发生了改变，博弈环境的状态也随着发生 随机探索；当T很小时，价值更大的动作被选取的 转移.同时在博弈进程中，从博弈开始到博弈结束， 可能性较大，则实现对知识的利用.所以在学习的过 其整个过程包含系列的博弈着法，即博弈着法的集 程中以一个较大的T值开始，不断地缩小T值，完 合；因此利用强化学习解决围棋博弈问题的核心，就 成探索直至利用知识， 是要建立一种合适的内部奖励机制，使得博奔程序 或围棋人工生命体能执行最大化内部奖励的局部动 2基于时间差分算法的围棋机器博奔 作，从而学会发现一个最佳的着法序列，并提高博弈 模型 水平 1.2时间差分算法 当求解问题的状态空间较大时，会使强化学习 时间差分算法(temporal difference)是强化学习 算法的收敛效率降低，这就要求增加实验次数，但降 的一种重要算法)，其利用探索所得到的下一状态 低了算法的实时性山.而在围棋机器博奔中，若搜 的价值和奖励来更新当前状态的价值⑧].本文经过 索超时则直接判负.并且当处于中局时，棋盘状态复 研究分析，构造了博弈状态转移特征方法，利用该方 杂度增加，若把每个可下点看作一个动作，则算法的 法获得的特征信息（特别是激励性信息）反馈于当 状态与动作数量大幅度增长.故需采用其他策略减 前博弈状态，并更新当前博弈状态，引导博弈系统的 少问题状态空间，以增强算法的实时性.为此，采用 价值取向，这就是本文引人时间差分算法的机器博 将静态估值与时间差分算法相结合的策略，在产生 奔的基本思路 可下节点时，选取静态估值较大的点，再在此点上利 在实际应用中，通常采用成对的状态-动作值 用时间差分算法完成动作的选取， Q(s,a,)来表示当处于状态s,时执行动作a,的价 2.1系统状态 值.在简单的确定的情况下，任意一对状态-动作只 在博弈过程中，围棋棋盘状态作为环境因素直接 有1个奖励和可能的下一状态，根据Bellman公式， 影响博弈智能体作出的决策，如开局时摆棋形、博奔过 可得如式(1)的简化公式1： 程中己方受威胁棋子、对方受威胁棋子等.本文选取环 Q(s:,a)=r++y maxQ(sI,a+). (1) 境因素中对博弈智能体的决策影响较大的因素作为系 + 统问题状态该状态集形式化描述如式(5)： 式中：max(s,+1,a+1)表示充分利用已有发现，选择 S={Sn,S。,S,0n,0.,0} (5) 具有最高价值的动作，当处于探索阶段时，若处于状 式中：S,为当前棋盘上己方棋子总数，S。为当前棋 态s,则随机选取一个动作a,返回一个奖励r+1,并 盘上己方眼总数，S:为当前棋盘上己方气总数，0 将状态转移至3+1·此时，前一动作的价值更新为 为当前棋盘上对方棋子总数，O.为当前棋盘上对方 Q(s,a)←-T+1+y maxQ(s+1,a+1).(2) 眼总数，O,为当前棋盘上对方气总数.其中，Sn与 a+1 由此可以看出Q(s+1,a+1)是更新后的值，具有更 0.直接关系到当前博弈双方对弈的局势；S。与O 高的正确概率.将式(2)引入，以减小当前Q值与一 直接关系到某串棋是否为活棋，如当某串棋有2个 个时间步骤之后的估计值之间的误差，则有式(3)： 眼，则被提掉的可能性减小至0；S,与O,则直接关
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<p<1),判断P 直接关系到参数是否达到目标精度，直接影响学习 值落在哪2个动作的P(αls)值之间，便可判断选取 效果 哪个动作a· 3.3实验结果 4结束语 在实验初期，由于采用零知识学习，未给予任何 本文将时间差分算法应用在机器博弈中，给出 其他相关辅助知识，如眼的识别判断、活棋的判断 了包含系统状态、系统动作及动作奖励的博弈系统 等；故此时该博弈系统并没有体现其优势，常走出坏 招死招.当加入知识判断时，系统的博弈能力明显提 模型，并通过实验验证了该方法的有效性.引入时间 高.并且通过实验发现，在单纯采用时间差分算法 差分算法后的博弈系统是一个具有自学习能力的博 弈智能体，能在不断的博弈过程中提高博弈水平.由
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