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(IS_SHOGI(gameInfo.variant)) {
1164         /* [HGM] Shogi promotions. '=' means defer */
1165         if(rf != DROP_RANK && cl.kind == NormalMove) {
1166             ChessSquare piece = board[rf][ff];
1167
1168             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1169             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1170                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1171                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1172                   promoChar = '+'; // allowed ICS notations
1173 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1174             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1175                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1176             else if(flags & F_WHITE_ON_MOVE) {
1177                 if( (int) piece < (int) WhiteWazir &&
1178                      (rf >= BOARD_HEIGHT - BOARD_HEIGHT/3 || rt >= BOARD_HEIGHT - BOARD_HEIGHT/3) ) {
1179                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1180                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1181                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1182                     else /* promotion optional, default is defer */
1183                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1184                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1185             } else {
1186                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1187                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1188                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1189                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1190                     else /* promotion optional, default is defer */
1191                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1192                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1193             }
1194         }
1195     } else
1196     if (promoChar != NULLCHAR) {
1197         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1198         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1199             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1200             if(piece == EmptySquare)
1201                 cl.kind = ImpossibleMove; // non-existing piece
1202             if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1203                 if(promoChar != PieceToChar(BlackKing)) {
1204                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1205                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1206                 } else { // promotion to King allowed only if we do not haave two yet
1207                     int r, f, kings = 0;
1208                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1209                     if(kings == 2) cl.kind = IllegalMove;
1210                 }
1211             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1212                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1213             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1214              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1215             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1216              cl.kind = IllegalMove; // promotion to King usually not allowed
1217         } else {
1218             cl.kind = IllegalMove;
1219         }
1220     }
1221     return cl.kind;
1222 }
1223
1224 typedef struct {
1225     int count;
1226 } MateTestClosure;
1227
1228 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1229                                 int rf, int ff, int rt, int ft,
1230                                 VOIDSTAR closure));
1231
1232 void
1233 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1234 {
1235     register MateTestClosure *cl = (MateTestClosure *) closure;
1236
1237     cl->count++;
1238 }
1239
1240 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1241 int
1242 MateTest (Board board, int flags)
1243 {
1244     MateTestClosure cl;
1245     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1246     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1247
1248     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1249         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1250         nrKing += (board[r][f] == king);   // stm has king
1251         if( board[r][f] != EmptySquare ) {
1252             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1253                  myPieces++;
1254             else hisPieces++;
1255         }
1256     }
1257     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1258         case VariantShatranj:
1259                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1260         default:
1261                 break;
1262         case VariantAtomic:
1263                 if(nrKing == 0) return MT_NOKING;
1264                 break;
1265         case VariantLosers:
1266                 if(myPieces == 1) return MT_BARE;
1267     }
1268     cl.count = 0;
1269     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1270     // [HGM] 3check: yet to do!
1271     if (cl.count > 0) {
1272         return inCheck ? MT_CHECK : MT_NONE;
1273     } else {
1274         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1275                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1276             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1277             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1278                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1279                     if(board[n][holdings] != EmptySquare) {
1280                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1281                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1282                     }
1283         }
1284         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1285                 return myPieces == hisPieces ? MT_STALEMATE :
1286                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1287         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1288         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1289
1290         return inCheck ? MT_CHECKMATE
1291                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || gameInfo.variant == VariantShogi) ?
1292                           MT_STAINMATE : MT_STALEMATE;
1293     }
1294 }
1295
1296
1297 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1298                                     int rf, int ff, int rt, int ft,
1299                                     VOIDSTAR closure));
1300
1301 void
1302 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1303 {
1304     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1305     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1306
1307     // [HGM] wild: for wild-card pieces rt and rf are dummies
1308     if(piece == WhiteFalcon || piece == BlackFalcon ||
1309        piece == WhiteCobra  || piece == BlackCobra)
1310         wildCard = TRUE;
1311
1312     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1313          || PieceToChar(board[rf][ff]) == '~'
1314               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1315                                                                       ) &&
1316         (cl->rfIn == -1 || cl->rfIn == rf) &&
1317         (cl->ffIn == -1 || cl->ffIn == ff) &&
1318         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1319         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1320
1321         cl->count++;
1322         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1323           // [HGM] oneclick: if multiple moves, be sure we remember capture
1324           cl->piece = board[rf][ff];
1325           cl->rf = rf;
1326           cl->ff = ff;
1327           cl->rt = wildCard ? cl->rtIn : rt;
1328           cl->ft = wildCard ? cl->ftIn : ft;
1329           cl->kind = kind;
1330         }
1331         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1332     }
1333 }
1334
1335 void
1336 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
1337 {
1338     int illegal = 0; char c = closure->promoCharIn;
1339
1340     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1341     closure->count = closure->captures = 0;
1342     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1343     closure->kind = ImpossibleMove;
1344     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
1345     fFilter = closure->ftIn;
1346     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
1347         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1348         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
1349             closure->count = closure->captures = 0;
1350             closure->rf = closure->ff = closure->rt = closure->ft = 0;
1351             closure->kind = ImpossibleMove;
1352             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1353         }
1354     } else
1355     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1356     if (closure->count == 0) {
1357         /* See if it's an illegal move due to check */
1358         illegal = 1;
1359         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1360         if (closure->count == 0) {
1361             /* No, it's not even that */
1362           if(!appData.testLegality && closure->pieceIn != EmptySquare) {
1363             int f, r; // if there is only a single piece of the requested type on the board, use that
1364             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
1365             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1366                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
1367             if(closure->count > 1) illegal = 0; // ambiguous
1368           }
1369           if(closure->count == 0) {
1370             if (appData.debugMode) { int i, j;
1371                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
1372                     for(j=0; j<BOARD_WIDTH; j++)
1373                         fprintf(debugFP, "%3d", (int) board[i][j]);
1374                     fprintf(debugFP, "\n");
1375                 }
1376             }
1377             return;
1378           }
1379         }
1380     }
1381
1382     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1383     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
1384         if(closure->piece < BlackPawn) { // white
1385             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
1386             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
1387             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
1388         } else {
1389             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
1390             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
1391             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
1392         }
1393     } else
1394     if(gameInfo.variant == VariantChu) {
1395         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
1396     } else
1397     if(gameInfo.variant == VariantShogi) {
1398         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1399         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1400             ChessSquare piece = closure->piece;
1401             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1402                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1403                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1404                    c = '+'; // allowed ICS notations
1405             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1406             else if(flags & F_WHITE_ON_MOVE) {
1407                 if( (int) piece < (int) WhiteWazir &&
1408                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1409                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1410                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1411                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1412                     else /* promotion optional, default is defer */
1413                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1414                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1415             } else {
1416                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1417                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1418                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1419                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1420                     else /* promotion optional, default is defer */
1421                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1422                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1423             }
1424         }
1425         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1426         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1427     } else
1428     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1429         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1430             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
1431                gameInfo.variant == VariantMakruk || gameInfo.variant == VariantASEAN)
1432                 c = PieceToChar(BlackFerz);
1433             else if(gameInfo.variant == VariantGreat)
1434                 c = PieceToChar(BlackMan);
1435             else if(gameInfo.variant == VariantGrand)
1436                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
1437             else
1438                 c = PieceToChar(BlackQueen);
1439         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1440     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1441
1442     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1443     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1444         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1445     if (closure->count > 1) {
1446         closure->kind = AmbiguousMove;
1447     }
1448     if (illegal) {
1449         /* Note: If more than one illegal move matches, but no legal
1450            moves, we return IllegalMove, not AmbiguousMove.  Caller
1451            can look at closure->count to detect this.
1452         */
1453         closure->kind = IllegalMove;
1454     }
1455 }
1456
1457
1458 typedef struct {
1459     /* Input */
1460     ChessSquare piece;
1461     int rf, ff, rt, ft;
1462     /* Output */
1463     ChessMove kind;
1464     int rank;
1465     int file;
1466     int either;
1467 } CoordsToAlgebraicClosure;
1468
1469 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1470                                          ChessMove kind, int rf, int ff,
1471                                          int rt, int ft, VOIDSTAR closure));
1472
1473 void
1474 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1475 {
1476     register CoordsToAlgebraicClosure *cl =
1477       (CoordsToAlgebraicClosure *) closure;
1478
1479     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
1480         (board[rf][ff] == cl->piece
1481          || PieceToChar(board[rf][ff]) == '~' &&
1482             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1483                                      ) {
1484         if (rf == cl->rf) {
1485             if (ff == cl->ff) {
1486                 cl->kind = kind; /* this is the move we want */
1487             } else {
1488                 cl->file++; /* need file to rule out this move */
1489             }
1490         } else {
1491             if (ff == cl->ff) {
1492                 cl->rank++; /* need rank to rule out this move */
1493             } else {
1494                 cl->either++; /* rank or file will rule out this move */
1495             }
1496         }
1497     }
1498 }
1499
1500 /* Convert coordinates to normal algebraic notation.
1501    promoChar must be NULLCHAR or 'x' if not a promotion.
1502 */
1503 ChessMove
1504 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
1505 {
1506     ChessSquare piece;
1507     ChessMove kind;
1508     char *outp = out, c;
1509     CoordsToAlgebraicClosure cl;
1510
1511     if (rf == DROP_RANK) {
1512         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
1513         /* Bughouse piece drop */
1514         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1515         *outp++ = '@';
1516         *outp++ = ft + AAA;
1517         if(rt+ONE <= '9')
1518            *outp++ = rt + ONE;
1519         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1520         *outp = NULLCHAR;
1521         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1522     }
1523
1524     if (promoChar == 'x') promoChar = NULLCHAR;
1525     piece = board[rf][ff];
1526     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1527
1528     switch (piece) {
1529       case WhitePawn:
1530       case BlackPawn:
1531         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1532         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1533             /* Keep short notation if move is illegal only because it
1534                leaves the player in check, but still return IllegalMove */
1535             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1536             if (kind == IllegalMove) break;
1537             kind = IllegalMove;
1538         }
1539         /* Pawn move */
1540         *outp++ = ff + AAA;
1541         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1542             /* Non-capture; use style "e5" */
1543             if(rt+ONE <= '9')
1544                *outp++ = rt + ONE;
1545             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1546         } else {
1547             /* Capture; use style "exd5" */
1548             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1549             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1550             *outp++ = ft + AAA;
1551             if(rt+ONE <= '9')
1552                *outp++ = rt + ONE;
1553             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1554         }
1555         /* Use promotion suffix style "=Q" */
1556         *outp = NULLCHAR;
1557         if (promoChar != NULLCHAR) {
1558             if(IS_SHOGI(gameInfo.variant)) {
1559                 /* [HGM] ... but not in Shogi! */
1560                 *outp++ = promoChar == '=' ? '=' : '+';
1561             } else {
1562                 *outp++ = '=';
1563                 *outp++ = ToUpper(promoChar);
1564             }
1565             *outp = NULLCHAR;
1566         }
1567         return kind;
1568
1569
1570       case WhiteKing:
1571       case BlackKing:
1572         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1573         /* Code added by Tord:  FRC castling. */
1574         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1575            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1576           if(ft > ff)
1577             safeStrCpy(out, "O-O", MOVE_LEN);
1578           else
1579             safeStrCpy(out, "O-O-O", MOVE_LEN);
1580           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1581         }
1582         /* End of code added by Tord */
1583         /* Test for castling or ICS wild castling */
1584         /* Use style "O-O" (oh-oh) for PGN compatibility */
1585         else if (rf == rt &&
1586             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1587             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1588             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1589              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1590             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1591               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1592             else
1593               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1594
1595             /* This notation is always unambiguous, unless there are
1596                kings on both the d and e files, with "wild castling"
1597                possible for the king on the d file and normal castling
1598                possible for the other.  ICS rules for wild 9
1599                effectively make castling illegal for either king in
1600                this situation.  So I am not going to worry about it;
1601                I'll just generate an ambiguous O-O in this case.
1602             */
1603             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1604         }
1605
1606         /* else fall through */
1607       default:
1608         /* Piece move */
1609         cl.rf = rf;
1610         cl.ff = ff;
1611         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1612         cl.ft = fFilter = ft;
1613         cl.piece = piece;
1614         cl.kind = IllegalMove;
1615         cl.rank = cl.file = cl.either = 0;
1616         c = PieceToChar(piece) ;
1617         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
1618
1619         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1620             /* Generate pretty moves for moving into check, but
1621                still return IllegalMove.
1622             */
1623             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
1624             if (cl.kind == IllegalMove) break;
1625             cl.kind = IllegalMove;
1626         }
1627
1628         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1629            else "Ngf3" or "Ngxf7",
1630            else "N1f3" or "N5xf7",
1631            else "Ng1f3" or "Ng5xf7".
1632         */
1633         if( c == '~' || c == '+') {
1634            /* [HGM] print nonexistent piece as its demoted version */
1635            piece = (ChessSquare) (DEMOTED piece);
1636         }
1637         if(c=='+') *outp++ = c;
1638         *outp++ = ToUpper(PieceToChar(piece));
1639
1640         if (cl.file || (cl.either && !cl.rank)) {
1641             *outp++ = ff + AAA;
1642         }
1643         if (cl.rank) {
1644             if(rf+ONE <= '9')
1645                 *outp++ = rf + ONE;
1646             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1647         }
1648
1649         if(board[rt][ft] != EmptySquare)
1650           *outp++ = 'x';
1651
1652         *outp++ = ft + AAA;
1653         if(rt+ONE <= '9')
1654            *outp++ = rt + ONE;
1655         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1656         if (IS_SHOGI(gameInfo.variant)) {
1657             /* [HGM] in Shogi non-pawns can promote */
1658             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1659         }
1660         else if (gameInfo.variant != VariantSuper && promoChar &&
1661                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
1662             *outp++ = '=';
1663             *outp++ = ToUpper(promoChar);
1664         }
1665         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
1666             *outp++ = '/';
1667             *outp++ = ToUpper(promoChar);
1668         }
1669         *outp = NULLCHAR;
1670         return cl.kind;
1671
1672       case EmptySquare:
1673         /* Moving a nonexistent piece */
1674         break;
1675     }
1676
1677     /* Not a legal move, even ignoring check.
1678        If there was a piece on the from square,
1679        use style "Ng1g3" or "Ng1xe8";
1680        if there was a pawn or nothing (!),
1681        use style "g1g3" or "g1xe8".  Use "x"
1682        if a piece was on the to square, even
1683        a piece of the same color.
1684     */
1685     outp = out;
1686     c = 0;
1687     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1688         int r, f;
1689       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
1690                 c += (board[r][f] == piece); // count on-board pieces of given type
1691         *outp++ = ToUpper(PieceToChar(piece));
1692     }
1693   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
1694     *outp++ = ff + AAA;
1695     if(rf+ONE <= '9')
1696        *outp++ = rf + ONE;
1697     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1698   }
1699     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1700     *outp++ = ft + AAA;
1701     if(rt+ONE <= '9')
1702        *outp++ = rt + ONE;
1703     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1704     /* Use promotion suffix style "=Q" */
1705     if (promoChar != NULLCHAR && promoChar != 'x') {
1706         *outp++ = '=';
1707         *outp++ = ToUpper(promoChar);
1708     }
1709     *outp = NULLCHAR;
1710
1711     return IllegalMove;
1712 }
1713
1714 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1715
1716 typedef struct {
1717     /* Input */
1718     int rf, ff, rt, ft;
1719     /* Output */
1720     int recaptures;
1721 } ChaseClosure;
1722
1723 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1724
1725 int preyStackPointer, chaseStackPointer;
1726
1727 struct {
1728 unsigned char rf, ff, rt, ft;
1729 } chaseStack[100];
1730
1731 struct {
1732 unsigned char rank, file;
1733 } preyStack[100];
1734
1735
1736
1737
1738 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1739
1740 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1741                                 int rf, int ff, int rt, int ft,
1742                                 VOIDSTAR closure));
1743
1744 void
1745 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1746 {   // For adding captures that can lead to chase indictment to the chaseStack
1747     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1748     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1749     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1750     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1751     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1752     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1753     chaseStack[chaseStackPointer].rf = rf;
1754     chaseStack[chaseStackPointer].ff = ff;
1755     chaseStack[chaseStackPointer].rt = rt;
1756     chaseStack[chaseStackPointer].ft = ft;
1757     chaseStackPointer++;
1758 }
1759
1760 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1761                                 int rf, int ff, int rt, int ft,
1762                                 VOIDSTAR closure));
1763
1764 void
1765 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1766 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1767     int i;
1768     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1769
1770     if(board[rt][ft] == EmptySquare) return; // no capture
1771     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1772         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1773     }
1774     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1775     for(i=0; i<chaseStackPointer; i++) {
1776         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1777            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1778             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1779             chaseStack[i] = chaseStack[--chaseStackPointer];
1780             break;
1781         }
1782     }
1783 }
1784
1785 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1786                                 int rf, int ff, int rt, int ft,
1787                                 VOIDSTAR closure));
1788
1789 void
1790 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1791 {   // for determining if a piece (given through the closure) is protected
1792     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1793
1794     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1795     if(appData.debugMode && board[rt][ft] != EmptySquare)
1796         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1797 }
1798
1799 extern char moveList[MAX_MOVES][MOVE_LEN];
1800
1801 int
1802 PerpetualChase (int first, int last)
1803 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1804     int i, j, k, tail;
1805     ChaseClosure cl;
1806     ChessSquare captured;
1807
1808     preyStackPointer = 0;        // clear stack of chased pieces
1809     for(i=first; i<last; i+=2) { // for all positions with same side to move
1810         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1811         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1812         // determine all captures possible after the move, and put them on chaseStack
1813         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
1814         if(appData.debugMode) { int n;
1815             for(n=0; n<chaseStackPointer; n++)
1816                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1817                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1818             fprintf(debugFP, ": all capts\n");
1819         }
1820         // determine all captures possible before the move, and delete them from chaseStack
1821         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1822         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1823         cl.rt = moveList[i][3]-ONE;
1824         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1825         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
1826         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
1827         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
1828         if(appData.debugMode) { int n;
1829             for(n=0; n<chaseStackPointer; n++)
1830                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1831                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1832             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1833         }
1834         // chaseSack now contains all captures made possible by the move
1835         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1836             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1837             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1838
1839             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1840             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1841
1842             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1843                 continue; // C or H attack on R is always chase; leave on chaseStack
1844
1845             if(attacker == victim) {
1846                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1847                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1848                         // we can capture back with equal piece, so this is no chase but a sacrifice
1849                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1850                         j--; /* ! */ continue;
1851                 }
1852
1853             }
1854
1855             // the attack is on a lower piece, or on a pinned or blocked equal one
1856             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
1857             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
1858             // test if the victim is protected by a true protector. First make the capture.
1859             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1860             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1861             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1862             // Then test if the opponent can recapture
1863             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1864             cl.rt = chaseStack[j].rt;
1865             cl.ft = chaseStack[j].ft;
1866             if(appData.debugMode) {
1867                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1868             }
1869             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
1870             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
1871             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
1872             // unmake the capture
1873             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1874             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1875             // if a recapture was found, piece is protected, and we are not chasing it.
1876             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1877                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1878                 j--; /* ! */
1879             }
1880         }
1881         // chaseStack now contains all moves that chased
1882         if(appData.debugMode) { int n;
1883             for(n=0; n<chaseStackPointer; n++)
1884                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1885                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1886             fprintf(debugFP, ": chases\n");
1887         }
1888         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1889             for(j=0; j<chaseStackPointer; j++) {
1890                 preyStack[j].rank = chaseStack[j].rt;
1891                 preyStack[j].file = chaseStack[j].ft;
1892             }
1893             preyStackPointer = chaseStackPointer;
1894         }
1895         tail = 0;
1896         for(j=0; j<chaseStackPointer; j++) {
1897             for(k=0; k<preyStackPointer; k++) {
1898                 // search the victim of each chase move on the preyStack (first occurrence)
1899                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1900                     if(k < tail) break; // piece was already identified as still being chased
1901                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1902                     preyStack[tail] = preyStack[k];                // by swapping
1903                     preyStack[k] = preyStack[preyStackPointer];
1904                     tail++;
1905                     break;
1906                 }
1907             }
1908         }
1909         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1910         if(appData.debugMode) { int n;
1911             for(n=0; n<preyStackPointer; n++)
1912                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1913             fprintf(debugFP, "always chased upto ply %d\n", i);
1914         }
1915         // now adjust the location of the chased pieces according to opponent move
1916         for(j=0; j<preyStackPointer; j++) {
1917             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1918                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1919                 preyStack[j].rank = moveList[i+1][3]-ONE;
1920                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1921                 break;
1922             }
1923         }
1924     }
1925     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
1926                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
1927 }