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