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