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