计算机象棋循序渐进
 
象棋百科全书网 (webmaster@xqbase.com) 20084
 
() 最后级的野生智能
 
  与本文配套的树模顺序是“象棋小巫师0.3版,顺序清单是:
  (1) XQWL03.CPP——C++源顺序;
  (2) XQWLIGHT.RC——资源形貌文件;
  (3) RESOURCE.H——资源符号界说文件;
  (4) RES目录——图标、图画、声响等资源。
 
  在阅读本章前,推荐读者先阅读象棋百科全书网盘算机博弈专栏的以下几篇译文:
  (1) 国际象棋顺序设想(四):基本搜索要领(François Dominic Laramée)
  (2) 国际象棋顺序设想(六):局势评价函数(François Dominic Laramée)
  (3) 基本搜索要领——简介()(David Eppstein)
  (4) 基本搜索要领——简介()(David Eppstein)
  (5) 基本搜索要领——最小-最大搜索(Bruce Moreland)
  (6) 基本搜索要领——Alpha-Beta搜索(Bruce Moreland)
  (7) 基本搜索要领——迭代加深(Bruce Moreland)
  (8) 低级搜索要领——简介()(David Eppstein)
  (9) 其他战略——胜利局势(David Eppstein)
  (10) 局势评价函数——简介(一)(David Eppstein)
 
3.1 局势评定函数
 
  依据国际象棋顺序的心得,局势评定函数中最重点的重点要点是子力价值(95象马31)。这个心得异样也适宜于中国象棋,而且适当调整就能够够失掉更好的效果——子力价值是跟它的一定职位相关的。最显著的案例是中国象棋中的兵(),过河前咱们给它很低的分数,过河后分数大涨,越靠近九宫分数就越高,九宫中央以至靠近一个马或炮的值。
  这样一来,每一个军种就都邑有一个与一定职位相关的价值数组,因而咱们的顺序里有一个常量数组 cucvlPiecePos[7][256],它是从开源的象棋顺序 ElephantEye 中照搬过去的。
  现在要最先停止局势评定了,咱们是否是应当这样做:
 
vlEvaluate = 0; // 一定红方来说的局势评定值
for (sq = 0; sq < 256; sq ++) {
 pc = ucpcSquares[sq];
 if (IS_RED(pc)) {
  vlEvaluate += cucvlPiecePos[PIECE_TYPE(pc)][sq];
 } else if (IS_BLACK(pc)) {
  vlEvaluate -= cucvlPiecePos[PIECE_TYPE(pc)][SQUARE_FLIP(sq)];
 }
}
 
  这样做太虚耗时刻了,由于基础没有需要每次都把棋盘扫描一遍。在咱们的顺序里,每走一步棋都邑调用两到三次 AddPiece (放一枚棋子)DelPiece (取走一枚棋子),能够趁这个时机更新 vlEvaluate(将下面代码中红色的局部放到 AddPiece DelPiece )
  关于象棋小巫师来说,这样的局势评定函数以前足够好了。
 
3.2 Alpha-Beta搜索庞大吗?
 
  咱们能够很随意纰漏地写出一个Alpha-Beta搜索函数:
 
int AlphaBeta(int vlAlpha, int vlBeta, int nDepth) {
 if (nDepth == 0) {
  return 局势评定函数;
 }
 天生悉数走法;
 排序悉数走法;
 for (每一个天生的走法) {
  走这个走法;
  int vl = -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);
  吊销这个走法; 
  if (vl >= vlBeta) {
   return vlBeta;
  }
  if (vl > vlAlpha) {
   vlAlpha = vl;
  }
 }
 return vlAlpha;
}
 
  然则,这样的顺序基础走不出棋来,由于它前往的是一个分数而不是一个走法。其余,咱们还发现几个问题:
  (1) 排序的依据是甚么?
  (2) 是否是每一个天生的走法都能够走?
  (3) 若是甚么走法都走不出来,那末前往vlAlpha恰当吗?
 
  重点一定上述几个问题,咱们对顺序做以下革新:
  (0) 若是函数在根节点处被调用,就把最好走法作为计算机要走的棋;
  (1) 国际象棋顺序的经考证实,历史表是异常不错的走法排序依据;
  (2) 由于咱们的走法天生器并没有斟酌自杀(被将军)的状况,因而走完一步后要搜检是否是被将军了,被将军时应马上退回来离去;
  (3) 若是没有走出过任何走法,说明以后局势是杀棋或困毙局势,应以后往杀棋的分数。
  下面是革新过的顺序,革新的中央用红色标出:
 
int AlphaBeta(int vlAlpha, int vlBeta, int nDepth) {
 if (nDepth == 0) {
  return 局势评定函数;
 }
 天生悉数走法;
 按历史表排序悉数走法;
 for (每一个天生的走法) {
  走这个走法;
  if (被将军) {
   吊销这个走法;
  } else {
   int vl = -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);
   吊销这个走法; 
   if (vl >= vlBeta) {
    将这个走纲纪录到历史表中;
    return vlBeta;
   }
   if (vl > vlAlpha) {
    设置最好走法;
    vlAlpha = vl;
   }
  }
 }
 if (没有走过任何走法) {
  return 杀棋的分数;
 }
 将最好走纲纪录到历史表中;
 if (根节点) {
  最好走法就是计算机要走的棋;
 }
 return vlAlpha;
}
 
3.3 杀棋的分数
 
  遇到将死或困毙的局势时,应以后往 nDistance - INFINITY,这样顺序就能够找到最短的搜索线路。nDistance 是以后节点距离根节点的步数,每走一个走法,nDistance 就增长1,每吊销一个走法,nDistance 就增加1
  若是顺序中运用了置换表,这个问题将变得越发庞大,咱们以后再议论。
 
3.4 历史表
 
  国际象棋顺序的经考证实,历史表是异常不错的走法排序依据。那末,甚么样的走法要纪录到历史表中去呢?象棋小巫师选择了以下两类走法:
  A. 发生Beta截断的走法;
  B. 不能发生Beta截断,但它是一切PV走法(vl > vlAlpha)中最好的走法。
 
  象棋小巫师的历史表是一个巨细为65536的数组,正好能将走法的数值(mv)作为目的,因而依据走法取得历史表的值异常随意纰漏,即nHistoryTable[mv]。那末,一个走纲纪录到历史表,终究该给 nHistoryTable 中的这个元素加若干分的值呢?咱们依旧因袭国际的心得——深度的平方。以是,更新历史表的代码异常简朴:
 
nHistoryTable[mv] += nDepth * nDepth;
 
3.5 迭代加深和时刻掌握
 
  迭代加深具有一石多鸟的功用,现在最显著的供效是充裕展现历史表的功用——浅一层搜索完毕后,历史表中累积了少量异常珍贵的数据,这将大幅度增加深一层搜索的时刻。
  在迭代加深的根蒂基本上完成时刻掌握,这将长短常简朴的:
 
for (i = 1; i < MAX_DEPTH; i ++) {
 AlphaBeta(-INFINITY, INFINITY, i);
 if (凌驾最短搜索时刻) {
  break;
 }
}
 
  固然,咱们还能够加入其他完毕迭代加深的条件,譬喻当顺序算出了杀棋(分值靠近INFINITY-INFINITY)时,就没有需要停止更深的搜索了。
  • 上一篇 计算机象棋循序渐进():掌握象棋划定礼貌
  • 下一篇 计算机象棋循序渐进():细微智慧些了
  • 返 回 象棋百科全书——盘算机博弈
  • www.xqbase.com