人机对弈围棋报告.doc

基于人工智能理论的围棋人机对弈摘要:人工智能及搜索的基本概念,实现人机对弈围棋的基本理论与方法,关于人机对弈围棋的算法,包括,蒙特卡罗算法,UCT算法,Prolog-EBG算法,MTD(f)算法,Alpha-Beta算法,回溯法-深度优先搜索。(一)基本概念:人工智能(ArtificialIntelligence):是在计算机科学,控制论,信息论,神经生理学,心理学,哲学,语言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。1,搜索的基本概念:(1)搜索的含义:根据问题的实际情况,不断寻找可利用知识,从而构造一条代价最小的推理路线,使问题得以解决的过程称为搜索。(2)状态空间法:状态空间法是人工智能中最基本的问题求解方法,它的基本思想是用“状态”和“操作”来表示和求解问题。(3)问题归约:是不同于状态空间方法的另外一种形式化方法,其基本思想是对问题进行解或变换。2,状态空间的盲目搜索(1)一般图搜索过程(2)广度优先搜索:也称深度优先搜索,它是一种先生成的节点先扩展的策略。(3)深度优先搜索:是一种后生成的节点先扩展的策略。(4)有界深度优先搜索:在深度优先策略中引入深度限制,即采用有界深度优先搜索。(5)代价树搜索:在搜索树中给每条边都标上其代价,称为代价树。3,状态空间的启发式搜索(1)启发性信息和估价函数:启发性信息是指那种与具体问题求解过程有关的,并可知道搜索过程朝着最有希望方向发展的控制信息。估价函数f(n)被定义为从初始节点S0出发,约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式是f(n)=g(n)+h(n)。(2)A算法:启发式搜索算法。(3)A*算法:是对估价函数加上一些限制后得到的一种启发式搜索。4,与/或树的盲目搜索:与或树的搜索过程其实是一个不断寻找树的过程,其搜索过程和状态空间的搜索过程类似,只是在搜索过程中需要多次强调用可解标记过程或不可解标记过程。5,与/或树的启发式搜索:与或树的启发搜索需要不断地选择,修正希望树。6,博弈树的启发式搜索:(1)概述:博弈是一类富有智能行为的竞争活动,可分为双人完备信息博弈和机遇性博弈。若把双人完备信息博弈过程用图表示出来,就可得到一棵与或树,这种与或树被称为博弈树。博弈树具有以下特点:(1)博弈的初始状态是初始节点。(2)博弈树中的或节点和与节点是逐层交替出现的。(3)整个博弈过程始终站在某一方的立场上。(2)极大极小过程:那些对MAX有利的节点,其估价函数取正值;那些对MIN有利的节点,其估价函数取负值;那些使双方均等的节点,其估价函数取接近于0的值。(3)α­β剪枝:与极大极小过程相比,极大极小过程是先生成与或树,然后再计算各节点的估值,这种生成节点和计算估值相分离的搜索方式,需要生成规定深度内的所有节点,因此搜索效率低。如果能边生成节点边估值,从而可以剪去一些没用的分枝,这种技术称为α­β剪枝过程。(二)实现人机围棋的基本方法(1)求任一解路得搜索策略[1]回溯法(backtracking)[2]爬山法(hillclimbing)[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]一般与或图搜索法(AO*)[2]大极小法(minimax)[3]Alpha-Beta算法[4]启发式剪枝法(heuristicpruning)(4)博弈树搜索:[1]博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准的博弈树搜索由四部分组成:1,状态表示2,候选走法产生3,确定目标状态4,一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法(比如α—β)增强了程序的表现。[2]状态表示:从完全信息的角度看,围棋盘面有19*19的3次方格,每个交叉点要么空,要么被黑子或白子占据。状态空间的大小是3的361次方(或10的172次方)。另外,博弈树的大小*例如可能的博弈数)在10的575次方和10的123次方个othello棋的10的55次方。[3]围棋局部死活搜索:围棋局部死活搜索时基于博弈树实现的,树中的结点对应于某个棋局,其分叉表示一步步棋。假设棋手先走,因为棋手可能有多种算法,对手走后得到棋局用“或”结点“表示;然后轮到对手走,用与结点表示这样棋手与对手轮流走棋,从而形成一颗具有”与、或“结点的[