- 《对弈程序基本技术》专题
-
- 着法生成器
-
- 作者 James Swafford
-
- “着法生成器”在不同的引擎中差异较大。本文将向你演示使用位棋盘(aka bitmaps)【编者注：即前两章所说的BitBoard】时生成着法的基本原理。高级的国际象棋引擎通常具备一次只生成一小部分着法的能力。例如，仅生成象走的着法，马走的着法，导致升变的着法，所有的吃子着法等等，这正是位棋盘的强项。那为什么用这种方式生成着法呢？原因是生成着法耗费一定的时间。如果你的引擎在检查了一部分着法后发现了必须走的棋，那它就无需生成余下的棋步了。因此，你可能想先生成所有吃子的着法，如果没有满意的棋再生成余下的着法。(用来减少耗时的着法生成策略很多——发挥你的想象力吧)。
- 大名鼎鼎的免费国际象棋引擎Crafty(其作者是Robert Hyatt博士)使用三个着法生成函数。一个用来生成所有伪合法吃子着法，一个生成所有伪合法不吃子着法，最后一个生成所有摆脱被将军状态的着法。注意前两个函数生成的是伪合法的着法。就是说，这些函数生成的着法并非都是合法的。例如，你要生成所有将军的着法并且发现了一步你想走的棋，但随后发现这步不合法再把它抛弃。这看起来很奇怪，但它确实比那种在所有局面下都严格生成合法着法的策略更快！Hyatt博士曾经这样解释：当国王被将时，你需要生成摆脱被将的着法，这时大部分生成的着法是不合法的，在这种局面中你使用生成所有合法着法的策略会帮你节省时间；但在大多数局面中，生成的着法都是合法的，推迟验证合法性会更有效率。
- 记住上面讲的内容，让我们看一些例程！下面这段代码选自我目前正在开发的引擎(其设计理念同时受到了Crafty和Tom'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着法产生方法
返 回 象棋百科全书——电脑象棋
