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