人机对弈围棋报告

基于人工智能理论的围棋人机对弈摘要：人工智能及搜索的基本概念，实现人机对弈围棋的基本理论与方法，关于人机对弈围棋的算法，包括，蒙特卡罗算法，UCT算法，Prolog-EBG算法，MTD(f)算法，Al

基于人工智能理论的围棋人机对弈 摘要： 人工智能及搜索的基本概念，实现人机对弈围棋的基本理论与方法，关于人机对弈围棋的算法，包 UCTMTD(f)- Prolog-EBGAlpha-Beta 括，蒙特卡罗算法，算法，算法，算法，算法，回溯法深度优先搜 索。 （一）基本概念： Artificial Intelligence 人工智能（）：是在计算机科学，控制论，信息论，神经生理学，心理学，哲学，语 言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。 1 ，搜索的基本概念： 1 （）搜索的含义：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线， 使问题得以解决的过程称为搜索。 2“”“ （）状态空间法：状态空间法是人工智能中最基本的问题求解方法，它的基本思想是用状态和操 ” 作来表示和求解问题。 3 （）问题归约：是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行解或变换。 2 ，状态空间的盲目搜索 1 （）一般图搜索过程 2 （）广度优先搜索：也称深度优先搜索，它是一种先生成的节点先扩展的策略。 3 （）深度优先搜索：是一种后生成的节点先扩展的策略。 4 （）有界深度优先搜索：在深度优先策略中引入深度限制，即采用有界深度优先搜索。 5 （）代价树搜索：在搜索树中给每条边都标上其代价，称为代价树。 3 ，状态空间的启发式搜索 1 （）启发性信息和估价函数：启发性信息是指那种与具体问题求解过程有关的，并可知道搜索过程朝着 f(n)S0n 最有希望方向发展的控制信息。估价函数被定义为从初始节点出发，约束经过节点到达目标 Sgf(n)=g(n)+h(n) 节点的所有路径中最小路径代价的估计值。它的一般形式是。 2A （）算法：启发式搜索算法。 3A* （）算法：是对估价函数加上一些限制后得到的一种启发式搜索。 4/ ，与或树的盲目搜索： 与或树的搜索过程其实是一个不断寻找树的过程，其搜索过程和状态空间的搜索过程类似，只是在 搜索过程中需要多次强调用可解标记过程或不可解标记过程。 5/ ，与或树的启发式搜索： 与或树的启发搜索需要不断地选择，修正希望树。 6 ，博弈树的启发式搜索： 1 （）概述：博弈是一类富有智能行为的竞争活动，可分为双人完备信息博弈和机遇性博弈。 若把双人完备信息博弈过程用图表示出来，就可得到一棵与或树，这种与或树被称为博弈树。 12 博弈树具有以下特点：（）博弈的初始状态是初始节点。（）博弈树中的或节点和与节点是逐层交 3 替出现的。（）整个博弈过程始终站在某一方的立场上。 2MAXMIN （）极大极小过程：那些对有利的节点，其估价函数取正值；那些对有利的节点，其估价 0 函数取负值；那些使双方均等的节点，其估价函数取接近于的值。 3α­β （）剪枝：与极大极小过程相比，极大极小过程是先生成与或树，然后再计算各节点的估值， 这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率低。 α­β 如果能边生成节点边估值，从而可以剪去一些没用的分枝，这种技术称为剪枝过程。