《棋战顺序基本手艺》专题
 
着法天生器
 
作者 James Swafford
 
  “着法天生器”在分歧的引擎中区别较大。本文将向你演示运用位棋盘(aka bitmaps)【编者注:即前两章所说的BitBoard时天生着法的基来源根基理。低级的国际象棋引擎一般具有一次只天生一小局部着法的才气。譬喻,仅天生象走的着法,马走的着法,致使升变的着法,一切的吃子着法等等,这正是位棋盘的强项。那为甚么用这类体式格局天生着法呢?缘由是天生着法消耗一定的时刻。若是你的引擎在搜检了一局部着法后发现了必需走的棋,那它就不用天生余下的棋步了。因而,你能够想师长西席成一切吃子的着法,若是没有写意的棋再天生余下的着法。(用来增加耗时的着法天生战略许多——展现你的想象力吧)
  默默无闻的收费国际象棋引擎Crafty(其作者是Robert Hyatt博士)运用三个着法天生函数。一个用来天生一切伪正当吃子着法,一个天生一切伪正当不吃子着法,最终一个天生一切挣脱被将军状态的着法。注重前两个函数天生的是伪正当的着法。就是说,这些函数天生的着法并非都是正当的。譬喻,你要天生一切将军的着法而且发现了一步你想走的棋,但随后发现这步不正当再把它扬弃。这看起来很新鲜,但它实在比那种在一切局势下都严厉天生正当着法的战略更快!Hyatt博士以前这样注释:当国王被将时,你要求天生挣脱被将的着法,这时刻大局部天生的着法是不正当的,在这类局势中你运用天生一符正当着法的战略会帮你节约时刻;但在大少数局势中,天生的着法都是正当的,推延考证正当性会更有用率。
  记住下面讲的内容,让咱们看一些例程!下面这段代码选自我现在正在开辟的引擎(其设想理念同时遭到了CraftyTom's Simple Chess Program的滋扰)。它天生伪正当的马吃子的着法。
 
gen_rec *GenWhiteKnightCaps(chess_pos *posptr, gen_rec *m) {
 piece_map = posptr -> whiteknights;
 while (piece_map) {
  from_sq = MSB(piece_map);
  piece_map ^= mask[from_sq];
  to_map = nmoves[from_sq] & posptr -> blackpieces;
  while (to_map) {
   to_sq = MSB(to_map);
   to_map ^= mask[to_sq];
   m -> m.b.from = from_sq;
   m -> m.b.to = to_sq;
   m -> m.b.promote = 0;
   m -> m.b.bits = 1;
   m -> score = piece_val[posptr -> piece[to_sq] + 7] - KNIGHT_value;
   m ++;
  }
 }
 return m;
}
 
  gen_rec是纪录着法和它的得分的数据组织。下面的函数取得的第一个参数是一个指针指向要求从中天生着法的位棋盘的职位。第二个参数异样是一个指针,指向着法栈(贮存天生着法的栈)中下一个寄存着法的职位。这个函数前往一个指针,指向着法栈中下一个能够寄存着法的职位。
  Piece_map是一个位棋盘,最后纪录一切白棋马的职位。然后,这些“位”(对应于棋盘上有白棋马的格)依次被剖析出来。剖析出来的“位”被用来天生其余一个位棋盘,它纪录了白马在该“位”(格子)上时一切受其进击且下面有黑棋的“位”()。这些“位”再被依次掏出,成为着法,被压入着法栈,附带存入这步棋的得分(虽然我是这样做的,但并非需要)
  咱们再来看下面的函数。它被设想整天生黑棋象和皇后的伪正当、不吃子着法。注重它并未天生一切皇后的不吃子着法,仅仅是它的顺着斜线走的着法。
 
gen_rec *GenBlackBishopQueenNonCaps(chess_pos *posptr, gen_rec *m) {
 piece_map = posptr -> blackbishops | posptr -> blackqueens;
 while (piece_map) {
  from_sq = LSB(piece_map);
  piece_map ^= mask[from_sq];
  to_map = BishopMoves(from_sq, posptr) & ~(posptr -> whitepieces | posptr -> blackpieces);
  while (to_map) {
   to_sq = LSB(to_map);
   to_map ^= mask[to_sq];
   m -> m.b.from = from_sq;
   m -> m.b.to = to_sq;
   m -> m.b.promote = 0;
   m -> m.b.bits = 0;
   m -> score=history[from_sq][to_sq];
   m++;
  }
 }
 return m;
}
 
  这个函数同上一个相比并没有太多的分歧。它收受接管一样的参数,前往指向最终一个被压入的着法的下面一个职位的指针。
  Piece_map位棋盘最后纪录一切黑棋象和皇后的职位,这些“位”被依次析出;天生棋子在该“位”上一切走斜线的着法的位棋盘,加上着法的得分并压入着法栈。
  但这两个函数是存在一些分歧的,譬喻这个函数中用“LSB()”来析取“位”,LSB(Least Significant Bit)意义是最低位。我在这个函数中用LSB是由于黑棋棋子靠近A8格,在我的顺序中A8格编号为0。相反,白棋则靠近H1,它在顺序中的编号为63,以是在天生白棋着法的例程中我运用MSB(Most Significant Bit,最高位)
  其余一个区分是评分算法。注重,在天生着法的时刻就给每一个着法打分并非需要,只是我的顺序中是这样做的。在天生吃子着法的例程中所运用的评分战略是MVV/LVA算法(最有价值的受益者/最没有价值的进击者)。事实上就是每步棋的得分即是被吃子的价值减掉吃它的子的价值。关于不吃子着法的例程,运用的是历史启示算法。历史启示算法将在以后给你引见。
  下面的代码将天生给定一方的一切伪正当的吃子着法。
 
gen_rec *GenCaps(chess_pos *posptr, gen_rec *m) {
 if (posptr -> player) {
  // white to move
  m = GenWhiteKnightCaps(posptr, m);
  m = GenWhiteBishopCaps(posptr, m);
  m = GenWhiteRookCaps(posptr, m);
  m = GenWhiteQueenCaps(posptr, m);
  m = GenWhiteKingCaps(posptr, m);
  m = GenWhitePawnCaps(posptr, m);
 } else {
  // black to move
  m = GenBlackKnightCaps(posptr, m);
  m = GenBlackBishopCaps(posptr, m);
  m = GenBlackRookCaps(posptr, m);
  m = GenBlackQueenCaps(posptr, m);
  m = GenBlackKingCaps(posptr, m);
  m = GenBlackPawnCaps(posptr, m);
 }
 return m;
}
 
  这个函数异常“直观”。它取得两个指针,离别指向棋盘职位和着法栈中响应的职位。然后天生走棋一方的一切棋子的吃子着法。最终前往一个指针,指向着法栈的下一个空位(就是你压入的最终一个着法的下面一个职位)
  现在你完整能够最先着手编写你自身的国际象棋引擎了!若是你想看更多的代码,请看下面。祝你好运!
 
  出处:不详
  译者:Allen Liu (http://lostboy.myrice.com/)
  类型:不详
  编纂:象棋百科全书网 (webmaster@xqbase.com)
  • 上一篇 数据组织——改动的位棋盘
  • 下一篇 数据组织——0x88着法发生要领
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com