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