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