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