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