📄 数据结构——着法生成器.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/struct_movegen.htm -->
<HTML><HEAD><TITLE>数据结构——着法生成器</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=数据结构——着法生成器_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《对弈程序基本技术》专题</FONT> </CENTER></DT></DIV>
<DT>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face=隶书 size=6>着法生成器</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>作者 <FONT face="Times New Roman">James Swafford (</FONT><A
href="mailto:james_swafford@hotmail.com"><FONT
face="Times New Roman">james_swafford@hotmail.com</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DT><FONT
color=#ff0000> 【编者的点评：比起“旋转的位棋盘”而言，原作者在“着法生成器”上的误导更加严重。两个看上去很神奇的函数，却使得着法生成器的速度慢了好几倍，程序在哪里出了问题呢，看看原作者的代码中是如何使用这两个函数的。】</FONT>
<DT> “着法生成器”在不同的引擎中差异较大。本文将向你演示使用位棋盘<FONT face="Times New Roman">(aka
bitmaps)</FONT><FONT color=#0000ff>【编者注：即前两章所说的</FONT><FONT
face="Times New Roman" color=#0000ff>BitBoard</FONT><FONT
color=#0000ff>】</FONT>时生成着法的基本原理。高级的国际象棋引擎通常具备一次只生成一小部分着法的能力。例如，仅生成象走的着法，马走的着法，导致升变的着法，所有的吃子着法等等，这正是位棋盘的强项。那为什么用这种方式生成着法呢？原因是生成着法耗费一定的时间。如果你的引擎在检查了一部分着法后发现了必须走的棋，那它就无需生成余下的棋步了。因此，你可能想先生成所有吃子的着法，如果没有满意的棋再生成余下的着法。<FONT
face="Times New Roman">(</FONT>用来减少耗时的着法生成策略很多——发挥你的想象力吧<FONT
face="Times New Roman">)</FONT>。
<DT> 大名鼎鼎的免费国际象棋引擎<FONT face="Times New Roman">Crafty(</FONT>其作者是<FONT
face="Times New Roman">Robert Hyatt</FONT>博士<FONT
face="Times New Roman">)</FONT>使用三个着法生成函数。一个用来生成所有伪合法吃子着法，一个生成所有伪合法不吃子着法，最后一个生成所有摆脱被将军状态的着法。注意前两个函数生成的是伪合法的着法。就是说，这些函数生成的着法并非都是合法的。例如，你要生成所有将军的着法并且发现了一步你想走的棋，但随后发现这步不合法再把它抛弃。这看起来很奇怪，但它确实比那种在所有局面下都严格生成合法着法的策略更快！<FONT
face="Times New Roman">Hyatt</FONT>博士曾经这样解释：当国王被将时，你需要生成摆脱被将的着法，这时大部分生成的着法是不合法的，在这种局面中你使用生成所有合法着法的策略会帮你节省时间；但在大多数局面中，生成的着法都是合法的，推迟验证合法性会更有效率。
<DT> 记住上面讲的内容，让我们看一些例程！下面这段代码选自我目前正在开发的引擎<FONT
face="Times New Roman">(</FONT>其设计理念同时受到了<FONT
face="Times New Roman">Crafty</FONT>和<FONT face="Times New Roman">Tom's Simple
Chess Program</FONT>的影响<FONT face="Times New Roman">)</FONT>。它生成伪合法的马吃子的着法。
<DT>
<DD>gen_rec *GenWhiteKnightCaps(chess_pos *posptr, gen_rec *m) {
<DD> piece_map = posptr -> whiteknights;
<DD> while (piece_map) {
<DD> from_sq = MSB(piece_map);
<DD> piece_map ^= mask[from_sq];
<DD> to_map = nmoves[from_sq] & posptr -> blackpieces;
<DD> while (to_map) {
<DD> to_sq = MSB(to_map);
<DD> to_map ^= mask[to_sq];
<DD> m -> m.b.from = from_sq;
<DD> m -> m.b.to = to_sq;
<DD> m -> m.b.promote = 0;
<DD> m -> m.b.bits = 1;
<DD> m -> score = piece_val[posptr -> piece[to_sq] + 7] -
KNIGHT_value;
<DD> m ++;
<DD> }
<DD> }
<DD> return m;
<DD>}
<DT>
<DT> <FONT
face="Times New Roman">gen_rec</FONT>是记录着法和它的得分的数据结构。上面的函数获得的第一个参数是一个指针指向需要从中生成着法的位棋盘的位置。第二个参数同样是一个指针，指向着法栈<FONT
face="Times New Roman">(</FONT>储存生成着法的栈<FONT
face="Times New Roman">)</FONT>中下一个存放着法的位置。这个函数返回一个指针，指向着法栈中下一个可以存放着法的位置。
<DT> <FONT
face="Times New Roman">Piece_map</FONT>是一个位棋盘，最初记录所有白棋马的位置。然后，这些“位”<FONT
face="Times New Roman">(</FONT>对应于棋盘上有白棋马的格<FONT
face="Times New Roman">)</FONT>依次被解析出来。解析出来的“位”被用来生成另一个位棋盘，它记录了白马在该“位”<FONT
face="Times New Roman">(</FONT>格子<FONT
face="Times New Roman">)</FONT>上时所有受其攻击且上面有黑棋的“位”<FONT
face="Times New Roman">(</FONT>格<FONT
face="Times New Roman">)</FONT>。这些“位”再被依次取出，成为着法，被压入着法栈，附带存入这步棋的得分<FONT
face="Times New Roman">(</FONT>虽然我是这样做的，但并非必要<FONT
face="Times New Roman">)</FONT>。
<DT> 我们再来看下面的函数。它被设计成生成黑棋象和皇后的伪合法、不吃子着法。注意它并未生成所有皇后的不吃子着法，仅仅是它的沿着斜线走的着法。
<DT>
<DD>gen_rec *GenBlackBishopQueenNonCaps(chess_pos *posptr, gen_rec *m) {
<DD> piece_map = posptr -> blackbishops | posptr -> blackqueens;
<DD> while (piece_map) {
<DD> from_sq = LSB(piece_map);
<DD> piece_map ^= mask[from_sq];
<DD> to_map = BishopMoves(from_sq, posptr) & ~(posptr -> whitepieces |
posptr -> blackpieces);
<DD> while (to_map) {
<DD> to_sq = LSB(to_map);
<DD> to_map ^= mask[to_sq];
<DD> m -> m.b.from = from_sq;
<DD> m -> m.b.to = to_sq;
<DD> m -> m.b.promote = 0;
<DD> m -> m.b.bits = 0;
<DD> m -> score=history[from_sq][to_sq];
<DD> m++;
<DD> }
<DD> }
<DD> return m;
<DD>}
<DD>
<DT> 这个函数同上一个相比并没有太多的不同。它接受一样的参数，返回指向最后一个被压入的着法的下面一个位置的指针。
<DT> <FONT
face="Times New Roman">Piece_map</FONT>位棋盘最初记录所有黑棋象和皇后的位置，这些“位”被依次析出；生成棋子在该“位”上所有走斜线的着法的位棋盘，加上着法的得分并压入着法栈。
<DT> 但这两个函数是存在一些不同的，例如这个函数中用“<FONT
face="Times New Roman">LSB()</FONT>”来析取“位”，<FONT
face="Times New Roman">LSB(Least Significant Bit)</FONT>意思是最低位。我在这个函数中用<FONT
face="Times New Roman">LSB</FONT>是因为黑棋棋子靠近<FONT
face="Times New Roman">A8</FONT>格，在我的程序中<FONT
face="Times New Roman">A8</FONT>格编号为<FONT
face="Times New Roman">0</FONT>。相反，白棋则靠近<FONT
face="Times New Roman">H1</FONT>，它在程序中的编号为<FONT
face="Times New Roman">63</FONT>，所以在生成白棋着法的例程中我使用<FONT
face="Times New Roman">MSB(Most Significant Bit</FONT>，最高位<FONT
face="Times New Roman">)</FONT>。
<DT> 另一个区别是评分算法。注意，在生成着法的时候就给每个着法打分并非必要，只是我的程序中是这样做的。在生成吃子着法的例程中所使用的评分策略是<FONT
face="Times New Roman">MVV/LVA</FONT>算法<FONT
face="Times New Roman">(</FONT>最有价值的受害者<FONT
face="Times New Roman">/</FONT>最没有价值的攻击者<FONT
face="Times New Roman">)</FONT>。其实就是每步棋的得分等于被吃子的价值减掉吃它的子的价值。对于不吃子着法的例程，使用的是历史启发算法。历史启发算法将在以后给你介绍。
<DT> 下面的代码将生成给定一方的所有伪合法的吃子着法。
<DT>
<DD>gen_rec *GenCaps(chess_pos *posptr, gen_rec *m) {
<DD> if (posptr -> player) {
<DD> // white to move
<DD> m = GenWhiteKnightCaps(posptr, m);
<DD> m = GenWhiteBishopCaps(posptr, m);
<DD> m = GenWhiteRookCaps(posptr, m);
<DD> m = GenWhiteQueenCaps(posptr, m);
<DD> m = GenWhiteKingCaps(posptr, m);
<DD> m = GenWhitePawnCaps(posptr, m);
<DD> } else {
<DD> // black to move
<DD> m = GenBlackKnightCaps(posptr, m);
<DD> m = GenBlackBishopCaps(posptr, m);
<DD> m = GenBlackRookCaps(posptr, m);
<DD> m = GenBlackQueenCaps(posptr, m);
<DD> m = GenBlackKingCaps(posptr, m);
<DD> m = GenBlackPawnCaps(posptr, m);
<DD> }
<DD> return m;
<DD>}
<DD>
<DT> 这个函数非常“直观”。它获得两个指针，分别指向棋盘位置和着法栈中相应的位置。然后生成走棋一方的所有棋子的吃子着法。最后返回一个指针，指向着法栈的下一个空位<FONT
face="Times New Roman">(</FONT>就是你压入的最后一个着法的下面一个位置<FONT
face="Times New Roman">)</FONT>。
<DT> 现在你完全可以开始动手编写你自己的国际象棋引擎了！如果你想看更多的代码，请看下面。祝你好运！
<DT><FONT color=#ff0000> 【很显然，编者所指的两个“神奇的函数”是</FONT><FONT
face="Times New Roman" color=#ff0000>MSB</FONT><FONT
color=#ff0000>和</FONT><FONT face="Times New Roman"
color=#ff0000>LSB</FONT><FONT color=#ff0000>，在前面的《</FONT><A
href="http://www.elephantbase.net/computer/struct_intro.htm"
target=_blank><FONT color=#ff0000>棋盘的表示</FONT></A><FONT
color=#ff0000>》一文中，编者已经提到两个函数的具体操作了，即便使用炫技，最快速的操作也需要大约</FONT><FONT
face="Times New Roman" color=#ff0000>15</FONT><FONT
color=#ff0000>次运算，并且在</FONT><FONT face="Times New Roman"
color=#ff0000>32</FONT><FONT
color=#ff0000>位处理器上要调用两次。更糟糕的是，这个函数被原作者放在两层循环的里面，可想而知对着法生成器的效率有多么大的影响。目前</FONT><FONT
face="Times New Roman" color=#ff0000>Intel 386</FONT><FONT
color=#ff0000>以上的处理器可以直接进行</FONT><FONT face="Times New Roman"
color=#ff0000>MSB</FONT><FONT color=#ff0000>和</FONT><FONT
face="Times New Roman" color=#ff0000>LSB</FONT><FONT
color=#ff0000>运算，即</FONT><FONT face="Times New Roman"
color=#ff0000>BSR</FONT><FONT color=#ff0000>和</FONT><FONT
face="Times New Roman" color=#ff0000>BSF</FONT><FONT
color=#ff0000>指令，但其速度如同乘除法一样，足以让电脑变成傻瓜。当然，如果今后处理器的运算有了质的突破，使得</FONT><FONT
face="Times New Roman" color=#ff0000>BSR</FONT><FONT
color=#ff0000>和</FONT><FONT face="Times New Roman"
color=#ff0000>BSF</FONT><FONT
color=#ff0000>指令跟加减法一样快，那么本文提到的析取位的思想或许可以尝试一下。】</FONT>
<DT>
<DT> 出处：不详
<DT> 译者：<FONT face="Times New Roman">Allen Liu (</FONT><A
href="mailto:ditch_u@yahoo.com"><FONT
face="Times New Roman">ditch_u@yahoo.com</FONT></A>，<A
href="http://lostboy.myrice.com/home.htm" target=_blank><FONT
face="Times New Roman"
color=#0000ff>http://lostboy.myrice.com/</FONT></A><FONT
face="Times New Roman">)</FONT>
<DT> 类型：不详
<DT> 编辑：黄晨 <FONT face="Times New Roman">(</FONT><A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </DT></DL>
<DIR>
<LI>上一篇 <A
href="http://www.elephantbase.net/computer/struct_rotation.htm">数据结构——旋转的位棋盘</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/struct_0x88.htm">数据结构——<FONT
face="Times New Roman">0x88</FONT>着法产生方法</A>
<LI>返 回 <A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A>
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
<TBODY>
<TR>
<TD>
<P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG
height=31 src="数据结构——着法生成器_files/elephantbase.gif" width=88
border=0></A></P></TD></TR>
<TR>
<TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial
size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -