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 = saveKill < 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                                      || victim == WhiteCobra || victim == BlackCobra) ) // (Pawn or Go Between)
1681                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1682         }
1683     }
1684
1685     /* For compatibility with ICS wild 9, we scan the board in the
1686        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1687        and we test only whether that one is in check. */
1688     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1689         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1690           if (board[cl.rking][cl.fking] == king) {
1691               cl.check = 0;
1692               if(gameInfo.variant == VariantXiangqi) {
1693                   /* [HGM] In Xiangqi opposing Kings means check as well */
1694                   int i, dir;
1695                   dir = (king >= BlackPawn) ? -1 : 1;
1696                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1697                                 board[i][cl.fking] == EmptySquare; i+=dir );
1698                   if(i>=0 && i<BOARD_HEIGHT &&
1699                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1700                           cl.check++;
1701               }
1702               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1703               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1704                  goto undo_move;  /* 2-level break */
1705           }
1706       }
1707
1708   undo_move:
1709
1710     if (rt >= 0) {
1711         if(rf != DROP_RANK) // [HGM] drop
1712             board[rf][ff] = board[rt][ft];
1713         if (enPassant) {
1714             board[rf][ft] = captured;
1715             board[rt][ft] = EmptySquare;
1716         } else {
1717             if(saveKill >= 0) board[killY][killX = saveKill] = trampled;
1718             board[rt][ft] = captured;
1719         }
1720         board[EP_STATUS] = ep;
1721     }
1722
1723     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1724 }
1725
1726 int
1727 HasLion (Board board, int flags)
1728 {
1729     int lion = F_WHITE_ON_MOVE & flags ? WhiteLion : BlackLion;
1730     int r, f;
1731     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1732         if(board[r][f] == lion) return 1;
1733     return 0;
1734 }
1735
1736 ChessMove
1737 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1738 {   // [HGM] put drop legality testing in separate routine for clarity
1739     int n;
1740 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1741     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1742     n = PieceToNumber(piece);
1743     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1744         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1745         return ImpossibleMove; // piece not available
1746     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1747         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1748            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1749             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1750             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1751         if(piece == WhitePawn || piece == BlackPawn) {
1752             int r, max = 1 + (BOARD_HEIGHT == 7); // two Pawns per file in Tori!
1753             for(r=1; r<BOARD_HEIGHT-1; r++)
1754                 if(!(max -= (board[r][ft] == piece))) return IllegalMove; // or there already is a Pawn in file
1755             // should still test if we mate with this Pawn
1756         }
1757     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1758         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1759     } else {
1760         if( (piece == WhitePawn || piece == BlackPawn) &&
1761             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1762             return IllegalMove; /* no pawn drops on 1st/8th */
1763     }
1764 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1765     if (!(flags & F_IGNORE_CHECK) &&
1766         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1767     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1768 }
1769
1770 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1771                                     int rf, int ff, int rt, int ft,
1772                                     VOIDSTAR closure));
1773
1774 void
1775 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1776 {
1777     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1778
1779     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1780         cl->captures++; // [HGM] losers: count legal captures
1781     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1782       cl->kind = kind;
1783 }
1784
1785 ChessMove
1786 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1787 {
1788     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1789
1790     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1791     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1792     piece = filterPiece = board[rf][ff];
1793     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1794
1795     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1796     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1797     if((piece == WhiteFalcon || piece == BlackFalcon ||
1798         piece == WhiteCobra  || piece == BlackCobra) && gameInfo.variant != VariantChu && !pieceDesc[piece])
1799         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1800
1801     cl.rf = rf;
1802     cl.ff = ff;
1803     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1804     cl.ft = fFilter = ft;
1805     cl.kind = IllegalMove;
1806     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1807     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1808     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1809     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1810                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1811         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1812
1813     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1814     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1815         if(board[rf][ff] < BlackPawn) { // white
1816             if(rf != 0) return IllegalMove; // must be on back rank
1817             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1818             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1819             if(cl.kind == WhiteHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1820             if(cl.kind == WhiteASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1821         } else {
1822             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1823             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1824             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1825             if(cl.kind == BlackHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1826             if(cl.kind == BlackASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1827         }
1828     } else
1829     if(gameInfo.variant == VariantChu) {
1830         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1831         if(promoChar != '+')
1832             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1833         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') {
1834             if(PieceToChar(CHUPROMOTED (board[rf][ff] < BlackPawn ? WhitePawn : BlackPawn)) != '.')
1835             return ImpossibleMove;
1836         }
1837         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1838     } else
1839     if(gameInfo.variant == VariantShogi) {
1840         /* [HGM] Shogi promotions. '=' means defer */
1841         if(rf != DROP_RANK && cl.kind == NormalMove) {
1842             ChessSquare piece = board[rf][ff];
1843             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
1844
1845             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1846             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1847                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1848                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1849                   promoChar = '+'; // allowed ICS notations
1850 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1851             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1852                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1853             else if(flags & F_WHITE_ON_MOVE) {
1854                 if( (int) piece < (int) WhiteWazir &&
1855                      (rf >= BOARD_HEIGHT - zone || rt >= BOARD_HEIGHT - zone) ) {
1856                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1857                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1858                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1859                     else /* promotion optional, default is defer */
1860                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1861                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1862             } else {
1863                 if( (int) piece < (int) BlackWazir && (rf < zone || rt < zone) ) {
1864                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1865                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1866                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1867                     else /* promotion optional, default is defer */
1868                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1869                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1870             }
1871         }
1872     } else
1873     if (promoChar != NULLCHAR) {
1874         if(cl.kind == NormalMove && promoChar == '+') { // allow shogi-style promotion is pieceToChar specifies them
1875             ChessSquare piece = board[rf][ff];
1876             if(piece < BlackPawn ? piece > WhiteMan : piece > BlackMan) return ImpossibleMove; // already promoted
1877             // should test if in zone, really
1878             if(gameInfo.variant == VariantChuChess && (piece == WhiteKnight || piece == BlackKnight) && HasLion(board, flags))
1879                 return IllegalMove;
1880             if(PieceToChar(PROMOTED piece) == '+') return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1881         } else
1882         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1883         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1884             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1885             if(piece == EmptySquare)
1886                 cl.kind = ImpossibleMove; // non-existing piece
1887             if(gameInfo.variant == VariantChuChess && promoChar == 'l' && HasLion(board, flags)) {
1888                 cl.kind = IllegalMove; // no two Lions
1889             } else if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1890                 if(promoChar != PieceToChar(BlackKing)) {
1891                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1892                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1893                 } else { // promotion to King allowed only if we do not have two yet
1894                     int r, f, kings = 0;
1895                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1896                     if(kings == 2) cl.kind = IllegalMove;
1897                 }
1898             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1899                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1900             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1901              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1902             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1903              cl.kind = IllegalMove; // promotion to King usually not allowed
1904         } else {
1905             cl.kind = IllegalMove;
1906         }
1907     }
1908     return cl.kind;
1909 }
1910
1911 typedef struct {
1912     int count;
1913 } MateTestClosure;
1914
1915 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1916                                 int rf, int ff, int rt, int ft,
1917                                 VOIDSTAR closure));
1918
1919 void
1920 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1921 {
1922     register MateTestClosure *cl = (MateTestClosure *) closure;
1923
1924     cl->count++;
1925 }
1926
1927 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1928 int
1929 MateTest (Board board, int flags)
1930 {
1931     MateTestClosure cl;
1932     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1933     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1934
1935     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1936         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1937         nrKing += (board[r][f] == king);   // stm has king
1938         if( board[r][f] != EmptySquare ) {
1939             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1940                  myPieces++;
1941             else hisPieces++;
1942         }
1943     }
1944     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1945         case VariantShatranj:
1946                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1947         default:
1948                 break;
1949         case VariantAtomic:
1950                 if(nrKing == 0) return MT_NOKING;
1951                 break;
1952         case VariantLosers:
1953                 if(myPieces == 1) return MT_BARE;
1954     }
1955     cl.count = 0;
1956     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1957     // [HGM] 3check: yet to do!
1958     if (cl.count > 0) {
1959         return inCheck ? MT_CHECK : MT_NONE;
1960     } else {
1961         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1962                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1963             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1964             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1965                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1966                     if(board[n][holdings] != EmptySquare) {
1967                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1968                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1969                     }
1970         }
1971         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1972                 return myPieces == hisPieces ? MT_STALEMATE :
1973                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1974         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1975         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1976
1977         return inCheck ? MT_CHECKMATE
1978                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || IS_SHOGI(gameInfo.variant)) ?
1979                           MT_STAINMATE : MT_STALEMATE;
1980     }
1981 }
1982
1983
1984 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1985                                     int rf, int ff, int rt, int ft,
1986                                     VOIDSTAR closure));
1987
1988 void
1989 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1990 {
1991     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1992     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1993     extern int kifu; // in parser.c
1994
1995     // [HGM] wild: for wild-card pieces rt and rf are dummies
1996     if(piece == WhiteFalcon || piece == BlackFalcon ||
1997        piece == WhiteCobra  || piece == BlackCobra)
1998         wildCard = TRUE;
1999
2000     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
2001          || PieceToChar(board[rf][ff]) == '~'
2002               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
2003                                                                       ) &&
2004         (cl->rfIn == -1 || cl->rfIn == rf) &&
2005         (cl->ffIn == -1 || cl->ffIn == ff) &&
2006         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
2007         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
2008
2009         if(cl->count && rf == cl->rf && ff == cl->ff) return; // duplicate move
2010
2011         if(cl->count == 1 && kifu & 0x7E && cl->rfIn == -1 && cl->ffIn == -1) { // traditional Shogi disambiguation required
2012             int this = 1, other = 1;
2013             if(kifu & 2) this &= (flags & 1 ? rt > rf : rt < rf), other &= (flags & 1 ? cl->rt > cl->rf : cl->rt < cl->rf);
2014             if(kifu & 4) this &= (flags & 1 ? rt < rf : rt > rf), other &= (flags & 1 ? cl->rt < cl->rf : cl->rt > cl->rf);
2015             if(kifu & 8) this &= (rf == rt), other &= (cl->rt == cl->rf);
2016             if(kifu & 0x10) this &= (flags & 1 ? ft <= ff : ft >= ff), other &= (flags & 1 ? cl->ft <= cl->ff : cl->ft >= cl->ff);
2017             if(kifu & 0x20) this &= (flags & 1 ? ft >= ff : ft <= ff), other &= (flags & 1 ? cl->ft >= cl->ff : cl->ft <= cl->ff);
2018             if(kifu & 0x40) this &= (ft == ff), other &= (cl->ft == cl->ff); // should never be used
2019             if(!other) cl->count--; // the old move did not satisfy the requested relative position, erase it
2020             if(!this) return;       // the current move does not satisfy the requested relative position, ignore it
2021         }
2022
2023         cl->count++;
2024         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
2025           // [HGM] oneclick: if multiple moves, be sure we remember capture
2026           cl->piece = board[rf][ff];
2027           cl->rf = rf;
2028           cl->ff = ff;
2029           cl->rt = wildCard ? cl->rtIn : rt;
2030           cl->ft = wildCard ? cl->ftIn : ft;
2031           cl->kind = kind;
2032         }
2033         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
2034     }
2035 }
2036
2037 void
2038 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
2039 {
2040     int illegal = 0; char c = closure->promoCharIn;
2041
2042     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
2043     closure->count = closure->captures = 0;
2044     closure->rf = closure->ff = closure->rt = closure->ft = 0;
2045     closure->kind = ImpossibleMove;
2046     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
2047     fFilter = closure->ftIn;
2048     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
2049         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2050         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
2051             closure->count = closure->captures = 0;
2052             closure->rf = closure->ff = closure->rt = closure->ft = 0;
2053             closure->kind = ImpossibleMove;
2054             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2055         }
2056     } else
2057     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2058     if (closure->count == 0) {
2059         /* See if it's an illegal move due to check */
2060         illegal = 1;
2061         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2062         if (closure->count == 0) {
2063             /* No, it's not even that */
2064           if(!appData.testLegality && !pieceDefs && closure->pieceIn != EmptySquare) {
2065             int f, r; // if there is only a single piece of the requested type on the board, use that
2066             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
2067             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
2068                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
2069             if(closure->count > 1) illegal = 0; // ambiguous
2070           }
2071           if(closure->count == 0) {
2072             if (appData.debugMode) { int i, j;
2073                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
2074                     for(j=0; j<BOARD_WIDTH; j++)
2075                         fprintf(debugFP, "%3d", (int) board[i][j]);
2076                     fprintf(debugFP, "\n");
2077                 }
2078             }
2079             return;
2080           }
2081         }
2082     } else if(pieceDefs && closure->count > 1) { // [HGM] gen: move is ambiguous under engine-defined rules
2083         DisambiguateClosure spare = *closure;
2084         pieceDefs = FALSE; spare.count = 0;     // See if the (erroneous) built-in rules would resolve that
2085         GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) &spare, closure->pieceIn);
2086         if(spare.count == 1) *closure = spare;  // It does, so use those in stead (game from file saved before gen patch?)
2087         pieceDefs = TRUE;
2088     }
2089
2090     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
2091     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
2092         if(closure->piece < BlackPawn) { // white
2093             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
2094             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
2095             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
2096             if(closure->kind == WhiteHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2097             if(closure->kind == WhiteASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2098         } else {
2099             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
2100             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
2101             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
2102             if(closure->kind == BlackHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2103             if(closure->kind == BlackASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2104         }
2105     } else
2106     if(gameInfo.variant == VariantChu) {
2107         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
2108     } else
2109     if(gameInfo.variant == VariantShogi) {
2110         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
2111         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
2112             ChessSquare piece = closure->piece;
2113             int zone = BOARD_HEIGHT/3 + (BOARD_HEIGHT == 8);
2114             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
2115                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
2116                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
2117                    c = '+'; // allowed ICS notations
2118             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
2119             else if(flags & F_WHITE_ON_MOVE) {
2120                 if( (int) piece < (int) WhiteWazir &&
2121                      (closure->rf >= BOARD_HEIGHT-zone || closure->rt >= BOARD_HEIGHT-zone) ) {
2122                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
2123                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
2124                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
2125                     else /* promotion optional, default is defer */
2126                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
2127                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2128             } else {
2129                 if( (int) piece < (int) BlackWazir && (closure->rf < zone || closure->rt < zone) ) {
2130                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
2131                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
2132                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
2133                     else /* promotion optional, default is defer */
2134                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
2135                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2136             }
2137         }
2138         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
2139         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
2140     } else
2141     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
2142         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
2143             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
2144                gameInfo.variant == VariantMakruk)
2145                 c = PieceToChar(BlackFerz);
2146             else if(gameInfo.variant == VariantASEAN)
2147                 c = PieceToChar(BlackRook);
2148             else if(gameInfo.variant == VariantGreat)
2149                 c = PieceToChar(BlackMan);
2150             else if(gameInfo.variant == VariantGrand)
2151                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
2152             else
2153                 c = PieceToChar(BlackQueen);
2154         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
2155         else if(c == 'l' && gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2156     } else if (c == '+') { // '+' outside shogi, check if pieceToCharTable enabled it
2157         ChessSquare p = closure->piece;
2158         if(p > WhiteMan && p < BlackPawn || p > BlackMan || PieceToChar(PROMOTED p) != '+')
2159             closure->kind = ImpossibleMove; // used on non-promotable piece
2160         else if(gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2161     } else if (c != NULLCHAR) closure->kind = IllegalMove;
2162
2163     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
2164     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
2165         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
2166     if (closure->count > 1) {
2167         closure->kind = AmbiguousMove;
2168     }
2169     if (illegal) {
2170         /* Note: If more than one illegal move matches, but no legal
2171            moves, we return IllegalMove, not AmbiguousMove.  Caller
2172            can look at closure->count to detect this.
2173         */
2174         closure->kind = IllegalMove;
2175     }
2176 }
2177
2178
2179 typedef struct {
2180     /* Input */
2181     ChessSquare piece;
2182     int rf, ff, rt, ft;
2183     /* Output */
2184     ChessMove kind;
2185     int rank;
2186     int file;
2187     int either;
2188 } CoordsToAlgebraicClosure;
2189
2190 extern void CoordsToAlgebraicCallback P((Board board, int flags,
2191                                          ChessMove kind, int rf, int ff,
2192                                          int rt, int ft, VOIDSTAR closure));
2193
2194 void
2195 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2196 {
2197     register CoordsToAlgebraicClosure *cl =
2198       (CoordsToAlgebraicClosure *) closure;
2199
2200     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
2201         (board[rf][ff] == cl->piece
2202          || PieceToChar(board[rf][ff]) == '~' &&
2203             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
2204                                      ) {
2205         if (rf == cl->rf) {
2206             if (ff == cl->ff) {
2207                 cl->kind = kind; /* this is the move we want */
2208             } else {
2209                 cl->file++; /* need file to rule out this move */
2210             }
2211         } else {
2212             if (ff == cl->ff) {
2213                 cl->rank++; /* need rank to rule out this move */
2214             } else {
2215                 cl->either++; /* rank or file will rule out this move */
2216             }
2217         }
2218     }
2219 }
2220
2221 /* Convert coordinates to normal algebraic notation.
2222    promoChar must be NULLCHAR or 'x' if not a promotion.
2223 */
2224 ChessMove
2225 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
2226 {
2227     ChessSquare piece;
2228     ChessMove kind;
2229     char *outp = out, c, capture;
2230     CoordsToAlgebraicClosure cl;
2231
2232     if (rf == DROP_RANK) {
2233         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
2234         /* Bughouse piece drop */
2235         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
2236         *outp++ = '@';
2237         *outp++ = ft + AAA;
2238         if(rt+ONE <= '9')
2239            *outp++ = rt + ONE;
2240         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2241         *outp = NULLCHAR;
2242         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
2243     }
2244
2245     if (promoChar == 'x') promoChar = NULLCHAR;
2246     piece = board[rf][ff];
2247     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
2248
2249     switch (piece) {
2250       case WhitePawn:
2251       case BlackPawn:
2252         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2253         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2254             /* Keep short notation if move is illegal only because it
2255                leaves the player in check, but still return IllegalMove */
2256             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
2257             if (kind == IllegalMove) break;
2258             kind = IllegalMove;
2259         }
2260         /* Pawn move */
2261         *outp++ = ff + AAA;
2262         capture = board[rt][ft] != EmptySquare || kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant;
2263         if (ff == ft && !capture) { /* [HGM] Xiangqi has straight noncapts! */
2264             /* Non-capture; use style "e5" */
2265             if(rt+ONE <= '9')
2266                *outp++ = rt + ONE;
2267             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2268         } else {
2269             /* Capture; use style "exd5" */
2270             if(capture)
2271             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
2272             *outp++ = ft + AAA;
2273             if(rt+ONE <= '9')
2274                *outp++ = rt + ONE;
2275             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2276         }
2277         /* Use promotion suffix style "=Q" */
2278         *outp = NULLCHAR;
2279         if (promoChar != NULLCHAR) {
2280             if(IS_SHOGI(gameInfo.variant)) {
2281                 /* [HGM] ... but not in Shogi! */
2282                 *outp++ = promoChar == '=' ? '=' : '+';
2283             } else {
2284                 *outp++ = '=';
2285                 *outp++ = ToUpper(promoChar);
2286             }
2287             *outp = NULLCHAR;
2288         }
2289         return kind;
2290
2291
2292       case WhiteKing:
2293       case BlackKing:
2294         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
2295         /* Code added by Tord:  FRC castling. */
2296         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
2297            (piece == BlackKing && board[rt][ft] == BlackRook)) {
2298           if(ft > ff)
2299             safeStrCpy(out, "O-O", MOVE_LEN);
2300           else
2301             safeStrCpy(out, "O-O-O", MOVE_LEN);
2302           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2303         }
2304         /* End of code added by Tord */
2305         /* Test for castling or ICS wild castling */
2306         /* Use style "O-O" (oh-oh) for PGN compatibility */
2307         else if (rf == rt &&
2308             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
2309             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
2310             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
2311              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
2312             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
2313               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2314             else
2315               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2316
2317             /* This notation is always unambiguous, unless there are
2318                kings on both the d and e files, with "wild castling"
2319                possible for the king on the d file and normal castling
2320                possible for the other.  ICS rules for wild 9
2321                effectively make castling illegal for either king in
2322                this situation.  So I am not going to worry about it;
2323                I'll just generate an ambiguous O-O in this case.
2324             */
2325             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2326         }
2327
2328         /* else fall through */
2329       default:
2330         /* Piece move */
2331         cl.rf = rf;
2332         cl.ff = ff;
2333         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
2334         cl.ft = fFilter = ft;
2335         cl.piece = piece;
2336         cl.kind = IllegalMove;
2337         cl.rank = cl.file = cl.either = 0;
2338         c = PieceToChar(piece) ;
2339         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
2340
2341         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2342             /* Generate pretty moves for moving into check, but
2343                still return IllegalMove.
2344             */
2345             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
2346             if (cl.kind == IllegalMove) break;
2347             cl.kind = IllegalMove;
2348         }
2349
2350         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
2351            else "Ngf3" or "Ngxf7",
2352            else "N1f3" or "N5xf7",
2353            else "Ng1f3" or "Ng5xf7".
2354         */
2355         if( c == '~' || c == '+') {
2356            /* [HGM] print nonexistent piece as its demoted version */
2357            piece = (ChessSquare) (DEMOTED piece - 11*(gameInfo.variant == VariantChu));
2358         }
2359         if(c=='+') *outp++ = c;
2360         *outp++ = ToUpper(PieceToChar(piece));
2361         if(*outp = PieceSuffix(piece)) outp++;
2362
2363         if (cl.file || (cl.either && !cl.rank)) {
2364             *outp++ = ff + AAA;
2365         }
2366         if (cl.rank) {
2367             if(rf+ONE <= '9')
2368                 *outp++ = rf + ONE;
2369             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2370         }
2371
2372         if(board[rt][ft] != EmptySquare)
2373           *outp++ = 'x';
2374
2375         *outp++ = ft + AAA;
2376         if(rt+ONE <= '9')
2377            *outp++ = rt + ONE;
2378         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2379         if (IS_SHOGI(gameInfo.variant)) {
2380             /* [HGM] in Shogi non-pawns can promote */
2381             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
2382         }
2383         else if (gameInfo.variant == VariantChuChess && promoChar ||
2384                  gameInfo.variant != VariantSuper && promoChar &&
2385                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
2386             *outp++ = '=';
2387             *outp++ = ToUpper(promoChar);
2388         }
2389         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
2390             *outp++ = '/';
2391             *outp++ = ToUpper(promoChar);
2392         }
2393         *outp = NULLCHAR;
2394         return cl.kind;
2395
2396       case EmptySquare:
2397         /* Moving a nonexistent piece */
2398         break;
2399     }
2400
2401     /* Not a legal move, even ignoring check.
2402        If there was a piece on the from square,
2403        use style "Ng1g3" or "Ng1xe8";
2404        if there was a pawn or nothing (!),
2405        use style "g1g3" or "g1xe8".  Use "x"
2406        if a piece was on the to square, even
2407        a piece of the same color.
2408     */
2409     outp = out;
2410     c = 0;
2411     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
2412         int r, f;
2413       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
2414                 c += (board[r][f] == piece); // count on-board pieces of given type
2415         *outp++ = ToUpper(PieceToChar(piece));
2416     }
2417   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2418     *outp++ = ff + AAA;
2419     if(rf+ONE <= '9')
2420        *outp++ = rf + ONE;
2421     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2422   }
2423     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2424     *outp++ = ft + AAA;
2425     if(rt+ONE <= '9')
2426        *outp++ = rt + ONE;
2427     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2428     /* Use promotion suffix style "=Q" */
2429     if (promoChar != NULLCHAR && promoChar != 'x') {
2430         *outp++ = '=';
2431         *outp++ = ToUpper(promoChar);
2432     }
2433     *outp = NULLCHAR;
2434
2435     return IllegalMove;
2436 }
2437
2438 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2439
2440 typedef struct {
2441     /* Input */
2442     int rf, ff, rt, ft;
2443     /* Output */
2444     int recaptures;
2445 } ChaseClosure;
2446
2447 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2448
2449 int preyStackPointer, chaseStackPointer;
2450
2451 struct {
2452 unsigned char rf, ff, rt, ft;
2453 } chaseStack[100];
2454
2455 struct {
2456 unsigned char rank, file;
2457 } preyStack[100];
2458
2459
2460
2461
2462 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2463
2464 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2465                                 int rf, int ff, int rt, int ft,
2466                                 VOIDSTAR closure));
2467
2468 void
2469 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2470 {   // For adding captures that can lead to chase indictment to the chaseStack
2471     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2472     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2473     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2474     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2475     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2476     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2477     chaseStack[chaseStackPointer].rf = rf;
2478     chaseStack[chaseStackPointer].ff = ff;
2479     chaseStack[chaseStackPointer].rt = rt;
2480     chaseStack[chaseStackPointer].ft = ft;
2481     chaseStackPointer++;
2482 }
2483
2484 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2485                                 int rf, int ff, int rt, int ft,
2486                                 VOIDSTAR closure));
2487
2488 void
2489 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2490 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2491     int i;
2492     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2493
2494     if(board[rt][ft] == EmptySquare) return; // no capture
2495     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2496         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2497     }
2498     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2499     for(i=0; i<chaseStackPointer; i++) {
2500         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2501            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2502             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2503             chaseStack[i] = chaseStack[--chaseStackPointer];
2504             break;
2505         }
2506     }
2507 }
2508
2509 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2510                                 int rf, int ff, int rt, int ft,
2511                                 VOIDSTAR closure));
2512
2513 void
2514 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2515 {   // for determining if a piece (given through the closure) is protected
2516     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2517
2518     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2519     if(appData.debugMode && board[rt][ft] != EmptySquare)
2520         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2521 }
2522
2523 extern char moveList[MAX_MOVES][MOVE_LEN];
2524
2525 int
2526 PerpetualChase (int first, int last)
2527 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2528     int i, j, k, tail;
2529     ChaseClosure cl;
2530     ChessSquare captured;
2531
2532     preyStackPointer = 0;        // clear stack of chased pieces
2533     for(i=first; i<last; i+=2) { // for all positions with same side to move
2534         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2535         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2536         // determine all captures possible after the move, and put them on chaseStack
2537         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2538         if(appData.debugMode) { int n;
2539             for(n=0; n<chaseStackPointer; n++)
2540                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2541                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2542             fprintf(debugFP, ": all capts\n");
2543         }
2544         // determine all captures possible before the move, and delete them from chaseStack
2545         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2546         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2547         cl.rt = moveList[i][3]-ONE;
2548         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2549         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2550         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2551         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2552         if(appData.debugMode) { int n;
2553             for(n=0; n<chaseStackPointer; n++)
2554                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2555                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2556             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2557         }
2558         // chaseSack now contains all captures made possible by the move
2559         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2560             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2561             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2562
2563             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2564             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2565
2566             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2567                 continue; // C or H attack on R is always chase; leave on chaseStack
2568
2569             if(attacker == victim) {
2570                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2571                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2572                         // we can capture back with equal piece, so this is no chase but a sacrifice
2573                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2574                         j--; /* ! */ continue;
2575                 }
2576
2577             }
2578
2579             // the attack is on a lower piece, or on a pinned or blocked equal one
2580             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2581             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2582             // test if the victim is protected by a true protector. First make the capture.
2583             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2584             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2585             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2586             // Then test if the opponent can recapture
2587             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2588             cl.rt = chaseStack[j].rt;
2589             cl.ft = chaseStack[j].ft;
2590             if(appData.debugMode) {
2591                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2592             }
2593             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2594             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2595             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2596             // unmake the capture
2597             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2598             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2599             // if a recapture was found, piece is protected, and we are not chasing it.
2600             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2601                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2602                 j--; /* ! */
2603             }
2604         }
2605         // chaseStack now contains all moves that chased
2606         if(appData.debugMode) { int n;
2607             for(n=0; n<chaseStackPointer; n++)
2608                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2609                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2610             fprintf(debugFP, ": chases\n");
2611         }
2612         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2613             for(j=0; j<chaseStackPointer; j++) {
2614                 preyStack[j].rank = chaseStack[j].rt;
2615                 preyStack[j].file = chaseStack[j].ft;
2616             }
2617             preyStackPointer = chaseStackPointer;
2618         }
2619         tail = 0;
2620         for(j=0; j<chaseStackPointer; j++) {
2621             for(k=0; k<preyStackPointer; k++) {
2622                 // search the victim of each chase move on the preyStack (first occurrence)
2623                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2624                     if(k < tail) break; // piece was already identified as still being chased
2625                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2626                     preyStack[tail] = preyStack[k];                // by swapping
2627                     preyStack[k] = preyStack[preyStackPointer];
2628                     tail++;
2629                     break;
2630                 }
2631             }
2632         }
2633         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2634         if(appData.debugMode) { int n;
2635             for(n=0; n<preyStackPointer; n++)
2636                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2637             fprintf(debugFP, "always chased upto ply %d\n", i);
2638         }
2639         // now adjust the location of the chased pieces according to opponent move
2640         for(j=0; j<preyStackPointer; j++) {
2641             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2642                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2643                 preyStack[j].rank = moveList[i+1][3]-ONE;
2644                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2645                 break;
2646             }
2647         }
2648     }
2649     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2650                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2651 }