基于人工智能理论的围棋人机对弈

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

（一）基本概念：
人工智能（Artificial Intelligence）：是在计算机科学，控制论，信息论，神经生理学，心理学，哲学，语言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科。

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] 爬山法（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(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次方）。另外，博弈树的大小*例如可能的博弈数）在10的575次方和10的123次方个othello棋的10的55次方。
[3] 围棋局部死活搜索：
围棋局部死活搜索时基于博弈树实现的，树中的结点对应于某个棋局，其分叉表示一步步棋。假设棋手先走，因为棋手可能有多种算法，对手走后得到棋局用“或”结点“表示；然后轮到对手走，用 与 结点表示这样棋手与对手轮流走棋，从而形成一颗具有”与、或“结点的
[4]  形式判断与模糊决策:
决策是针对某一问题，根据确定的目标及当时的实际情况指定多个候选方案，然后按一定标准从中选出最佳方案的思维过程。围棋中的每一步棋都是棋手决策的结果，而这种决策又与形式判断密切相关。



（三）算法
1，蒙特卡罗算法（Monte Carlo method）
,（1）算法介绍：运用蒙特卡罗算法作为评估函数，并且试图运用这一评估函数，作为全局性的搜索，蒙特卡罗方法主要理论基础是依据大数定理，在随机取样情况下，可以获得有误差的评估值。
（2）蒙特卡罗方法应用于围棋，其核心思想是，在于通过统计许多模拟棋局的结果，进行局面的优劣判断。亦即将蒙特卡罗作为局面评估函数，以决定着手的好坏。
[1] 将分布式计算应用于围棋人机对弈程序上，充分利用多台计算机的运算能力，将运算任务按“能者多劳”的原则分配下去，大大缩短程序的“思考”时间。
[2] 后台计算功能：人机对弈中，在用户思考的同时，计算机不会停止思考的脚步。引擎会将局面进行深入的静态分析并只将对方最有可能落子的点传递给模拟实战的蒙特卡罗算法模块。这样模拟人类在下棋时的思考方式，可以节省很多轮到自己落子时的用时。
[3] 针对蒙特卡罗算法，提出各种改进方式和延伸算法。核心思想为，利用静态分析和搜索为蒙特卡罗算法排除一些坏棋，也可利用改变蒙特卡罗模拟对局中双方落子所用的围棋知识，模拟特殊情况。改进后的蒙特卡罗算法可是具有更高的棋力，对局面的把握更精准。
[4] 算法组合思想：细致深入地挖掘各个经典算法的内在联系，了解各种算法的优势和不足，通过将各个算法模块进行有机的组合和互补，扬长避短，例如让稳定却战斗力不足的搜索和静态分析模块为蒙特卡罗模块提供备选点，既保证程序落子有良好的棋感，也可以保证有强大的计算力为程序的落子进行模拟实战检验。
（3）研究来源：篇名：蒙特卡罗方法在计算机围棋中的应用。
/程序员2008年12期/Sylvain Gelly等　
篇名：围棋与人工智能/中国体育科技2005年06期/师军
2，UCT算法（又名UCB for Tree Search）：
（1）算法介绍：
[1]一个mc围棋程序随机地下棋，而且根据中国规则可以很容易地对双方结束后的态势,行估值。Mc程序经过计算无数个棋局搜索那个取得最高胜率的走法。
[2] 一个最基本的mc程序会简单地为第一个根节点统计数值。但是这些着法的mc估值不会趋向于一个最佳着法，因此需要做更深的搜索。
[3] UCT算法（树图置信）是对mc搜索自然的扩展，对每一盘棋，通过搜索一个在内存中生长的树来确定最初的着法选择。
[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）研究来源：计算机围棋相关问题研究。中国新技术新产品。２００９，（１６）：２７

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的形式是：TargetConcept←SufficientConditions
[4]返回LearnedRules
例，最佳棋着（b,n）←非禁着点（b,n）ʌ 非劫争禁着点（b,n，历史棋谱）
ʌ立（b,n）ʌ将对方分为两快棋（b,n）
ʌ若下子则整块气被杀（左边棋块（b,n），-n,color）
ʌ若下子则整块气被杀（右边棋块（b,n），-n,color）
ʌ效率最高（所有好着）
值得注意的是，类似“非禁着点（b,n）”或“立（b,n）”这样的充分条件很容易在对弈时 ，而“效率最高（所有好着）”则很难判断。在这里“效率”指的是围棋中的子效（着子效率）。针对这个问题，在本文所研究的围棋学习方法中，特别增加了一个评价函数：IGE=LTE∪PTE

4，MTD(f)算法：
（1）算法介绍：
[1] 通常试探值并不一定设成零，而是用迭代加深的形式由浅一层的MTD(f)搜索给出；
　[2] 局面评价得越粗糙，MTD(f)的效率越高，围棋中可使一个棋子的价值由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 < upperbound);   
11.        　return score;   
12.        }  
5，Alpha-Beta算法：
（1）算法介绍：
[1]Alpha值代表的是发起走棋一方(期望极大值)做能接受的最小值,搜索极大值一方必须要找到一个比Alpha值更大的，否则这步棋就没有任何意义
    Beta值代表的是对手(期望极小值)所能接受的最坏值，搜索极小值的一方必须找到一个比Beta值小
一步棋，否则也是没意义的（因为有更好的一步棋已经生成了)
[2]Alpha值是父节点（非root)能搜索到的最大值，任何比他小的值都没意义。
Beta值是你所能找到的最坏的一种情况，任何比它大的都没意义。
{  int val = -AlphaBeta(depth - 1, -beta, -alpha);  }
注意这个所谓的负极大的估值函数是估算本方的最优值，所以你的对手（子节点）估算出来的最优值如果大于你的-Beta 。例如，-beta == 3 子节点估值== 4，那么他实际上返回后（取负得-4）是小于你的Beta,所以它是有意义的。再看这个-alpha。实际上是本层的beta是上一层节点（对手)的最大值的负值，如果任何本层节点取值,例如-alpha == 3,子节点估值为4，4 >= 3，那么返回的是-4，-4< -3（alpha那个地方），所以无意义，因为在本层所有节点又都是越取越大（负极大），
（缺点）：这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法，那么Beta截断就不会发生，因此该算法就如同最小-最大一样，效率非常低。该算法最终会找遍整个博弈树，就像最小-最大算法一样。
（改进）：如果程序总是能挑最好的着法来首先搜索，那么数学上有效分枝因子就接近于实际分枝因子的平方根。这是Alpha-Beta算法可能达到的最好的情况。
（2）算法的实现　
int AlphaBeta(int depth, int alpha, int beta)
{ if(depth == 0 || IsGameOver()) return Evaluate(); //如果层数为0或者已达最终状态则返回本步棋的估值
   for(each possible move)
   {  MakeMove();
     int val = -AlphaBeta(depth - 1, -beta, -alpha);
     UnMakeMove();
   if(val >= beta)
  {  return val;
  } if(val > alpha)
  {  alpha = val;
  } return alpha;//返回最好的值
}
（3）研究来源：王晓春，上海理工大学计算机工程学院，棋类对弈人工智能算法研究，2006-12　

6，回溯法（深度优先搜索）：
（1）回溯法的应用模式：
[1] 设置初始化的方案（给变量赋初值，读入已知数据等）。令Ｉ－表示行变量。Ａ（Ｉ）－表示列变量。Ｉ＝１．Ａ（Ｉ）＝１
[2] 变换方式去试探，Ｉ＝Ｉ＋１，Ａ（Ｉ）＝Ａ（１）＋１，若Ｉ＞８则转（６）若Ａ（Ｉ）＞８则转（７）。
[3] 判断此方法是否成功，若Ａ（Ｉ）－Ａ（Ｊ）＝ＳＮＧ（Ａ（Ｉ）－Ａ（Ｊ）＊（Ｉ－Ｊ）成功则转（２）。
[4] 试探成功则前进一步再试探。
[5] 正确方案（Ｉ＝８）还未找到则转（２）。
[6] 已找到一种方案则记录并打印。
[7] 退回一步（回溯），若为退到头则转（２）。
[8] 已退到头（Ｉ＝０）则结束或打印无解。
(2) 算法的实现：
１０　ＤＩＭ　Ａ（８）：Ｎ＝０
　　　２０　Ｉ＝１：Ａ（Ｉ）＝１
３０　Ｉ＝Ｉ＋１：ＩＦＩ＞８　ＴＨＥＮ　８０
４０　Ａ（Ｉ）＝Ａ（１）＋１：ＩＦＡ（Ｉ）＞８ＴＨＥＮ１００
５０　ＦＯＲＪ＝Ｉ－１　ＴＯ　ＳＴＥＰ－１
６０　ＩＦＡＡ（Ｉ）－Ａ（Ｊ）＝ＳＮＧ（Ａ（Ｉ）－Ａ（Ｊ）＊（Ｉ－Ｊ）
７０　ＮＥＸＴ：ＧＯＹＯ　３０
８０　Ｎ＝Ｎ＋１：ＦＯＲ　Ｋ＝１　ＴＯ　８
９０　Ｉ＝Ｉ－１：ＧＯＹＯ　４０
１００　Ａ（Ｉ）＝０；Ｉ＝Ｉ－１
１１０　ＩＦＩ＝０　ＴＨＥＮ　ＥＮＤ
１２０　ＧＯＴＯ　４０
（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 node
for (;;)
{  
BestNode=ReturnBestNode();
if (BestNode->NodeNum == TileNumDest) // if we've found the end, break
and finish
break;
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);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( 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);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( 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 from
BestNode to Successor
TileNumS = TileNum(x,y); // identification purposes/
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to NULL then not in
OPEN list, else it returns the Node in Old
{
for( c = 0; c < 8; c++)
if( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's C
hildren (or Successors).
break;
BestNode->Child[c] = Old
if ( g < Old->g ) // if our new g value is < Old's then reset Old's paren
t to point to BestNode
{
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}else
if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to NULL then not
in OPEN list, else it returns the Node in Old
{
for( c = 0; c< 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Chi
ldren (or Successors).
break;BestNode->Child[c] = Old;
if ( g < Old->g ) // if our new g value is < Old's then reset Old's paren
t to point to BestNode
{ Old->Parent = BestNode;
Old->g = g;Old->f = g + Old->h;
PropagateDown(Old); // Since we changed the g value of Old, we nee
d}}else
{ 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 si
nce we don't really
Successor->f = g+Successor->h; // care about the distance but just whi
ch branch looks
Successor->x = x; // better this should suffice. Anyayz it
's faster.
Successor->y = y;
Successor->NodeNum = TileNumS;
Insert(Successor); // Insert Successor on OPEN list wrt f
for( c =0; c < 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Ch
ildren (or Successors).
break;
BestNode->Child[c] = Successor;
}
}













基于人工智能理论的围棋人机对弈








08计算机
1班11号
张超
20081118610015



（3）UCT Tree 搜索流程总结如下：UCT算法使用极大极小游戏树（minimax game tree）,
搭配节点选择公式（UCB公式），选择树节点，展开要测试的节点，然后使用
Monte Carlo方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程图如下：
（4）研究来源：计算机围棋相关问题研究。中国新技术新产品。２００９，（１６）：２７













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的形式是：TargetConcept←SufficientConditions
[4]返回LearnedRules
例，最佳棋着（b,n）←非禁着点（b,n）ʌ 非劫争禁着点（b,n，历史棋谱）
ʌ立（b,n）ʌ将对方分为两快棋（b,n）
ʌ若下子则整块气被杀（左边棋块（b,n），-n,color）
ʌ若下子则整块气被杀（右边棋块（b,n），-n,color）
ʌ效率最高（所有好着）
值得注意的是，类似“非禁着点（b,n）”或“立（b,n）”这样的充分条件很容易在对弈时 ，而“效率最高（所有好着）”则很难判断。在这里“效率”指的是围棋中的子效（着子效率）。针对这个问题，在本文所研究的围棋学习方法中，特别增加了一个评价函数：IGE=LTE∪PTE

不知道现在银星围棋有几段了