千古无同局

基于围棋博弈搜索过程的相关研究及其应用摘要“千古无同局”是关于围棋的谚语，说的是从古至今，人们下的每一局棋都不一样。围棋纵横各十九路，合计三百六十一个交叉点，围棋变化总和大概等于3的361次方，变幻无穷。更何况，有的时候挑起“劫争”，变化更加复杂莫测。正是如此丰富的变化潜力，才造就了“千古无同局”的定律。而本文正是借鉴于围棋当中博弈方面的内容，着手于围棋博弈机器的相关认知及其研究。本文将围棋机器博弈系统看作一个博弈智能体，该智能体利用已有的棋谱知识，通过不断地试探性下棋，从中获取可利用知识，寻找当下或几个步骤之内的最优步伐，以求胜利，并最终完成下棋。这个过程总的概括为一个‘搜索’过程，在这个搜索过程中，博弈智能体通过一定的方法对经验进行学习，最后获得可用知识，达成目标。本文主要分析了如下几个问题：1.阐述博弈相关概念，机器博弈常用算法，以及围棋机器博弈的特点及关键技术；分析机器学习对智能的重要作用，以及在围棋机器博弈中应用机器学习算法的意义；2.介绍机器学习在围棋机器博弈中的解决方法，即人工神经网络以及增强学习。其中，重点介绍了增强学习中时间差分算法的原理机制与应用，建立了基于时间差分算法的围棋机器博弈系统的模型。3.量化围棋博弈动作，改进应用在围棋机器博弈中的时间差分算法，将经过时间差分算法学习后的棋盘状态值作为选取动作后所得的奖励之一，使博弈智能体获得更接近真实的棋盘信息。4.采用围棋机器博弈平台实际对弈方式进行试验，不断进行对弈学习，逐步提高博弈能力；通过大量实验及训练，并比较算法应用前后、改进前后博弈智能体的博弈水平,验证采用时间差分算法与改进效果。关键词：围棋、博弈、机器学习、时间差分、神经网络1一、问题重述围棋博弈相对其他棋类博弈来说，有着更为庞大的搜索空间。早在1000多年前的北宋，当时著名的科学家沈括在其著作《梦溪笔谈》中，详细描述了围棋的状态空间复杂度：“尽三百六十一路，大约连书万字四十三，即是局之大数。其法：初一路可变三局，一黑、一白、一空。自后不以横直，但增一子，即三因之。凡三百六十一增，皆三因之，即是都局数。”沈括计算围棋博弈复杂度的方法比较简单，即19X19的棋盘，共361个点，每个点上可放一颗黑棋或者白棋或者为空。这样，围棋的状态空间复杂度就是361172310。但这只是初步的计算，并没有考虑没有气的子不能放于棋盘上，以及可能有重复的盘面状态。有学者通蒙特卡洛方法计算合法状态的比率约为0.012，则围棋的状态空间复杂度约为0.012×3613≈2.089×17010。这样，相对于象棋的空间复杂度4810而言，围棋有着更大的状态空间复杂度。也正是由于这个原因，计算机围棋可以看作是计算机科学研究的顶峰。2007年，加拿大阿尔伯塔大学JonathanSchaeffer等人在数学上证明西洋跳棋(checkers)的可解性。JonathanSchaeffer通过研究5万亿亿个(5×2010)跳棋位置，构建了达到极致、无法被击败的西洋跳棋程序Chinook。即使下棋者表现良好，最后也只能是平局。但现在人们设计的计算机围棋程序，却无法达到这样的效果。对于围棋庞大的状态空间来说，仅仅凭借枚举经验与高性能设备，在有限时间内也是无法完成的。传统的计算机围棋方法有很大的局限性，前面介绍到的深蓝计算机战胜国际象棋世界冠军卡斯帕罗夫，以及Jonathan等人证明西洋跳棋的可解性，都是基于一定程度的蛮力搜索与高性能设备的。由于计算机其独特特性，缺少能像人一样思考的思维能力与抽象能力，使其更适合一些简单重复的计算。2006年匈牙利学者提出的UCT算法则是基于一定的知识，以蛮力计算为辅助的方法。通过事实证明，这样基于领域知识与蛮力齐备的智能方法，更有其使用价值与优势。但采用这样的方法时，博弈程序每次均采取重新学习的方式，使得博弈程序不能延续以前的学习内容。本文正是基于这样的背景环境下，探讨机器学习算法在围棋机器博弈中的研究与应用，使得围棋机器博弈程序拥有自学习能力，能在不断2的博弈过程中提高博弈水平。提出基于时间差分算法的围棋机器博弈系统模型，并探索时间差分算法在围棋机器博弈中的应用可行性。在整个过程中，本文将围棋博弈系统看作一个博弈智能体，博弈智能体根据所获知识，进行“思考”、“学习”，最后做出决策行为。对以下问题进行研究：1、围棋博弈的软件平台的改进，并且应用于本文的实验研究；2、借鉴机器学习、博弈论中的相关方法，将时间差分算法引入围棋博弈之中，建立基于时间差分算法的围棋机器博弈系统模型；3、改进了时间差分算法，将经过时间差分方法学习后的棋盘状态值作为系统选取后所得奖励之一；4、将BP神经网络应用于基于时间差分算法的围棋机器博弈系统中，为智能体提供“记忆”能力。二、问题分析问题一：本文在围棋博弈中主要采用博弈树及其主要算法进行相关方面的研究，使之能够更加形象具体的展现出围棋博弈与围棋机器主要特点与面临的问题与特点。问题二：主要引进时间差分法进行围棋博弈系统模型的建立。问题三：首要目的是改进时间差分法，将其中的学习算法进行棋盘状态值的学习，提出使用的系统输入的模型机制，实现围棋博弈形式化描述。问题四：引进BP神经网络，并使之应用于时间差分法的围棋系统中，设计设计合理实验方式并得到实验结果。三、模型假设1、假设棋力是恒定的。2、假设黑白棋子足够多。3、假设机器始终在无故障状态下运行。4、根据实际需要，围棋棋盘的大小应适中。四、符号说明符号符号说明3ta智能体在t时刻所执行的动作(,)ttQsa当处于状态ts时执行动作ta的价值tr选取动作ta后所得的系统奖励()tVs表示智能体处于状态时的价值ˆ(,)ttQsa表示一个稍晚的值表示一个稍晚的值nS当前棋盘上己方棋子总数eS当前棋盘上己方眼总数lS当前棋盘上己方气总数tS当前棋盘己方受威胁棋子总数nO当前棋盘上对方棋子总数eO当前棋盘上对方眼总数lO当前其盘上对方气总数tO当前棋盘上对方受威胁棋子总数tV经过学习返回的状态值nS己方棋子总数与对方棋子总数的差值nT吃子数ar动作奖励的具体方式为连接权重为更新因子E（k+1）表示第k+1次迭代后总的误差平方和E(k)表示第k次迭代后总的误差平方和五、模型的建立与求解45.1问题一模型的建立与求解：在问题一中，本文引进了博弈树及其主要算法，下面我们将对博弈树及其算法进行相关介绍。5.1.1博弈树围棋在实际下棋过程中为双人轮流下子，属于双人博弈问题。那么，围棋机器博弈在实际解决过程中也属于双人博弈范畴。用以解决博弈问题的最基本模型，则是博弈树模型。博弈树模型中，博弈树的节点表示不同的博弈盘面，博弈树的边即表示从一个博弈盘面向另一博弈盘面转变的落子行为。用井子游戏举例，博弈双发分别轮流把X和O画在一个33的网格棋盘内。首先在横向、纵向或对角线方向上练成3子1线的一方获胜。表1给出井子游戏的前三层博弈树结构，其中对称的局面视为同一局面。5.1.2博弈树相关算法当采用博弈树模型时，围棋博弈的复杂度又有另一种表示方式，即博弈树复杂度。博弈树复杂度指的是从博弈初始状态所产生的、能完整解决该博弈问题的最小博弈树叶子节点的个数。例如当通过围棋比赛的记录，估计平均每次比赛时所下的步数，确定每个博弈树节点上分支个数，即可知道博弈树复杂度。当每盘棋平均下棋步数为150，平均节点分支数为250时，十九路围棋的博弈树复杂度约为36010。也有学者形象的将围棋的搜索空间与中国象棋和国际象棋作比较，十九路围棋的搜索空间是中国象棋的搜索空间的21010倍，是国际象棋搜索空间的22710倍。这样的数量级可能无法想象到底是何巨大，有学者通过原子核的直径与太阳系的直径作比较，指出这样的数量级比太阳系直径相对于原子核的直径倍数的数量级还要大。由此可见，围棋博弈的复杂度远远超出其他几类常见棋类博弈。下面给出几种博弈的空间状态复杂度和博弈树复杂度。表1常见棋类的状态空间复杂度及博弈树复杂度博弈空间状态复杂度博弈树复杂度国际象棋4610123105中国象棋481015010九路围棋38103510十九路围棋1701036010建立好博弈树模型后，博弈中着法的搜索则转变为博弈树搜索，并且这样的搜索直接关系到智能系统的性能与效率。每次轮到己方下棋时，根据所构建的博弈树搜索到最优子节点，便能寻找到当前最优着法。但这样是否意味着，这样的博弈问题已变得非常简单，每次不停的搜索即可找到最优。事实上，对于一颗非常庞大的博弈树而言，如果访问每个子节点，采用对每个子节点都进行分析来得到最优，是非常困难的。因为节点数量很多，在时间和空间限制条件下，很难在特定的环境中搜索到最优的路径。JonathanSchaeffer等人在证明西洋跳棋checkers的可解性时，便是使用大量计算机硬件设备存储博弈状态。但这在围棋机器博弈中，是无法适用的。围棋博弈空间巨大，采用此方法无法在有限时间内达到预期目标。因此在搜索过程中，如何将对搜索无意义的节点剪枝也是博弈树搜索要解决的关键问题。5.1.3添加描述搜索树的结构体strList，用于存储节点相关信息structstrList{intx;//动作具体位置inty;//动作具体位置intcolor;//颜色（黑、白）intactType;//动作类型（32种之一）doublevalueQ;//Q值unsignedlongstate;//状态intstateV;//状态值VintstateFactor;//状态参数，8位，每一位分别表示状态特征值strList*next;}5.1.4获取样本集，增加棋谱导入功能6在CQUT-GO人机界面上添加[导入棋谱]功能，程序自动读取指定目录下所有*.SGF棋谱格式文件。每读取一张棋谱便模拟棋局下棋，通过递归迭代方式多次更新获得(,)ttQsa值，将具体的状态、动作、与(,)ttQsa值信息存入样本集文件中。继续下一张棋谱文件的导入，直至读取完目录下所有棋谱文件。5.1.5增加开局库，实现部分开局定式围棋的开局布局很重要，为后续下子增加影响力。围棋中意经典口诀为“金角银边草肚皮”，职业选手或业余玩家在开局时基本采用定式。在开局时使用定式使得，博弈对方若想占此块地方，需付出更多的代价，进一步增加己方棋子影响力。5.2问题二模型的建立与求解：在问题二中，本文主要采用时间差分法进行模型的求解。5.2.1时间差分法时间差分算法（temporaldifference，TD）是强化学习算法中一种重要算法，是Sutton于1988年提出的著名算法。TD算法是蒙特卡洛思想和动态规划思想的结合，使得TD算法在不需要系统模型的情况直接从经验中学习。其主要过程为利用探索所得到的下一状态的价值和奖励来更新当前状态的价值，奖励和下一状态分别采样于各自相应的概率分布P(1tr|ts，ta)和P(1ts|ts,ta)。s表示智能体在t时刻的状态，ta表示智能体在t时刻所执行的动作。实际应用中，用Q(ts,ta)表示当处于状态ts时执行动作ta的价值，tr为选取动作ta后所得的系统奖励，用V(ts)表示智能体处于状态ts时的价值。在确定性情况下，即对于任意一对状态动作均只有一个奖励和下一状态。此时，根据Bellman公式，可得如下公式：1111(,)(,)maxttttttaQsarQsa（1）由上式可知，在实际运用中(,)ttQsa的值由11(,)ttQsa得到，11(,)ttQsa的值由22(,)ttQsa得到，即欲得到前一状态-动作价值需得到后一状态-动作价值。为此，式（1）可更新为：71111ˆˆ(,)max(,)ttttttaQsarQsa（2）ˆ(,)ttQsa表示一个稍晚的值，表示一个稍晚的值（0≤γ1）。在上述公式的基础上，将一步ˆ(,)ttQsa值记为：1(1)111ˆ(,)max(,)ttttttaQsarQsa（3）若将第二步即11ˆ(,)ttQsa带入式（5.1.3）中，则：2(2)21222ˆ(,)max(,)tttttttaQsarrQsa