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