📄 解剖大象的眼睛——中国象棋程序设计探索(二)：棋盘结构和着法生成器.htm
字号:
face=Arial><STRONG>f5</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>f6</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>f7</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>f8</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>f9</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>fa</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>fb</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>fc</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>fd</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>fe</STRONG></FONT></TD>
<TD align=middle bgColor=#ff00ff><FONT
face=Arial><STRONG>ff</STRONG></FONT></TD></TR></TBODY></TABLE></CENTER></DIV>
<DL>
<DT> 在中国象棋里，短程棋子<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">8</FONT>个着法，增量分别是±<FONT
face="Times New Roman">0x0e</FONT>、±<FONT
face="Times New Roman">0x12</FONT>、±<FONT
face="Times New Roman">0x1f</FONT>和±<FONT
face="Times New Roman">0x21</FONT>，红方的过河兵有<FONT
face="Times New Roman">3</FONT>个着法，增量分别是<FONT face=Symbol>-</FONT><FONT
face="Times New Roman">0x10</FONT>和±<FONT face="Times New Roman">0x01</FONT>。
<DT> <FONT
face="Times New Roman">16x16</FONT>的扩展棋盘如上图所示，底色是红色的格子都被标上“出界”的标记，目标格在这些格子上就说明着法无效。这样，马的着法产生就非常简单了：
<DD>
<DD>const int cnKnightMoveTab[8] = {-0x21, -0x1f, -0x12, -0x0e, +0x0e, +0x12,
+0x1f, +0x21};
<DD>const int cnHorseLegTab[8] = {-0x10, -0x10, -0x01, +0x01, -0x01, +0x01,
+0x10, +0x10};
<DD>
<DD>for (i = MyFirstHorse; i < MyLastHorse; i ++) {
<DD> // 在ElephantEye的Pieces[48]中，红方的MyFirstHorse为21，MyLastHorse为22。
<DD> SrcSq = ucsqPieces[i];
<DD> if (SrcSq != 0) {
<DD> for (j = 0; j < 8; j ++) {
<DD> DstSq = SrcSq + cnKnightMoveTab[j];
<DD> LegSq = SrcSq + cnHorseLegTab[j];
<DD> if (cbcInBoard[DstSq] && (ucpcSquares[DstSq] & MyPieceMask)
== 0 && ucpcSquares[LegSq] == 0) {
<DD> MoveList[MoveNum].Src = SrcSq;
<DD> MoveList[MoveNum].Dst = DstSq;
<DD> MoveNum ++;
<DD> }
<DD> }
<DD> }
<DD>}
<DT>
<DT> 上面的代码是着法生成器的典型写法，用了两层循环，第一层循环用来确定要走的棋子，第二层循环用来确定棋子走到的目标格。如果要加快程序的运行速度，第二个循环可以拆成顺序结构。这个代码还加入了蹩马腿的判断，马腿的位置增量由<FONT
face="Times New Roman">ccHorseLegTab[j]</FONT>给出。
<DT> 其它棋子的着法也同样处理，只要注意帅<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">InBoard[DstSq]</FONT>改为<FONT
face="Times New Roman">InFort[DstSq]</FONT>就可以了。而对于兵和象等需要考虑是否能过河的棋子，判断是否过河的方法非常简单：红方是<FONT
face="Times New Roman">(SrcSq/DstSq & 0x80) != 0</FONT>，黑方是<FONT
face="Times New Roman">(SrcSq/DstSq & 0x80) == 0</FONT>。
<DT> <FONT
face="Times New Roman">Pieces[48]</FONT>这个扩展的棋子数组比较难以理解，实际上用了“屏蔽位”的设计，即<FONT
face="Times New Roman">1</FONT>位表示红子<FONT
face="Times New Roman">(16)</FONT>，<FONT
face="Times New Roman">1</FONT>位表示黑子<FONT
face="Times New Roman">(32)</FONT>。因此<FONT
face="Times New Roman">0</FONT>到<FONT
face="Times New Roman">16</FONT>没有作用，<FONT
face="Times New Roman">16</FONT>到<FONT
face="Times New Roman">31</FONT>代表红方棋子<FONT
face="Times New Roman">(16</FONT>代表帅，<FONT
face="Times New Roman">17</FONT>和<FONT
face="Times New Roman">18</FONT>代表仕，依此类推，直到<FONT
face="Times New Roman">27</FONT>到<FONT
face="Times New Roman">31</FONT>代表兵<FONT face="Times New Roman">)</FONT>，<FONT
face="Times New Roman">32</FONT>到<FONT
face="Times New Roman">47</FONT>代表黑方棋子<FONT
face="Times New Roman">(</FONT>在红方基础上加<FONT
face="Times New Roman">16)</FONT>。这样，棋盘数组<FONT
face="Times New Roman">Squares[256]</FONT>中的每个元素的意义就明确了，<FONT
face="Times New Roman">0</FONT>代表没有棋子，<FONT
face="Times New Roman">16</FONT>到<FONT
face="Times New Roman">31</FONT>代表红方棋子，<FONT
face="Times New Roman">32</FONT>到<FONT
face="Times New Roman">47</FONT>代表黑方棋子。这样表示的好处就是：它可以快速判断棋子的颜色，<FONT
face="Times New Roman">(Piece & 16)</FONT>可以判断是否为红方棋子，<FONT
face="Times New Roman">(Piece & 32)</FONT>可以判断是否为黑方棋子。
<DT> “屏蔽位”的设计不仅仅限制在判断红方棋子还是黑方棋子，如果在棋子数组上再多加<FONT
face="Times New Roman">7</FONT>个屏蔽位，就可以对每个兵种作快速判断，例如判断是否是红兵，不需要用<FONT
face="Times New Roman">(Piece >= 27 && Piece <=
31)</FONT>，而只要简单的<FONT face="Times New Roman">(Piece &
WhitePawnBitMask)</FONT>即可。这样的话，棋子数组的大小就增加到<FONT
face="Times New Roman">2^12=4096</FONT>个了，其中<FONT
face="Times New Roman">9</FONT>个屏蔽位，还有<FONT
face="Times New Roman">3</FONT>位表示同兵种棋子的编号<FONT
face="Times New Roman">(</FONT>注意兵有<FONT
face="Times New Roman">5</FONT>个，所以必须占据<FONT
face="Times New Roman">3</FONT>位<FONT
face="Times New Roman">)</FONT>。事实上，确实有象棋程序是使用<FONT
face="Times New Roman">Pieces[4096]</FONT>的。
<DT>
<DT><FONT face=Arial size=4><STRONG>2.5 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>着法预生成数组</STRONG></FONT>
<DT>
<DT> 上面提到的着法生成技术，在速度上并不是最快的。我们仍旧以马的着法为例，在很多情况下，马会处于棋盘的边缘，所以往往着法只有很少，而并不需要对每个马都作<FONT
face="Times New Roman">8</FONT>次是否出界的判断。因此，对于每个短程子力，都给定一个<FONT
face="Times New Roman">[256][4]</FONT>到<FONT
face="Times New Roman">[256][9]</FONT>不等的数组，它们保存着棋子可以到达的绝对位置，这些数组称为“着法预生成数组”。例如，<FONT
face="Times New Roman">ElephantEye</FONT>里用了<FONT
face="Times New Roman">ucsqKnightMoves[256][12]</FONT>和<FONT
face="Times New Roman">ucsqHorseLegs[256][8]</FONT>，前一个数组的第二个维度之所以大于<FONT
face="Times New Roman">8</FONT>，是因为着法生成器依次读取数组中的值，读到<FONT
face="Times New Roman">0</FONT>就表示不再有着法<FONT
face="Times New Roman">(12</FONT>则是为了对齐地址<FONT
face="Times New Roman">)</FONT>。程序基本上是这样的：
<DD>
<DD>for (i = MyFirstHorse; i <= MyLastHorse; i ++) {
<DD> SrcSq = ucsqPieces[i];
<DD> if (SrcSq != 0) {
<DD> j = 0;
<DD> DstSq = ucsqKnightMoves[SrcSq][j];
<DD> while (DstSq != 0) {
<DD> LegSq = ucsqHorseLegs[SrcSq][j];
<DD> if (!(ucpcSquares[DstSq] & MyPieceMask) &&
ucpcSquares[LegSq] == 0) {
<DD> MoveList[MoveNum].Src = SrcSq;
<DD> MoveList[MoveNum].Dst = DstSq;
<DD> MoveNum ++;
<DD> }
<DD> j ++;
<DD> DstSq = ucsqHorseMoves[SrcSq][j];
<DD> }
<DD> }
<DD>}
<DT>
<DT> 和前一个程序一样，这个程序也同样用了两层循环，不同之处在于第二个循环读取的是着法预生成数组，<FONT
face="Times New Roman">DstSq</FONT>从<FONT
face="Times New Roman">ucsqHorseMoves[256][12]</FONT>中读出，<FONT
face="Times New Roman">LegSq</FONT>从<FONT
face="Times New Roman">ucsqHorseLegs[256][8]</FONT>中读出。
<DT>
<DT><FONT face=Arial size=4><STRONG>2.6 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>位行和位列</STRONG></FONT>
<DT>
<DT> 车和炮的着法分为吃子和不吃子两种，这两种着法生成器原则上是分开的，因此分为车炮不吃子、车吃子和炮吃子三个部分。不吃子的着法可以沿着上下左右四条射线逐一生成<FONT
face="Times New Roman">(</FONT>即并列做<FONT
face="Times New Roman">4</FONT>个循环<FONT
face="Times New Roman">)</FONT>。我们感兴趣的是吃子的着法，因为静态搜索只需要生成这种着法，能否不用循环就能做到？<FONT
face="Times New Roman">ElephantEye</FONT>几乎就做到了。
<DT> “位行”和“位列”是目前比较流行的着法生成技术，但仅限于车和炮的着法，它是否有速度上的优势还很难说，但是设计程序时可以减少一层循环，这个思想就已经比较领先了。以“位”的形式记录棋盘上某一行所有的格子的状态<FONT
face="Times New Roman">(</FONT>仅仅指是否有子<FONT
face="Times New Roman">)</FONT>，就称为“位行”<FONT
face="Times New Roman">(BitRank)</FONT>，与之对应的是“位列”<FONT
face="Times New Roman">(BitFile)</FONT>，棋盘结构应该包含<FONT
face="Times New Roman">10</FONT>个位行和<FONT
face="Times New Roman">9</FONT>个位列，即：
<DD>
<DD>struct PositionStruct {
<DD> ……
<DD> unsigned short wBitFiles[16];
<DD> unsigned short wBitRanks[16];
<DD> ……
<DD>};
<DT>
<DT> 值得注意的是，它仅仅是棋盘的附加信息，“棋盘<FONT
face="Times New Roman">-</FONT>棋子联系数组”仍旧是必不可少的。它的运作方式有点和“棋盘<FONT
face="Times New Roman">-</FONT>棋子联系数组”类似：
<DT> <FONT face="Times New Roman">(1)
</FONT>同时用位行数组和位列数组表示棋盘上的棋子分布信息，位行数组和位列数组之间可以互相转换；
<DT> <FONT face="Times New Roman">(2) </FONT>随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。
<DT> 因此，移走或放入一颗棋子时，必须在位行和位列上置位：
<DD>
<DD><FONT face=宋体>void AddPiece(int Square, int Piece) {</FONT>
<DD> ……
<DD> x = Square % 16;
<DD> y = Square / 16;
<DD> wBitFiles[x] = 1 << (y - 3);
<DD> wBitRanks[y] = 1 << (x - 3);
<DD> ……
<DD><FONT face=宋体>}</FONT>
<DT>
<DT> 车和炮是否能吃子<FONT face="Times New Roman">(</FONT>暂时不管吃到的是我方棋子还是敌方棋子<FONT
face="Times New Roman">)</FONT>，只取决于它所在的行和列上的每个格子上是否有棋子，而跟棋子的颜色和兵种无关，因此这些信息完全反映在位行和位列中。预置一个“能吃到的格子”的数组，以位行或位列为指标查找数组，就可以立即知道车或炮能吃哪个子了。预置数组到底有多大呢？
<DD>
<DD>// 某列各个位置的车或炮(10)在各种棋子排列下(1024)能走到的最上边或最下边的格子
<DD>unsigned char ucsqFileMoveNonCap[10][1024][2]; // 不吃子
<DD>unsigned char ucsqFileMoveRookCap[10][1024][2]; // 车吃子
<DD>unsigned char ucsqFileMoveCannonCap[10][1024][2]; // 炮吃子
<DD>// 某列各个位置的车或炮(9)在各种棋子排列下(512)能走到的最左边或最右边的格子
<DD>unsigned char ucsqRankMoveNonCap[9][512][2];
<DD>……
<DT>
<DT> 数组中的值记录的是目标格子的偏移值，即相对于该行或列第一个格子的编号。产生吃子着法很简单，以车吃子位例：
<DD>
<DD>for (i = MyFirstRook; i <= MyLastRook; i ++) {
<DD> SrcSq = ucsqPieces[i];
<DD> if (SrcSq != -1) {
<DD> x = SrcSq % 16;
<DD> y = SrcSq / 16;
<DD> DstSq = ucsqFileMoveRookCap[y - 3][wBitFiles[x]][0]; // 得到向上吃子的目标格
<DD> if (DstSq != 0) {
<DD> DstSq += x * 16; // 注意：第x列的第一个格子总是x * 16。
<DD> MoveList[MoveNum].Src = SrcSq;
<DD> MoveList[MoveNum].Dst = DstSq;
<DD> MoveNum ++;
<DD> }
<DD> …… // 再把FileMoveRookCap[...][...][0]替换成[...][...][1]，得到向下吃子的着法
<DD> DstSq = ucsqRankMoveRookCap[x - 3][wBitRanks[y]][0]; // 得到向左吃子的目标格
<DD> if (DstSq != 0) {
<DD> DstSq += y; // 注意：第y行的第一个格子总是y。
<DD> MoveList[MoveNum].Src = SrcSq;
<DD> MoveList[MoveNum].Dst = DstSq;
<DD> MoveNum ++;
<DD> }
<DD> …… // 再把RankMoveRookCap[...][...][0]替换成[...][...][1]，得到向右吃子的着法
<DD> }
<DD>}
<DT>
<DT><FONT face=Arial size=4><STRONG>2.7 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>着法合理性的判断</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">ElephantEye</FONT>搜索每个结点时，着法都有四个来源：<FONT
face="Times New Roman">(1) </FONT>置换表，<FONT face="Times New Roman">(2)
</FONT>吃子着法生成器，<FONT face="Times New Roman">(2) </FONT>杀手着法表，<FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -