《人机对弈围棋报告》由会员分享，可在线阅读，更多相关《人机对弈围棋报告（11页珍藏版）》请在金锄头文库上搜索。
1、基于人工智能理论的围棋人机对弈摘要：人工智能及搜索的基本概念，实现人机对弈围棋的基本理论与方法，关于人机对弈围棋的算法，包括，蒙特卡罗算法，UCT算法，Prolog-EBG算法，MTD(f)算法，Alpha-Beta算法，回溯法-深度优先搜索。（一）基本概念：人工智能（Artificial Intelligence）：是在计算机科学，控制论，信息论，神经生理学，心理学，哲学，语言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。1，搜索的基本概念：（1）搜索的含义：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。（2）状态空间法：状态
2、空间法是人工智能中最基本的问题求解方法，它的基本思想是用“状态”和“操作”来表示和求解问题。（3）问题归约：是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行解或变换。2，状态空间的盲目搜索（1）一般图搜索过程（2）广度优先搜索：也称深度优先搜索，它是一种先生成的节点先扩展的策略。（3）深度优先搜索：是一种后生成的节点先扩展的策略。（4）有界深度优先搜索：在深度优先策略中引入深度限制，即采用有界深度优先搜索。（5）代价树搜索：在搜索树中给每条边都标上其代价，称为代价树。3，状态空间的启发式搜索（1）启发性信息和估价函数：启发性信息是指那种与具体问题求解过程有关的，并可知道搜索过程
3、朝着最有希望方向发展的控制信息。估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式是f(n)=g(n)+h(n)。（2）A算法：启发式搜索算法。（3）A*算法：是对估价函数加上一些限制后得到的一种启发式搜索。4，与/或树的盲目搜索：与或树的搜索过程其实是一个不断寻找树的过程，其搜索过程和状态空间的搜索过程类似，只是在搜索过程中需要多次强调用可解标记过程或不可解标记过程。5，与/或树的启发式搜索：与或树的启发搜索需要不断地选择，修正希望树。6，博弈树的启发式搜索：（1）概述：博弈是一类富有智能行为的竞争活动，可分为双人完备信息
4、博弈和机遇性博弈。若把双人完备信息博弈过程用图表示出来，就可得到一棵与或树，这种与或树被称为博弈树。博弈树具有以下特点：（1）博弈的初始状态是初始节点。（2）博弈树中的或节点和与节点是逐层交替出现的。（3）整个博弈过程始终站在某一方的立场上。（2）极大极小过程：那些对MAX有利的节点，其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。（3）剪枝：与极大极小过程相比，极大极小过程是先生成与或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率低。如果能边生成节点边估值，从而可以剪去
5、一些没用的分枝，这种技术称为剪枝过程。（二）实现人机围棋的基本方法（1）求任一解路得搜索策略1 回溯法（backtracking）2 爬山法（hill climbing）3 宽度优先法（breadth-first）4 深度优先法（depth-first）5 限定范围搜索法（beam search）6 好的优先法（best-first）7 Prolog-EBG算法8 蒙特卡罗算法9 UCT算法（2）求最佳解路的搜索策略1 大英博物馆法（British Museum）2 分支界限法（branch and bound）3 动态规划法（dynamic programming）4 最佳图搜索法（A*）5
6、 MTD(f)算法（3）求与或关系解图的搜索法1 一般与或图搜索法（AO*）2 大极小法（minimax）3 Alpha-Beta算法4 启发式剪枝法（heuristic pruning）（4）博弈树搜索：1 博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准的博弈树搜索由四部分组成：1，状态表示2，候选走法产生3，确定目标状态4，一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如）增强了程序的表现。2 状态表示：从完全信息的角度看，围棋盘面有19*19的3次方格，每个交叉点要么空，要么被黑子或白子占据。状态空间的大小是3的361次方（或10的172次方）。另外，博弈树的大小
7、*例如可能的博弈数）在10的575次方和10的123次方个othello棋的10的55次方。3 围棋局部死活搜索：围棋局部死活搜索时基于博弈树实现的，树中的结点对应于某个棋局，其分叉表示一步步棋。假设棋手先走，因为棋手可能有多种算法，对手走后得到棋局用“或”结点“表示；然后轮到对手走，用 与 结点表示这样棋手与对手轮流走棋，从而形成一颗具有”与、或“结点的4 形式判断与模糊决策:决策是针对某一问题，根据确定的目标及当时的实际情况指定多个候选方案，然后按一定标准从中选出最佳方案的思维过程。围棋中的每一步棋都是棋手决策的结果，而这种决策又与形式判断密切相关。（三）算法1，蒙特卡罗算法（Monte
8、Carlo method）,（1）算法介绍：运用蒙特卡罗算法作为评估函数，并且试图运用这一评估函数，作为全局性的搜索，蒙特卡罗方法主要理论基础是依据大数定理，在随机取样情况下，可以获得有误差的评估值。（2）蒙特卡罗方法应用于围棋，其核心思想是，在于通过统计许多模拟棋局的结果，进行局面的优劣判断。亦即将蒙特卡罗作为局面评估函数，以决定着手的好坏。1 将分布式计算应用于围棋人机对弈程序上，充分利用多台计算机的运算能力，将运算任务按“能者多劳”的原则分配下去，大大缩短程序的“思考”时间。2 后台计算功能：人机对弈中，在用户思考的同时，计算机不会停止思考的脚步。引擎会将局面进行深入的静态分析并只将对方
9、最有可能落子的点传递给模拟实战的蒙特卡罗算法模块。这样模拟人类在下棋时的思考方式，可以节省很多轮到自己落子时的用时。3 针对蒙特卡罗算法，提出各种改进方式和延伸算法。核心思想为，利用静态分析和搜索为蒙特卡罗算法排除一些坏棋，也可利用改变蒙特卡罗模拟对局中双方落子所用的围棋知识，模拟特殊情况。改进后的蒙特卡罗算法可是具有更高的棋力，对局面的把握更精准。4 算法组合思想：细致深入地挖掘各个经典算法的内在联系，了解各种算法的优势和不足，通过将各个算法模块进行有机的组合和互补，扬长避短，例如让稳定却战斗力不足的搜索和静态分析模块为蒙特卡罗模块提供备选点，既保证程序落子有良好的棋感，也可以保证有强大的计
10、算力为程序的落子进行模拟实战检验。（3）研究来源：篇名：蒙特卡罗方法在计算机围棋中的应用。/程序员2008年12期/Sylvain Gelly等篇名：围棋与人工智能/中国体育科技2005年06期/师军2，UCT算法（又名UCB for Tree Search）：（1）算法介绍：1一个mc围棋程序随机地下棋，而且根据中国规则可以很容易地对双方结束后的态势,行估值。Mc程序经过计算无数个棋局搜索那个取得最高胜率的走法。2 一个最基本的mc程序会简单地为第一个根节点统计数值。但是这些着法的mc估值不会趋向于一个最佳着法，因此需要做更深的搜索。3 UCT算法（树图置信）是对mc搜索自然的扩展，对每一盘
11、棋，通过搜索一个在内存中生长的树来确定最初的着法选择。4 当一个端节点出现时，再生长一个新的枝节点，余下的棋自由走下去。利用棋局最后的5 估值更新对局树中所有走法的统计数据，而这些走法仅是棋局的一部分。,6 UCT算法解决了一个问题，就是在树中选择走法，重要的走法比那些看起来差点的走法更多地被。一个办法就是选择最高胜率高过50的，或者随机走法。（2）应用于围棋的算法描述：Tree Search开始时，UCT会建立一颗Tree，然后1 从根结点开始。2 利用UCB公式计算每个子节点的UCB值，选择最大值的子节点。3 若此节点不是叶节点，则从此节点开始，重复2。4 直到遇到叶节点，如果叶节点曾经被
12、模拟对局过，为这个叶节点生成子节点，从此节点开始重复2。5 否则对这个叶节点进行模拟对局，得到胜负结果，将这个收益按对应颜色更新到该节点及它的每一级祖先节点上去。6 回到1，除非时间结束或者到达预设循环次数。7 从根节点的子节点中挑选平均收益最高的，作为最佳点,此节点就是UCT的结果。（3）UCT Tree 搜索流程总结如下：UCT算法使用极大极小游戏树（minimax game tree）,搭配节点选择公式（UCB公式），选择树节点，展开要测试的节点，然后使用Monte Carlo方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程图如下：（4）研究来源：计算机围棋相关问题研究。中国新技术新
13、产品。，（）：3，Prolog-EBG算法：（1）Prolog-EBG是一种序列覆盖算法，其过程为：1 单个Horn子句规则，移去此规则覆盖的正例；2 在剩余正例上重复这个过程，直到覆盖所有正例为止。对任意的正例集合，Prolog-EBG输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件（2）Prolog-EBG算法的具体过程如下:Prolog-EBG（TargetConcept,TrainingExamples,DomainTheroy）1 LearnedRules=2 Pos=TrainingExamples中的正例3 对Pos中没有被LearnedRules覆盖的每个正例，做解释：
14、Explanation=以DomanTheory表示的解释，说明正例满足TargetConcept改进：SuffcientConditions= 按照Explanation能够充分满足 TargetConcept正例的最一般特征集合LearnedRules=LearnedRules+NewHornClause,其中NewHornClause的形式是：TargetConceptSufficientConditions4返回LearnedRules例，最佳棋着（b,n）非禁着点（b,n） 非劫争禁着点（b,n，历史棋谱）立（b,n）将对方分为两快棋（b,n）若下子则整块气被杀（左边棋块（b,n），
15、-n,color）若下子则整块气被杀（右边棋块（b,n），-n,color）效率最高（所有好着）值得注意的是，类似“非禁着点（b,n）”或“立（b,n）”这样的充分条件很容易在对弈时 ，而“效率最高（所有好着）”则很难判断。在这里“效率”指的是围棋中的子效（着子效率）。针对这个问题，在本文所研究的围棋学习方法中，特别增加了一个评价函数：IGE=LTEPTE4，MTD(f)算法：（1）算法介绍：1 通常试探值并不一定设成零，而是用迭代加深的形式由浅一层的MTD(f)搜索给出；2 局面评价得越粗糙，MTD(f)的效率越高，围棋中可使一个棋子的价值由100降低为10，其他子力也相应比例降低，以提高MTD(f)的效率(但粗糙的局面评价函数却不利于迭代加深启发，因此需要寻求一个均衡点)； 3 零宽度窗口的搜索需要置换表的有力支持，因此称为“用存储器增强的试探驱动器”(Memory-enhanced Test Drive
