- 《对弈程序基本技术》专题
-
- 0x88着法产生方法
-
- Bruce Moreland / 文
-
- 历史
-
- 我在1995年香港举行的世界电脑国际象棋锦标赛(WCCC)上和 David Kittinger 交流时，他跟我说了这个着法产生的技术，当时我就把它忘了。如今回过头来看，我已经很多次提到这个技术了。由于当时我还不知道它的名称，我就给它起了别的名字。它名称应该是0x88，即十六进制的88。
- 之所以称为0x88，是因为0x88概括了这个技术的要点。
- 0x88技术的优势在于：
- (1) 它很容易理解；
- (2) 代码非常短小，一点也不复杂；
- (3) 很容易检查棋子是否超出边界。
-
- 棋盘表示和基本原理
-
- 通常的国际象棋棋盘是8x8的格子，格子的“标准”编号应该从0到63，a1格是0，b1格是1，a2格是8，h8格是63，其余的格子由你自己填上。
- 0x88采用稍微不同的棋盘，它有128个格子，a1到h1仍旧是0到7，但是在h列右边还有从未用到的i到p列，简单地说就是把一个虚的棋盘放在实的棋盘的右边。
- 因此a2被编为16，a8是112，h8是119。
- 任意一个格子都符合下面的公式：
-
- 指标 = 行号 x 16 + 列号
-
- 你可能会问为什么要这样做，其实有很多理由，这里我们只讨论最关键的。这个理由就是，这样做可以检查射线是否走到了棋盘的左边界或右边界。
- 你可能仍旧不明白。假设你仍然用8x8的棋盘，并且考虑a3格的车，在8x8的棋盘上它的编号是16。现在来产生这个车的目标格子，先从纵线上的着法开始。在纵线上前进一格，就增加8，16加上8就得到24。这个格子是否在棋盘上呢？在8x8的棋盘上可以检查它是否小于64。现在24小于64，所以它在棋盘上。下一个格子是32，然后依次是40、48和64，64不小于64，所以它在棋盘外边，我们就停了下来。
- 非常好，现在我们从a3往下走。a3是16，减去8得到8，它在棋盘上吗？此时要检查它是否大于或等于零，而8确实是的。再下一个格子是-8，因为小于零，所以不在棋盘上。
- 我们不厌其烦做了两次测试，如果只需要做一次测试那就更好了。现在测试棋子是否在棋盘上的代码是：
-
- if ((index < 0) || (index >= 64))
-
- 其实这就包含了两次测试，我们远远没有满足，因为它完全可以只做一次测试：
-
- if (!(index & 0x40))
-
- 这就涵盖了判断棋子超出棋盘下边界和超出棋盘上边界的两种情况。超出棋盘上边界时，由于大于64而0x40置为1，超出棋盘下边界时，用补码表示负数的机制使得0x40也置为1。
- 如果你还没有明白，那么你最好停下来别看下去了，否则下面要说的东西对你来说就是天书。
- 如果你留意一下，你会注意到我们只让车朝上朝下走，而没有让它朝左朝右走。我们之所以不让它朝左朝右走，是因为这套机制不允许这么做，它无法判断朝左或朝右的射线是否到达棋盘的边界。如果你从a3开始朝右走，每走一格加1直到h3，此时你可以继续加1到达a4。a4仍就在棋盘上，然而没有什么技巧可以让你判断是否超越了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个格子了)，并且两次测试要同时完成。把0x80和0x08结合起来就是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键值
返 回 象棋百科全书——电脑象棋
