moves.c

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