人机对弈围棋报告

基于人工智能理论的围棋人机对弈摘要：人工智能及搜索的基本概念，实现人机对弈围棋的基本理论与方法，关于人机对弈围棋的算法，包 括，蒙特卡罗算法，UCT算法，PrologEBG算法，MTD算法，AlphaBeta算法，回溯法-深度优先搜 索。（一）基本概念：人工智能（Artificial Intelligence）：是在计算机科学，控制论，信息论，神经生理学，心理学，哲学，语言 学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。1，搜索的基本概念：（ 1）搜索的含义：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问 题得以解决的过程称为搜索。（ 2）状态空间法：状态空间法是人工智能中最基本的问题求解方法，它的基本思想是用“状态”和“操作” 来表示和求解问题。（ 3）问题归约：是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行解或变换。 2，状态空间的盲目搜索（ 1）一般图搜索过程（ 2）广度优先搜索：也称深度优先搜索，它是一种先生成的节点先扩展的策略。（ 3）深度优先搜索：是一种后生成的节点先扩展的策略。（ 4）有界深度优先搜索：在深度优先策略中引入深度限制，即采用有界深度优先搜索。（ 5）代价树搜索：在搜索树中给每条边都标上其代价，称为代价树。 3，状态空间的启发式搜索（ 1）启发性信息和估价函数：启发性信息是指那种与具体问题求解过程有关的，并可知道搜索过程朝着最 有希望方向发展的控制信息。估价函数f（n）被定义为从初始节点SO出发，约束经过节点n到达目标节点 Sg 的所有路径中最小路径代价的估计值。它的一般形式是 f（n）=g（n）+h（n）。（ 2） A 算法：启发式搜索算法。（3）A*算法：是对估价函数加上一些限制后得到的一种启发式搜索。 4，与/或树的盲目搜索：与或树的搜索过程其实是一个不断寻找树的过程，其搜索过程和状态空间的搜索过程类似，只是在 搜索过程中需要多次强调用可解标记过程或不可解标记过程。5，与/或树的启发式搜索：与或树的启发搜索需要不断地选择，修正希望树。 6，博弈树的启发式搜索：（1）概述：博弈是一类富有智能行为的竞争活动，可分为双人完备信息博弈和机遇性博弈。 若把双人完备信息博弈过程用图表示出来，就可得到一棵与或树，这种与或树被称为博弈树。博弈树具有以下特点：（1）博弈的初始状态是初始节点。（2）博弈树中的或节点和与节点是逐层交替 出现的。（3）整个博弈过程始终站在某一方的立场上。（2）极大极小过程：那些对 MAX 有利的节点，其估价函数取正值；那些对 MIN 有利的节点，其估价函 数取负值；那些使双方均等的节点，其估价函数取接近于0的值。（3）a 0剪枝：与极大极小过程相比，极大极小过程是先生成与或树，然后再计算各节点的估值，这种 生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率低。如果能 边生成节点边估值，从而可以剪去一些没用的分枝，这种技术称为a 0剪枝过程。二)实现人机围棋的基本方法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 MTD算法3) 求与或关系解图的搜索法1 一般与或图搜索法(A0*)2 大极小法( minimax)3 Alpha-Beta 算法4 启发式剪枝法( heuristic pruning)4) 博弈树搜索：1 博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准的博弈树搜索由四部分组成：1， 状态表示 2，候选走法产生 3，确定目标状态 4，一个确定相对优势状态的静态评估函数。有效的 博弈树剪枝方法(比如a 0 )增强了程序的表现。2 状态表示：从完全信息的角度看，围棋盘面有19*19的3次方格，每个交叉点要么空，要么被黑子或白子 占据。状态空间的大小是3的361次方(或10的172次方)。另外，博弈树的大小*例如可能的 博弈数)在10的575次方和10的123次方个Othello棋的10的55次方。3 围棋局部死活搜索：围棋局部死活搜索时基于博弈树实现的，树中的结点对应于某个棋局，其分叉表示一步步棋。假 设棋手先走，因为棋手可能有多种算法，对手走后得到棋局用“或”结点“表示；然后轮到对手走 用 与 结点表示这样棋手与对手轮流走棋，从而形成一颗具有”与、或“结点的4 形式判断与模糊决策:决策是针对某一问题，根据确定的目标及当时的实际情况指定多个候选方案，然后按一定标准从 中选出最佳方案的思维过程。围棋中的每一步棋都是棋手决策的结果，而这种决策又与形式判断密切 相关。（三）算法1 ，蒙特卡罗算法（ Monte Carlo method） ,（1）算法介绍：运用蒙特卡罗算法作为评估函数，并且试图运用这一评估函数，作为全局性的搜索，蒙 特卡罗方法主要理论基础是依据大数定理，在随机取样情况下，可以获得有误差的评估值。（2）蒙特卡罗方法应用于围棋，其核心思想是，在于通过统计许多模拟棋局的结果，进行局面的优劣判断。 亦即将蒙特卡罗作为局面评估函数，以决定着手的好坏。1 将分布式计算应用于围棋人机对弈程序上，充分利用多台计算机的运算能力，将运算任务按“能者 多劳”的原则分配下去，大大缩短程序的“思考”时间。2 后台计算功能：人机对弈中，在用户思考的同时，计算机不会停止思考的脚步。引擎会将局面进行 深入的静态分析并只将对方最有可能落子的点传递给模拟实战的蒙特卡罗算法模块。这样模拟人类在 下棋时的思考方式，可以节省很多轮到自己落子时的用时。3 针对蒙特卡罗算法，提出各种改进方式和延伸算法。核心思想为，利用静态分析和搜索为蒙特卡罗 算法排除一些坏棋，也可利用改变蒙特卡罗模拟对局中双方落子所用的围棋知识，模拟特殊情况。改 进后的蒙特卡罗算法可是具有更高的棋力，对局面的把握更精准。4 算法组合思想：细致深入地挖掘各个经典算法的内在联系，了解各种算法的优势和不足，通过将各 个算法模块进行有机的组合和互补，扬长避短，例如让稳定却战斗力不足的搜索和静态分析模块为蒙 特卡罗模块提供备选点，既保证程序落子有良好的棋感，也可以保证有强大的计算力为程序的落子进 行模拟实战检验。（3）研究来源：篇名：蒙特卡罗方法在计算机围棋中的应用。/程序员 2008 年 12 期/Sylvain Geliy 等 篇名：围棋与人工智能/中国体育科技2005年06期/师军2，UCT 算法（又名 UCB for Tree Search）：（1）算法介绍：1 一个me围棋程序随机地下棋，而且根据中国规则可以很容易地对双方结束后的态势，行估值。Me程 序经过计算无数个棋局搜索那个取得最高胜率的走法。2 一个最基本的 me 程序会简单地为第一个根节点统计数值。但是这些着法的 me 估值不会趋向于一 个最佳着法，因此需要做更深的搜索。3 UCT算法（树图置信）是对me搜索自然的扩展，对每一盘棋，通过搜索一个在内存中生长的树来 确定最初的着法选择。4 当一个端节点出现时，再生长一个新的枝节点，余下的棋自由走下去。利用棋局最后的5 估值更新对局树中所有走法的统计数据，而这些走法仅是棋局的一部分。 ，6 UCT 算法解决了一个问题，就是在树中选择走法，重要的走法比那些看起来差点的走法更多地被。 一个办法就是选择最高胜率高过 50的，或者随机走法。（2）应用于围棋的算法描述：Tree Search开始时，UCT会建立一颗Tree，然后1 从根结点开始。2 利用 UCB 公式计算每个子节点的 UCB 值，选择最大值的子节点。3 若此节点不是叶节点，则从此节点开始，重复 2。4 直到遇到叶节点，如果叶节点曾经被模拟对局过，为这个叶节点生成子节点，从此节点开始重复 2。5 否则对这个叶节点进行模拟对局，得到胜负结果，将这个收益按对应颜色更新到该节点及它的每一 级祖先节点上去。6 回到 1，除非时间结束或者到达预设循环次数。7 从根节点的子节点中挑选平均收益最高的，作为最佳点，此节点就是UCT的结果。（3）UCT Tree搜索流程总结如下：UCT算法使用极大极小游戏树（minimax game tree）, 搭配节点选择公式（UCB公式），选择树节点，展开要测试的节点，然后使用 Monte Carlo方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程图如下：（4）研究来源：计算机围棋相关问题研究。中国新技术新产品。2 0 0 9, （ 1 6 ）： 27O 艰貝*机*选择节点展卄节点 k 棋局模拟 叫嵋更新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 覆盖的每个正例，做解释：Explanation =以 DomanTheory 表示的解释，说明正例满足 TargetConcept改进：SuffcientConditions=按照Explanation能够充分满足TargetConcept正例的最一般特征集合LearnedRules=LearnedRules+NewHornClause,其中 NewHornClause 的形式是：TargetConceptSufficientConditions4返回 LearnedRules例，最佳棋着（b,n）非禁着点（b,n） a非劫争禁着点（b,n,历史棋谱）人立（b,n） a将对方分为两快棋（b,n）a若下子则整块气被杀（左边棋块（b,n）, -n,color）a若下子则整块气被杀（右边棋块（b,n）, -n,color）a效率最高（所有好着）值得注意的是，类似“非禁着点（b,n）”或“立（b,n）”这样的充分条件很容易在对弈时，而“效率 最高（所有好着）”则很难判断。在这里“效率”指的是围棋中的子效（着子效率）。针对这个问题，在本 文所研究的围棋学习方法中，特别增加了一个评价函数：IGE = LTEUPTE4, MTD（f）算法：（1）算法介绍：1 通常试探值并不一定设成零，而是用迭代加深的形式由浅一层的MTD（f）搜索给出；2 局面评价得越粗糙，MTD的效率越高，围棋中可使一个棋子的价值由100降低为10,其他子力也 相应比例降低，以提高MTD（f）的效率（但粗糙的局面评价函数却不利于迭代加深启发，因此需要寻 求一个均衡点）；3 零宽度窗口的搜索需要置换表的有力支持，因此称为“用存储器增强的试探驱动器”（Memory-enhanced Test Driver，即MTD），它只需要传递两个参数（深度n和试探值f）,故得名为MTD（n,f），缩写为MTD（f）。4 MTD（f）的一个大的优势在于我们可以简化Alpha-Beta搜索，因为它只需要两个参数（深度和Alpha）而 不是三个。（2）算法的实现：（Java代码）1. int MTDF（int test, int depth） 2. int score, beta, upperbound, lowerbound;3. score = test;4. upperbound = +INFINITY;5. lowerbound = -INFINITY;6. do 7. beta = （score = lowerbound ? score + 1 : score）;8. score = alphabeta（depth, beta - 1, beta）;9. （score beta ? upperbound : lowerbound） = score;10. while （lowerbound = 3，那么返回的是-4, -4= beta) return val; if(val alpha) alpha = val; return alpha；/返回最好的值(3) 研究来源：王晓春，上海理工大学计算机工程学院，棋类对弈人工智能算法研究，2006-12 6，回溯法(深度优先搜索)：(1) 回溯法的应用模式：1 设置初始化的方案(给变量赋初值，读入已知数据等)。令I表示行变量A(I)表示列变量。1 = 1.A(I)=12 变换方式去试探，I = I + 1 ,A(I)=A(1 )+1,若I8则转(6)若A(I)8则 转(7)。3 判断此方法是否成功，若A(I)A(J)=SNG(A(I)A(J)(I J)成功则 转(2)。4 试探成功则前进一步再试探。5 正确方案(I = 8)还未找到则转(2)。6 已找到一种方案则记录并打印。7 退回一步(回溯)，若为退到头则转(2)。8 已退到头(I = 0 )则结束或打印无解。(2) 算法的实现：10 DIM A(8)： N=02 0 I = 1：A(I)=13 0 I = I + 1：I FI8 THEN 8040A(I)=A(1)+1： IFA(I)8THEN10050FORJ=I1 TO STEP16 0 IFAA(I)A(J)=SNG(A(I)A(J)*(IJ)7 0NEXT：GOYO 3080N=N+1： FOR K=1TO890I=I1：GOYO40100A(I)=0；I=I1110 IFI=0 THEN END120 GOTO 40(3) 研究来源：专题性智能搜索研究与实现，昆明理工大学 2005： 34-37(四)相关函数、类：LoadString LoadAccelerators GetMessage TranslateAccelerator TranslateMessage DispatchMessage RegisterClassEx LoadIcon LoadCursor CreateWindow ShowWindow UpdateWindow FillRect GetStockObject GetDC GetClientRect InvalidateRect DialogBox DestroyWindow DefWindowProc BeginPaint Rectangle EndPaint PostQuitMessage EndDialog SetRect GetPath GetParent SetFocus Arc timeGetTime SwapBuffers Polygon ReleaseDC RegOpenKeyEx RegQueryValueEx RegCloseKey(五)程序：void AstarPathfinder:FindPath(int sx, int sy, int dx, int dy)NODE *Node, *BestNode;int TileNumDest;TileNumDest = TileNum(sx, sy);/生成 Open 和 Closed 表/*EN=( NODE*/;calloc(1,sizeof( NODE );CLOSED=( NODE* )calloc(1,sizeof( NODE );Node=( NODE* )calloc(1,sizeof( NODE );Node-g = 0;Node-h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); / should really use sqrt().Node-f = Node-g+Node-h;Node-NodeNum = TileNum(dx, dy);Node-x = dx;Node-y = dy;OPEN-NextNode=Node; / make Open List point to first nodefor (;)BestNode=ReturnBestNode();if (BestNode-NodeNum = TileNumDest) / if weve found the end, breakand finishbreak;GenerateSuccessors(BestNode,sx,sy);PATH = BestNode;GenerateSuccessors：void AstarPathfinder:GenerateSuccessors(NODE *BestNode, int dx, int dy)int x, y;if ( FreeTile(x=BestNode-x-TILESIZE, y=BestNode-y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);/ Upperif ( FreeTile(x=BestNode-x, y=BestNode-y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);/ Upper-Rightif ( FreeTile(x=BestNode-x+TILESIZE, y=BestNode-y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);if ( FreeTile(x=BestNode-x+TILESIZE, y=BestNode-y) ) GenerateSucc(BestNode,x,y,dx,dy);if ( FreeTile(x=BestNode-x+TILESIZE, y=BestNode-y+TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);/ Lowerif ( FreeTile(x=BestNode-x, y=BestNode-y+TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);/ Lower-Leftif ( FreeTile(x=BestNode-x-TILESIZE, y=BestNode-y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);/ Leftif ( FreeTile(x=BestNode-x-TILESIZE, y=BestNode-y) )GenerateSucc(BestNode,x,y,dx,dy);GenerateSucc：void AstarPathfinder:GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy)int g, TileNumS, c = 0;NODE *Old, *Successor;g = BestNode-g+1; / g(Successor)=g(BestNode)+cost of getting fromBestNode to SuccessorTileNumS = TileNum(x,y); / identification purposes/if ( (Old=CheckOPEN(TileNumS) != NULL ) / if equal to NULL then not inOPEN list, else it returns the Node in Oldfor( c = 0; c Childc = NULL ) / Add Old to the list of BestNodes C hildren (or Successors).break;BestNode-Childc = Oldif ( g g ) / if our new g value is Parent = BestNode;Old-g = g;Old-f = g + Old-h;elseif ( (Old=CheckCLOSED(TileNumS) != NULL ) / if equal to NULL then not in OPEN list, else it returns the Node in Oldfor( c = 0; cChildc = NULL ) / Add Old to the list of BestNodes Chi ldren (or Successors).break;BestNode-Childc = Old;if ( g g ) / if our new g value is Parent = BestNode;Old-g = g;Old-f = g + Old-h;PropagateDown(Old); / Since we changed the g value of Old, we nee delse Successor = ( NODE* )calloc(1,sizeof( NODE );Successor-Parent = BestNode;Successor-g = g;Successor-h = (x-dx)*(x-dx) + (y-dy)*(y-dy); / should do sqrt(), but since we dont reallySuccessor-f = g+Successor-h; / care about the distance but just which branch looksSuccessor-x = x; / better this should suffice. Anyayz its faster.Successor-y = y;Successor-NodeNum = TileNumS;Insert(Successor); / Insert Successor on OPEN list wrt ffor( c =0; c Childc = NULL ) / Add Old to the list of BestNodes Ch ildren (or Successors).break;BestNode-Childc = Successor;基于人工智能理论的围棋人机对弈08 计算机1 班 11 号张超20081118610015（3）UCT Tree搜索流程总结如下：UCT算法使用极大极小游戏树（minimax game tree）, 搭配节点选择公式（UCB公式），选择树节点，展开要测试的节点，然后使用 Monte Carlo 方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程图如下：（4）研究来源：计算机围棋相关问题研究。中国新技术新产品。2 0 0 9, （ 1 6 ）： 273，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 覆盖的每个正例，做解释：Explanation =以 DomanTheory 表示的解释，说明正例满足 TargetConcept改进：SuffcientConditions=按照Explanation能够充分满足TargetConcept正例的最一般特征集合LearnedRules=LearnedRules+NewHornClause,其中 NewHornClause 的形式是：TargetConceptSufficientConditions4返回 LearnedRules例，最佳棋着（b,n）非禁着点（b,n） a非劫争禁着点（b,n,历史棋谱）人立（b,n） a将对方分为两快棋（b,n）a若下子则整块气被杀（左边棋块（b,n）, -n,color）a若下子则整块气被杀（右边棋块（b,n）, -n,color）a效率最高（所有好着）值得注意的是，类似“非禁着点（b,n）”或“立（b,n）”这样的充分条件很容易在对弈时，而“效率 最高（所有好着）”则很难判断。在这里“效率”指的是围棋中的子效（着子效率）。针对这个问题，在本 文所研究的围棋学习方法中，特别增加了一个评价函数：IGE = LTEUPTE