moves.c

   1 /*
   2  * moves.c - Move generation and checking
   3  *
   4  * Copyright 1991 by Digital Equipment Corporation, Maynard,
   5  * Massachusetts.
   6  *
   7  * Enhancements Copyright 1992-2001, 2002, 2003, 2004, 2005, 2006,
   8  * 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Free Software Foundation, Inc.
   9  *
  10  * Enhancements Copyright 2005 Alessandro Scotti
  11  *
  12  * The following terms apply to Digital Equipment Corporation's copyright
  13  * interest in XBoard:
  14  * ------------------------------------------------------------------------
  15  * All Rights Reserved
  16  *
  17  * Permission to use, copy, modify, and distribute this software and its
  18  * documentation for any purpose and without fee is hereby granted,
  19  * provided that the above copyright notice appear in all copies and that
  20  * both that copyright notice and this permission notice appear in
  21  * supporting documentation, and that the name of Digital not be
  22  * used in advertising or publicity pertaining to distribution of the
  23  * software without specific, written prior permission.
  24  *
  25  * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  26  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  27  * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  28  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  29  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  30  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  31  * SOFTWARE.
  32  * ------------------------------------------------------------------------
  33  *
  34  * The following terms apply to the enhanced version of XBoard
  35  * distributed by the Free Software Foundation:
  36  * ------------------------------------------------------------------------
  37  *
  38  * GNU XBoard is free software: you can redistribute it and/or modify
  39  * it under the terms of the GNU General Public License as published by
  40  * the Free Software Foundation, either version 3 of the License, or (at
  41  * your option) any later version.
  42  *
  43  * GNU XBoard is distributed in the hope that it will be useful, but
  44  * WITHOUT ANY WARRANTY; without even the implied warranty of
  45  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  46  * General Public License for more details.
  47  *
  48  * You should have received a copy of the GNU General Public License
  49  * along with this program. If not, see http://www.gnu.org/licenses/.  *
  50  *
  51  *------------------------------------------------------------------------
  52  ** See the file ChangeLog for a revision history.  */
  53
  54 #include "config.h"
  55
  56 #include <stdio.h>
  57 #include <ctype.h>
  58 #include <stdlib.h>
  59 #if HAVE_STRING_H
  60 # include <string.h>
  61 #else /* not HAVE_STRING_H */
  62 # include <strings.h>
  63 #endif /* not HAVE_STRING_H */
  64 #include "common.h"
  65 #include "backend.h"
  66 #include "moves.h"
  67 #include "parser.h"
  68
  69 int WhitePiece P((ChessSquare));
  70 int BlackPiece P((ChessSquare));
  71 int SameColor P((ChessSquare, ChessSquare));
  72 int PosFlags(int index);
  73
  74 extern signed char initialRights[BOARD_FILES]; /* [HGM] all rights enabled, set in InitPosition */
  75 int quickFlag;
  76 char *pieceDesc[EmptySquare];
  77 char *defaultDesc[EmptySquare] = {
  78  "fmWfceFifmnD", "N", "B", "R", "Q",
  79  "F", "A", "BN", "RN", "W", "K",
  80  "mRcpR", "N0", "BW", "RF", "gQ",
  81  "", "", "QN", "", "N", "",
  82  "", "", "", "", "",
  83  "", "", "", "", "", "",
  84  "", "", "", "", "",
  85  "", "", "", "", "", "K"
  86 };
  87
  88 int
  89 WhitePiece (ChessSquare piece)
  90 {
  91     return (int) piece >= (int) WhitePawn && (int) piece < (int) BlackPawn;
  92 }
  93
  94 int
  95 BlackPiece (ChessSquare piece)
  96 {
  97     return (int) piece >= (int) BlackPawn && (int) piece < (int) EmptySquare;
  98 }
  99
 100 #if 0
 101 int
 102 SameColor (ChessSquare piece1, ChessSquare piece2)
 103 {
 104     return ((int) piece1 >= (int) WhitePawn &&   /* [HGM] can be > King ! */
 105             (int) piece1 <  (int) BlackPawn &&
 106             (int) piece2 >= (int) WhitePawn &&
 107             (int) piece2 <  (int) BlackPawn)
 108       ||   ((int) piece1 >= (int) BlackPawn &&
 109             (int) piece1 <  (int) EmptySquare &&
 110             (int) piece2 >= (int) BlackPawn &&
 111             (int) piece2 <  (int) EmptySquare);
 112 }
 113 #else
 114 #define SameColor(piece1, piece2) (piece1 < EmptySquare && piece2 < EmptySquare && (piece1 < BlackPawn) == (piece2 < BlackPawn) || piece1 == DarkSquare || piece2 == DarkSquare)
 115 #endif
 116
 117 unsigned char pieceToChar[EmptySquare+1] = {
 118                         'P', 'N', 'B', 'R', 'Q', 'F', 'E', 'A', 'C', 'W', 'M',
 119                         'O', 'H', 'I', 'J', 'G', 'D', 'V', 'L', 'S', 'U', 'K',
 120                         'p', 'n', 'b', 'r', 'q', 'f', 'e', 'a', 'c', 'w', 'm',
 121                         'o', 'h', 'i', 'j', 'g', 'd', 'v', 'l', 's', 'u', 'k',
 122                         'x' };
 123 unsigned char pieceNickName[EmptySquare];
 124
 125 char
 126 PieceToChar (ChessSquare p)
 127 {
 128     int c;
 129     if((int)p < 0 || (int)p >= (int)EmptySquare) return('x'); /* [HGM] for safety */
 130     c = pieceToChar[(int) p];
 131     if(c & 128) c = c & 63 | 64;
 132     return c;
 133 }
 134
 135 char
 136 PieceSuffix (ChessSquare p)
 137 {
 138     int c;
 139     if((int)p < 0 || (int)p >= (int)EmptySquare) return 0; /* [HGM] for safety */
 140     c = pieceToChar[(int) p];
 141     if(c < 128) return 0;
 142     return SUFFIXES[c - 128 >> 6];
 143 }
 144
 145 int
 146 PieceToNumber (ChessSquare p)  /* [HGM] holdings: count piece type, ignoring non-participating piece types */
 147 {
 148     int i=0;
 149     ChessSquare start = (int)p >= (int)BlackPawn ? BlackPawn : WhitePawn;
 150
 151     while(start++ != p) if(pieceToChar[start-1] != '.' && pieceToChar[start-1] != '+') i++;
 152     return i;
 153 }
 154
 155 ChessSquare
 156 CharToPiece (int c)
 157 {
 158      int i;
 159      if(c == '.') return EmptySquare;
 160      for(i=0; i< (int) EmptySquare; i++)
 161           if(pieceNickName[i] == c) return (ChessSquare) i;
 162      for(i=0; i< (int) EmptySquare; i++)
 163           if(pieceToChar[i] == c) return (ChessSquare) i;
 164      return EmptySquare;
 165 }
 166
 167 void
 168 CopyBoard (Board to, Board from)
 169 {
 170     int i, j;
 171
 172     for (i = 0; i < BOARD_HEIGHT; i++)
 173       for (j = 0; j < BOARD_WIDTH; j++)
 174         to[i][j] = from[i][j];
 175     for (j = 0; j < BOARD_FILES; j++) // [HGM] gamestate: copy castling rights and ep status
 176         to[VIRGIN][j] = from[VIRGIN][j],
 177         to[CASTLING][j] = from[CASTLING][j];
 178     to[HOLDINGS_SET] = 0; // flag used in ICS play
 179 }
 180
 181 int
 182 CompareBoards (Board board1, Board board2)
 183 {
 184     int i, j;
 185
 186     for (i = 0; i < BOARD_HEIGHT; i++)
 187       for (j = 0; j < BOARD_WIDTH; j++) {
 188           if (board1[i][j] != board2[i][j])
 189             return FALSE;
 190     }
 191     return TRUE;
 192 }
 193
 194 char defaultName[] = "PNBRQ......................................K"  // white
 195                      "pnbrq......................................k"; // black
 196 char shogiName[]   = "PNBRLS...G.++++++..........................K"  // white
 197                      "pnbrls...g.++++++..........................k"; // black
 198 char xqName[]      = "PH.R.AE..K.C................................"  // white
 199                      "ph.r.ae..k.c................................"; // black
 200
 201 char *
 202 CollectPieceDescriptors ()
 203 {   // make a line of piece descriptions for use in the PGN Piece tag:
 204     // dump all engine defined pieces, and pieces with non-standard names,
 205     // but suppress black pieces that are the same as their white counterpart
 206     ChessSquare p;
 207     static char buf[MSG_SIZ];
 208     char *m, c, d, *pieceName = defaultName;
 209     int len;
 210     *buf = NULLCHAR;
 211     if(!pieceDefs) return "";
 212     if(gameInfo.variant == VariantChu) return ""; // for now don't do this for Chu Shogi
 213     if(gameInfo.variant == VariantShogi) pieceName = shogiName;
 214     if(gameInfo.variant == VariantXiangqi) pieceName = xqName;
 215     for(p=WhitePawn; p<EmptySquare; p++) {
 216         if((c = pieceToChar[p]) == '.' || c == '~') continue;  // does not participate
 217         m = pieceDesc[p]; d = (c == '+' ? pieceToChar[DEMOTED(p)] : c);
 218         if(p >= BlackPawn && pieceToChar[BLACK_TO_WHITE p] == toupper(c)
 219              && (c != '+' || pieceToChar[DEMOTED(BLACK_TO_WHITE p)] == d)) {// black member of normal pair
 220             char *wm = pieceDesc[BLACK_TO_WHITE p];
 221             if(!m && !wm || m && wm && !strcmp(wm, m)) continue;            // moves as a white piece
 222         } else                                                              // white or unpaired black
 223         if((p < BlackPawn || CharToPiece(toupper(d)) != EmptySquare) &&     // white or lone black
 224            !pieceDesc[p] /*&& pieceName[p] == c*/) continue; // orthodox piece known by its usual name
 225 // TODO: listing pieces because of unusual name can only be done if we have accurate Betza of all defaults
 226         if(!m) m = defaultDesc[p];
 227         len = strlen(buf);
 228         snprintf(buf+len, MSG_SIZ-len, "%s%s%c:%s", len ? ";" : "", c == '+' ? "+" : "", d, m);
 229     }
 230     return buf;
 231 }
 232
 233 // [HGM] gen: configurable move generation from Betza notation sent by engine.
 234 // Some notes about two-leg moves: GenPseudoLegal() works in two modes, depending on whether a 'kill-
 235 // square has been set: without one is generates all moves, and a global int legNr flags in bits 0 and 1
 236 // if the move has 1 or 2 legs. Only the marking of squares makes use of this info, by only marking
 237 // target squares of leg 1 (rejecting null move). A dummy move with MoveType 'FirstLeg' to the relay square
 238 // is generated, so a cyan marker can be put there, and other functions can ignore such a move. When the
 239 // user selects this square, it becomes the kill-square. Once a kill-square is set, only 2-leg moves are
 240 // generated that use that square as relay, plus 1-leg moves, so the 1-leg move that goes to the kill-square
 241 // can be marked during 2nd-leg entry to terminate the move there. For judging the pseudo-legality of the
 242 // 2nd leg, the from-square has to be considered empty, although the moving piece is still on it.
 243
 244 Boolean pieceDefs;
 245
 246 //  alphabet      "abcdefghijklmnopqrstuvwxyz"
 247 char symmetry[] = "FBNW.FFW.NKN.NW.QR....W..N";
 248 char xStep[]    = "2110.130.102.10.00....0..2";
 249 char yStep[]    = "2132.133.313.20.11....1..3";
 250 char dirType[]  = "01000104000200000260050000";
 251 char upgrade[]  = "AFCD.BGH.JQL.NO.KW....R..Z";
 252 char rotate[]   = "DRCA.WHG.JKL.NO.QB....F..Z";
 253
 254 //  alphabet   "a b    c d e f    g h    i j k l    m n o p q r    s    t u v    w x y z "
 255 int dirs1[] = { 0,0x3C,0,0,0,0xC3,0,0,   0,0,0,0xF0,0,0,0,0,0,0x0F,0   ,0,0,0   ,0,0,0,0 };
 256 int dirs2[] = { 0,0x18,0,0,0,0x81,0,0xFF,0,0,0,0x60,0,0,0,0,0,0x06,0x66,0,0,0x99,0,0,0,0 };
 257 int dirs3[] = { 0,0x38,0,0,0,0x83,0,0xFF,0,0,0,0xE0,0,0,0,0,0,0x0E,0xEE,0,0,0xBB,0,0,0,0 };
 258 int dirs4[] = { 0,0x10,0,0,0,0x01,0,0xFF,0,0,0,0x40,0,0,0,0,0,0x04,0x44,0,0,0x11,0,0,0,0 };
 259
 260 int rot[][4] = { // rotation matrices for each direction
 261   { 1, 0, 0, 1 },
 262   { 0, 1, 1, 0 },
 263   { 0, 1,-1, 0 },
 264   { 1, 0, 0,-1 },
 265   {-1, 0, 0,-1 },
 266   { 0,-1,-1, 0 },
 267   { 0,-1, 1, 0 },
 268   {-1, 0, 0, 1 }
 269 };
 270
 271 void
 272 OK (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR cl)
 273 {
 274     (*(int*)cl)++;
 275 }
 276
 277 void
 278 MovesFromString (Board board, int flags, int f, int r, int tx, int ty, int angle, char *desc, MoveCallback cb, VOIDSTAR cl)
 279 {
 280     char buf[80], *p = desc, *atom = NULL;
 281     int mine, his, dir, bit, occup, i, ep, promoRank = -1;
 282     ChessMove promo= NormalMove; ChessSquare pc = board[r][f];
 283     if(pc == DarkSquare) return; // this is not a piece, but a 'hole' in the board
 284     if(flags & F_WHITE_ON_MOVE) his = 2, mine = 1; else his = 1, mine = 2;
 285     if(pc == WhitePawn || pc == WhiteLance) promo = WhitePromotion, promoRank = BOARD_HEIGHT-1; else
 286     if(pc == BlackPawn || pc == BlackLance) promo = BlackPromotion, promoRank = 0;
 287     while(*p) {                  // more moves to go
 288         int expo = 1, dx, dy, x, y, mode, dirSet, ds2=0, retry=0, initial=0, jump=1, skip = 0, all = 0;
 289         char *cont = NULL;
 290         while(*p == 'i') initial++, desc = ++p;
 291         while(islower(*p)) p++;  // skip prefixes
 292         if(!isupper(*p)) return; // syntax error: no atom
 293         dx = xStep[*p-'A'] - '0';// step vector of atom
 294         dy = yStep[*p-'A'] - '0';
 295         dirSet = 0;              // build direction set based on atom symmetry
 296         switch(symmetry[*p-'A']) {
 297           case 'B': expo = 0;    // bishop, slide
 298           case 'F': all = 0xAA;  // diagonal atom (degenerate 4-fold)
 299                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 300                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 301                         int b = dirs1[*desc-'a']; // use wide version
 302                         if( islower(desc[1]) &&
 303                                  ((i | dirType[desc[1]-'a']) & 3) == 3) {   // combinable (perpendicular dim)
 304                             b = dirs1[*desc-'a'] & dirs1[desc[1]-'a'];      // intersect wide & perp wide
 305                             desc += 2;
 306                         } else desc++;
 307                         dirSet |= b;
 308                     }
 309                     dirSet &= 0xAA; if(!dirSet) dirSet = 0xAA;
 310                     break;
 311           case 'R': expo = 0;    // rook, slide
 312           case 'W': all = 0x55;  // orthogonal atom (non-deg 4-fold)
 313                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 314                     while(islower(*desc) && (dirType[*desc-'a'] & ~4) != '0') dirSet |= dirs2[*desc++-'a'];
 315                     dirSet &= 0x55; if(!dirSet) dirSet = 0x55;
 316                     dirSet = (dirSet << angle | dirSet >> 8-angle) & 255;   // re-orient direction system
 317                     break;
 318           case 'N': all = 0xFF;  // oblique atom (degenerate 8-fold)
 319                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 320                     if(*desc == 'h') {            // chiral direction sets 'hr' and 'hl'
 321                         dirSet = (desc[1] == 'r' ? 0x55 :  0xAA); desc += 2;
 322                     } else
 323                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 324                         int b = dirs2[*desc-'a']; // when alone, use narrow version
 325                         if(desc[1] == 'h') b = dirs1[*desc-'a'], desc += 2; // dirs1 is wide version
 326                         else if(*desc == desc[1] || islower(desc[1]) && i < '4'
 327                                 && ((i | dirType[desc[1]-'a']) & 3) == 3) { // combinable (perpendicular dim or same)
 328                             b = dirs1[*desc-'a'] & dirs2[desc[1]-'a'];      // intersect wide & perp narrow
 329                             desc += 2;
 330                         } else desc++;
 331                         dirSet |= b;
 332                     }
 333                     if(!dirSet) dirSet = 0xFF;
 334                     break;
 335           case 'Q': expo = 0;    // queen, slide
 336           case 'K': all = 0xFF;  // non-deg (pseudo) 8-fold
 337           king:
 338                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 339                         int b = dirs4[*desc-'a'];    // when alone, use narrow version
 340                         if(desc[1] == *desc) desc++; // doubling forces alone
 341                         else if(islower(desc[1]) && i < '4'
 342                                 && ((i | dirType[desc[1]-'a']) & 3) == 3) { // combinable (perpendicular dim or same)
 343                             b = dirs3[*desc-'a'] & dirs3[desc[1]-'a'];      // intersect wide & perp wide
 344                             desc += 2;
 345                         } else desc++;
 346                         dirSet |= b;
 347                     }
 348                     if(!dirSet) dirSet = (tx < 0 ? 0xFF                     // default is all directions, but in continuation leg
 349                                           : all == 0xFF ? 0xEF : 0x45);     // omits backward, and for 4-fold atoms also diags
 350                     dirSet = (dirSet << angle | dirSet >> 8-angle) & 255;   // re-orient direction system
 351                     ds2 = dirSet & 0xAA;          // extract diagonal directions
 352                     if(dirSet &= 0x55)            // start with orthogonal moves, if present
 353                          retry = 1, dx = 0;       // and schedule the diagonal moves for later
 354                     else dx = dy, dirSet = ds2;   // if no orthogonal directions, do diagonal immediately
 355                     break;       // should not have direction indicators
 356           default:  return;      // syntax error: invalid atom
 357         }
 358         if(mine == 2 && tx < 0) dirSet = dirSet >> 4 | dirSet << 4 & 255;   // invert black moves
 359         mode = 0;                // build mode mask
 360         if(*desc == 'm') mode |= 4, desc++;           // move to empty
 361         if(*desc == 'c') mode |= his, desc++;         // capture foe
 362         if(*desc == 'd') mode |= mine, desc++;        // destroy (capture friend)
 363         if(*desc == 'e') mode |= 8, desc++;           // e.p. capture last mover
 364         if(*desc == 't') mode |= 16, desc++;          // exclude enemies as hop platform ('test')
 365         if(*desc == 'p') mode |= 32, desc++;          // hop over occupied
 366         if(*desc == 'g') mode |= 64, desc++;          // hop and toggle range
 367         if(*desc == 'o') mode |= 128, desc++;         // wrap around cylinder board
 368         if(*desc == 'y') mode |= 512, desc++;         // toggle range on empty square
 369         if(*desc == 'n') jump = 0, desc++;            // non-jumping
 370         while(*desc == 'j') jump++, desc++;           // must jump (on B,R,Q: skip first square)
 371         if(*desc == 'a') cont = ++desc;               // move again after doing what preceded it
 372         if(isdigit(*++p)) expo = atoi(p++);           // read exponent
 373         if(expo > 9) p++;                             // allow double-digit
 374         desc = p;                                     // this is start of next move
 375         if(initial == 2) { if(board[r][f] != initialPosition[r-2*his+3][f]) continue; } else
 376         if(initial && (board[r][f] != initialPosition[r][f] ||
 377                        r == 0              && board[TOUCHED_W] & 1<<f ||
 378                        r == BOARD_HEIGHT-1 && board[TOUCHED_B] & 1<<f   ) ) continue;
 379         if(expo > 1 && dx == 0 && dy == 0) {          // castling indicated by O + number
 380             mode |= 1024; dy = 1;
 381         }
 382         if(!cont) {
 383             if(!(mode & 15)) mode |= his + 4;         // no mode spec, use default = mc
 384         } else {
 385             strncpy(buf, cont, 80); cont = buf;       // copy next leg(s), so we can modify
 386             atom = buf; while(islower(*atom)) atom++; // skip to atom
 387             if(mode & 32) mode ^= 256 + 32;           // in non-final legs 'p' means 'pass through'
 388             if(mode & 64 + 512) {
 389                 mode |= 256;                          // and 'g' too, but converts leaper <-> slider
 390                 if(mode & 512) mode ^= 0x304;         // and 'y' is m-like 'g'
 391                 *atom = upgrade[*atom-'A'];           // replace atom, BRQ <-> FWK
 392                 atom[1] = atom[2] = '\0';             // make sure any old range is stripped off
 393                 if(expo == 1) atom[1] = '0';          // turn other leapers into riders
 394             }
 395             if(!(mode & 0x30F)) mode |= 4;            // and default of this leg = m
 396         }
 397         if(dy == 1) skip = jump - 1, jump = 1;        // on W & F atoms 'j' = skip first square
 398         do {
 399           for(dir=0, bit=1; dir<8; dir++, bit += bit) { // loop over directions
 400             int i = expo, j = skip, hop = mode, vx, vy, loop = 0;
 401             if(!(bit & dirSet)) continue;             // does not move in this direction
 402             if(dy != 1 || mode & 1024) j = 0;         //
 403             vx = dx*rot[dir][0] + dy*rot[dir][1];     // rotate step vector
 404             vy = dx*rot[dir][2] + dy*rot[dir][3];
 405             if(tx < 0) x = f, y = r;                  // start square
 406             else      x = tx, y = ty;                 // from previous to-square if continuation
 407             do {                                      // traverse ray
 408                 x += vx; y += vy;                     // step to next square
 409                 if(y < 0 || y >= BOARD_HEIGHT) break; // vertically off-board: always done
 410                 if(x <  BOARD_LEFT) { if(mode & 128) x += BOARD_RGHT - BOARD_LEFT, loop++; else break; }
 411                 if(x >= BOARD_RGHT) { if(mode & 128) x -= BOARD_RGHT - BOARD_LEFT, loop++; else break; }
 412                 if(j) { j--; continue; }              // skip irrespective of occupation
 413                 if(board[y][x] == DarkSquare) break;  // black squares are supposed to be off board
 414                 if(!jump    && board[y - vy + vy/2][x - vx + vx/2] != EmptySquare) break; // blocked
 415                 if(jump > 1 && board[y - vy + vy/2][x - vx + vx/2] == EmptySquare) break; // no hop
 416                 if(x == f && y == r && !loop) occup = 4;     else // start square counts as empty (if not around cylinder!)
 417                 if(board[y][x] < BlackPawn)   occup = 0x101; else
 418                 if(board[y][x] < EmptySquare) occup = 0x102; else
 419                                               occup = 4;
 420                 if(cont) {                            // non-final leg
 421                   if(mode&16 && his&occup) occup &= 3;// suppress hopping foe in t-mode
 422                   if(occup & mode) {                  // valid intermediate square, do continuation
 423                     char origAtom = *atom;
 424                     if(!(bit & all)) *atom = rotate[*atom - 'A']; // orth-diag interconversion to make direction valid
 425                     if(occup & mode & 0x104)          // no side effects, merge legs to one move
 426                         MovesFromString(board, flags, f, r, x, y, dir, cont, cb, cl);
 427                     if(occup & mode & 3 && (killX < 0 || killX == x && killY == y)) {     // destructive first leg
 428                         int cnt = 0;
 429                         MovesFromString(board, flags, f, r, x, y, dir, cont, &OK, &cnt);  // count possible continuations
 430                         if(cnt) {                                                         // and if there are
 431                             if(killX < 0) cb(board, flags, FirstLeg, r, f, y, x, cl);     // then generate their first leg
 432                             legNr <<= 1;
 433                             MovesFromString(board, flags, f, r, x, y, dir, cont, cb, cl);
 434                             legNr >>= 1;
 435                         }
 436                     }
 437                     *atom = origAtom;        // undo any interconversion
 438                   }
 439                   if(occup != 4) break;      // occupied squares always terminate the leg
 440                   continue;
 441                 }
 442                 if(hop & 32+64) { if(occup != 4) { if(hop & 64 && i != 1) i = 2; hop &= 31; } continue; } // hopper
 443                 ep = board[EP_RANK];
 444                 if(mode & 8 && occup == 4 && board[EP_FILE] == x && (y == (ep & 127) || y - vy == ep - 128)) { // to e.p. square (or 2nd e.p. square)
 445                     cb(board, flags, mine == 1 ? WhiteCapturesEnPassant : BlackCapturesEnPassant, r, f, y, x, cl);
 446                 }
 447                 if(mode & 1024) {            // castling
 448                     i = 2;                   // kludge to elongate move indefinitely
 449                     if(occup == 4) continue; // skip empty squares
 450                     if((x == BOARD_LEFT + skip || x > BOARD_LEFT + skip && vx < 0 && board[y][x-1-skip] == DarkSquare)
 451                                                                     && board[y][x] == initialPosition[y][x]) { // reached initial corner piece
 452                       if(pc != WhiteKing && pc != BlackKing) { // non-royal castling (to be entered as two-leg move via 'Rook')
 453                         if(killX < 0) cb(board, flags, FirstLeg,   r, f, y, x, cl); if(killX < f)
 454                         legNr <<= 1,  cb(board, flags, NormalMove, r, f, y, f - expo, cl), legNr >>= 1;
 455                       } else
 456                         cb(board, flags, mine == 1 ? WhiteQueenSideCastle : BlackQueenSideCastle, r, f, y, f - expo, cl);
 457                     }
 458                     if((x == BOARD_RGHT-1-skip || x < BOARD_RGHT-1-skip && vx > 0 && board[y][x+1+skip] == DarkSquare)
 459                                                                     && board[y][x] == initialPosition[y][x]) {
 460                       if(pc != WhiteKing && pc != BlackKing) {
 461                         if(killX < 0) cb(board, flags, FirstLeg,   r, f, y, x, cl); if(killX > f)
 462                         legNr <<= 1,  cb(board, flags, NormalMove, r, f, y, f + expo, cl), legNr >>= 1;
 463                       } else
 464                         cb(board, flags, mine == 1 ? WhiteKingSideCastle : BlackKingSideCastle, r, f, y, f + expo, cl);
 465                     }
 466                     break;
 467                 }
 468                 if(mode & 16 && (board[y][x] == WhiteKing || board[y][x] == BlackKing)) break; // tame piece, cannot capture royal
 469                 if(occup & mode) cb(board, flags, y == promoRank ? promo : NormalMove, r, f, y, x, cl); // allowed, generate
 470                 if(occup != 4) break; // not valid transit square
 471             } while(--i);
 472           }
 473           dx = dy; dirSet = ds2;      // prepare for diagonal moves of K,Q
 474         } while(retry-- && ds2);      // and start doing them
 475         if(tx >= 0) break;            // don't do other atoms in continuation legs
 476     }
 477 } // next atom
 478
 479 // [HGM] move generation now based on hierarchy of subroutines for rays and combinations of rays
 480
 481 void
 482 SlideForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 483 {
 484   int i, rt, ft = ff;
 485   for (i = 1;; i++) {
 486       rt = rf + i;
 487       if (rt >= BOARD_HEIGHT) break;
 488       if (SameColor(board[rf][ff], board[rt][ft])) break;
 489       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 490       if (board[rt][ft] != EmptySquare) break;
 491   }
 492 }
 493
 494 void
 495 SlideBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 496 {
 497   int i, rt, ft = ff;
 498   for (i = 1;; i++) {
 499       rt = rf - i;
 500       if (rt < 0) break;
 501       if (SameColor(board[rf][ff], board[rt][ft])) break;
 502       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 503       if (board[rt][ft] != EmptySquare) break;
 504   }
 505 }
 506
 507 void
 508 SlideVertical (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 509 {
 510   SlideForward(board, flags, rf, ff, callback, closure);
 511   SlideBackward(board, flags, rf, ff, callback, closure);
 512 }
 513
 514 void
 515 SlideSideways (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 516 {
 517   int i, s, rt = rf, ft;
 518   for(s = -1; s <= 1; s+= 2) {
 519     for (i = 1;; i++) {
 520       ft = ff + i*s;
 521       if (ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 522       if (SameColor(board[rf][ff], board[rt][ft])) break;
 523       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 524       if (board[rt][ft] != EmptySquare) break;
 525     }
 526   }
 527 }
 528
 529 void
 530 SlideDiagForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 531 {
 532   int i, s, rt, ft;
 533   for(s = -1; s <= 1; s+= 2) {
 534     for (i = 1;; i++) {
 535       rt = rf + i;
 536       ft = ff + i * s;
 537       if (rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 538       if (SameColor(board[rf][ff], board[rt][ft])) break;
 539       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 540       if (board[rt][ft] != EmptySquare) break;
 541     }
 542   }
 543 }
 544
 545 void
 546 SlideDiagBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 547 {
 548   int i, s, rt, ft;
 549   for(s = -1; s <= 1; s+= 2) {
 550     for (i = 1;; i++) {
 551       rt = rf - i;
 552       ft = ff + i * s;
 553       if (rt < 0 || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 554       if (SameColor(board[rf][ff], board[rt][ft])) break;
 555       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 556       if (board[rt][ft] != EmptySquare) break;
 557     }
 558   }
 559 }
 560
 561 void
 562 Rook (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 563 {
 564   SlideVertical(board, flags, rf, ff, callback, closure);
 565   SlideSideways(board, flags, rf, ff, callback, closure);
 566 }
 567
 568 void
 569 Bishop (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 570 {
 571   SlideDiagForward(board, flags, rf, ff, callback, closure);
 572   SlideDiagBackward(board, flags, rf, ff, callback, closure);
 573 }
 574
 575 void
 576 Sting (Board board, int flags, int rf, int ff, int dy, int dx, MoveCallback callback, VOIDSTAR closure)
 577 { // Lion-like move of Horned Falcon and Souring Eagle
 578   int ft = ff + dx, rt = rf + dy;
 579   if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) return;
 580   legNr += 2;
 581   if (!SameColor(board[rf][ff], board[rt][ft]))
 582     callback(board, flags, board[rt][ft] != EmptySquare ? FirstLeg : NormalMove, rf, ff, rt, ft, closure);
 583   legNr -= 2;
 584   ft += dx; rt += dy;
 585   if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) return;
 586   legNr += 2;
 587   if (!SameColor(board[rf][ff], board[rt][ft]))
 588     callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 589   if (!SameColor(board[rf][ff], board[rf+dy][ff+dx]))
 590     callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 591   legNr -= 2;
 592 }
 593
 594 void
 595 StepForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 596 {
 597   int ft = ff, rt = rf + 1;
 598   if (rt >= BOARD_HEIGHT) return;
 599   if (SameColor(board[rf][ff], board[rt][ft])) return;
 600   callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 601 }
 602
 603 void
 604 StepBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 605 {
 606   int ft = ff, rt = rf - 1;
 607   if (rt < 0) return;
 608   if (SameColor(board[rf][ff], board[rt][ft])) return;
 609   callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 610 }
 611
 612 void
 613 StepSideways (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 614 {
 615   int ft, rt = rf;
 616   ft = ff + 1;
 617   if (!(rt >= BOARD_HEIGHT || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 618       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 619   ft = ff - 1;
 620   if (!(rt >= BOARD_HEIGHT || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 621       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 622 }
 623
 624 void
 625 StepDiagForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 626 {
 627   int ft, rt = rf + 1;
 628   if (rt >= BOARD_HEIGHT) return;
 629   ft = ff + 1;
 630   if (!(rt >= BOARD_HEIGHT || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 631       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 632   ft = ff - 1;
 633   if (!(rt >= BOARD_HEIGHT || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 634       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 635 }
 636
 637 void
 638 StepDiagBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 639 {
 640   int ft, rt = rf - 1;
 641   if(rt < 0) return;
 642   ft = ff + 1;
 643   if (!(rt < 0 || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 644       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 645   ft = ff - 1;
 646   if (!(rt < 0 || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 647       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 648 }
 649
 650 void
 651 StepVertical (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 652 {
 653   StepForward(board, flags, rf, ff, callback, closure);
 654   StepBackward(board, flags, rf, ff, callback, closure);
 655 }
 656
 657 void
 658 Ferz (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 659 {
 660   StepDiagForward(board, flags, rf, ff, callback, closure);
 661   StepDiagBackward(board, flags, rf, ff, callback, closure);
 662 }
 663
 664 void
 665 Wazir (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 666 {
 667   StepVertical(board, flags, rf, ff, callback, closure);
 668   StepSideways(board, flags, rf, ff, callback, closure);
 669 }
 670
 671 void
 672 Knight (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 673 {
 674     int i, j, s, rt, ft;
 675     for (i = -1; i <= 1; i += 2)
 676         for (j = -1; j <= 1; j += 2)
 677             for (s = 1; s <= 2; s++) {
 678                 rt = rf + i*s;
 679                 ft = ff + j*(3-s);
 680                 if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 681                     && ( gameInfo.variant != VariantXiangqi || board[rf+i*(s-1)][ff+j*(2-s)] == EmptySquare)
 682                     && !SameColor(board[rf][ff], board[rt][ft]))
 683                     callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 684             }
 685 }
 686
 687 /* Call callback once for each pseudo-legal move in the given
 688    position, except castling moves. A move is pseudo-legal if it is
 689    legal, or if it would be legal except that it leaves the king in
 690    check.  In the arguments, epfile is EP_NONE if the previous move
 691    was not a double pawn push, or the file 0..7 if it was, or
 692    EP_UNKNOWN if we don't know and want to allow all e.p. captures.
 693    Promotion moves generated are to Queen only.
 694 */
 695 void
 696 GenPseudoLegal (Board board, int flags, MoveCallback callback, VOIDSTAR closure, ChessSquare filter)
 697 // speed: only do moves with this piece type
 698 {
 699     int rf, ff;
 700     int i, j, d, s, fs, rs, rt, ft, m;
 701     int epfile = (signed char)board[EP_STATUS]; // [HGM] gamestate: extract ep status from board
 702     int promoRank = gameInfo.variant == VariantMakruk || gameInfo.variant == VariantGrand || gameInfo.variant == VariantChuChess ? 3 : 1;
 703
 704     for (rf = 0; rf < BOARD_HEIGHT; rf++)
 705       for (ff = BOARD_LEFT; ff < BOARD_RGHT; ff++) {
 706           ChessSquare piece;
 707
 708           if(board[rf][ff] == EmptySquare) continue;
 709           if ((flags & F_WHITE_ON_MOVE) != (board[rf][ff] < BlackPawn)) continue; // [HGM] speed: wrong color
 710           m = 0; piece = board[rf][ff];
 711           if(PieceToChar(piece) == '~')
 712                  piece = (ChessSquare) ( DEMOTED(piece) );
 713           if(filter != EmptySquare && piece != filter) continue;
 714           if(pieceDefs && pieceDesc[piece]) { // [HGM] gen: use engine-defined moves
 715               MovesFromString(board, flags, ff, rf, -1, -1, 0, pieceDesc[piece], callback, closure);
 716               continue;
 717           }
 718           if(IS_SHOGI(gameInfo.variant))
 719                  piece = (ChessSquare) ( SHOGI piece );
 720
 721           switch ((int)piece) {
 722             /* case EmptySquare: [HGM] this is nonsense, and conflicts with Shogi cases */
 723             default:
 724               /* can't happen ([HGM] except for faries...) */
 725               break;
 726
 727              case WhitePawn:
 728               if(gameInfo.variant == VariantXiangqi) {
 729                   /* [HGM] capture and move straight ahead in Xiangqi */
 730                   if (rf < BOARD_HEIGHT-1 &&
 731                            !SameColor(board[rf][ff], board[rf + 1][ff]) ) {
 732                            callback(board, flags, NormalMove,
 733                                     rf, ff, rf + 1, ff, closure);
 734                   }
 735                   /* and move sideways when across the river */
 736                   for (s = -1; s <= 1; s += 2) {
 737                       if (rf >= BOARD_HEIGHT>>1 &&
 738                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 739                           !WhitePiece(board[rf][ff+s]) ) {
 740                            callback(board, flags, NormalMove,
 741                                     rf, ff, rf, ff+s, closure);
 742                       }
 743                   }
 744                   break;
 745               }
 746               if (rf < BOARD_HEIGHT-1 && board[rf + 1][ff] == EmptySquare) {
 747                   callback(board, flags,
 748                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 749                            rf, ff, rf + 1, ff, closure);
 750               }
 751               if (rf <= (BOARD_HEIGHT>>1)-3 && board[rf+1][ff] == EmptySquare && // [HGM] grand: also on 3rd rank on 10-board
 752                   gameInfo.variant != VariantShatranj && /* [HGM] */
 753                   gameInfo.variant != VariantCourier  && /* [HGM] */
 754                   board[rf+2][ff] == EmptySquare ) {
 755                       callback(board, flags, NormalMove,
 756                                rf, ff, rf+2, ff, closure);
 757               }
 758               for (s = -1; s <= 1; s += 2) {
 759                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 760                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 761                        BlackPiece(board[rf + 1][ff + s]))) {
 762                       callback(board, flags,
 763                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 764                                rf, ff, rf + 1, ff + s, closure);
 765                   }
 766                   if (rf >= BOARD_HEIGHT+1>>1) {// [HGM] grand: 4th & 5th rank on 10-board
 767                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 768                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf < BOARD_HEIGHT-3 &&
 769                           board[rf][ff + s] == BlackPawn &&
 770                           board[rf+1][ff + s] == EmptySquare) {
 771                           callback(board, flags, WhiteCapturesEnPassant,
 772                                    rf, ff, rf+1, ff + s, closure);
 773                       }
 774                   }
 775               }
 776               break;
 777
 778             case BlackPawn:
 779               if(gameInfo.variant == VariantXiangqi) {
 780                   /* [HGM] capture straight ahead in Xiangqi */
 781                   if (rf > 0 && !SameColor(board[rf][ff], board[rf - 1][ff]) ) {
 782                            callback(board, flags, NormalMove,
 783                                     rf, ff, rf - 1, ff, closure);
 784                   }
 785                   /* and move sideways when across the river */
 786                   for (s = -1; s <= 1; s += 2) {
 787                       if (rf < BOARD_HEIGHT>>1 &&
 788                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 789                           !BlackPiece(board[rf][ff+s]) ) {
 790                            callback(board, flags, NormalMove,
 791                                     rf, ff, rf, ff+s, closure);
 792                       }
 793                   }
 794                   break;
 795               }
 796               if (rf > 0 && board[rf - 1][ff] == EmptySquare) {
 797                   callback(board, flags,
 798                            rf <= promoRank ? BlackPromotion : NormalMove,
 799                            rf, ff, rf - 1, ff, closure);
 800               }
 801               if (rf >= (BOARD_HEIGHT+1>>1)+2 && board[rf-1][ff] == EmptySquare && // [HGM] grand
 802                   gameInfo.variant != VariantShatranj && /* [HGM] */
 803                   gameInfo.variant != VariantCourier  && /* [HGM] */
 804                   board[rf-2][ff] == EmptySquare) {
 805                   callback(board, flags, NormalMove,
 806                            rf, ff, rf-2, ff, closure);
 807               }
 808               for (s = -1; s <= 1; s += 2) {
 809                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 810                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 811                        WhitePiece(board[rf - 1][ff + s]))) {
 812                       callback(board, flags,
 813                                rf <= promoRank ? BlackPromotion : NormalMove,
 814                                rf, ff, rf - 1, ff + s, closure);
 815                   }
 816                   if (rf < BOARD_HEIGHT>>1) {
 817                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 818                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf > 2 &&
 819                           board[rf][ff + s] == WhitePawn &&
 820                           board[rf-1][ff + s] == EmptySquare) {
 821                           callback(board, flags, BlackCapturesEnPassant,
 822                                    rf, ff, rf-1, ff + s, closure);
 823                       }
 824                   }
 825               }
 826               break;
 827
 828             case WhiteUnicorn:
 829             case BlackUnicorn:
 830             case WhiteKnight:
 831             case BlackKnight:
 832               for (i = -1; i <= 1; i += 2)
 833                 for (j = -1; j <= 1; j += 2)
 834                   for (s = 1; s <= 2; s++) {
 835                       rt = rf + i*s;
 836                       ft = ff + j*(3-s);
 837                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 838                           && ( gameInfo.variant != VariantXiangqi || board[rf+i*(s-1)][ff+j*(2-s)] == EmptySquare)
 839                           && !SameColor(board[rf][ff], board[rt][ft]))
 840                       callback(board, flags, NormalMove,
 841                                rf, ff, rt, ft, closure);
 842                   }
 843               break;
 844
 845             case SHOGI WhiteKnight:
 846               for (s = -1; s <= 1; s += 2) {
 847                   if (rf < BOARD_HEIGHT-2 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 848                       !SameColor(board[rf][ff], board[rf + 2][ff + s])) {
 849                       callback(board, flags, NormalMove,
 850                                rf, ff, rf + 2, ff + s, closure);
 851                   }
 852               }
 853               break;
 854
 855             case SHOGI BlackKnight:
 856               for (s = -1; s <= 1; s += 2) {
 857                   if (rf > 1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 858                       !SameColor(board[rf][ff], board[rf - 2][ff + s])) {
 859                       callback(board, flags, NormalMove,
 860                                rf, ff, rf - 2, ff + s, closure);
 861                   }
 862               }
 863               break;
 864
 865             case WhiteCannon:
 866             case BlackCannon:
 867               for (d = 0; d <= 1; d++)
 868                 for (s = -1; s <= 1; s += 2) {
 869                   m = 0;
 870                   for (i = 1;; i++) {
 871                       rt = rf + (i * s) * d;
 872                       ft = ff + (i * s) * (1 - d);
 873                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 874                       if (m == 0 && board[rt][ft] == EmptySquare)
 875                                  callback(board, flags, NormalMove,
 876                                           rf, ff, rt, ft, closure);
 877                       if (m == 1 && board[rt][ft] != EmptySquare &&
 878                           !SameColor(board[rf][ff], board[rt][ft]) )
 879                                  callback(board, flags, NormalMove,
 880                                           rf, ff, rt, ft, closure);
 881                       if (board[rt][ft] != EmptySquare && m++) break;
 882                   }
 883                 }
 884               break;
 885
 886             /* Gold General (and all its promoted versions) . First do the */
 887             /* diagonal forward steps, then proceed as normal Wazir        */
 888             case SHOGI (PROMO WhitePawn):
 889                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 890             case SHOGI (PROMO BlackPawn):
 891                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 892                 SlideVertical(board, flags, rf, ff, callback, closure);
 893                 break;
 894
 895             case SHOGI (PROMO WhiteKnight):
 896                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 897             case SHOGI BlackDrunk:
 898             case SHOGI BlackAlfil:
 899                 Ferz(board, flags, rf, ff, callback, closure);
 900                 StepSideways(board, flags, rf, ff, callback, closure);
 901                 StepBackward(board, flags, rf, ff, callback, closure);
 902                 break;
 903
 904             case SHOGI (PROMO BlackKnight):
 905                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 906             case SHOGI WhiteDrunk:
 907             case SHOGI WhiteAlfil:
 908                 Ferz(board, flags, rf, ff, callback, closure);
 909                 StepSideways(board, flags, rf, ff, callback, closure);
 910                 StepForward(board, flags, rf, ff, callback, closure);
 911                 break;
 912
 913
 914             case SHOGI WhiteStag:
 915             case SHOGI BlackStag:
 916                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 917                 SlideVertical(board, flags, rf, ff, callback, closure);
 918                 Ferz(board, flags, rf, ff, callback, closure);
 919                 StepSideways(board, flags, rf, ff, callback, closure);
 920                 break;
 921
 922             case SHOGI (PROMO WhiteQueen):
 923             case SHOGI WhiteTokin:
 924             case SHOGI WhiteWazir:
 925             WhiteGold:
 926                 StepDiagForward(board, flags, rf, ff, callback, closure);
 927                 Wazir(board, flags, rf, ff, callback, closure);
 928                 break;
 929
 930             case SHOGI (PROMO BlackQueen):
 931             case SHOGI BlackTokin:
 932             case SHOGI BlackWazir:
 933             BlackGold:
 934                 StepDiagBackward(board, flags, rf, ff, callback, closure);
 935                 Wazir(board, flags, rf, ff, callback, closure);
 936                 break;
 937
 938             case WhiteWazir:
 939             case BlackWazir:
 940                 Wazir(board, flags, rf, ff, callback, closure);
 941                 break;
 942
 943             case SHOGI WhiteMarshall:
 944             case SHOGI BlackMarshall:
 945                 Ferz(board, flags, rf, ff, callback, closure);
 946                 for (d = 0; d <= 1; d++)
 947                     for (s = -2; s <= 2; s += 4) {
 948                         rt = rf + s * d;
 949                         ft = ff + s * (1 - d);
 950                         if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 951                         if (!SameColor(board[rf][ff], board[rt][ft]) )
 952                             callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 953                     }
 954                 break;
 955
 956             case SHOGI WhiteAngel:
 957             case SHOGI BlackAngel:
 958                 Wazir(board, flags, rf, ff, callback, closure);
 959
 960             case WhiteAlfil:
 961             case BlackAlfil:
 962                 /* [HGM] support Shatranj pieces */
 963                 for (rs = -1; rs <= 1; rs += 2)
 964                   for (fs = -1; fs <= 1; fs += 2) {
 965                       rt = rf + 2 * rs;
 966                       ft = ff + 2 * fs;
 967                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 968                           && ( gameInfo.variant != VariantXiangqi ||
 969                                board[rf+rs][ff+fs] == EmptySquare && (2*rf < BOARD_HEIGHT) == (2*rt < BOARD_HEIGHT) )
 970
 971                           && !SameColor(board[rf][ff], board[rt][ft]))
 972                                callback(board, flags, NormalMove,
 973                                         rf, ff, rt, ft, closure);
 974                       if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
 975                          gameInfo.variant == VariantChu      || gameInfo.variant == VariantXiangqi) continue; // classical Alfil
 976                       rt = rf + rs; // in unknown variant we assume Modern Elephant, which can also do one step
 977                       ft = ff + fs;
 978                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 979                           && !SameColor(board[rf][ff], board[rt][ft]))
 980                                callback(board, flags, NormalMove,
 981                                         rf, ff, rt, ft, closure);
 982                   }
 983                 if(gameInfo.variant == VariantSpartan)
 984                    for(fs = -1; fs <= 1; fs += 2) {
 985                       ft = ff + fs;
 986                       if (!(ft < BOARD_LEFT || ft >= BOARD_RGHT) && board[rf][ft] == EmptySquare)
 987                                callback(board, flags, NormalMove, rf, ff, rf, ft, closure);
 988                    }
 989                 break;
 990
 991             /* Make Dragon-Horse also do Dababba moves outside Shogi, for better disambiguation in variant Fairy */
 992             case WhiteCardinal:
 993             case BlackCardinal:
 994               if(gameInfo.variant == VariantChuChess) goto DragonHorse;
 995               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
 996                 for (s = -2; s <= 2; s += 4) {
 997                       rt = rf + s * d;
 998                       ft = ff + s * (1 - d);
 999                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
1000                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
1001                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
1002                   }
1003
1004             /* Shogi Dragon Horse has to continue with Wazir after Bishop */
1005             case SHOGI WhiteCardinal:
1006             case SHOGI BlackCardinal:
1007             case SHOGI WhitePCardinal:
1008             case SHOGI BlackPCardinal:
1009             DragonHorse:
1010                 Bishop(board, flags, rf, ff, callback, closure);
1011                 Wazir(board, flags, rf, ff, callback, closure);
1012                 break;
1013
1014             /* Capablanca Archbishop continues as Knight                  */
1015             case WhiteAngel:
1016             case BlackAngel:
1017                 Knight(board, flags, rf, ff, callback, closure);
1018
1019             /* Shogi Bishops are ordinary Bishops */
1020             case SHOGI WhiteBishop:
1021             case SHOGI BlackBishop:
1022             case SHOGI WhitePBishop:
1023             case SHOGI BlackPBishop:
1024             case WhiteBishop:
1025             case BlackBishop:
1026                 Bishop(board, flags, rf, ff, callback, closure);
1027                 break;
1028
1029             /* Shogi Lance is unlike anything, and asymmetric at that */
1030             case SHOGI WhiteQueen:
1031               if(gameInfo.variant == VariantChu) goto doQueen;
1032               for(i = 1;; i++) {
1033                       rt = rf + i;
1034                       ft = ff;
1035                       if (rt >= BOARD_HEIGHT) break;
1036                       if (SameColor(board[rf][ff], board[rt][ft])) break;
1037                       callback(board, flags, NormalMove,
1038                                rf, ff, rt, ft, closure);
1039                       if (board[rt][ft] != EmptySquare) break;
1040               }
1041               break;
1042
1043             case SHOGI BlackQueen:
1044               if(gameInfo.variant == VariantChu) goto doQueen;
1045               for(i = 1;; i++) {
1046                       rt = rf - i;
1047                       ft = ff;
1048                       if (rt < 0) break;
1049                       if (SameColor(board[rf][ff], board[rt][ft])) break;
1050                       callback(board, flags, NormalMove,
1051                                rf, ff, rt, ft, closure);
1052                       if (board[rt][ft] != EmptySquare) break;
1053               }
1054               break;
1055
1056             /* Make Dragon-King Dababba & Rook-like outside Shogi, for better disambiguation in variant Fairy */
1057             case WhiteDragon:
1058             case BlackDragon:
1059               if(gameInfo.variant == VariantChuChess) goto DragonKing;
1060               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
1061                 for (s = -2; s <= 2; s += 4) {
1062                       rt = rf + s * d;
1063                       ft = ff + s * (1 - d);
1064                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
1065                       if (board[rf+rt>>1][ff+ft>>1] == EmptySquare && gameInfo.variant != VariantSpartan) continue;
1066                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
1067                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
1068                   }
1069               if(gameInfo.variant == VariantSpartan) // in Spartan Chess restrict range to modern Dababba
1070                 Wazir(board, flags, rf, ff, callback, closure);
1071               else
1072                 Rook(board, flags, rf, ff, callback, closure);
1073               break;
1074
1075             /* Shogi Dragon King has to continue as Ferz after Rook moves */
1076             case SHOGI WhiteDragon:
1077             case SHOGI BlackDragon:
1078             case SHOGI WhitePDragon:
1079             case SHOGI BlackPDragon:
1080             DragonKing:
1081                 Rook(board, flags, rf, ff, callback, closure);
1082                 Ferz(board, flags, rf, ff, callback, closure);
1083                 break;
1084               m++;
1085
1086             /* Capablanca Chancellor sets flag to continue as Knight      */
1087             case WhiteMarshall:
1088             case BlackMarshall:
1089                 Rook(board, flags, rf, ff, callback, closure);
1090                 if(gameInfo.variant == VariantSpartan) // in Spartan Chess Chancellor is used for Dragon King.
1091                     Ferz(board, flags, rf, ff, callback, closure);
1092                 else
1093                     Knight(board, flags, rf, ff, callback, closure);
1094                 break;
1095
1096             /* Shogi Rooks are ordinary Rooks */
1097             case SHOGI WhiteRook:
1098             case SHOGI BlackRook:
1099             case SHOGI WhitePRook:
1100             case SHOGI BlackPRook:
1101             case WhiteRook:
1102             case BlackRook:
1103                 Rook(board, flags, rf, ff, callback, closure);
1104                 break;
1105
1106             case WhiteQueen:
1107             case BlackQueen:
1108             case SHOGI WhiteMother:
1109             case SHOGI BlackMother:
1110             doQueen:
1111                 Rook(board, flags, rf, ff, callback, closure);
1112                 Bishop(board, flags, rf, ff, callback, closure);
1113                 break;
1114
1115            case SHOGI WhitePawn:
1116                 StepForward(board, flags, rf, ff, callback, closure);
1117                 break;
1118
1119             case SHOGI BlackPawn:
1120                 StepBackward(board, flags, rf, ff, callback, closure);
1121                 break;
1122
1123             case WhiteMan:
1124                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
1125             case SHOGI WhiteFerz:
1126                 Ferz(board, flags, rf, ff, callback, closure);
1127                 StepForward(board, flags, rf, ff, callback, closure);
1128                 break;
1129
1130             case BlackMan:
1131                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
1132             case SHOGI BlackFerz:
1133                 StepBackward(board, flags, rf, ff, callback, closure);
1134
1135             case WhiteFerz:
1136             case BlackFerz:
1137                 /* [HGM] support Shatranj pieces */
1138                 Ferz(board, flags, rf, ff, callback, closure);
1139                 break;
1140
1141             case WhiteSilver:
1142             case BlackSilver:
1143                 Knight(board, flags, rf, ff, callback, closure); // [HGM] superchess: use for Centaur
1144
1145             commoner:
1146             case SHOGI WhiteMonarch:
1147             case SHOGI BlackMonarch:
1148             case SHOGI WhiteKing:
1149             case SHOGI BlackKing:
1150             case WhiteKing:
1151             case BlackKing:
1152                 Ferz(board, flags, rf, ff, callback, closure);
1153                 Wazir(board, flags, rf, ff, callback, closure);
1154                 break;
1155
1156             case WhiteNightrider:
1157             case BlackNightrider:
1158               for (i = -1; i <= 1; i += 2)
1159                 for (j = -1; j <= 1; j += 2)
1160                   for (s = 1; s <= 2; s++) {  int k;
1161                     for(k=1;; k++) {
1162                       rt = rf + k*i*s;
1163                       ft = ff + k*j*(3-s);
1164                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
1165                       if (SameColor(board[rf][ff], board[rt][ft])) break;
1166                       callback(board, flags, NormalMove,
1167                                rf, ff, rt, ft, closure);
1168                       if (board[rt][ft] != EmptySquare) break;
1169                     }
1170                   }
1171               break;
1172
1173             Amazon:
1174                 Bishop(board, flags, rf, ff, callback, closure);
1175                 Rook(board, flags, rf, ff, callback, closure);
1176                 Knight(board, flags, rf, ff, callback, closure);
1177                 break;
1178
1179             // Use Lance as Berolina / Spartan Pawn.
1180             case WhiteLance:
1181               if(gameInfo.variant == VariantSuper) goto Amazon;
1182               if (rf < BOARD_HEIGHT-1 && BlackPiece(board[rf + 1][ff]))
1183                   callback(board, flags,
1184                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
1185                            rf, ff, rf + 1, ff, closure);
1186               for (s = -1; s <= 1; s += 2) {
1187                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf + 1][ff + s] == EmptySquare)
1188                       callback(board, flags,
1189                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
1190                                rf, ff, rf + 1, ff + s, closure);
1191                   if (rf == 1 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[3][ff + 2*s] == EmptySquare )
1192                       callback(board, flags, NormalMove, rf, ff, 3, ff + 2*s, closure);
1193               }
1194               break;
1195
1196             case BlackLance:
1197               if(gameInfo.variant == VariantSuper) goto Amazon;
1198               if (rf > 0 && WhitePiece(board[rf - 1][ff]))
1199                   callback(board, flags,
1200                            rf <= promoRank ? BlackPromotion : NormalMove,
1201                            rf, ff, rf - 1, ff, closure);
1202               for (s = -1; s <= 1; s += 2) {
1203                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf - 1][ff + s] == EmptySquare)
1204                       callback(board, flags,
1205                                rf <= promoRank ? BlackPromotion : NormalMove,
1206                                rf, ff, rf - 1, ff + s, closure);
1207                   if (rf == BOARD_HEIGHT-2 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[rf-2][ff + 2*s] == EmptySquare )
1208                       callback(board, flags, NormalMove, rf, ff, rf-2, ff + 2*s, closure);
1209               }
1210             break;
1211
1212             case SHOGI WhiteNothing:
1213             case SHOGI BlackNothing:
1214             case SHOGI WhiteLion:
1215             case SHOGI BlackLion:
1216             case WhiteLion:
1217             case BlackLion:
1218               for(rt = rf - 2; rt <= rf + 2; rt++) for(ft = ff - 2; ft <= ff + 2; ft++) {
1219                 if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
1220                 if (!(ff == ft && rf == rt) && SameColor(board[rf][ff], board[rt][ft])) continue;
1221                 i = (killX >= 0 && (rt-killY)*(rt-killY) + (killX-ft)*(killX-ft) < 3); legNr += 2*i;
1222                 callback(board, flags, (rt-rf)*(rt-rf) + (ff-ft)*(ff-ft) < 3 && board[rt][ft] != EmptySquare ? FirstLeg : NormalMove,
1223                          rf, ff, rt, ft, closure);
1224                 legNr -= 2*i;
1225               }
1226               break;
1227
1228             case SHOGI WhiteFalcon:
1229             case SHOGI BlackFalcon:
1230             case SHOGI WhitePDagger:
1231             case SHOGI BlackPDagger:
1232                 SlideSideways(board, flags, rf, ff, callback, closure);
1233                 StepVertical(board, flags, rf, ff, callback, closure);
1234                 break;
1235
1236             case SHOGI WhiteCobra:
1237             case SHOGI BlackCobra:
1238                 StepVertical(board, flags, rf, ff, callback, closure);
1239                 break;
1240
1241             case SHOGI (PROMO WhiteFerz):
1242                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
1243             case SHOGI (PROMO BlackFerz):
1244                 if(gameInfo.variant == VariantShogi) goto BlackGold;
1245             case SHOGI WhitePSword:
1246             case SHOGI BlackPSword:
1247                 SlideVertical(board, flags, rf, ff, callback, closure);
1248                 StepSideways(board, flags, rf, ff, callback, closure);
1249                 break;
1250
1251             case SHOGI WhiteUnicorn:
1252             case SHOGI BlackUnicorn:
1253                 Ferz(board, flags, rf, ff, callback, closure);
1254                 StepVertical(board, flags, rf, ff, callback, closure);
1255                 break;
1256
1257             case SHOGI WhiteMan:
1258                 StepDiagForward(board, flags, rf, ff, callback, closure);
1259                 StepVertical(board, flags, rf, ff, callback, closure);
1260                 break;
1261
1262             case SHOGI BlackMan:
1263                 StepDiagBackward(board, flags, rf, ff, callback, closure);
1264                 StepVertical(board, flags, rf, ff, callback, closure);
1265                 break;
1266
1267             case SHOGI WhiteHCrown:
1268             case SHOGI BlackHCrown:
1269                 Bishop(board, flags, rf, ff, callback, closure);
1270                 SlideSideways(board, flags, rf, ff, callback, closure);
1271                 break;
1272
1273             case SHOGI WhiteCrown:
1274             case SHOGI BlackCrown:
1275                 Bishop(board, flags, rf, ff, callback, closure);
1276                 SlideVertical(board, flags, rf, ff, callback, closure);
1277                 break;
1278
1279             case SHOGI WhiteHorned:
1280                 Sting(board, flags, rf, ff, 1, 0, callback, closure);
1281                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1282                 if(killX >= 0) break;
1283                 Bishop(board, flags, rf, ff, callback, closure);
1284                 SlideSideways(board, flags, rf, ff, callback, closure);
1285                 SlideBackward(board, flags, rf, ff, callback, closure);
1286                 break;
1287
1288             case SHOGI BlackHorned:
1289                 Sting(board, flags, rf, ff, -1, 0, callback, closure);
1290                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1291                 if(killX >= 0) break;
1292                 Bishop(board, flags, rf, ff, callback, closure);
1293                 SlideSideways(board, flags, rf, ff, callback, closure);
1294                 SlideForward(board, flags, rf, ff, callback, closure);
1295                 break;
1296
1297             case SHOGI WhiteEagle:
1298                 Sting(board, flags, rf, ff, 1,  1, callback, closure);
1299                 Sting(board, flags, rf, ff, 1, -1, callback, closure);
1300                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1301                 if(killX >= 0) break;
1302                 Rook(board, flags, rf, ff, callback, closure);
1303                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
1304                 break;
1305
1306             case SHOGI BlackEagle:
1307                 Sting(board, flags, rf, ff, -1,  1, callback, closure);
1308                 Sting(board, flags, rf, ff, -1, -1, callback, closure);
1309                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1310                 if(killX >= 0) break;
1311                 Rook(board, flags, rf, ff, callback, closure);
1312                 SlideDiagForward(board, flags, rf, ff, callback, closure);
1313                 break;
1314
1315             case SHOGI WhiteDolphin:
1316             case SHOGI BlackHorse:
1317                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
1318                 SlideVertical(board, flags, rf, ff, callback, closure);
1319                 break;
1320
1321             case SHOGI BlackDolphin:
1322             case SHOGI WhiteHorse:
1323                 SlideDiagForward(board, flags, rf, ff, callback, closure);
1324                 SlideVertical(board, flags, rf, ff, callback, closure);
1325                 break;
1326
1327             case SHOGI WhiteLance:
1328                 SlideForward(board, flags, rf, ff, callback, closure);
1329                 break;
1330
1331             case SHOGI BlackLance:
1332                 SlideBackward(board, flags, rf, ff, callback, closure);
1333                 break;
1334
1335             case WhiteFalcon: // [HGM] wild: for wildcards, self-capture symbolizes move to anywhere
1336             case BlackFalcon:
1337             case WhiteCobra:
1338             case BlackCobra:
1339               callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1340               break;
1341
1342           }
1343       }
1344 }
1345
1346
1347 typedef struct {
1348     MoveCallback cb;
1349     VOIDSTAR cl;
1350 } GenLegalClosure;
1351
1352 int rFilter, fFilter; // [HGM] speed: sorry, but I get a bit tired of this closure madness
1353 Board xqCheckers, nullBoard;
1354
1355 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
1356                                 int rf, int ff, int rt, int ft,
1357                                 VOIDSTAR closure));
1358
1359 void
1360 GenLegalCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1361 {
1362     register GenLegalClosure *cl = (GenLegalClosure *) closure;
1363
1364     if(rFilter >= 0 && rFilter != rt || fFilter >= 0 && fFilter != ft) return; // [HGM] speed: ignore moves with wrong to-square
1365
1366     if (board[EP_STATUS] == EP_IRON_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)) return; //[HGM] lion
1367
1368     if (!(flags & F_IGNORE_CHECK) ) {
1369       int check, promo = (gameInfo.variant == VariantSpartan && kind == BlackPromotion);
1370       if(promo) {
1371             int r, f, kings=0;
1372             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT;       f++)
1373                 kings += (board[r][f] == BlackKing);
1374             if(kings >= 2)
1375               promo = 0;
1376             else
1377                 board[rf][ff] = BlackKing; // [HGM] spartan: promote to King before check-test
1378         }
1379         check = CheckTest(board, flags, rf, ff, rt, ft,
1380                   kind == WhiteCapturesEnPassant ||
1381                   kind == BlackCapturesEnPassant);
1382         if(promo) board[rf][ff] = BlackLance;
1383       if(check) return;
1384     }
1385     if (flags & F_ATOMIC_CAPTURE) {
1386       if (board[rt][ft] != EmptySquare ||
1387           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
1388         int r, f;
1389         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
1390         if (board[rf][ff] == king) return;
1391         for (r = rt-1; r <= rt+1; r++) {
1392           for (f = ft-1; f <= ft+1; f++) {
1393             if (r >= 0 && r < BOARD_HEIGHT && f >= BOARD_LEFT && f < BOARD_RGHT &&
1394                 board[r][f] == king) return;
1395           }
1396         }
1397       }
1398     }
1399     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
1400 }
1401
1402
1403 typedef struct {
1404     int rf, ff, rt, ft;
1405     ChessMove kind;
1406     int captures; // [HGM] losers
1407 } LegalityTestClosure;
1408
1409
1410 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
1411    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
1412    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
1413    moves that would destroy your own king.  The CASTLE_OK flags are
1414    true if castling is not yet ruled out by a move of the king or
1415    rook.  Return TRUE if the player on move is currently in check and
1416    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
1417 int
1418 GenLegal (Board board, int  flags, MoveCallback callback, VOIDSTAR closure, ChessSquare filter)
1419 {
1420     GenLegalClosure cl;
1421     int ff, ft, k, left, right, swap;
1422     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
1423     ChessSquare wKing = WhiteKing, bKing = BlackKing, *castlingRights = board[CASTLING];
1424     int inCheck = !ignoreCheck && CheckTest(board, flags, -1, -1, -1, -1, FALSE); // kludge alert: this would mark pre-existing checkers if status==1
1425     char *p;
1426
1427     cl.cb = callback;
1428     cl.cl = closure;
1429     xqCheckers[EP_STATUS] *= 2; // quasi: if previous CheckTest has been marking, we now set flag for suspending same checkers
1430     if(filter == EmptySquare) rFilter = fFilter = -1; // [HGM] speed: do not filter on square if we do not filter on piece
1431     GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl, filter);
1432
1433     if (inCheck) return TRUE;
1434
1435     /* Generate castling moves */
1436     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
1437         wKing = WhiteUnicorn; bKing = BlackUnicorn;
1438     }
1439
1440     p = (flags & F_WHITE_ON_MOVE ? pieceDesc[wKing] : pieceDesc[bKing]);
1441     if(p && strchr(p, 'O')) return FALSE; // [HGM] gen: castlings were already generated from string
1442
1443     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
1444         if ((flags & F_WHITE_ON_MOVE) &&
1445             (flags & F_WHITE_KCASTLE_OK) &&
1446             board[0][ff] == wKing &&
1447             board[0][ff + 1] == EmptySquare &&
1448             board[0][ff + 2] == EmptySquare &&
1449             board[0][BOARD_RGHT-3] == EmptySquare &&
1450             board[0][BOARD_RGHT-2] == EmptySquare &&
1451             board[0][BOARD_RGHT-1] == WhiteRook &&
1452             castlingRights[0] != NoRights && /* [HGM] check rights */
1453             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1454             (ignoreCheck ||
1455              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
1456               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
1457               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
1458               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
1459
1460             callback(board, flags,
1461                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
1462                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1463         }
1464         if ((flags & F_WHITE_ON_MOVE) &&
1465             (flags & F_WHITE_QCASTLE_OK) &&
1466             board[0][ff] == wKing &&
1467             board[0][ff - 1] == EmptySquare &&
1468             board[0][ff - 2] == EmptySquare &&
1469             board[0][BOARD_LEFT+2] == EmptySquare &&
1470             board[0][BOARD_LEFT+1] == EmptySquare &&
1471             board[0][BOARD_LEFT+0] == WhiteRook &&
1472             castlingRights[1] != NoRights && /* [HGM] check rights */
1473             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1474             (ignoreCheck ||
1475              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
1476               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
1477               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
1478
1479             callback(board, flags,
1480                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
1481                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
1482         }
1483         if (!(flags & F_WHITE_ON_MOVE) &&
1484             (flags & F_BLACK_KCASTLE_OK) &&
1485             board[BOARD_HEIGHT-1][ff] == bKing &&
1486             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
1487             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
1488             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
1489             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
1490             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
1491             castlingRights[3] != NoRights && /* [HGM] check rights */
1492             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1493             (ignoreCheck ||
1494              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
1495               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
1496               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
1497               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
1498
1499             callback(board, flags,
1500                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
1501                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1502         }
1503         if (!(flags & F_WHITE_ON_MOVE) &&
1504             (flags & F_BLACK_QCASTLE_OK) &&
1505             board[BOARD_HEIGHT-1][ff] == bKing &&
1506             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
1507             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
1508             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
1509             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
1510             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
1511             castlingRights[4] != NoRights && /* [HGM] check rights */
1512             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1513             (ignoreCheck ||
1514              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
1515               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
1516               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
1517
1518             callback(board, flags,
1519                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
1520                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
1521         }
1522     }
1523
1524   if((swap = gameInfo.variant == VariantSChess) || flags & F_FRC_TYPE_CASTLING) {
1525
1526     /* generate all potential FRC castling moves (KxR), ignoring flags */
1527     /* [HGM] test if the Rooks we find have castling rights */
1528     /* In S-Chess we generate RxK for allowed castlings, for gating at Rook square */
1529
1530
1531     if ((flags & F_WHITE_ON_MOVE) != 0) {
1532         ff = castlingRights[2]; /* King file if we have any rights */
1533         if(ff != NoRights && board[0][ff] == WhiteKing) {
1534     if (appData.debugMode) {
1535         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
1536                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
1537     }
1538             ft = castlingRights[0]; /* Rook file if we have H-side rights */
1539             left  = ff+1;
1540             right = BOARD_RGHT-2;
1541             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1542             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1543                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1544             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1545                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1546             if(ft != NoRights && board[0][ft] == WhiteRook) {
1547                 if(flags & F_FRC_TYPE_CASTLING) callback(board, flags, WhiteHSideCastleFR, 0, ff, 0, ft, closure);
1548                 if(swap)                        callback(board, flags, WhiteHSideCastleFR, 0, ft, 0, ff, closure);
1549             }
1550
1551             ft = castlingRights[1]; /* Rook file if we have A-side rights */
1552             left  = BOARD_LEFT+2;
1553             right = ff-1;
1554             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1555             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1556                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1557             if(ft == 0 && ff != 1 && board[0][1] != EmptySquare) ft = NoRights; /* Rook can be blocked on b1 */
1558             if(ff > BOARD_LEFT+2)
1559             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1560                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1561             if(ft != NoRights && board[0][ft] == WhiteRook) {
1562                 if(flags & F_FRC_TYPE_CASTLING) callback(board, flags, WhiteASideCastleFR, 0, ff, 0, ft, closure);
1563                 if(swap)                        callback(board, flags, WhiteASideCastleFR, 0, ft, 0, ff, closure);
1564             }
1565         }
1566     } else {
1567         ff = castlingRights[5]; /* King file if we have any rights */
1568         if(ff != NoRights && board[BOARD_HEIGHT-1][ff] == BlackKing) {
1569             ft = castlingRights[3]; /* Rook file if we have H-side rights */
1570             left  = ff+1;
1571             right = BOARD_RGHT-2;
1572             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1573             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1574                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1575             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1576                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1577             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook) {
1578                 if(flags & F_FRC_TYPE_CASTLING) callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
1579                 if(swap)                        callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, ft, BOARD_HEIGHT-1, ff, closure);
1580             }
1581
1582             ft = castlingRights[4]; /* Rook file if we have A-side rights */
1583             left  = BOARD_LEFT+2;
1584             right = ff-1;
1585             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1586             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1587                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1588             if(ft == 0 && ff != 1 && board[BOARD_HEIGHT-1][1] != EmptySquare) ft = NoRights; /* Rook can be blocked on b8 */
1589             if(ff > BOARD_LEFT+2)
1590             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1591                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1592             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook) {
1593                 if(flags & F_FRC_TYPE_CASTLING) callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
1594                 if(swap)                        callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, ft, BOARD_HEIGHT-1, ff, closure);
1595             }
1596         }
1597     }
1598
1599   }
1600
1601     return FALSE;
1602 }
1603
1604
1605 typedef struct {
1606     int rking, fking;
1607     int check;
1608 } CheckTestClosure;
1609
1610
1611 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
1612                                  int rf, int ff, int rt, int ft,
1613                                  VOIDSTAR closure));
1614
1615
1616 void
1617 CheckTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1618 {
1619     register CheckTestClosure *cl = (CheckTestClosure *) closure;
1620
1621     if (rt == cl->rking && ft == cl->fking) {
1622         if(xqCheckers[EP_STATUS] >= 2 && xqCheckers[rf][ff]) return; // checker is piece with suspended checking power
1623         cl->check++;
1624         xqCheckers[rf][ff] = xqCheckers[EP_STATUS] & 1; // remember who is checking (if status == 1)
1625     }
1626     if( board[EP_STATUS] == EP_ROYAL_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)
1627         && (gameInfo.variant != VariantLion || board[rf][ff] != WhiteKing && board[rf][ff] != BlackKing) )
1628         cl->check++; // [HGM] lion: forbidden counterstrike against Lion equated to putting yourself in check
1629 }
1630
1631
1632 /* If the player on move were to move from (rf, ff) to (rt, ft), would
1633    he leave himself in check?  Or if rf == -1, is the player on move
1634    in check now?  enPassant must be TRUE if the indicated move is an
1635    e.p. capture.  The possibility of castling out of a check along the
1636    back rank is not accounted for (i.e., we still return nonzero), as
1637    this is illegal anyway.  Return value is the number of times the
1638    king is in check. */
1639 int
1640 CheckTest (Board board, int flags, int rf, int ff, int rt, int ft, int enPassant)
1641 {
1642     CheckTestClosure cl;
1643     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1644     ChessSquare captured = EmptySquare, ep=0, trampled=0;
1645     int saveKill = killX;
1646     /*  Suppress warnings on uninitialized variables    */
1647
1648     if(gameInfo.variant == VariantXiangqi)
1649         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
1650     if(gameInfo.variant == VariantKnightmate)
1651         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
1652     if(gameInfo.variant == VariantChu || gameInfo.variant == VariantShogi) { // strictly speaking this is not needed, as Chu officially has no check
1653         int r, f, k = king, royals=0, prince = flags & F_WHITE_ON_MOVE ? WhiteMonarch : BlackMonarch;
1654         if(gameInfo.variant == VariantShogi) prince -= 11;                   // White/BlackFalcon
1655         for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1656             if(board[r][f] == k || board[r][f] == prince) {
1657                 if(++royals > 1) return FALSE; // no check if we have two royals (ignores double captureby Lion!)
1658                 king = board[r][f]; // remember hich one we had
1659             }
1660         }
1661     }
1662
1663     if (rt >= 0) {
1664         if (enPassant) {
1665             captured = board[rf][ft];
1666             board[rf][ft] = EmptySquare;
1667         } else {
1668             captured = board[rt][ft];
1669             if(killX >= 0) { trampled = board[killY][killX]; board[killY][killX] = EmptySquare; killX = -1; }
1670         }
1671         if(rf == DROP_RANK) board[rt][ft] = ff; else { // [HGM] drop
1672             board[rt][ft] = board[rf][ff];
1673             if(rf != rt || ff != ft) board[rf][ff] = EmptySquare;
1674         }
1675         ep = board[EP_STATUS];
1676         if( captured == WhiteLion || captured == BlackLion ) { // [HGM] lion: Chu Lion-capture rules
1677             ChessSquare victim = saveKill < 0 ? EmptySquare : trampled;
1678             if( (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion) &&           // capturer is Lion
1679                 (ff - ft > 1 || ft - ff > 1 || rf - rt > 1 || rt - rf > 1) &&           // captures from a distance
1680                 (victim == EmptySquare || victim == WhitePawn || victim == BlackPawn    // no or worthless 'bridge'
1681                                      || victim == WhiteCobra || victim == BlackCobra) ) // (Pawn or Go Between)
1682                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1683         }
1684     }
1685
1686     /* For compatibility with ICS wild 9, we scan the board in the
1687        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1688        and we test only whether that one is in check. */
1689     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1690         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1691           if (board[cl.rking][cl.fking] == king) {
1692               cl.check = 0;
1693               if(gameInfo.variant == VariantXiangqi) {
1694                   /* [HGM] In Xiangqi opposing Kings means check as well */
1695                   int i, dir;
1696                   dir = (king >= BlackPawn) ? -1 : 1;
1697                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1698                                 board[i][cl.fking] == EmptySquare; i+=dir );
1699                   if(i>=0 && i<BOARD_HEIGHT &&
1700                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1701                           cl.check++;
1702               }
1703               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1704               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1705                  goto undo_move;  /* 2-level break */
1706           }
1707       }
1708
1709   undo_move:
1710
1711     if (rt >= 0) {
1712         if(rf != DROP_RANK) // [HGM] drop
1713             board[rf][ff] = board[rt][ft];
1714         if (enPassant) {
1715             board[rf][ft] = captured;
1716             board[rt][ft] = EmptySquare;
1717         } else {
1718             if(saveKill >= 0) board[killY][killX = saveKill] = trampled;
1719             board[rt][ft] = captured;
1720         }
1721         board[EP_STATUS] = ep;
1722     }
1723
1724     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1725 }
1726
1727 int
1728 HasLion (Board board, int flags)
1729 {
1730     int lion = F_WHITE_ON_MOVE & flags ? WhiteLion : BlackLion;
1731     int r, f;
1732     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1733         if(board[r][f] == lion) return 1;
1734     return 0;
1735 }
1736
1737 ChessMove
1738 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1739 {   // [HGM] put drop legality testing in separate routine for clarity
1740     int n;
1741 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1742     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1743     n = PieceToNumber(piece);
1744     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1745         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1746         return ImpossibleMove; // piece not available
1747     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1748         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1749            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1750             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1751             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1752         if(piece == WhitePawn || piece == BlackPawn) {
1753             int r, max = 1 + (BOARD_HEIGHT == 7); // two Pawns per file in Tori!
1754             for(r=1; r<BOARD_HEIGHT-1; r++)
1755                 if(!(max -= (board[r][ft] == piece))) return IllegalMove; // or there already is a Pawn in file
1756             // should still test if we mate with this Pawn
1757         }
1758     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1759         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1760     } else {
1761         if( (piece == WhitePawn || piece == BlackPawn) &&
1762             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1763             return IllegalMove; /* no pawn drops on 1st/8th */
1764     }
1765 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1766     if (!(flags & F_IGNORE_CHECK) &&
1767         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1768     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1769 }
1770
1771 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1772                                     int rf, int ff, int rt, int ft,
1773                                     VOIDSTAR closure));
1774
1775 void
1776 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1777 {
1778     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1779
1780     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1781         cl->captures++; // [HGM] losers: count legal captures
1782     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1783       cl->kind = kind;
1784 }
1785
1786 ChessMove
1787 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1788 {
1789     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1790
1791     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1792     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1793     piece = filterPiece = board[rf][ff];
1794     if(PieceToChar(piece) == '~') filterPiece = DEMOTED(piece);
1795
1796     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1797     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1798     if((piece == WhiteFalcon || piece == BlackFalcon ||
1799         piece == WhiteCobra  || piece == BlackCobra) && gameInfo.variant != VariantChu && !pieceDesc[piece])
1800         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1801
1802     cl.rf = rf;
1803     cl.ff = ff;
1804     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1805     cl.ft = fFilter = ft;
1806     cl.kind = IllegalMove;
1807     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1808     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1809     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1810     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1811                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1812         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1813
1814     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1815     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1816         if(board[rf][ff] < BlackPawn) { // white
1817             if(rf != 0) return IllegalMove; // must be on back rank
1818             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1819             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1820             if(cl.kind == WhiteHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1821             if(cl.kind == WhiteASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1822         } else {
1823             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1824             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1825             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1826             if(cl.kind == BlackHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1827             if(cl.kind == BlackASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1828         }
1829     } else
1830     if(gameInfo.variant == VariantChu) {
1831         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1832         if(promoChar != '+')
1833             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1834         if(PieceToChar(CHUPROMOTED(board[rf][ff])) != '+') {
1835             if(PieceToChar(CHUPROMOTED (board[rf][ff] < BlackPawn ? WhitePawn : BlackPawn)) != '.')
1836             return ImpossibleMove;
1837         }
1838         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1839     } else
1840     if(gameInfo.variant == VariantShogi) {
1841         /* [HGM] Shogi promotions. '=' means defer */
1842         if(rf != DROP_RANK && cl.kind == NormalMove) {
1843             ChessSquare piece = board[rf][ff];
1844             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
1845
1846             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1847             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1848                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1849                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1850                   promoChar = '+'; // allowed ICS notations
1851 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1852             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1853                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1854             else if(flags & F_WHITE_ON_MOVE) {
1855                 if( (int) piece < (int) WhiteWazir &&
1856                      (rf >= BOARD_HEIGHT - zone || rt >= BOARD_HEIGHT - zone) ) {
1857                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1858                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1859                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1860                     else /* promotion optional, default is defer */
1861                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1862                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1863             } else {
1864                 if( (int) piece < (int) BlackWazir && (rf < zone || rt < zone) ) {
1865                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1866                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1867                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1868                     else /* promotion optional, default is defer */
1869                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1870                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1871             }
1872         }
1873     } else
1874     if (promoChar != NULLCHAR) {
1875         if(cl.kind == NormalMove && promoChar == '+') { // allow shogi-style promotion is pieceToChar specifies them
1876             ChessSquare piece = board[rf][ff];
1877             if(piece < BlackPawn ? piece > WhiteMan : piece > BlackMan) return ImpossibleMove; // already promoted
1878             // should test if in zone, really
1879             if(gameInfo.variant == VariantChuChess && (piece == WhiteKnight || piece == BlackKnight) && HasLion(board, flags))
1880                 return IllegalMove;
1881             if(PieceToChar(PROMOTED(piece)) == '+') return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1882         } else
1883         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1884         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1885             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1886             if(piece == EmptySquare)
1887                 cl.kind = ImpossibleMove; // non-existing piece
1888             if(gameInfo.variant == VariantChuChess && promoChar == 'l' && HasLion(board, flags)) {
1889                 cl.kind = IllegalMove; // no two Lions
1890             } else if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1891                 if(promoChar != PieceToChar(BlackKing)) {
1892                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1893                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1894                 } else { // promotion to King allowed only if we do not have two yet
1895                     int r, f, kings = 0;
1896                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1897                     if(kings == 2) cl.kind = IllegalMove;
1898                 }
1899             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1900                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1901             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1902              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1903             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1904              cl.kind = IllegalMove; // promotion to King usually not allowed
1905         } else {
1906             cl.kind = IllegalMove;
1907         }
1908     }
1909     return cl.kind;
1910 }
1911
1912 typedef struct {
1913     int count;
1914 } MateTestClosure;
1915
1916 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1917                                 int rf, int ff, int rt, int ft,
1918                                 VOIDSTAR closure));
1919
1920 void
1921 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1922 {
1923     register MateTestClosure *cl = (MateTestClosure *) closure;
1924
1925     cl->count++;
1926 }
1927
1928 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1929 int
1930 MateTest (Board board, int flags)
1931 {
1932     MateTestClosure cl;
1933     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1934     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1935
1936     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1937         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1938         nrKing += (board[r][f] == king);   // stm has king
1939         if( board[r][f] != EmptySquare ) {
1940             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1941                  myPieces++;
1942             else hisPieces++;
1943         }
1944     }
1945     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1946         case VariantShatranj:
1947                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1948         default:
1949                 break;
1950         case VariantAtomic:
1951                 if(nrKing == 0) return MT_NOKING;
1952                 break;
1953         case VariantLosers:
1954                 if(myPieces == 1) return MT_BARE;
1955     }
1956     cl.count = 0;
1957     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1958     // [HGM] 3check: yet to do!
1959     if (cl.count > 0) {
1960         return inCheck ? MT_CHECK : MT_NONE;
1961     } else {
1962         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1963                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1964             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1965             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1966                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1967                     if(board[n][holdings] != EmptySquare) {
1968                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1969                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1970                     }
1971         }
1972         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1973                 return myPieces == hisPieces ? MT_STALEMATE :
1974                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1975         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1976         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1977
1978         return inCheck ? MT_CHECKMATE
1979                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || IS_SHOGI(gameInfo.variant)) ?
1980                           MT_STAINMATE : MT_STALEMATE;
1981     }
1982 }
1983
1984
1985 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1986                                     int rf, int ff, int rt, int ft,
1987                                     VOIDSTAR closure));
1988
1989 void
1990 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1991 {
1992     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1993     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1994     extern int kifu; // in parser.c
1995
1996     // [HGM] wild: for wild-card pieces rt and rf are dummies
1997     if(piece == WhiteFalcon || piece == BlackFalcon ||
1998        piece == WhiteCobra  || piece == BlackCobra)
1999         wildCard = TRUE;
2000
2001     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
2002          || PieceToChar(board[rf][ff]) == '~'
2003               && cl->pieceIn == (ChessSquare)(DEMOTED(board[rf][ff]))
2004                                                                       ) &&
2005         (cl->rfIn == -1 || cl->rfIn == rf) &&
2006         (cl->ffIn == -1 || cl->ffIn == ff) &&
2007         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
2008         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
2009
2010         if(cl->count && rf == cl->rf && ff == cl->ff) return; // duplicate move
2011
2012         if(cl->count == 1 && kifu & 0x7E && cl->rfIn == -1 && cl->ffIn == -1) { // traditional Shogi disambiguation required
2013             int this = 1, other = 1;
2014             if(kifu & 2) this &= (flags & 1 ? rt > rf : rt < rf), other &= (flags & 1 ? cl->rt > cl->rf : cl->rt < cl->rf);
2015             if(kifu & 4) this &= (flags & 1 ? rt < rf : rt > rf), other &= (flags & 1 ? cl->rt < cl->rf : cl->rt > cl->rf);
2016             if(kifu & 8) this &= (rf == rt), other &= (cl->rt == cl->rf);
2017             if(kifu & 0x10) this &= (flags & 1 ? ft <= ff : ft >= ff), other &= (flags & 1 ? cl->ft <= cl->ff : cl->ft >= cl->ff);
2018             if(kifu & 0x20) this &= (flags & 1 ? ft >= ff : ft <= ff), other &= (flags & 1 ? cl->ft >= cl->ff : cl->ft <= cl->ff);
2019             if(kifu & 0x40) this &= (ft == ff), other &= (cl->ft == cl->ff); // should never be used
2020             if(!other) cl->count--; // the old move did not satisfy the requested relative position, erase it
2021             if(!this) return;       // the current move does not satisfy the requested relative position, ignore it
2022         }
2023
2024         cl->count++;
2025         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
2026           // [HGM] oneclick: if multiple moves, be sure we remember capture
2027           cl->piece = board[rf][ff];
2028           cl->rf = rf;
2029           cl->ff = ff;
2030           cl->rt = wildCard ? cl->rtIn : rt;
2031           cl->ft = wildCard ? cl->ftIn : ft;
2032           cl->kind = kind;
2033         }
2034         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
2035     }
2036 }
2037
2038 void
2039 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
2040 {
2041     int illegal = 0; char c = closure->promoCharIn;
2042
2043     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
2044     closure->count = closure->captures = 0;
2045     closure->rf = closure->ff = closure->rt = closure->ft = 0;
2046     closure->kind = ImpossibleMove;
2047     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
2048     fFilter = closure->ftIn;
2049     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
2050         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2051         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
2052             closure->count = closure->captures = 0;
2053             closure->rf = closure->ff = closure->rt = closure->ft = 0;
2054             closure->kind = ImpossibleMove;
2055             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2056         }
2057     } else
2058     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2059     if (closure->count == 0) {
2060         /* See if it's an illegal move due to check */
2061         illegal = 1;
2062         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2063         if (closure->count == 0) {
2064             /* No, it's not even that */
2065           if(!appData.testLegality && !pieceDefs && closure->pieceIn != EmptySquare) {
2066             int f, r; // if there is only a single piece of the requested type on the board, use that
2067             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
2068             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
2069                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
2070             if(closure->count > 1) illegal = 0; // ambiguous
2071           }
2072           if(closure->count == 0) {
2073             if (appData.debugMode) { int i, j;
2074                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
2075                     for(j=0; j<BOARD_WIDTH; j++)
2076                         fprintf(debugFP, "%3d", (int) board[i][j]);
2077                     fprintf(debugFP, "\n");
2078                 }
2079             }
2080             return;
2081           }
2082         }
2083     } else if(pieceDefs && closure->count > 1) { // [HGM] gen: move is ambiguous under engine-defined rules
2084         DisambiguateClosure spare = *closure;
2085         pieceDefs = FALSE; spare.count = 0;     // See if the (erroneous) built-in rules would resolve that
2086         GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) &spare, closure->pieceIn);
2087         if(spare.count == 1) *closure = spare;  // It does, so use those in stead (game from file saved before gen patch?)
2088         pieceDefs = TRUE;
2089     }
2090
2091     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
2092     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
2093         if(closure->piece < BlackPawn) { // white
2094             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
2095             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
2096             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
2097             if(closure->kind == WhiteHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2098             if(closure->kind == WhiteASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2099         } else {
2100             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
2101             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
2102             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
2103             if(closure->kind == BlackHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2104             if(closure->kind == BlackASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2105         }
2106     } else
2107     if(gameInfo.variant == VariantChu) {
2108         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
2109     } else
2110     if(gameInfo.variant == VariantShogi) {
2111         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
2112         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
2113             ChessSquare piece = closure->piece;
2114             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
2115             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
2116                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
2117                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
2118                    c = '+'; // allowed ICS notations
2119             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
2120             else if(flags & F_WHITE_ON_MOVE) {
2121                 if( (int) piece < (int) WhiteWazir &&
2122                      (closure->rf >= BOARD_HEIGHT-zone || closure->rt >= BOARD_HEIGHT-zone) ) {
2123                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
2124                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
2125                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
2126                     else /* promotion optional, default is defer */
2127                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
2128                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2129             } else {
2130                 if( (int) piece < (int) BlackWazir && (closure->rf < zone || closure->rt < zone) ) {
2131                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
2132                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
2133                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
2134                     else /* promotion optional, default is defer */
2135                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
2136                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2137             }
2138         }
2139         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
2140         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
2141     } else
2142     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
2143         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
2144             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
2145                gameInfo.variant == VariantMakruk)
2146                 c = PieceToChar(BlackFerz);
2147             else if(gameInfo.variant == VariantASEAN)
2148                 c = PieceToChar(BlackRook);
2149             else if(gameInfo.variant == VariantGreat)
2150                 c = PieceToChar(BlackMan);
2151             else if(gameInfo.variant == VariantGrand)
2152                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
2153             else
2154                 c = PieceToChar(BlackQueen);
2155         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
2156         else if(c == 'l' && gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2157     } else if (c == '+') { // '+' outside shogi, check if pieceToCharTable enabled it
2158         ChessSquare p = closure->piece;
2159         if(p > WhiteMan && p < BlackPawn || p > BlackMan || PieceToChar(PROMOTED(p)) != '+')
2160             closure->kind = ImpossibleMove; // used on non-promotable piece
2161         else if(gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2162     } else if (c != NULLCHAR) closure->kind = IllegalMove;
2163
2164     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
2165     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
2166         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
2167     if (closure->count > 1) {
2168         closure->kind = AmbiguousMove;
2169     }
2170     if (illegal) {
2171         /* Note: If more than one illegal move matches, but no legal
2172            moves, we return IllegalMove, not AmbiguousMove.  Caller
2173            can look at closure->count to detect this.
2174         */
2175         closure->kind = IllegalMove;
2176     }
2177 }
2178
2179
2180 typedef struct {
2181     /* Input */
2182     ChessSquare piece;
2183     int rf, ff, rt, ft;
2184     /* Output */
2185     ChessMove kind;
2186     int rank;
2187     int file;
2188     int either;
2189 } CoordsToAlgebraicClosure;
2190
2191 extern void CoordsToAlgebraicCallback P((Board board, int flags,
2192                                          ChessMove kind, int rf, int ff,
2193                                          int rt, int ft, VOIDSTAR closure));
2194
2195 void
2196 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2197 {
2198     register CoordsToAlgebraicClosure *cl =
2199       (CoordsToAlgebraicClosure *) closure;
2200
2201     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
2202         (board[rf][ff] == cl->piece
2203          || PieceToChar(board[rf][ff]) == '~' &&
2204             (ChessSquare) (DEMOTED(board[rf][ff])) == cl->piece)
2205                                      ) {
2206         if (rf == cl->rf) {
2207             if (ff == cl->ff) {
2208                 cl->kind = kind; /* this is the move we want */
2209             } else {
2210                 cl->file++; /* need file to rule out this move */
2211             }
2212         } else {
2213             if (ff == cl->ff) {
2214                 cl->rank++; /* need rank to rule out this move */
2215             } else {
2216                 cl->either++; /* rank or file will rule out this move */
2217             }
2218         }
2219     }
2220 }
2221
2222 /* Convert coordinates to normal algebraic notation.
2223    promoChar must be NULLCHAR or 'x' if not a promotion.
2224 */
2225 ChessMove
2226 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
2227 {
2228     ChessSquare piece;
2229     ChessMove kind;
2230     char *outp = out, c, capture;
2231     CoordsToAlgebraicClosure cl;
2232
2233     if (rf == DROP_RANK) {
2234         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
2235         /* Bughouse piece drop */
2236         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
2237         *outp++ = '@';
2238         *outp++ = ft + AAA;
2239         if(rt+ONE <= '9')
2240            *outp++ = rt + ONE;
2241         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2242         *outp = NULLCHAR;
2243         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
2244     }
2245
2246     if (promoChar == 'x') promoChar = NULLCHAR;
2247     piece = board[rf][ff];
2248     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED(piece));
2249
2250     switch (piece) {
2251       case WhitePawn:
2252       case BlackPawn:
2253         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2254         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2255             /* Keep short notation if move is illegal only because it
2256                leaves the player in check, but still return IllegalMove */
2257             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
2258             if (kind == IllegalMove) break;
2259             kind = IllegalMove;
2260         }
2261         /* Pawn move */
2262         *outp++ = ff + AAA;
2263         capture = board[rt][ft] != EmptySquare || kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant;
2264         if (ff == ft && !capture) { /* [HGM] Xiangqi has straight noncapts! */
2265             /* Non-capture; use style "e5" */
2266             if(rt+ONE <= '9')
2267                *outp++ = rt + ONE;
2268             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2269         } else {
2270             /* Capture; use style "exd5" */
2271             if(capture)
2272             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
2273             *outp++ = ft + AAA;
2274             if(rt+ONE <= '9')
2275                *outp++ = rt + ONE;
2276             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2277         }
2278         /* Use promotion suffix style "=Q" */
2279         *outp = NULLCHAR;
2280         if (promoChar != NULLCHAR) {
2281             if(IS_SHOGI(gameInfo.variant)) {
2282                 /* [HGM] ... but not in Shogi! */
2283                 *outp++ = promoChar == '=' ? '=' : '+';
2284             } else {
2285                 *outp++ = '=';
2286                 *outp++ = ToUpper(promoChar);
2287             }
2288             *outp = NULLCHAR;
2289         }
2290         return kind;
2291
2292
2293       case WhiteKing:
2294       case BlackKing:
2295         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
2296         /* Code added by Tord:  FRC castling. */
2297         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
2298            (piece == BlackKing && board[rt][ft] == BlackRook)) {
2299           if(ft > ff)
2300             safeStrCpy(out, "O-O", MOVE_LEN);
2301           else
2302             safeStrCpy(out, "O-O-O", MOVE_LEN);
2303           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2304         }
2305         /* End of code added by Tord */
2306         /* Test for castling or ICS wild castling */
2307         /* Use style "O-O" (oh-oh) for PGN compatibility */
2308         else if (rf == rt &&
2309             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
2310             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
2311             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
2312              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
2313             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
2314               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2315             else
2316               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2317
2318             /* This notation is always unambiguous, unless there are
2319                kings on both the d and e files, with "wild castling"
2320                possible for the king on the d file and normal castling
2321                possible for the other.  ICS rules for wild 9
2322                effectively make castling illegal for either king in
2323                this situation.  So I am not going to worry about it;
2324                I'll just generate an ambiguous O-O in this case.
2325             */
2326             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2327         }
2328
2329         /* else fall through */
2330       default:
2331         /* Piece move */
2332         cl.rf = rf;
2333         cl.ff = ff;
2334         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
2335         cl.ft = fFilter = ft;
2336         cl.piece = piece;
2337         cl.kind = IllegalMove;
2338         cl.rank = cl.file = cl.either = 0;
2339         c = PieceToChar(piece) ;
2340         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED(piece))); // [HGM] speed
2341
2342         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2343             /* Generate pretty moves for moving into check, but
2344                still return IllegalMove.
2345             */
2346             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED(piece)));
2347             if (cl.kind == IllegalMove) break;
2348             cl.kind = IllegalMove;
2349         }
2350
2351         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
2352            else "Ngf3" or "Ngxf7",
2353            else "N1f3" or "N5xf7",
2354            else "Ng1f3" or "Ng5xf7".
2355         */
2356         if( c == '~' || c == '+') {
2357            /* [HGM] print nonexistent piece as its demoted version */
2358            piece = (ChessSquare) (CHUDEMOTED(piece));
2359         }
2360         if(c=='+') *outp++ = c;
2361         *outp++ = ToUpper(PieceToChar(piece));
2362         if(*outp = PieceSuffix(piece)) outp++;
2363
2364         if (cl.file || (cl.either && !cl.rank)) {
2365             *outp++ = ff + AAA;
2366         }
2367         if (cl.rank) {
2368             if(rf+ONE <= '9')
2369                 *outp++ = rf + ONE;
2370             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2371         }
2372
2373         if(board[rt][ft] != EmptySquare)
2374           *outp++ = 'x';
2375
2376         *outp++ = ft + AAA;
2377         if(rt+ONE <= '9')
2378            *outp++ = rt + ONE;
2379         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2380         if (IS_SHOGI(gameInfo.variant)) {
2381             /* [HGM] in Shogi non-pawns can promote */
2382             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
2383         }
2384         else if (gameInfo.variant == VariantChuChess && promoChar ||
2385                  gameInfo.variant != VariantSuper && promoChar &&
2386                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
2387             *outp++ = '=';
2388             *outp++ = ToUpper(promoChar);
2389         }
2390         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
2391             *outp++ = '/';
2392             *outp++ = ToUpper(promoChar);
2393         }
2394         *outp = NULLCHAR;
2395         return cl.kind;
2396
2397       case EmptySquare:
2398         /* Moving a nonexistent piece */
2399         break;
2400     }
2401
2402     /* Not a legal move, even ignoring check.
2403        If there was a piece on the from square,
2404        use style "Ng1g3" or "Ng1xe8";
2405        if there was a pawn or nothing (!),
2406        use style "g1g3" or "g1xe8".  Use "x"
2407        if a piece was on the to square, even
2408        a piece of the same color.
2409     */
2410     outp = out;
2411     c = 0;
2412     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
2413         int r, f;
2414       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
2415                 c += (board[r][f] == piece); // count on-board pieces of given type
2416         *outp++ = ToUpper(PieceToChar(piece));
2417     }
2418   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2419     *outp++ = ff + AAA;
2420     if(rf+ONE <= '9')
2421        *outp++ = rf + ONE;
2422     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2423   }
2424     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2425     *outp++ = ft + AAA;
2426     if(rt+ONE <= '9')
2427        *outp++ = rt + ONE;
2428     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2429     /* Use promotion suffix style "=Q" */
2430     if (promoChar != NULLCHAR && promoChar != 'x') {
2431         *outp++ = '=';
2432         *outp++ = ToUpper(promoChar);
2433     }
2434     *outp = NULLCHAR;
2435
2436     return IllegalMove;
2437 }
2438
2439 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2440
2441 typedef struct {
2442     /* Input */
2443     int rf, ff, rt, ft;
2444     /* Output */
2445     int recaptures;
2446 } ChaseClosure;
2447
2448 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2449
2450 int preyStackPointer, chaseStackPointer;
2451
2452 struct {
2453 unsigned char rf, ff, rt, ft;
2454 } chaseStack[100];
2455
2456 struct {
2457 unsigned char rank, file;
2458 } preyStack[100];
2459
2460
2461
2462
2463 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2464
2465 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2466                                 int rf, int ff, int rt, int ft,
2467                                 VOIDSTAR closure));
2468
2469 void
2470 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2471 {   // For adding captures that can lead to chase indictment to the chaseStack
2472     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2473     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2474     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2475     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2476     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2477     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2478     chaseStack[chaseStackPointer].rf = rf;
2479     chaseStack[chaseStackPointer].ff = ff;
2480     chaseStack[chaseStackPointer].rt = rt;
2481     chaseStack[chaseStackPointer].ft = ft;
2482     chaseStackPointer++;
2483 }
2484
2485 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2486                                 int rf, int ff, int rt, int ft,
2487                                 VOIDSTAR closure));
2488
2489 void
2490 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2491 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2492     int i;
2493     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2494
2495     if(board[rt][ft] == EmptySquare) return; // no capture
2496     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2497         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2498     }
2499     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2500     for(i=0; i<chaseStackPointer; i++) {
2501         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2502            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2503             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2504             chaseStack[i] = chaseStack[--chaseStackPointer];
2505             break;
2506         }
2507     }
2508 }
2509
2510 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2511                                 int rf, int ff, int rt, int ft,
2512                                 VOIDSTAR closure));
2513
2514 void
2515 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2516 {   // for determining if a piece (given through the closure) is protected
2517     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2518
2519     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2520     if(appData.debugMode && board[rt][ft] != EmptySquare)
2521         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2522 }
2523
2524 extern char moveList[MAX_MOVES][MOVE_LEN];
2525
2526 int
2527 PerpetualChase (int first, int last)
2528 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2529     int i, j, k, tail;
2530     ChaseClosure cl;
2531     ChessSquare captured;
2532
2533     preyStackPointer = 0;        // clear stack of chased pieces
2534     for(i=first; i<last; i+=2) { // for all positions with same side to move
2535         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2536         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2537         // determine all captures possible after the move, and put them on chaseStack
2538         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2539         if(appData.debugMode) { int n;
2540             for(n=0; n<chaseStackPointer; n++)
2541                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2542                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2543             fprintf(debugFP, ": all capts\n");
2544         }
2545         // determine all captures possible before the move, and delete them from chaseStack
2546         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2547         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2548         cl.rt = moveList[i][3]-ONE;
2549         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2550         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2551         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2552         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2553         if(appData.debugMode) { int n;
2554             for(n=0; n<chaseStackPointer; n++)
2555                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2556                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2557             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2558         }
2559         // chaseSack now contains all captures made possible by the move
2560         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2561             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2562             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2563
2564             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2565             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2566
2567             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2568                 continue; // C or H attack on R is always chase; leave on chaseStack
2569
2570             if(attacker == victim) {
2571                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2572                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2573                         // we can capture back with equal piece, so this is no chase but a sacrifice
2574                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2575                         j--; /* ! */ continue;
2576                 }
2577
2578             }
2579
2580             // the attack is on a lower piece, or on a pinned or blocked equal one
2581             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2582             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2583             // test if the victim is protected by a true protector. First make the capture.
2584             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2585             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2586             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2587             // Then test if the opponent can recapture
2588             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2589             cl.rt = chaseStack[j].rt;
2590             cl.ft = chaseStack[j].ft;
2591             if(appData.debugMode) {
2592                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2593             }
2594             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2595             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2596             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2597             // unmake the capture
2598             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2599             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2600             // if a recapture was found, piece is protected, and we are not chasing it.
2601             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2602                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2603                 j--; /* ! */
2604             }
2605         }
2606         // chaseStack now contains all moves that chased
2607         if(appData.debugMode) { int n;
2608             for(n=0; n<chaseStackPointer; n++)
2609                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2610                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2611             fprintf(debugFP, ": chases\n");
2612         }
2613         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2614             for(j=0; j<chaseStackPointer; j++) {
2615                 preyStack[j].rank = chaseStack[j].rt;
2616                 preyStack[j].file = chaseStack[j].ft;
2617             }
2618             preyStackPointer = chaseStackPointer;
2619         }
2620         tail = 0;
2621         for(j=0; j<chaseStackPointer; j++) {
2622             for(k=0; k<preyStackPointer; k++) {
2623                 // search the victim of each chase move on the preyStack (first occurrence)
2624                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2625                     if(k < tail) break; // piece was already identified as still being chased
2626                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2627                     preyStack[tail] = preyStack[k];                // by swapping
2628                     preyStack[k] = preyStack[preyStackPointer];
2629                     tail++;
2630                     break;
2631                 }
2632             }
2633         }
2634         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2635         if(appData.debugMode) { int n;
2636             for(n=0; n<preyStackPointer; n++)
2637                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2638             fprintf(debugFP, "always chased upto ply %d\n", i);
2639         }
2640         // now adjust the location of the chased pieces according to opponent move
2641         for(j=0; j<preyStackPointer; j++) {
2642             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2643                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2644                 preyStack[j].rank = moveList[i+1][3]-ONE;
2645                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2646                 break;
2647             }
2648         }
2649     }
2650     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2651                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2652 }