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