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