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