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