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 || gameInfo.variant == VariantShogi) { // 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         if(gameInfo.variant == VariantShogi) prince -= 11;                   // White/BlackFalcon
1626         for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1627             if(board[r][f] == k || board[r][f] == prince) {
1628                 if(++royals > 1) return FALSE; // no check if we have two royals (ignores double captureby Lion!)
1629                 king = board[r][f]; // remember hich one we had
1630             }
1631         }
1632     }
1633
1634     if (rt >= 0) {
1635         if (enPassant) {
1636             captured = board[rf][ft];
1637             board[rf][ft] = EmptySquare;
1638         } else {
1639             captured = board[rt][ft];
1640             if(killX >= 0) { trampled = board[killY][killX]; board[killY][killX] = EmptySquare; killX = -1; }
1641         }
1642         if(rf == DROP_RANK) board[rt][ft] = ff; else { // [HGM] drop
1643             board[rt][ft] = board[rf][ff];
1644             if(rf != rt || ff != ft) board[rf][ff] = EmptySquare;
1645         }
1646         ep = board[EP_STATUS];
1647         if( captured == WhiteLion || captured == BlackLion ) { // [HGM] lion: Chu Lion-capture rules
1648             ChessSquare victim = killX < 0 ? EmptySquare : trampled;
1649             if( (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion) &&           // capturer is Lion
1650                 (ff - ft > 1 || ft - ff > 1 || rf - rt > 1 || rt - rf > 1) &&           // captures from a distance
1651                 (victim == EmptySquare || victim == WhitePawn || victim == BlackPawn) ) // no or worthless 'bridge'
1652                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1653         }
1654     }
1655
1656     /* For compatibility with ICS wild 9, we scan the board in the
1657        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1658        and we test only whether that one is in check. */
1659     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1660         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1661           if (board[cl.rking][cl.fking] == king) {
1662               cl.check = 0;
1663               if(gameInfo.variant == VariantXiangqi) {
1664                   /* [HGM] In Xiangqi opposing Kings means check as well */
1665                   int i, dir;
1666                   dir = (king >= BlackPawn) ? -1 : 1;
1667                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1668                                 board[i][cl.fking] == EmptySquare; i+=dir );
1669                   if(i>=0 && i<BOARD_HEIGHT &&
1670                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1671                           cl.check++;
1672               }
1673               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1674               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1675                  goto undo_move;  /* 2-level break */
1676           }
1677       }
1678
1679   undo_move:
1680
1681     if (rt >= 0) {
1682         if(rf != DROP_RANK) // [HGM] drop
1683             board[rf][ff] = board[rt][ft];
1684         if (enPassant) {
1685             board[rf][ft] = captured;
1686             board[rt][ft] = EmptySquare;
1687         } else {
1688             if(saveKill >= 0) board[killY][killX = saveKill] = trampled;
1689             board[rt][ft] = captured;
1690         }
1691         board[EP_STATUS] = ep;
1692     }
1693
1694     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1695 }
1696
1697 int
1698 HasLion (Board board, int flags)
1699 {
1700     int lion = F_WHITE_ON_MOVE & flags ? WhiteLion : BlackLion;
1701     int r, f;
1702     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1703         if(board[r][f] == lion) return 1;
1704     return 0;
1705 }
1706
1707 ChessMove
1708 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1709 {   // [HGM] put drop legality testing in separate routine for clarity
1710     int n;
1711 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1712     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1713     n = PieceToNumber(piece);
1714     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1715         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1716         return ImpossibleMove; // piece not available
1717     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1718         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1719            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1720             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1721             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1722         if(piece == WhitePawn || piece == BlackPawn) {
1723             int r, max = 1 + (BOARD_HEIGHT == 7); // two Pawns per file in Tori!
1724             for(r=1; r<BOARD_HEIGHT-1; r++)
1725                 if(!(max -= (board[r][ft] == piece))) return IllegalMove; // or there already is a Pawn in file
1726             // should still test if we mate with this Pawn
1727         }
1728     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1729         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1730     } else {
1731         if( (piece == WhitePawn || piece == BlackPawn) &&
1732             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1733             return IllegalMove; /* no pawn drops on 1st/8th */
1734     }
1735 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1736     if (!(flags & F_IGNORE_CHECK) &&
1737         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1738     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1739 }
1740
1741 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1742                                     int rf, int ff, int rt, int ft,
1743                                     VOIDSTAR closure));
1744
1745 void
1746 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1747 {
1748     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1749
1750     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1751         cl->captures++; // [HGM] losers: count legal captures
1752     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1753       cl->kind = kind;
1754 }
1755
1756 ChessMove
1757 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1758 {
1759     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1760
1761     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1762     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1763     piece = filterPiece = board[rf][ff];
1764     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1765
1766     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1767     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1768     if((piece == WhiteFalcon || piece == BlackFalcon ||
1769         piece == WhiteCobra  || piece == BlackCobra) && gameInfo.variant != VariantChu && !pieceDesc[piece])
1770         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1771
1772     cl.rf = rf;
1773     cl.ff = ff;
1774     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1775     cl.ft = fFilter = ft;
1776     cl.kind = IllegalMove;
1777     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1778     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1779     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1780     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1781                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1782         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1783
1784     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1785     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1786         if(board[rf][ff] < BlackPawn) { // white
1787             if(rf != 0) return IllegalMove; // must be on back rank
1788             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1789             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1790             if(cl.kind == WhiteHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1791             if(cl.kind == WhiteASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1792         } else {
1793             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1794             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1795             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1796             if(cl.kind == BlackHSideCastleFR && (ff == BOARD_RGHT-2 || ff == BOARD_RGHT-3)) return ImpossibleMove;
1797             if(cl.kind == BlackASideCastleFR && (ff == BOARD_LEFT+2 || ff == BOARD_LEFT+3)) return ImpossibleMove;
1798         }
1799     } else
1800     if(gameInfo.variant == VariantChu) {
1801         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1802         if(promoChar != '+')
1803             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1804         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') return ImpossibleMove;
1805         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1806     } else
1807     if(gameInfo.variant == VariantShogi) {
1808         /* [HGM] Shogi promotions. '=' means defer */
1809         if(rf != DROP_RANK && cl.kind == NormalMove) {
1810             ChessSquare piece = board[rf][ff];
1811
1812             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1813             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1814                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1815                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1816                   promoChar = '+'; // allowed ICS notations
1817 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1818             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1819                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1820             else if(flags & F_WHITE_ON_MOVE) {
1821                 if( (int) piece < (int) WhiteWazir &&
1822                      (rf >= BOARD_HEIGHT - BOARD_HEIGHT/3 || rt >= BOARD_HEIGHT - BOARD_HEIGHT/3) ) {
1823                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1824                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1825                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1826                     else /* promotion optional, default is defer */
1827                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1828                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1829             } else {
1830                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1831                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1832                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1833                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1834                     else /* promotion optional, default is defer */
1835                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1836                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1837             }
1838         }
1839     } else
1840     if (promoChar != NULLCHAR) {
1841         if(cl.kind == NormalMove && promoChar == '+') { // allow shogi-style promotion is pieceToChar specifies them
1842             ChessSquare piece = board[rf][ff];
1843             if(piece < BlackPawn ? piece > WhiteMan : piece > BlackMan) return ImpossibleMove; // already promoted
1844             // should test if in zone, really
1845             if(gameInfo.variant == VariantChuChess && (piece == WhiteKnight || piece == BlackKnight) && HasLion(board, flags))
1846                 return IllegalMove;
1847             if(PieceToChar(PROMOTED piece) == '+') return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1848         } else
1849         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1850         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1851             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1852             if(piece == EmptySquare)
1853                 cl.kind = ImpossibleMove; // non-existing piece
1854             if(gameInfo.variant == VariantChuChess && promoChar == 'l' && HasLion(board, flags)) {
1855                 cl.kind = IllegalMove; // no two Lions
1856             } else if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1857                 if(promoChar != PieceToChar(BlackKing)) {
1858                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1859                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1860                 } else { // promotion to King allowed only if we do not have two yet
1861                     int r, f, kings = 0;
1862                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1863                     if(kings == 2) cl.kind = IllegalMove;
1864                 }
1865             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1866                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1867             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1868              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1869             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1870              cl.kind = IllegalMove; // promotion to King usually not allowed
1871         } else {
1872             cl.kind = IllegalMove;
1873         }
1874     }
1875     return cl.kind;
1876 }
1877
1878 typedef struct {
1879     int count;
1880 } MateTestClosure;
1881
1882 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1883                                 int rf, int ff, int rt, int ft,
1884                                 VOIDSTAR closure));
1885
1886 void
1887 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1888 {
1889     register MateTestClosure *cl = (MateTestClosure *) closure;
1890
1891     cl->count++;
1892 }
1893
1894 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1895 int
1896 MateTest (Board board, int flags)
1897 {
1898     MateTestClosure cl;
1899     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1900     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1901
1902     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1903         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1904         nrKing += (board[r][f] == king);   // stm has king
1905         if( board[r][f] != EmptySquare ) {
1906             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1907                  myPieces++;
1908             else hisPieces++;
1909         }
1910     }
1911     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1912         case VariantShatranj:
1913                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1914         default:
1915                 break;
1916         case VariantAtomic:
1917                 if(nrKing == 0) return MT_NOKING;
1918                 break;
1919         case VariantLosers:
1920                 if(myPieces == 1) return MT_BARE;
1921     }
1922     cl.count = 0;
1923     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1924     // [HGM] 3check: yet to do!
1925     if (cl.count > 0) {
1926         return inCheck ? MT_CHECK : MT_NONE;
1927     } else {
1928         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1929                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1930             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1931             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1932                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1933                     if(board[n][holdings] != EmptySquare) {
1934                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1935                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1936                     }
1937         }
1938         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1939                 return myPieces == hisPieces ? MT_STALEMATE :
1940                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1941         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1942         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1943
1944         return inCheck ? MT_CHECKMATE
1945                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || IS_SHOGI(gameInfo.variant)) ?
1946                           MT_STAINMATE : MT_STALEMATE;
1947     }
1948 }
1949
1950
1951 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1952                                     int rf, int ff, int rt, int ft,
1953                                     VOIDSTAR closure));
1954
1955 void
1956 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1957 {
1958     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1959     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1960
1961     // [HGM] wild: for wild-card pieces rt and rf are dummies
1962     if(piece == WhiteFalcon || piece == BlackFalcon ||
1963        piece == WhiteCobra  || piece == BlackCobra)
1964         wildCard = TRUE;
1965
1966     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1967          || PieceToChar(board[rf][ff]) == '~'
1968               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1969                                                                       ) &&
1970         (cl->rfIn == -1 || cl->rfIn == rf) &&
1971         (cl->ffIn == -1 || cl->ffIn == ff) &&
1972         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1973         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1974
1975         if(cl->count && rf == cl->rf && ff == cl->ff) return; // duplicate move
1976
1977         cl->count++;
1978         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1979           // [HGM] oneclick: if multiple moves, be sure we remember capture
1980           cl->piece = board[rf][ff];
1981           cl->rf = rf;
1982           cl->ff = ff;
1983           cl->rt = wildCard ? cl->rtIn : rt;
1984           cl->ft = wildCard ? cl->ftIn : ft;
1985           cl->kind = kind;
1986         }
1987         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1988     }
1989 }
1990
1991 void
1992 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
1993 {
1994     int illegal = 0; char c = closure->promoCharIn;
1995
1996     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1997     closure->count = closure->captures = 0;
1998     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1999     closure->kind = ImpossibleMove;
2000     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
2001     fFilter = closure->ftIn;
2002     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
2003         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2004         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
2005             closure->count = closure->captures = 0;
2006             closure->rf = closure->ff = closure->rt = closure->ft = 0;
2007             closure->kind = ImpossibleMove;
2008             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2009         }
2010     } else
2011     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
2012     if (closure->count == 0) {
2013         /* See if it's an illegal move due to check */
2014         illegal = 1;
2015         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
2016         if (closure->count == 0) {
2017             /* No, it's not even that */
2018           if(!appData.testLegality && closure->pieceIn != EmptySquare) {
2019             int f, r; // if there is only a single piece of the requested type on the board, use that
2020             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
2021             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
2022                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
2023             if(closure->count > 1) illegal = 0; // ambiguous
2024           }
2025           if(closure->count == 0) {
2026             if (appData.debugMode) { int i, j;
2027                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
2028                     for(j=0; j<BOARD_WIDTH; j++)
2029                         fprintf(debugFP, "%3d", (int) board[i][j]);
2030                     fprintf(debugFP, "\n");
2031                 }
2032             }
2033             return;
2034           }
2035         }
2036     } else if(pieceDefs && closure->count > 1) { // [HGM] gen: move is ambiguous under engine-defined rules
2037         DisambiguateClosure spare = *closure;
2038         pieceDefs = FALSE; spare.count = 0;     // See if the (erroneous) built-in rules would resolve that
2039         GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) &spare, closure->pieceIn);
2040         if(spare.count == 1) *closure = spare;  // It does, so use those in stead (game from file saved before gen patch?)
2041         pieceDefs = TRUE;
2042     }
2043
2044     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
2045     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
2046         if(closure->piece < BlackPawn) { // white
2047             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
2048             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
2049             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
2050             if(closure->kind == WhiteHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2051             if(closure->kind == WhiteASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2052         } else {
2053             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
2054             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
2055             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
2056             if(closure->kind == BlackHSideCastleFR && (closure->ff == BOARD_RGHT-2 || closure->ff == BOARD_RGHT-3)) closure->kind = ImpossibleMove;
2057             if(closure->kind == BlackASideCastleFR && (closure->ff == BOARD_LEFT+2 || closure->ff == BOARD_LEFT+3)) closure->kind = ImpossibleMove;
2058         }
2059     } else
2060     if(gameInfo.variant == VariantChu) {
2061         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
2062     } else
2063     if(gameInfo.variant == VariantShogi) {
2064         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
2065         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
2066             ChessSquare piece = closure->piece;
2067             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
2068                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
2069                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
2070                    c = '+'; // allowed ICS notations
2071             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
2072             else if(flags & F_WHITE_ON_MOVE) {
2073                 if( (int) piece < (int) WhiteWazir &&
2074                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
2075                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
2076                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
2077                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
2078                     else /* promotion optional, default is defer */
2079                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
2080                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2081             } else {
2082                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
2083                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
2084                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
2085                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
2086                     else /* promotion optional, default is defer */
2087                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
2088                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
2089             }
2090         }
2091         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
2092         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
2093     } else
2094     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
2095         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
2096             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
2097                gameInfo.variant == VariantMakruk)
2098                 c = PieceToChar(BlackFerz);
2099             else if(gameInfo.variant == VariantASEAN)
2100                 c = PieceToChar(BlackRook);
2101             else if(gameInfo.variant == VariantGreat)
2102                 c = PieceToChar(BlackMan);
2103             else if(gameInfo.variant == VariantGrand)
2104                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
2105             else
2106                 c = PieceToChar(BlackQueen);
2107         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
2108         else if(c == 'l' && gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2109     } else if (c == '+') { // '+' outside shogi, check if pieceToCharTable enabled it
2110         ChessSquare p = closure->piece;
2111         if(p > WhiteMan && p < BlackPawn || p > BlackMan || PieceToChar(PROMOTED p) != '+')
2112             closure->kind = ImpossibleMove; // used on non-promotable piece
2113         else if(gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
2114     } else if (c != NULLCHAR) closure->kind = IllegalMove;
2115
2116     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
2117     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
2118         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
2119     if (closure->count > 1) {
2120         closure->kind = AmbiguousMove;
2121     }
2122     if (illegal) {
2123         /* Note: If more than one illegal move matches, but no legal
2124            moves, we return IllegalMove, not AmbiguousMove.  Caller
2125            can look at closure->count to detect this.
2126         */
2127         closure->kind = IllegalMove;
2128     }
2129 }
2130
2131
2132 typedef struct {
2133     /* Input */
2134     ChessSquare piece;
2135     int rf, ff, rt, ft;
2136     /* Output */
2137     ChessMove kind;
2138     int rank;
2139     int file;
2140     int either;
2141 } CoordsToAlgebraicClosure;
2142
2143 extern void CoordsToAlgebraicCallback P((Board board, int flags,
2144                                          ChessMove kind, int rf, int ff,
2145                                          int rt, int ft, VOIDSTAR closure));
2146
2147 void
2148 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2149 {
2150     register CoordsToAlgebraicClosure *cl =
2151       (CoordsToAlgebraicClosure *) closure;
2152
2153     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
2154         (board[rf][ff] == cl->piece
2155          || PieceToChar(board[rf][ff]) == '~' &&
2156             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
2157                                      ) {
2158         if (rf == cl->rf) {
2159             if (ff == cl->ff) {
2160                 cl->kind = kind; /* this is the move we want */
2161             } else {
2162                 cl->file++; /* need file to rule out this move */
2163             }
2164         } else {
2165             if (ff == cl->ff) {
2166                 cl->rank++; /* need rank to rule out this move */
2167             } else {
2168                 cl->either++; /* rank or file will rule out this move */
2169             }
2170         }
2171     }
2172 }
2173
2174 /* Convert coordinates to normal algebraic notation.
2175    promoChar must be NULLCHAR or 'x' if not a promotion.
2176 */
2177 ChessMove
2178 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
2179 {
2180     ChessSquare piece;
2181     ChessMove kind;
2182     char *outp = out, c, capture;
2183     CoordsToAlgebraicClosure cl;
2184
2185     if (rf == DROP_RANK) {
2186         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
2187         /* Bughouse piece drop */
2188         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
2189         *outp++ = '@';
2190         *outp++ = ft + AAA;
2191         if(rt+ONE <= '9')
2192            *outp++ = rt + ONE;
2193         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2194         *outp = NULLCHAR;
2195         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
2196     }
2197
2198     if (promoChar == 'x') promoChar = NULLCHAR;
2199     piece = board[rf][ff];
2200     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
2201
2202     switch (piece) {
2203       case WhitePawn:
2204       case BlackPawn:
2205         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2206         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2207             /* Keep short notation if move is illegal only because it
2208                leaves the player in check, but still return IllegalMove */
2209             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
2210             if (kind == IllegalMove) break;
2211             kind = IllegalMove;
2212         }
2213         /* Pawn move */
2214         *outp++ = ff + AAA;
2215         capture = board[rt][ft] != EmptySquare || kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant;
2216         if (ff == ft && !capture) { /* [HGM] Xiangqi has straight noncapts! */
2217             /* Non-capture; use style "e5" */
2218             if(rt+ONE <= '9')
2219                *outp++ = rt + ONE;
2220             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2221         } else {
2222             /* Capture; use style "exd5" */
2223             if(capture)
2224             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
2225             *outp++ = ft + AAA;
2226             if(rt+ONE <= '9')
2227                *outp++ = rt + ONE;
2228             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2229         }
2230         /* Use promotion suffix style "=Q" */
2231         *outp = NULLCHAR;
2232         if (promoChar != NULLCHAR) {
2233             if(IS_SHOGI(gameInfo.variant)) {
2234                 /* [HGM] ... but not in Shogi! */
2235                 *outp++ = promoChar == '=' ? '=' : '+';
2236             } else {
2237                 *outp++ = '=';
2238                 *outp++ = ToUpper(promoChar);
2239             }
2240             *outp = NULLCHAR;
2241         }
2242         return kind;
2243
2244
2245       case WhiteKing:
2246       case BlackKing:
2247         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
2248         /* Code added by Tord:  FRC castling. */
2249         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
2250            (piece == BlackKing && board[rt][ft] == BlackRook)) {
2251           if(ft > ff)
2252             safeStrCpy(out, "O-O", MOVE_LEN);
2253           else
2254             safeStrCpy(out, "O-O-O", MOVE_LEN);
2255           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2256         }
2257         /* End of code added by Tord */
2258         /* Test for castling or ICS wild castling */
2259         /* Use style "O-O" (oh-oh) for PGN compatibility */
2260         else if (rf == rt &&
2261             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
2262             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
2263             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
2264              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
2265             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
2266               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2267             else
2268               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
2269
2270             /* This notation is always unambiguous, unless there are
2271                kings on both the d and e files, with "wild castling"
2272                possible for the king on the d file and normal castling
2273                possible for the other.  ICS rules for wild 9
2274                effectively make castling illegal for either king in
2275                this situation.  So I am not going to worry about it;
2276                I'll just generate an ambiguous O-O in this case.
2277             */
2278             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
2279         }
2280
2281         /* else fall through */
2282       default:
2283         /* Piece move */
2284         cl.rf = rf;
2285         cl.ff = ff;
2286         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
2287         cl.ft = fFilter = ft;
2288         cl.piece = piece;
2289         cl.kind = IllegalMove;
2290         cl.rank = cl.file = cl.either = 0;
2291         c = PieceToChar(piece) ;
2292         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
2293
2294         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
2295             /* Generate pretty moves for moving into check, but
2296                still return IllegalMove.
2297             */
2298             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
2299             if (cl.kind == IllegalMove) break;
2300             cl.kind = IllegalMove;
2301         }
2302
2303         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
2304            else "Ngf3" or "Ngxf7",
2305            else "N1f3" or "N5xf7",
2306            else "Ng1f3" or "Ng5xf7".
2307         */
2308         if( c == '~' || c == '+') {
2309            /* [HGM] print nonexistent piece as its demoted version */
2310            piece = (ChessSquare) (DEMOTED piece - 11*(gameInfo.variant == VariantChu));
2311         }
2312         if(c=='+') *outp++ = c;
2313         *outp++ = ToUpper(PieceToChar(piece));
2314
2315         if (cl.file || (cl.either && !cl.rank)) {
2316             *outp++ = ff + AAA;
2317         }
2318         if (cl.rank) {
2319             if(rf+ONE <= '9')
2320                 *outp++ = rf + ONE;
2321             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2322         }
2323
2324         if(board[rt][ft] != EmptySquare)
2325           *outp++ = 'x';
2326
2327         *outp++ = ft + AAA;
2328         if(rt+ONE <= '9')
2329            *outp++ = rt + ONE;
2330         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2331         if (IS_SHOGI(gameInfo.variant)) {
2332             /* [HGM] in Shogi non-pawns can promote */
2333             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
2334         }
2335         else if (gameInfo.variant == VariantChuChess && promoChar ||
2336                  gameInfo.variant != VariantSuper && promoChar &&
2337                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
2338             *outp++ = '=';
2339             *outp++ = ToUpper(promoChar);
2340         }
2341         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
2342             *outp++ = '/';
2343             *outp++ = ToUpper(promoChar);
2344         }
2345         *outp = NULLCHAR;
2346         return cl.kind;
2347
2348       case EmptySquare:
2349         /* Moving a nonexistent piece */
2350         break;
2351     }
2352
2353     /* Not a legal move, even ignoring check.
2354        If there was a piece on the from square,
2355        use style "Ng1g3" or "Ng1xe8";
2356        if there was a pawn or nothing (!),
2357        use style "g1g3" or "g1xe8".  Use "x"
2358        if a piece was on the to square, even
2359        a piece of the same color.
2360     */
2361     outp = out;
2362     c = 0;
2363     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
2364         int r, f;
2365       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
2366                 c += (board[r][f] == piece); // count on-board pieces of given type
2367         *outp++ = ToUpper(PieceToChar(piece));
2368     }
2369   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2370     *outp++ = ff + AAA;
2371     if(rf+ONE <= '9')
2372        *outp++ = rf + ONE;
2373     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2374   }
2375     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2376     *outp++ = ft + AAA;
2377     if(rt+ONE <= '9')
2378        *outp++ = rt + ONE;
2379     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2380     /* Use promotion suffix style "=Q" */
2381     if (promoChar != NULLCHAR && promoChar != 'x') {
2382         *outp++ = '=';
2383         *outp++ = ToUpper(promoChar);
2384     }
2385     *outp = NULLCHAR;
2386
2387     return IllegalMove;
2388 }
2389
2390 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2391
2392 typedef struct {
2393     /* Input */
2394     int rf, ff, rt, ft;
2395     /* Output */
2396     int recaptures;
2397 } ChaseClosure;
2398
2399 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2400
2401 int preyStackPointer, chaseStackPointer;
2402
2403 struct {
2404 unsigned char rf, ff, rt, ft;
2405 } chaseStack[100];
2406
2407 struct {
2408 unsigned char rank, file;
2409 } preyStack[100];
2410
2411
2412
2413
2414 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2415
2416 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2417                                 int rf, int ff, int rt, int ft,
2418                                 VOIDSTAR closure));
2419
2420 void
2421 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2422 {   // For adding captures that can lead to chase indictment to the chaseStack
2423     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2424     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2425     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2426     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2427     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2428     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2429     chaseStack[chaseStackPointer].rf = rf;
2430     chaseStack[chaseStackPointer].ff = ff;
2431     chaseStack[chaseStackPointer].rt = rt;
2432     chaseStack[chaseStackPointer].ft = ft;
2433     chaseStackPointer++;
2434 }
2435
2436 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2437                                 int rf, int ff, int rt, int ft,
2438                                 VOIDSTAR closure));
2439
2440 void
2441 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2442 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2443     int i;
2444     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2445
2446     if(board[rt][ft] == EmptySquare) return; // no capture
2447     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2448         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2449     }
2450     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2451     for(i=0; i<chaseStackPointer; i++) {
2452         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2453            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2454             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2455             chaseStack[i] = chaseStack[--chaseStackPointer];
2456             break;
2457         }
2458     }
2459 }
2460
2461 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2462                                 int rf, int ff, int rt, int ft,
2463                                 VOIDSTAR closure));
2464
2465 void
2466 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2467 {   // for determining if a piece (given through the closure) is protected
2468     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2469
2470     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2471     if(appData.debugMode && board[rt][ft] != EmptySquare)
2472         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2473 }
2474
2475 extern char moveList[MAX_MOVES][MOVE_LEN];
2476
2477 int
2478 PerpetualChase (int first, int last)
2479 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2480     int i, j, k, tail;
2481     ChaseClosure cl;
2482     ChessSquare captured;
2483
2484     preyStackPointer = 0;        // clear stack of chased pieces
2485     for(i=first; i<last; i+=2) { // for all positions with same side to move
2486         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2487         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2488         // determine all captures possible after the move, and put them on chaseStack
2489         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2490         if(appData.debugMode) { int n;
2491             for(n=0; n<chaseStackPointer; n++)
2492                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2493                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2494             fprintf(debugFP, ": all capts\n");
2495         }
2496         // determine all captures possible before the move, and delete them from chaseStack
2497         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2498         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2499         cl.rt = moveList[i][3]-ONE;
2500         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2501         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2502         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2503         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2504         if(appData.debugMode) { int n;
2505             for(n=0; n<chaseStackPointer; n++)
2506                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2507                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2508             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2509         }
2510         // chaseSack now contains all captures made possible by the move
2511         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2512             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2513             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2514
2515             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2516             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2517
2518             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2519                 continue; // C or H attack on R is always chase; leave on chaseStack
2520
2521             if(attacker == victim) {
2522                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2523                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2524                         // we can capture back with equal piece, so this is no chase but a sacrifice
2525                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2526                         j--; /* ! */ continue;
2527                 }
2528
2529             }
2530
2531             // the attack is on a lower piece, or on a pinned or blocked equal one
2532             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2533             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2534             // test if the victim is protected by a true protector. First make the capture.
2535             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2536             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2537             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2538             // Then test if the opponent can recapture
2539             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2540             cl.rt = chaseStack[j].rt;
2541             cl.ft = chaseStack[j].ft;
2542             if(appData.debugMode) {
2543                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2544             }
2545             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2546             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2547             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2548             // unmake the capture
2549             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2550             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2551             // if a recapture was found, piece is protected, and we are not chasing it.
2552             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2553                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2554                 j--; /* ! */
2555             }
2556         }
2557         // chaseStack now contains all moves that chased
2558         if(appData.debugMode) { int n;
2559             for(n=0; n<chaseStackPointer; n++)
2560                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2561                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2562             fprintf(debugFP, ": chases\n");
2563         }
2564         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2565             for(j=0; j<chaseStackPointer; j++) {
2566                 preyStack[j].rank = chaseStack[j].rt;
2567                 preyStack[j].file = chaseStack[j].ft;
2568             }
2569             preyStackPointer = chaseStackPointer;
2570         }
2571         tail = 0;
2572         for(j=0; j<chaseStackPointer; j++) {
2573             for(k=0; k<preyStackPointer; k++) {
2574                 // search the victim of each chase move on the preyStack (first occurrence)
2575                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2576                     if(k < tail) break; // piece was already identified as still being chased
2577                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2578                     preyStack[tail] = preyStack[k];                // by swapping
2579                     preyStack[k] = preyStack[preyStackPointer];
2580                     tail++;
2581                     break;
2582                 }
2583             }
2584         }
2585         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2586         if(appData.debugMode) { int n;
2587             for(n=0; n<preyStackPointer; n++)
2588                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2589             fprintf(debugFP, "always chased upto ply %d\n", i);
2590         }
2591         // now adjust the location of the chased pieces according to opponent move
2592         for(j=0; j<preyStackPointer; j++) {
2593             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2594                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2595                 preyStack[j].rank = moveList[i+1][3]-ONE;
2596                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2597                 break;
2598             }
2599         }
2600     }
2601     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2602                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2603 }