moves.c

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