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, 2016 Free
   9  * Software Foundation, Inc.
  10  *
  11  * Enhancements Copyright 2005 Alessandro Scotti
  12  *
  13  * The following terms apply to Digital Equipment Corporation's copyright
  14  * interest in XBoard:
  15  * ------------------------------------------------------------------------
  16  * All Rights Reserved
  17  *
  18  * Permission to use, copy, modify, and distribute this software and its
  19  * documentation for any purpose and without fee is hereby granted,
  20  * provided that the above copyright notice appear in all copies and that
  21  * both that copyright notice and this permission notice appear in
  22  * supporting documentation, and that the name of Digital not be
  23  * used in advertising or publicity pertaining to distribution of the
  24  * software without specific, written prior permission.
  25  *
  26  * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  27  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  28  * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  29  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  30  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  31  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  32  * SOFTWARE.
  33  * ------------------------------------------------------------------------
  34  *
  35  * The following terms apply to the enhanced version of XBoard
  36  * distributed by the Free Software Foundation:
  37  * ------------------------------------------------------------------------
  38  *
  39  * GNU XBoard is free software: you can redistribute it and/or modify
  40  * it under the terms of the GNU General Public License as published by
  41  * the Free Software Foundation, either version 3 of the License, or (at
  42  * your option) any later version.
  43  *
  44  * GNU XBoard is distributed in the hope that it will be useful, but
  45  * WITHOUT ANY WARRANTY; without even the implied warranty of
  46  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  47  * General Public License for more details.
  48  *
  49  * You should have received a copy of the GNU General Public License
  50  * along with this program. If not, see http://www.gnu.org/licenses/.  *
  51  *
  52  *------------------------------------------------------------------------
  53  ** See the file ChangeLog for a revision history.  */
  54
  55 #include "config.h"
  56
  57 #include <stdio.h>
  58 #include <ctype.h>
  59 #include <stdlib.h>
  60 #if HAVE_STRING_H
  61 # include <string.h>
  62 #else /* not HAVE_STRING_H */
  63 # include <strings.h>
  64 #endif /* not HAVE_STRING_H */
  65 #include "common.h"
  66 #include "backend.h"
  67 #include "moves.h"
  68 #include "parser.h"
  69
  70 int WhitePiece P((ChessSquare));
  71 int BlackPiece P((ChessSquare));
  72 int SameColor P((ChessSquare, ChessSquare));
  73 int PosFlags(int index);
  74
  75 extern signed char initialRights[BOARD_FILES]; /* [HGM] all rights enabled, set in InitPosition */
  76 int quickFlag;
  77 char *pieceDesc[EmptySquare];
  78 char *defaultDesc[EmptySquare] = {
  79  "fmWfceFifmnD", "N", "B", "R", "Q",
  80  "F", "A", "BN", "RN", "W", "K",
  81  "mRcpR", "N0", "BW", "RF", "gQ",
  82  "", "", "QN", "", "N", "",
  83  "", "", "", "", "",
  84  "", "", "", "", "", "",
  85  "", "", "", "", "",
  86  "", "", "", "", "", "K"
  87 };
  88
  89 int
  90 WhitePiece (ChessSquare piece)
  91 {
  92     return (int) piece >= (int) WhitePawn && (int) piece < (int) BlackPawn;
  93 }
  94
  95 int
  96 BlackPiece (ChessSquare piece)
  97 {
  98     return (int) piece >= (int) BlackPawn && (int) piece < (int) EmptySquare;
  99 }
 100
 101 #if 0
 102 int
 103 SameColor (ChessSquare piece1, ChessSquare piece2)
 104 {
 105     return ((int) piece1 >= (int) WhitePawn &&   /* [HGM] can be > King ! */
 106             (int) piece1 <  (int) BlackPawn &&
 107             (int) piece2 >= (int) WhitePawn &&
 108             (int) piece2 <  (int) BlackPawn)
 109       ||   ((int) piece1 >= (int) BlackPawn &&
 110             (int) piece1 <  (int) EmptySquare &&
 111             (int) piece2 >= (int) BlackPawn &&
 112             (int) piece2 <  (int) EmptySquare);
 113 }
 114 #else
 115 #define SameColor(piece1, piece2) (piece1 < EmptySquare && piece2 < EmptySquare && (piece1 < BlackPawn) == (piece2 < BlackPawn) || piece1 == DarkSquare || piece2 == DarkSquare)
 116 #endif
 117
 118 unsigned char pieceToChar[EmptySquare+1] = {
 119                         'P', 'N', 'B', 'R', 'Q', 'F', 'E', 'A', 'C', 'W', 'M',
 120                         'O', 'H', 'I', 'J', 'G', 'D', 'V', 'L', 'S', 'U', 'K',
 121                         'p', 'n', 'b', 'r', 'q', 'f', 'e', 'a', 'c', 'w', 'm',
 122                         'o', 'h', 'i', 'j', 'g', 'd', 'v', 'l', 's', 'u', 'k',
 123                         'x' };
 124 unsigned char pieceNickName[EmptySquare];
 125
 126 char
 127 PieceToChar (ChessSquare p)
 128 {
 129     int c;
 130     if((int)p < 0 || (int)p >= (int)EmptySquare) return('x'); /* [HGM] for safety */
 131     c = pieceToChar[(int) p];
 132     if(c & 128) c = c & 63 | 64;
 133     return c;
 134 }
 135
 136 char
 137 PieceSuffix (ChessSquare p)
 138 {
 139     int c;
 140     if((int)p < 0 || (int)p >= (int)EmptySquare) return 0; /* [HGM] for safety */
 141     c = pieceToChar[(int) p];
 142     if(c < 128) return 0;
 143     return SUFFIXES[c - 128 >> 6];
 144 }
 145
 146 int
 147 PieceToNumber (ChessSquare p)  /* [HGM] holdings: count piece type, ignoring non-participating piece types */
 148 {
 149     int i=0;
 150     ChessSquare start = (int)p >= (int)BlackPawn ? BlackPawn : WhitePawn;
 151
 152     while(start++ != p) if(pieceToChar[start-1] != '.' && pieceToChar[start-1] != '+') i++;
 153     return i;
 154 }
 155
 156 ChessSquare
 157 CharToPiece (int c)
 158 {
 159      int i;
 160      if(c == '.') return EmptySquare;
 161      for(i=0; i< (int) EmptySquare; i++)
 162           if(pieceNickName[i] == c) return (ChessSquare) i;
 163      for(i=0; i< (int) EmptySquare; i++)
 164           if(pieceToChar[i] == c) return (ChessSquare) i;
 165      return EmptySquare;
 166 }
 167
 168 void
 169 CopyBoard (Board to, Board from)
 170 {
 171     int i, j;
 172
 173     for (i = 0; i < BOARD_HEIGHT; i++)
 174       for (j = 0; j < BOARD_WIDTH; j++)
 175         to[i][j] = from[i][j];
 176     for (j = 0; j < BOARD_FILES; j++) // [HGM] gamestate: copy castling rights and ep status
 177         to[VIRGIN][j] = from[VIRGIN][j],
 178         to[CASTLING][j] = from[CASTLING][j];
 179     to[HOLDINGS_SET] = 0; // flag used in ICS play
 180 }
 181
 182 int
 183 CompareBoards (Board board1, Board board2)
 184 {
 185     int i, j;
 186
 187     for (i = 0; i < BOARD_HEIGHT; i++)
 188       for (j = 0; j < BOARD_WIDTH; j++) {
 189           if (board1[i][j] != board2[i][j])
 190             return FALSE;
 191     }
 192     return TRUE;
 193 }
 194
 195 char defaultName[] = "PNBRQ......................................K"  // white
 196                      "pnbrq......................................k"; // black
 197 char shogiName[]   = "PNBRLS...G.++++++..........................K"  // white
 198                      "pnbrls...g.++++++..........................k"; // black
 199 char xqName[]      = "PH.R.AE..K.C................................"  // white
 200                      "ph.r.ae..k.c................................"; // black
 201
 202 char *
 203 CollectPieceDescriptors ()
 204 {   // make a line of piece descriptions for use in the PGN Piece tag:
 205     // dump all engine defined pieces, and pieces with non-standard names,
 206     // but suppress black pieces that are the same as their white counterpart
 207     ChessSquare p;
 208     static char buf[MSG_SIZ];
 209     char *m, c, d, *pieceName = defaultName;
 210     int len;
 211     *buf = NULLCHAR;
 212     if(!pieceDefs) return "";
 213     if(gameInfo.variant == VariantChu) return ""; // for now don't do this for Chu Shogi
 214     if(gameInfo.variant == VariantShogi) pieceName = shogiName;
 215     if(gameInfo.variant == VariantXiangqi) pieceName = xqName;
 216     for(p=WhitePawn; p<EmptySquare; p++) {
 217         if((c = pieceToChar[p]) == '.' || c == '~') continue;  // does not participate
 218         m = pieceDesc[p]; d = (c == '+' ? pieceToChar[DEMOTED p] : c);
 219         if(p >= BlackPawn && pieceToChar[BLACK_TO_WHITE p] == toupper(c)
 220              && (c != '+' || pieceToChar[DEMOTED BLACK_TO_WHITE p] == d)) { // black member of normal pair
 221             char *wm = pieceDesc[BLACK_TO_WHITE p];
 222             if(!m && !wm || m && wm && !strcmp(wm, m)) continue;            // moves as a white piece
 223         } else                                                              // white or unpaired black
 224         if((p < BlackPawn || CharToPiece(toupper(d)) != EmptySquare) &&     // white or lone black
 225            !pieceDesc[p] /*&& pieceName[p] == c*/) continue; // orthodox piece known by its usual name
 226 // TODO: listing pieces because of unusual name can only be done if we have accurate Betza of all defaults
 227         if(!m) m = defaultDesc[p];
 228         len = strlen(buf);
 229         snprintf(buf+len, MSG_SIZ-len, "%s%s%c:%s", len ? ";" : "", c == '+' ? "+" : "", d, m);
 230     }
 231     return buf;
 232 }
 233
 234 // [HGM] gen: configurable move generation from Betza notation sent by engine.
 235 // Some notes about two-leg moves: GenPseudoLegal() works in two modes, depending on whether a 'kill-
 236 // square has been set: without one is generates all moves, and a global int legNr flags in bits 0 and 1
 237 // if the move has 1 or 2 legs. Only the marking of squares makes use of this info, by only marking
 238 // target squares of leg 1 (rejecting null move). A dummy move with MoveType 'FirstLeg' to the relay square
 239 // is generated, so a cyan marker can be put there, and other functions can ignore such a move. When the
 240 // user selects this square, it becomes the kill-square. Once a kill-square is set, only 2-leg moves are
 241 // generated that use that square as relay, plus 1-leg moves, so the 1-leg move that goes to the kill-square
 242 // can be marked during 2nd-leg entry to terminate the move there. For judging the pseudo-legality of the
 243 // 2nd leg, the from-square has to be considered empty, although the moving piece is still on it.
 244
 245 Boolean pieceDefs;
 246
 247 //  alphabet      "abcdefghijklmnopqrstuvwxyz"
 248 char symmetry[] = "FBNW.FFW.NKN.NW.QR....W..N";
 249 char xStep[]    = "2110.130.102.10.00....0..2";
 250 char yStep[]    = "2132.133.313.20.11....1..3";
 251 char dirType[]  = "01000104000200000260050000";
 252 char upgrade[]  = "AFCD.BGH.JQL.NO.KW....R..Z";
 253 char rotate[]   = "DRCA.WHG.JKL.NO.QB....F..Z";
 254
 255 //  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 "
 256 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 };
 257 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 };
 258 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 };
 259 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 };
 260
 261 int rot[][4] = { // rotation matrices for each direction
 262   { 1, 0, 0, 1 },
 263   { 0, 1, 1, 0 },
 264   { 0, 1,-1, 0 },
 265   { 1, 0, 0,-1 },
 266   {-1, 0, 0,-1 },
 267   { 0,-1,-1, 0 },
 268   { 0,-1, 1, 0 },
 269   {-1, 0, 0, 1 }
 270 };
 271
 272 void
 273 OK (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR cl)
 274 {
 275     (*(int*)cl)++;
 276 }
 277
 278 void
 279 MovesFromString (Board board, int flags, int f, int r, int tx, int ty, int angle, char *desc, MoveCallback cb, VOIDSTAR cl)
 280 {
 281     char buf[80], *p = desc, *atom = NULL;
 282     int mine, his, dir, bit, occup, i, ep, promoRank = -1;
 283     ChessMove promo= NormalMove; ChessSquare pc = board[r][f];
 284     if(pc == DarkSquare) return; // this is not a piece, but a 'hole' in the board
 285     if(flags & F_WHITE_ON_MOVE) his = 2, mine = 1; else his = 1, mine = 2;
 286     if(pc == WhitePawn || pc == WhiteLance) promo = WhitePromotion, promoRank = BOARD_HEIGHT-1; else
 287     if(pc == BlackPawn || pc == BlackLance) promo = BlackPromotion, promoRank = 0;
 288     while(*p) {                  // more moves to go
 289         int expo = 1, dx, dy, x, y, mode, dirSet, ds2=0, retry=0, initial=0, jump=1, skip = 0, all = 0;
 290         char *cont = NULL;
 291         if(*p == 'i') initial = 1, desc = ++p;
 292         while(islower(*p)) p++;  // skip prefixes
 293         if(!isupper(*p)) return; // syntax error: no atom
 294         dx = xStep[*p-'A'] - '0';// step vector of atom
 295         dy = yStep[*p-'A'] - '0';
 296         dirSet = 0;              // build direction set based on atom symmetry
 297         switch(symmetry[*p-'A']) {
 298           case 'B': expo = 0;    // bishop, slide
 299           case 'F': all = 0xAA;  // diagonal atom (degenerate 4-fold)
 300                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 301                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 302                         int b = dirs1[*desc-'a']; // use wide version
 303                         if( islower(desc[1]) &&
 304                                  ((i | dirType[desc[1]-'a']) & 3) == 3) {   // combinable (perpendicular dim)
 305                             b = dirs1[*desc-'a'] & dirs1[desc[1]-'a'];      // intersect wide & perp wide
 306                             desc += 2;
 307                         } else desc++;
 308                         dirSet |= b;
 309                     }
 310                     dirSet &= 0xAA; if(!dirSet) dirSet = 0xAA;
 311                     break;
 312           case 'R': expo = 0;    // rook, slide
 313           case 'W': all = 0x55;  // orthogonal atom (non-deg 4-fold)
 314                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 315                     while(islower(*desc) && (dirType[*desc-'a'] & ~4) != '0') dirSet |= dirs2[*desc++-'a'];
 316                     dirSet &= 0x55; if(!dirSet) dirSet = 0x55;
 317                     dirSet = (dirSet << angle | dirSet >> 8-angle) & 255;   // re-orient direction system
 318                     break;
 319           case 'N': all = 0xFF;  // oblique atom (degenerate 8-fold)
 320                     if(tx >= 0) goto king;        // continuation legs specified in K/Q system!
 321                     if(*desc == 'h') {            // chiral direction sets 'hr' and 'hl'
 322                         dirSet = (desc[1] == 'r' ? 0x55 :  0xAA); desc += 2;
 323                     } else
 324                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 325                         int b = dirs2[*desc-'a']; // when alone, use narrow version
 326                         if(desc[1] == 'h') b = dirs1[*desc-'a'], desc += 2; // dirs1 is wide version
 327                         else if(*desc == desc[1] || islower(desc[1]) && i < '4'
 328                                 && ((i | dirType[desc[1]-'a']) & 3) == 3) { // combinable (perpendicular dim or same)
 329                             b = dirs1[*desc-'a'] & dirs2[desc[1]-'a'];      // intersect wide & perp narrow
 330                             desc += 2;
 331                         } else desc++;
 332                         dirSet |= b;
 333                     }
 334                     if(!dirSet) dirSet = 0xFF;
 335                     break;
 336           case 'Q': expo = 0;    // queen, slide
 337           case 'K': all = 0xFF;  // non-deg (pseudo) 8-fold
 338           king:
 339                     while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
 340                         int b = dirs4[*desc-'a'];    // when alone, use narrow version
 341                         if(desc[1] == *desc) desc++; // doubling forces alone
 342                         else if(islower(desc[1]) && i < '4'
 343                                 && ((i | dirType[desc[1]-'a']) & 3) == 3) { // combinable (perpendicular dim or same)
 344                             b = dirs3[*desc-'a'] & dirs3[desc[1]-'a'];      // intersect wide & perp wide
 345                             desc += 2;
 346                         } else desc++;
 347                         dirSet |= b;
 348                     }
 349                     if(!dirSet) dirSet = (tx < 0 ? 0xFF                     // default is all directions, but in continuation leg
 350                                           : all == 0xFF ? 0xEF : 0x45);     // omits backward, and for 4-fold atoms also diags
 351                     dirSet = (dirSet << angle | dirSet >> 8-angle) & 255;   // re-orient direction system
 352                     ds2 = dirSet & 0xAA;          // extract diagonal directions
 353                     if(dirSet &= 0x55)            // start with orthogonal moves, if present
 354                          retry = 1, dx = 0;       // and schedule the diagonal moves for later
 355                     else dx = dy, dirSet = ds2;   // if no orthogonal directions, do diagonal immediately
 356                     break;       // should not have direction indicators
 357           default:  return;      // syntax error: invalid atom
 358         }
 359         if(mine == 2 && tx < 0) dirSet = dirSet >> 4 | dirSet << 4 & 255;   // invert black moves
 360         mode = 0;                // build mode mask
 361         if(*desc == 'm') mode |= 4, desc++;           // move to empty
 362         if(*desc == 'c') mode |= his, desc++;         // capture foe
 363         if(*desc == 'd') mode |= mine, desc++;        // destroy (capture friend)
 364         if(*desc == 'e') mode |= 8, desc++;           // e.p. capture last mover
 365         if(*desc == 't') mode |= 16, desc++;          // exclude enemies as hop platform ('test')
 366         if(*desc == 'p') mode |= 32, desc++;          // hop over occupied
 367         if(*desc == 'g') mode |= 64, desc++;          // hop and toggle range
 368         if(*desc == 'o') mode |= 128, desc++;         // wrap around cylinder board
 369         if(*desc == 'y') mode |= 512, desc++;         // toggle range on empty square
 370         if(*desc == 'n') jump = 0, desc++;            // non-jumping
 371         while(*desc == 'j') jump++, desc++;           // must jump (on B,R,Q: skip first square)
 372         if(*desc == 'a') cont = ++desc;               // move again after doing what preceded it
 373         if(isdigit(*++p)) expo = atoi(p++);           // read exponent
 374         if(expo > 9) p++;                             // allow double-digit
 375         desc = p;                                     // this is start of next move
 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(board[y][x] == DarkSquare) break;  // black squares are supposed to be off board
 413                 if(j) { j--; continue; }              // skip irrespective of occupation
 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 (PROMOTED WhitePawn):
 889                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 890             case SHOGI (PROMOTED BlackPawn):
 891                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 892                 SlideVertical(board, flags, rf, ff, callback, closure);
 893                 break;
 894
 895             case SHOGI (PROMOTED 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 (PROMOTED 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 (PROMOTED 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 (PROMOTED 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 (PROMOTED WhiteFerz):
1242                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
1243             case SHOGI (PROMOTED 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 = killX < 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                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1682         }
1683     }
1684
1685     /* For compatibility with ICS wild 9, we scan the board in the
1686        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1687        and we test only whether that one is in check. */
1688     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1689         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1690           if (board[cl.rking][cl.fking] == king) {
1691               cl.check = 0;
1692               if(gameInfo.variant == VariantXiangqi) {
1693                   /* [HGM] In Xiangqi opposing Kings means check as well */
1694                   int i, dir;
1695                   dir = (king >= BlackPawn) ? -1 : 1;
1696                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1697                                 board[i][cl.fking] == EmptySquare; i+=dir );
1698                   if(i>=0 && i<BOARD_HEIGHT &&
1699                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1700                           cl.check++;
1701               }
1702               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1703               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1704                  goto undo_move;  /* 2-level break */
1705           }
1706       }
1707
1708   undo_move:
1709
1710     if (rt >= 0) {
1711         if(rf != DROP_RANK) // [HGM] drop
1712             board[rf][ff] = board[rt][ft];
1713         if (enPassant) {
1714             board[rf][ft] = captured;
1715             board[rt][ft] = EmptySquare;
1716         } else {
1717             if(saveKill >= 0) board[killY][killX = saveKill] = trampled;
1718             board[rt][ft] = captured;
1719         }
1720         board[EP_STATUS] = ep;
1721     }
1722
1723     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1724 }
1725
1726 int
1727 HasLion (Board board, int flags)
1728 {
1729     int lion = F_WHITE_ON_MOVE & flags ? WhiteLion : BlackLion;
1730     int r, f;
1731     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1732         if(board[r][f] == lion) return 1;
1733     return 0;
1734 }
1735
1736 ChessMove
1737 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1738 {   // [HGM] put drop legality testing in separate routine for clarity
1739     int n;
1740 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1741     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1742     n = PieceToNumber(piece);
1743     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1744         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1745         return ImpossibleMove; // piece not available
1746     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1747         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1748            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1749             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1750             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1751         if(piece == WhitePawn || piece == BlackPawn) {
1752             int r, max = 1 + (BOARD_HEIGHT == 7); // two Pawns per file in Tori!
1753             for(r=1; r<BOARD_HEIGHT-1; r++)
1754                 if(!(max -= (board[r][ft] == piece))) return IllegalMove; // or there already is a Pawn in file
1755             // should still test if we mate with this Pawn
1756         }
1757     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1758         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1759     } else {
1760         if( (piece == WhitePawn || piece == BlackPawn) &&
1761             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1762             return IllegalMove; /* no pawn drops on 1st/8th */
1763     }
1764 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1765     if (!(flags & F_IGNORE_CHECK) &&
1766         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1767     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1768 }
1769
1770 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1771                                     int rf, int ff, int rt, int ft,
1772                                     VOIDSTAR closure));
1773
1774 void
1775 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1776 {
1777     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1778
1779     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1780         cl->captures++; // [HGM] losers: count legal captures
1781     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1782       cl->kind = kind;
1783 }
1784
1785 ChessMove
1786 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1787 {
1788     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1789
1790     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1791     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1792     piece = filterPiece = board[rf][ff];
1793     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1794
1795     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1796     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1797     if((piece == WhiteFalcon || piece == BlackFalcon ||
1798         piece == WhiteCobra  || piece == BlackCobra) && gameInfo.variant != VariantChu && !pieceDesc[piece])
1799         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1800
1801     cl.rf = rf;
1802     cl.ff = ff;
1803     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1804     cl.ft = fFilter = ft;
1805     cl.kind = IllegalMove;
1806     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1807     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1808     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1809     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1810                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1811         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1812
1813     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1814     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1815         if(board[rf][ff] < BlackPawn) { // white
1816             if(rf != 0) return IllegalMove; // must be on back rank
1817             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1818             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1819             if(cl.kind == WhiteHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1820             if(cl.kind == WhiteASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1821         } else {
1822             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1823             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1824             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1825             if(cl.kind == BlackHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1826             if(cl.kind == BlackASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1827         }
1828     } else
1829     if(gameInfo.variant == VariantChu) {
1830         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1831         if(promoChar != '+')
1832             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1833         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') {
1834             if(PieceToChar(CHUPROMOTED (board[rf][ff] < BlackPawn ? WhitePawn : BlackPawn)) != '.')
1835             return ImpossibleMove;
1836         }
1837         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1838     } else
1839     if(gameInfo.variant == VariantShogi) {
1840         /* [HGM] Shogi promotions. '=' means defer */
1841         if(rf != DROP_RANK && cl.kind == NormalMove) {
1842             ChessSquare piece = board[rf][ff];
1843             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
1844
1845             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1846             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1847                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1848                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1849                   promoChar = '+'; // allowed ICS notations
1850 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1851             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1852                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1853             else if(flags & F_WHITE_ON_MOVE) {
1854                 if( (int) piece < (int) WhiteWazir &&
1855                      (rf >= BOARD_HEIGHT - zone || rt >= BOARD_HEIGHT - zone) ) {
1856                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1857                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1858                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1859                     else /* promotion optional, default is defer */
1860                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1861                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1862             } else {
1863                 if( (int) piece < (int) BlackWazir && (rf < zone || rt < zone) ) {
1864                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1865                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1866                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1867                     else /* promotion optional, default is defer */
1868                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1869                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1870             }
1871         }
1872     } else
1873     if (promoChar != NULLCHAR) {
1874         if(cl.kind == NormalMove && promoChar == '+') { // allow shogi-style promotion is pieceToChar specifies them
1875             ChessSquare piece = board[rf][ff];
1876             if(piece < BlackPawn ? piece > WhiteMan : piece > BlackMan) return ImpossibleMove; // already promoted
1877             // should test if in zone, really
1878             if(gameInfo.variant == VariantChuChess && (piece == WhiteKnight || piece == BlackKnight) && HasLion(board, flags))
1879                 return IllegalMove;
1880             if(PieceToChar(PROMOTED piece) == '+') return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1881         } else
1882         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1883         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1884             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1885             if(piece == EmptySquare)
1886                 cl.kind = ImpossibleMove; // non-existing piece
1887             if(gameInfo.variant == VariantChuChess && promoChar == 'l' && HasLion(board, flags)) {
1888                 cl.kind = IllegalMove; // no two Lions
1889             } else if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1890                 if(promoChar != PieceToChar(BlackKing)) {
1891                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1892                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1893                 } else { // promotion to King allowed only if we do not have two yet
1894                     int r, f, kings = 0;
1895                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1896                     if(kings == 2) cl.kind = IllegalMove;
1897                 }
1898             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1899                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1900             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1901              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1902             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1903              cl.kind = IllegalMove; // promotion to King usually not allowed
1904         } else {
1905             cl.kind = IllegalMove;
1906         }
1907     }
1908     return cl.kind;
1909 }
1910
1911 typedef struct {
1912     int count;
1913 } MateTestClosure;
1914
1915 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1916                                 int rf, int ff, int rt, int ft,
1917                                 VOIDSTAR closure));
1918
1919 void
1920 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1921 {
1922     register MateTestClosure *cl = (MateTestClosure *) closure;
1923
1924     cl->count++;
1925 }
1926
1927 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1928 int
1929 MateTest (Board board, int flags)
1930 {
1931     MateTestClosure cl;
1932     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1933     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1934
1935     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1936         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1937         nrKing += (board[r][f] == king);   // stm has king
1938         if( board[r][f] != EmptySquare ) {
1939             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1940                  myPieces++;
1941             else hisPieces++;
1942         }
1943     }
1944     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1945         case VariantShatranj:
1946                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1947         default:
1948                 break;
1949         case VariantAtomic:
1950                 if(nrKing == 0) return MT_NOKING;
1951                 break;
1952         case VariantLosers:
1953                 if(myPieces == 1) return MT_BARE;
1954     }
1955     cl.count = 0;
1956     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1957     // [HGM] 3check: yet to do!
1958     if (cl.count > 0) {
1959         return inCheck ? MT_CHECK : MT_NONE;
1960     } else {
1961         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1962                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1963             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1964             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1965                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1966                     if(board[n][holdings] != EmptySquare) {
1967                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1968                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1969                     }
1970         }
1971         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1972                 return myPieces == hisPieces ? MT_STALEMATE :
1973                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1974         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1975         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1976
1977         return inCheck ? MT_CHECKMATE
1978                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || IS_SHOGI(gameInfo.variant)) ?
1979                           MT_STAINMATE : MT_STALEMATE;
1980     }
1981 }
1982
1983
1984 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1985                                     int rf, int ff, int rt, int ft,
1986                                     VOIDSTAR closure));
1987
1988 void
1989 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1990 {
1991     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1992     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1993     extern int kifu; // in parser.c
1994
1995     // [HGM] wild: for wild-card pieces rt and rf are dummies
1996     if(piece == WhiteFalcon || piece == BlackFalcon ||
1997        piece == WhiteCobra  || piece == BlackCobra)
1998         wildCard = TRUE;
1999
2000     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
2001          || PieceToChar(board[rf][ff]) == '~'
2002               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
2003                                                                       ) &&
2004         (cl->rfIn == -1 || cl->rfIn == rf) &&
2005         (cl->ffIn == -1 || cl->ffIn == ff) &&
2006         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
2007         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
2008
2009         if(cl->count && rf == cl->rf && ff == cl->ff) return; // duplicate move
2010
2011         if(cl->count == 1 && kifu & 0x7E && cl->rfIn == -1 && cl->ffIn == -1) { // traditional Shogi disambiguation required
2012             int this = 1, other = 1;
2013             if(kifu & 2) this &= (flags & 1 ? rt > rf : rt < rf), other &= (flags & 1 ? cl->rt > cl->rf : cl->rt < cl->rf);
2014             if(kifu & 4) this &= (flags & 1 ? rt < rf : rt > rf), other &= (flags & 1 ? cl->rt < cl->rf : cl->rt > cl->rf);
2015             if(kifu & 8) this &= (rf == rt), other &= (cl->rt == cl->rf);
2016             if(kifu & 0x10) this &= (flags & 1 ? ft <= ff : ft >= ff), other &= (flags & 1 ? cl->ft <= cl->ff : cl->ft >= cl->ff);
2017             if(kifu & 0x20) this &= (flags & 1 ? ft >= ff : ft <= ff), other &= (flags & 1 ? cl->ft >= cl->ff : cl->ft <= cl->ff);
2018             if(kifu & 0x40) this &= (ft == ff), other &= (cl->ft == cl->ff); // should never be used
2019             if(!other) cl->count--; // the old move did not satisfy the requested relative position, erase it
2020             if(!this) return;       // the current move does not satisfy the requested relative position, ignore it
2021         }
2022
2023         cl->count++;
2024         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
2025           // [HGM] oneclick: if multiple moves, be sure we remember capture
2026           cl->piece = board[rf][ff];
2027           cl->rf = rf;
2028           cl->ff = ff;
2029           cl->rt = wildCard ? cl->rtIn : rt;
2030           cl->ft = wildCard ? cl->ftIn : ft;
2031           cl->kind = kind;
2032         }
2033         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
2034     }
2035 }
2036
2037 void
2038 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
2039 {
2040     int illegal = 0; char c = closure->promoCharIn;
2041
2042     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
2043     closure->count = closure->captures = 0;
2044     closure->rf = closure->ff = closure->rt = closure->ft = 0;
2045     closure->kind = ImpossibleMove;
2046     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
2047     fFilter = closure->ftIn;
2048     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
2049         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2050         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
2051             closure->count = closure->captures = 0;
2052             closure->rf = closure->ff = closure->rt = closure->ft = 0;
2053             closure->kind = ImpossibleMove;
2054             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2055         }
2056     } else
2057     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2058     if (closure->count == 0) {
2059         /* See if it's an illegal move due to check */
2060         illegal = 1;
2061         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2062         if (closure->count == 0) {
2063             /* No, it's not even that */
2064           if(!appData.testLegality && !pieceDefs && closure->pieceIn != EmptySquare) {
2065             int f, r; // if there is only a single piece of the requested type on the board, use that
2066             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
2067             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
2068                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
2069             if(closure->count > 1) illegal = 0; // ambiguous
2070           }
2071           if(closure->count == 0) {
2072             if (appData.debugMode) { int i, j;
2073                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
2074                     for(j=0; j<BOARD_WIDTH; j++)
2075                         fprintf(debugFP, "%3d", (int) board[i][j]);
2076                     fprintf(debugFP, "\n");
2077                 }
2078             }
2079             return;
2080           }
2081         }
2082     } else if(pieceDefs && closure->count > 1) { // [HGM] gen: move is ambiguous under engine-defined rules
2083         DisambiguateClosure spare = *closure;
2084         pieceDefs = FALSE; spare.count = 0;     // See if the (erroneous) built-in rules would resolve that
2085         GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) &spare, closure->pieceIn);
2086         if(spare.count == 1) *closure = spare;  // It does, so use those in stead (game from file saved before gen patch?)
2087         pieceDefs = TRUE;
2088     }
2089
2090     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
2091     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
2092         if(closure->piece < BlackPawn) { // white
2093             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
2094             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
2095             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
2096             if(closure->kind == WhiteHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2097             if(closure->kind == WhiteASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2098         } else {
2099             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
2100             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
2101             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
2102             if(closure->kind == BlackHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2103             if(closure->kind == BlackASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2104         }
2105     } else
2106     if(gameInfo.variant == VariantChu) {
2107         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
2108     } else
2109     if(gameInfo.variant == VariantShogi) {
2110         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
2111         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
2112             ChessSquare piece = closure->piece;
2113             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
2114             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
2115                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
2116                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
2117                    c = '+'; // allowed ICS notations
2118             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
2119             else if(flags & F_WHITE_ON_MOVE) {
2120                 if( (int) piece < (int) WhiteWazir &&
2121                      (closure->rf >= BOARD_HEIGHT-zone || closure->rt >= BOARD_HEIGHT-zone) ) {
2122                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
2123                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
2124                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
2125                     else /* promotion optional, default is defer */
2126                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
2127                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2128             } else {
2129                 if( (int) piece < (int) BlackWazir && (closure->rf < zone || closure->rt < zone) ) {
2130                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
2131                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
2132                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
2133                     else /* promotion optional, default is defer */
2134                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
2135                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2136             }
2137         }
2138         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
2139         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
2140     } else
2141     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
2142         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
2143             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
2144                gameInfo.variant == VariantMakruk)
2145                 c = PieceToChar(BlackFerz);
2146             else if(gameInfo.variant == VariantASEAN)
2147                 c = PieceToChar(BlackRook);
2148             else if(gameInfo.variant == VariantGreat)
2149                 c = PieceToChar(BlackMan);
2150             else if(gameInfo.variant == VariantGrand)
2151                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
2152             else
2153                 c = PieceToChar(BlackQueen);
2154         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
2155         else if(c == 'l' && gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2156     } else if (c == '+') { // '+' outside shogi, check if pieceToCharTable enabled it
2157         ChessSquare p = closure->piece;
2158         if(p > WhiteMan && p < BlackPawn || p > BlackMan || PieceToChar(PROMOTED p) != '+')
2159             closure->kind = ImpossibleMove; // used on non-promotable piece
2160         else if(gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2161     } else if (c != NULLCHAR) closure->kind = IllegalMove;
2162
2163     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
2164     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
2165         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
2166     if (closure->count > 1) {
2167         closure->kind = AmbiguousMove;
2168     }
2169     if (illegal) {
2170         /* Note: If more than one illegal move matches, but no legal
2171            moves, we return IllegalMove, not AmbiguousMove.  Caller
2172            can look at closure->count to detect this.
2173         */
2174         closure->kind = IllegalMove;
2175     }
2176 }
2177
2178
2179 typedef struct {
2180     /* Input */
2181     ChessSquare piece;
2182     int rf, ff, rt, ft;
2183     /* Output */
2184     ChessMove kind;
2185     int rank;
2186     int file;
2187     int either;
2188 } CoordsToAlgebraicClosure;
2189
2190 extern void CoordsToAlgebraicCallback P((Board board, int flags,
2191                                          ChessMove kind, int rf, int ff,
2192                                          int rt, int ft, VOIDSTAR closure));
2193
2194 void
2195 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2196 {
2197     register CoordsToAlgebraicClosure *cl =
2198       (CoordsToAlgebraicClosure *) closure;
2199
2200     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
2201         (board[rf][ff] == cl->piece
2202          || PieceToChar(board[rf][ff]) == '~' &&
2203             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
2204                                      ) {
2205         if (rf == cl->rf) {
2206             if (ff == cl->ff) {
2207                 cl->kind = kind; /* this is the move we want */
2208             } else {
2209                 cl->file++; /* need file to rule out this move */
2210             }
2211         } else {
2212             if (ff == cl->ff) {
2213                 cl->rank++; /* need rank to rule out this move */
2214             } else {
2215                 cl->either++; /* rank or file will rule out this move */
2216             }
2217         }
2218     }
2219 }
2220
2221 /* Convert coordinates to normal algebraic notation.
2222    promoChar must be NULLCHAR or 'x' if not a promotion.
2223 */
2224 ChessMove
2225 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
2226 {
2227     ChessSquare piece;
2228     ChessMove kind;
2229     char *outp = out, c, capture;
2230     CoordsToAlgebraicClosure cl;
2231
2232     if (rf == DROP_RANK) {
2233         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
2234         /* Bughouse piece drop */
2235         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
2236         *outp++ = '@';
2237         *outp++ = ft + AAA;
2238         if(rt+ONE <= '9')
2239            *outp++ = rt + ONE;
2240         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2241         *outp = NULLCHAR;
2242         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
2243     }
2244
2245     if (promoChar == 'x') promoChar = NULLCHAR;
2246     piece = board[rf][ff];
2247     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
2248
2249     switch (piece) {
2250       case WhitePawn:
2251       case BlackPawn:
2252         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2253         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2254             /* Keep short notation if move is illegal only because it
2255                leaves the player in check, but still return IllegalMove */
2256             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
2257             if (kind == IllegalMove) break;
2258             kind = IllegalMove;
2259         }
2260         /* Pawn move */
2261         *outp++ = ff + AAA;
2262         capture = board[rt][ft] != EmptySquare || kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant;
2263         if (ff == ft && !capture) { /* [HGM] Xiangqi has straight noncapts! */
2264             /* Non-capture; use style "e5" */
2265             if(rt+ONE <= '9')
2266                *outp++ = rt + ONE;
2267             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2268         } else {
2269             /* Capture; use style "exd5" */
2270             if(capture)
2271             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
2272             *outp++ = ft + AAA;
2273             if(rt+ONE <= '9')
2274                *outp++ = rt + ONE;
2275             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2276         }
2277         /* Use promotion suffix style "=Q" */
2278         *outp = NULLCHAR;
2279         if (promoChar != NULLCHAR) {
2280             if(IS_SHOGI(gameInfo.variant)) {
2281                 /* [HGM] ... but not in Shogi! */
2282                 *outp++ = promoChar == '=' ? '=' : '+';
2283             } else {
2284                 *outp++ = '=';
2285                 *outp++ = ToUpper(promoChar);
2286             }
2287             *outp = NULLCHAR;
2288         }
2289         return kind;
2290
2291
2292       case WhiteKing:
2293       case BlackKing:
2294         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
2295         /* Code added by Tord:  FRC castling. */
2296         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
2297            (piece == BlackKing && board[rt][ft] == BlackRook)) {
2298           if(ft > ff)
2299             safeStrCpy(out, "O-O", MOVE_LEN);
2300           else
2301             safeStrCpy(out, "O-O-O", MOVE_LEN);
2302           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2303         }
2304         /* End of code added by Tord */
2305         /* Test for castling or ICS wild castling */
2306         /* Use style "O-O" (oh-oh) for PGN compatibility */
2307         else if (rf == rt &&
2308             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
2309             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
2310             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
2311              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
2312             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
2313               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2314             else
2315               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2316
2317             /* This notation is always unambiguous, unless there are
2318                kings on both the d and e files, with "wild castling"
2319                possible for the king on the d file and normal castling
2320                possible for the other.  ICS rules for wild 9
2321                effectively make castling illegal for either king in
2322                this situation.  So I am not going to worry about it;
2323                I'll just generate an ambiguous O-O in this case.
2324             */
2325             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2326         }
2327
2328         /* else fall through */
2329       default:
2330         /* Piece move */
2331         cl.rf = rf;
2332         cl.ff = ff;
2333         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
2334         cl.ft = fFilter = ft;
2335         cl.piece = piece;
2336         cl.kind = IllegalMove;
2337         cl.rank = cl.file = cl.either = 0;
2338         c = PieceToChar(piece) ;
2339         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
2340
2341         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2342             /* Generate pretty moves for moving into check, but
2343                still return IllegalMove.
2344             */
2345             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
2346             if (cl.kind == IllegalMove) break;
2347             cl.kind = IllegalMove;
2348         }
2349
2350         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
2351            else "Ngf3" or "Ngxf7",
2352            else "N1f3" or "N5xf7",
2353            else "Ng1f3" or "Ng5xf7".
2354         */
2355         if( c == '~' || c == '+') {
2356            /* [HGM] print nonexistent piece as its demoted version */
2357            piece = (ChessSquare) (DEMOTED piece - 11*(gameInfo.variant == VariantChu));
2358         }
2359         if(c=='+') *outp++ = c;
2360         *outp++ = ToUpper(PieceToChar(piece));
2361         if(*outp = PieceSuffix(piece)) outp++;
2362
2363         if (cl.file || (cl.either && !cl.rank)) {
2364             *outp++ = ff + AAA;
2365         }
2366         if (cl.rank) {
2367             if(rf+ONE <= '9')
2368                 *outp++ = rf + ONE;
2369             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2370         }
2371
2372         if(board[rt][ft] != EmptySquare)
2373           *outp++ = 'x';
2374
2375         *outp++ = ft + AAA;
2376         if(rt+ONE <= '9')
2377            *outp++ = rt + ONE;
2378         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2379         if (IS_SHOGI(gameInfo.variant)) {
2380             /* [HGM] in Shogi non-pawns can promote */
2381             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
2382         }
2383         else if (gameInfo.variant == VariantChuChess && promoChar ||
2384                  gameInfo.variant != VariantSuper && promoChar &&
2385                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
2386             *outp++ = '=';
2387             *outp++ = ToUpper(promoChar);
2388         }
2389         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
2390             *outp++ = '/';
2391             *outp++ = ToUpper(promoChar);
2392         }
2393         *outp = NULLCHAR;
2394         return cl.kind;
2395
2396       case EmptySquare:
2397         /* Moving a nonexistent piece */
2398         break;
2399     }
2400
2401     /* Not a legal move, even ignoring check.
2402        If there was a piece on the from square,
2403        use style "Ng1g3" or "Ng1xe8";
2404        if there was a pawn or nothing (!),
2405        use style "g1g3" or "g1xe8".  Use "x"
2406        if a piece was on the to square, even
2407        a piece of the same color.
2408     */
2409     outp = out;
2410     c = 0;
2411     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
2412         int r, f;
2413       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
2414                 c += (board[r][f] == piece); // count on-board pieces of given type
2415         *outp++ = ToUpper(PieceToChar(piece));
2416     }
2417   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2418     *outp++ = ff + AAA;
2419     if(rf+ONE <= '9')
2420        *outp++ = rf + ONE;
2421     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2422   }
2423     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2424     *outp++ = ft + AAA;
2425     if(rt+ONE <= '9')
2426        *outp++ = rt + ONE;
2427     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2428     /* Use promotion suffix style "=Q" */
2429     if (promoChar != NULLCHAR && promoChar != 'x') {
2430         *outp++ = '=';
2431         *outp++ = ToUpper(promoChar);
2432     }
2433     *outp = NULLCHAR;
2434
2435     return IllegalMove;
2436 }
2437
2438 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2439
2440 typedef struct {
2441     /* Input */
2442     int rf, ff, rt, ft;
2443     /* Output */
2444     int recaptures;
2445 } ChaseClosure;
2446
2447 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2448
2449 int preyStackPointer, chaseStackPointer;
2450
2451 struct {
2452 unsigned char rf, ff, rt, ft;
2453 } chaseStack[100];
2454
2455 struct {
2456 unsigned char rank, file;
2457 } preyStack[100];
2458
2459
2460
2461
2462 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2463
2464 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2465                                 int rf, int ff, int rt, int ft,
2466                                 VOIDSTAR closure));
2467
2468 void
2469 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2470 {   // For adding captures that can lead to chase indictment to the chaseStack
2471     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2472     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2473     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2474     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2475     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2476     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2477     chaseStack[chaseStackPointer].rf = rf;
2478     chaseStack[chaseStackPointer].ff = ff;
2479     chaseStack[chaseStackPointer].rt = rt;
2480     chaseStack[chaseStackPointer].ft = ft;
2481     chaseStackPointer++;
2482 }
2483
2484 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2485                                 int rf, int ff, int rt, int ft,
2486                                 VOIDSTAR closure));
2487
2488 void
2489 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2490 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2491     int i;
2492     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2493
2494     if(board[rt][ft] == EmptySquare) return; // no capture
2495     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2496         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2497     }
2498     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2499     for(i=0; i<chaseStackPointer; i++) {
2500         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2501            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2502             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2503             chaseStack[i] = chaseStack[--chaseStackPointer];
2504             break;
2505         }
2506     }
2507 }
2508
2509 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2510                                 int rf, int ff, int rt, int ft,
2511                                 VOIDSTAR closure));
2512
2513 void
2514 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2515 {   // for determining if a piece (given through the closure) is protected
2516     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2517
2518     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2519     if(appData.debugMode && board[rt][ft] != EmptySquare)
2520         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2521 }
2522
2523 extern char moveList[MAX_MOVES][MOVE_LEN];
2524
2525 int
2526 PerpetualChase (int first, int last)
2527 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2528     int i, j, k, tail;
2529     ChaseClosure cl;
2530     ChessSquare captured;
2531
2532     preyStackPointer = 0;        // clear stack of chased pieces
2533     for(i=first; i<last; i+=2) { // for all positions with same side to move
2534         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2535         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2536         // determine all captures possible after the move, and put them on chaseStack
2537         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2538         if(appData.debugMode) { int n;
2539             for(n=0; n<chaseStackPointer; n++)
2540                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2541                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2542             fprintf(debugFP, ": all capts\n");
2543         }
2544         // determine all captures possible before the move, and delete them from chaseStack
2545         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2546         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2547         cl.rt = moveList[i][3]-ONE;
2548         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2549         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2550         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2551         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2552         if(appData.debugMode) { int n;
2553             for(n=0; n<chaseStackPointer; n++)
2554                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2555                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2556             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2557         }
2558         // chaseSack now contains all captures made possible by the move
2559         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2560             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2561             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2562
2563             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2564             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2565
2566             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2567                 continue; // C or H attack on R is always chase; leave on chaseStack
2568
2569             if(attacker == victim) {
2570                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2571                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2572                         // we can capture back with equal piece, so this is no chase but a sacrifice
2573                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2574                         j--; /* ! */ continue;
2575                 }
2576
2577             }
2578
2579             // the attack is on a lower piece, or on a pinned or blocked equal one
2580             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2581             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2582             // test if the victim is protected by a true protector. First make the capture.
2583             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2584             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2585             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2586             // Then test if the opponent can recapture
2587             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2588             cl.rt = chaseStack[j].rt;
2589             cl.ft = chaseStack[j].ft;
2590             if(appData.debugMode) {
2591                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2592             }
2593             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2594             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2595             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2596             // unmake the capture
2597             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2598             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2599             // if a recapture was found, piece is protected, and we are not chasing it.
2600             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2601                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2602                 j--; /* ! */
2603             }
2604         }
2605         // chaseStack now contains all moves that chased
2606         if(appData.debugMode) { int n;
2607             for(n=0; n<chaseStackPointer; n++)
2608                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2609                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2610             fprintf(debugFP, ": chases\n");
2611         }
2612         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2613             for(j=0; j<chaseStackPointer; j++) {
2614                 preyStack[j].rank = chaseStack[j].rt;
2615                 preyStack[j].file = chaseStack[j].ft;
2616             }
2617             preyStackPointer = chaseStackPointer;
2618         }
2619         tail = 0;
2620         for(j=0; j<chaseStackPointer; j++) {
2621             for(k=0; k<preyStackPointer; k++) {
2622                 // search the victim of each chase move on the preyStack (first occurrence)
2623                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2624                     if(k < tail) break; // piece was already identified as still being chased
2625                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2626                     preyStack[tail] = preyStack[k];                // by swapping
2627                     preyStack[k] = preyStack[preyStackPointer];
2628                     tail++;
2629                     break;
2630                 }
2631             }
2632         }
2633         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2634         if(appData.debugMode) { int n;
2635             for(n=0; n<preyStackPointer; n++)
2636                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2637             fprintf(debugFP, "always chased upto ply %d\n", i);
2638         }
2639         // now adjust the location of the chased pieces according to opponent move
2640         for(j=0; j<preyStackPointer; j++) {
2641             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2642                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2643                 preyStack[j].rank = moveList[i+1][3]-ONE;
2644                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2645                 break;
2646             }
2647         }
2648     }
2649     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2650                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2651 }