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