moves.c

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