moves.c

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