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