人机对弈围棋报告.doc

《人机对弈围棋报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于人工智能理论的围棋人机对弈摘要：人工智能及搜索的基本概念，实现人机对弈围棋的基本理论与方法，关于人机对弈围棋的算法，包括，蒙特卡罗算法，UCT算法，Prolog-EBG算法，MTD(f)算法，Alpha-Beta算法，回溯法-深度优先搜索。（一）基本概念：人工智能（ArtificialIntelligence）：是在计算机科学，控制论，信息论，神经生理学，心理学，哲学，语言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。1，搜索的基本概念：（1）搜索的含义：根据问题的实际情况，不断寻找可利用知识，

2、从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。（2）状态空间法：状态空间法是人工智能中最基本的问题求解方法，它的基本思想是用“状态”和“操作”来表示和求解问题。（3）问题归约：是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行解或变换。2，状态空间的盲目搜索（1）一般图搜索过程（2）广度优先搜索：也称深度优先搜索，它是一种先生成的节点先扩展的策略。（3）深度优先搜索：是一种后生成的节点先扩展的策略。（4）有界深度优先搜索：在深度优先策略中引入深度限制，即采用有界深度优先搜索。（5

3、）代价树搜索：在搜索树中给每条边都标上其代价，称为代价树。3，状态空间的启发式搜索（1）启发性信息和估价函数：启发性信息是指那种与具体问题求解过程有关的，并可知道搜索过程朝着最有希望方向发展的控制信息。估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式是f(n)=g(n)+h(n)。（2）A算法：启发式搜索算法。（3）A*算法：是对估价函数加上一些限制后得到的一种启发式搜索。4，与/或树的盲目搜索：与或树的搜索过程其实是一个不断寻找树的过程

4、，其搜索过程和状态空间的搜索过程类似，只是在搜索过程中需要多次强调用可解标记过程或不可解标记过程。5，与/或树的启发式搜索：与或树的启发搜索需要不断地选择，修正希望树。6，博弈树的启发式搜索：（1）概述：博弈是一类富有智能行为的竞争活动，可分为双人完备信息博弈和机遇性博弈。若把双人完备信息博弈过程用图表示出来，就可得到一棵与或树，这种与或树被称为博弈树。博弈树具有以下特点：（1）博弈的初始状态是初始节点。（2）博弈树中的或节点和与节点是逐层交替出现的。（3）整个博弈过程始终站在某一方的立场上。（2）极大极小过

5、程：那些对MAX有利的节点，其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。（3）αβ剪枝：与极大极小过程相比，极大极小过程是先生成与或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率低。如果能边生成节点边估值，从而可以剪去一些没用的分枝，这种技术称为αβ剪枝过程。（二）实现人机围棋的基本方法（1）求任一解路得搜索策略[1]回溯法（backtracking）[2]爬山法（hillclimb

6、ing）[3]宽度优先法（breadth-first）[4]深度优先法（depth-first）[5]限定范围搜索法（beamsearch）[6]好的优先法（best-first）[7]Prolog-EBG算法[8]蒙特卡罗算法[9]UCT算法（2）求最佳解路的搜索策略[1]大英博物馆法（BritishMuseum）[2]分支界限法（branchandbound）[3]动态规划法（dynamicprogramming）[4]最佳图搜索法（A*）[5]MTD(f)算法（3）求与或关系解图的搜索法[1]一般与或图

7、搜索法（AO*）[2]大极小法（minimax）[3]Alpha-Beta算法[4]启发式剪枝法（heuristicpruning）（4）博弈树搜索：[1]博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准的博弈树搜索由四部分组成：1，状态表示2，候选走法产生3，确定目标状态4，一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如α—β）增强了程序的表现。[2]状态表示：从完全信息的角度看，围棋盘面有19*19的3次方格，每个交叉点要么空，要么被黑子或白子占据。状态空间的大小是3的361次方（

8、或10的172次方）。另外，博弈树的大小*例如可能的博弈数）在10的575次方和10的123次方个othello棋的10的55次方。[3]围棋局部死活搜索：围棋局部死活搜索时基于博弈树实现的，树中的结点对应于某个棋局，其分叉表示一步步棋。假设棋手先走，因为棋手可能有多种算法，对手走后得到棋局用“或”结点“表示；然后轮到对手走，用与结点表示这样棋手与对手轮流走棋，从而形成一颗具有”与、或“结点的[4]