moves.c

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