【《围棋博弈基础理论与方法综述》3100字】

围棋博弈基础理论与方法综述目录TOC\o"1-3"\h\u5438围棋博弈基础理论与方法综述 1206191.1围棋博弈基础知识 1285801.1.1围棋起源与规则 1320751.1.2围棋的复杂度 1147641.2基本树搜索理论 287001.2.1极小-极大搜索 2267241.2.2α-β剪枝搜索 3204971.3蒙特卡洛树搜索与围棋 4321431.3.1简单蒙特卡洛方法 4184221.3.2蒙特卡洛树搜索（MCTS） 4119841.3.3MCTS应用于围棋 5围棋博弈基础知识围棋起源与规则围棋是一种二人棋类游戏，相传由五千年前我国的黄帝所创。后来传入东亚各国和欧美地区。围棋使用方形棋盘及黑白两种颜色的圆形棋子进行游戏，棋盘被横纵19条线段（正式比赛多为19*19的棋盘，也有9路、13路和21路围棋）分成361个交叉点，在交叉点上落棋，双方交替走棋，当一个交叉点或一条棋链最外围都被对方的棋子包围则为死棋，落子后除非为死棋（从棋盘上清除）否则不能移动，最后以围地多者为胜。因为黑方先行有优先布局的优势，因此人为规定黑方在棋局结束时要给白方贴目（即黑方减去一些领地进行胜负结算），我国的贴目数为7.5目，日本为6.5目。围棋的复杂度围棋长期以来被成为人类博弈智慧的巅峰，在于其博弈过程变化多端、非常复杂，需要庞大地计算量对棋局进行评估。仅从结果论讲，一盘棋的结果为3的361次方，而其中蕴含的打劫吃子等手段，使得棋局变化更加复杂，而宇宙原子总数也仅仅约为10的80次方，相比之下围棋的变化远超宇宙原子总数，所以以穷举法算尽围棋的规则以达到攻克围棋的目的是非常困难的REF_Ref72182464\r\h[2]。下表为三种棋类的复杂度对比如表2.1所示：表2.1棋类游戏复杂度表游戏围棋井字棋国际象棋State-spaceComplexity31010Game-treeSize361!≈9!10Game-treeComplexity2501010基本树搜索理论极小-极大搜索极小-极大搜索方法是博弈树搜索的基本方法。首先需要设计一个评价函数对棋局进行局面评估。在博弈过程中，我们总是希望自己落子时候能够对己方利益最大化，而敌方落子时总是落在对我们最不利的位置，极小-极大搜索算法便是根据这个思想设计而来。极小-极大搜索的具体过程如下所示，附图2.1：1、轮到我方落子时，搜索一定深度内棋局的所有状态，计算所有叶节点下的棋局评估得分。然后从最深一层的节点开始逆向计算；2、对于我方的落子点，选择子节点中的最大值；3、对于对方的落子点，选择子节点中的最小值；4、循环2、3过程直至得出根节点的值，根节点取值的分枝为当前的最佳走法。图2.1极小-极大搜索过程极小-极大搜索是一种假设对手每次回应都如预料的情况下，从中找出对我方最有利的行棋步骤的搜索方法。但实际博弈过程中对手往往不会如我们所预测的步骤行棋，所以在使用极小-极大搜索算法时，不管设定的搜索深度是多少，只适用于当前一步棋的行棋选择，再次轮到我方行棋时，需要重新对棋局进行搜索，来重新决定下一步棋如何走。对于棋局较小的游戏（如井字棋）而言，计算机使用极小-极大算法遍历所有可能会非常方便，但对于国际象棋或围棋这种局面复杂的游戏而言，棋局本身的复杂度都是宇宙级别的，并且通过极小-极大搜索生成的博弈树将会非常庞大，通过极小极大值搜索将会是一个非常漫长的过程，所以要在复杂的棋类游戏中进行树搜索，需要一种策略来减少树的部分，这种减少搜索树大小的策略称之为剪枝。α-β剪枝搜索Alpha-beta剪枝是一种降低极小-极大算法搜索树大小的搜索算法。该算法核心为：评估出某策略的后续走法比之前策略的还差时，不再计算该策略的后续。该算法和极小-极大算法所得结论相同，但搜索时规避了不具搜索价值的分枝。Alpha-eta剪枝建立在两个基础上：1、整个博弈过程属于零和博弈，即一方的收益必然对应着另一方的损失；2、每一方在行动时总会选择使自己利益最大化的决策。在上述前提下，α-β剪枝算法的核心思想就是：有一个选择A和选择B，在得知B选择不如A选择好，那么就不需要再考虑B选择的具体情况。以2.2.1中的树形结构图为基础，进行剪枝的过程如图2.2所示：1、对于红色方的第一个分支的5和1，选择对自己最有利的5，并向前回溯，存入上一层的节点中；2、对于蓝色方而言，选择对自己最有利的，所以以目前的搜索情况看，需要选择小于等于5的节点；3、红色方继续搜索下一分支，发现有大于5的6，所以向前回溯的过程中，上层节点必然大于等于6；4、根据第一次的搜索情况，蓝色方要小于等于5，此时6的节点对自己更不利，必然不会选择，所以红色方第二次搜索过程中之后的节点无需进行，剪枝完成；5、循环以上过程，进行回溯。图2.2α-β剪枝搜索过程蒙特卡洛树搜索与围棋蒙特卡洛树搜索又称随机抽样方法，是以概率和统计理论方法为基础的一种方法，是使用随机数来解决计算问题的方法。传统的经验方法由于不能逼近真实的物理过程，难以得到满意的结果，而蒙特卡洛树搜索通过模拟采样能够真实地预测现实情况并且可以得到相对满意的结果。蒙特卡洛方法通常将所求解的问题同一定的概率模型相联系，用电子计算机实现抽样模拟与统计，以求得近似解REF_Ref72182519\r\h[3]。简单蒙特卡洛方法简单蒙特卡罗搜索基于一个强化学习模型Mv和一个模拟策略π.在此基础上，对于当前我们要选择动作的状态S{S_t,a,R_(t+1)^k,A_(t+1)^k,……S_t^k}k+1K对于每个(StQa

简单蒙特卡罗搜索可以处理中等规模的问题。但是对于围棋这种状态动作数量级非常大的问题，搜索过程会变得非常慢。同时，由于使用蒙特卡罗法计算其动作价值函数，模拟采样得到的一些中间状态和对应行为的价值就被忽略了。蒙特卡洛树搜索（MCTS）MCTS不再对当前状态St每个动作都要进行K次模拟采样，而是总共对当前状态St进行K次采样，这样采样到的动作可能只是动作全集的一部分。MCTS降低了采样的数量和采样后的搜索计算，而代价是动作全集中的很多动作可能没有采样到，会错失好的动作选择。在MCTS中，基于一个强化学习模型Mv{S_t,a,R_(t+1)^k,A_(t+1)^k,……S_t^k}k+1K采样完毕后，基于采样结果构建MCTS的搜索树，然后近似计算QSt,aQaMCTS搜索的策略分为两个阶段：第一个是树内策略：为当模拟采样得到的状态存在于当前的搜索树时使用的策略。树内策略可以使用ϵ−贪婪策略，随着模拟的进行策略可以得到持续改善，还可以使用上限置信区间算法UCT；第二个是默认策略：如果当前状态不在搜索树内，使用默认策略完成整个状态序列的采样，并把当前状态纳入到搜索树中REF_Ref72182612\r\h[5]。MCTS应用于围棋在围棋游戏中，一步棋只有在棋局结束才能得到真正的结果，一次采样要到棋局结束然后把结果反馈到之前的所有节点中。对于MCTS的树结构，在节点上保存状态对应的历史胜负记录，在每条边上保存采样的动作。以图2.3为例，MCTS的搜索共有四步：图2.3蒙特卡洛树搜索过程1、选择：从根节点开始，每次都选一个价值最高的节点，一般使用UCT选择分数最高的节点，直到来到一个从未扩展过的节点，如图中的3/3节点，然后进入第二步；2、扩展：在这个未扩展的子节点上加一个0/0的子节点，表示没有记录参考，然后进入第三步；3、仿真：从上面没有试过的行棋法开始，使用监督学习得到的快速