moves.c

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