《棋战顺序基本手艺》专题
 
0x88着法发生要领
 
Bruce Moreland /
 
历史
 
  我在1995年香港举行的天下计算机国际象棋锦标赛(WCCC)上和 David Kittinger 交流时,他跟我说了这个着法发生的手艺,事先我就把它忘了。现在回过头来看,我以前许屡次说到这个手艺了。由于事先我还不知道它的称呼,我就给它起了其余名字。它称呼应当是0x88,即十六进制的88
  之以是称为0x88,是由于0x88归纳综合了这个手艺的要点。
  0x88手艺的优势在于:
  (1) 它很随意纰漏体谅;
  (2) 代码异常短小,一点也不庞大;
  (3) 很随意纰漏搜检棋子是否是超越界限。
 
棋盘透露表现和基来源根基理
 
  一般的国际象棋棋盘是8x8的格子,格子的“规范”编号应当从063a1格是0b1格是1a2格是8h8格是63,剩余的格子由你自身填上。
  0x88使用细微分歧的棋盘,它有128个格子,a1h1依旧是07,然则在h列左边另有从未用到的ip列,简朴地说就是把一个虚的棋盘放在实的棋盘的左边。
  因而a2被编为16a8112h8119
  恣意一个格子都相符下面的公式:
 
目的 = 行号 x 16 + 列号
 
  你能够会问为甚么要这样做,事实上有许多因由,这里咱们只议论最重点的。这个因由就是,这样做能够搜检射线是否是走到了棋盘的左侧界或左界限。
  你能够依旧不晓畅。假定你依然用8x8的棋盘,而且斟酌a3格的车,在8x8的棋盘上它的编号是16。现在来发生这个车的目的格子,先从纵线上的着法最先。在纵线上提高一格,就增长816加上8就失掉24。这个格子是否是在棋盘上呢?在8x8的棋盘上能够搜检它是否是小于64。现在24小于64,以是它在棋盘上。下一个格子是32,然后依次是40486464不小于64,以是它在棋盘外边,咱们就停了上去。
  异常好,现在咱们从a3往下走。a316,减去8失掉8,它在棋盘上吗?这时候要搜检它是否是大于或即是零,而8实在是的。再下一个格子是-8,由于小于零,以是不在棋盘上。
  咱们诲人不倦做了两次测试,若是只要求做一次测试那就更好了。现在测试棋子是否是在棋盘上的代码是:
 
if ((index < 0) || (index >= 64))
 
  事实上这就包罗了两次测试,咱们远远没有知足,由于它完整能够只做一次测试:
 
if (!(index & 0x40))
 
  这就涵盖了剖断棋子超越棋盘下界限和超越棋盘上界限的两种状况。超越棋盘上界限时,由于大于640x40置为1,超越棋盘下界限时,用补码透露表现正数的机制使得0x40也置为1
  若是你还没有晓畅,那末你最好停上去别看下去了,否则下面要说的器械对你来说就是天书。
  若是你注意一下,你会注重到咱们只让车朝上朝下走,而没有让它朝左朝右走。咱们之以是不让它朝左朝右走,是由于这套机制不允许这么做,它没有设施剖断朝左或朝右的射线是否是抵达棋盘的界限。若是你从a3最先朝右走,每走一格加1直到h3,这时候你能够连续加1抵达a4a4仍就在棋盘上,然则没有甚么窍门可以使你剖断是否是逾越了h列。朝左走也一样,从a3格最先减1,就会到h2,它依然在棋盘上,然则国际象棋里没有哪一个棋子能这么走。
  而0x88机制正好能够处置责罚这个问题。用一个16x8的棋盘,就失掉一个符号位,你就能够知道棋子是否是到了左边谁人没用的棋盘上,由于在这个棋盘上0x08职位为1。譬喻h1标号是7,加1后就是8,而0x08位酿成了1。左侧的实棋盘上没有一格的0x08位是1,而左边的虚棋盘每一个格子的0x08位都是1。若是你在a3而且要朝左走,你会抵达p2,这是在虚棋盘上,0x08位是1
  能够把0x08的检测和0x80的检测联系起来(正本的0x40酿成了0x80,由于现在棋盘酿成128个格子了),而且两次测试要同时完成。把0x800x08联系起来就是0x88,这就是这套计划的称呼。
  若是你知道我在说甚么,你就晓畅0x88是怎样运作的。你的着法发生的循环就应当写成下面的样子容貌:
 
while (!(index & 0x88)) {
 GenerateMove(index);
 index += delta;
}
 
  这就异常清新了,你能够这么写:
 
void GenerateMoves(int square, int * ptab) {
 for (; *ptab; ptab++) {
  int index;
  for (index = square; !(index & 0x88); index += *ptab) {
   GenerateMove(index);
  }
 }
}
int argdBishop[] = { 17, 15, -17, -15, 0 };
void GenerateBishopMoves(int square) {
 GenerateMove(square, argdBishop);
}
 
  这样写就异常快了,而且代码很短。车也许后跟象的区分只是表中的数据分歧而已,因而你能够花很短的时刻把其他棋子的代码加上,而且不要求任何改动。
  固然,你依然要求为兵和王车易位另写代码,但每一个系统都得这样。0x88系统能给你一点资助,然则代码写出来依然很丑。
 
夸奖
 
  0x88系统还能够快速剖断进击,这就是要运用16x8棋盘的其余一个缘由。若是你将两格子的号码相减,你会失掉两个格子之间的相干。
  譬喻,若是两个格子减上去是1,那末第二个格子就在第一个格子的左侧。若是减上去是16,那末第二个格子就在第一个格子的下面。
  这在8x8棋盘上是做不到的。d1 - c1 = 1实在这样,然则a2 - h1也是1。这个“回圈”问题能够在128个格子的棋盘上处置责罚。
  你在写剖断将军也许一个子是否是在捉其余一个子的函数时,能够应用上述这个窍门。
  你能够用一个约莫257个元素(-128 ~ +128)的数组,外面寄存一些象征棋子的位域,来说明哪些棋子能在某两格间移动,而移动的增量就是数组的目的。你能够用少于257个的元素,然则我没有实验过。
  譬喻在增量为1的元素里,应当有王、后、车的职位是置1的。若是增量是17,那末置1的是王、后、象和白兵。
  这样就能够够写出对照快的搜检将军的顺序了。你把进击子的格子和目的格子相减失掉增量,加上128以免负的目的,然后去找预先盘算好的进击数组,看看是否是相符这个进击子的类型,以确认它有能够一步抵达目的格。
  若是你确认这个子能够抵达目的格,那末你还要搜检它是否是是长武器(后、车或象)。若是不是,那就完成剖断了,否则你要顺着从进击子到目的格的射线去找有无阻挠的棋子。
  我不想供应这个顺序的代码,由于它很随意纰漏写。这个顺序的速率是对照快的。
 
  原文:http://www.seanet.com/~brucemo/topics/0x88.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 数据组织——着法天生器
  • 下一篇 数据组织——Zobrist键值
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com