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             case WhiteFalcon: // [HGM] wild: for wildcards, self-capture symbolizes move to anywhere
 626             case BlackFalcon:
 627             case WhiteCobra:
 628             case BlackCobra:
 629             case WhiteLance:
 630             case BlackLance:
 631               callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 632               break;
 633
 634           }
 635       }
 636 }
 637
 638
 639 typedef struct {
 640     MoveCallback cb;
 641     VOIDSTAR cl;
 642 } GenLegalClosure;
 643
 644 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
 645                                 int rf, int ff, int rt, int ft,
 646                                 VOIDSTAR closure));
 647
 648 void GenLegalCallback(board, flags, kind, rf, ff, rt, ft, closure)
 649      Board board;
 650      int flags;
 651      ChessMove kind;
 652      int rf, ff, rt, ft;
 653      VOIDSTAR closure;
 654 {
 655     register GenLegalClosure *cl = (GenLegalClosure *) closure;
 656
 657     if (!(flags & F_IGNORE_CHECK) &&
 658         CheckTest(board, flags, rf, ff, rt, ft,
 659                   kind == WhiteCapturesEnPassant ||
 660                   kind == BlackCapturesEnPassant)) return;
 661     if (flags & F_ATOMIC_CAPTURE) {
 662       if (board[rt][ft] != EmptySquare ||
 663           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
 664         int r, f;
 665         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
 666         if (board[rf][ff] == king) return;
 667         for (r = rt-1; r <= rt+1; r++) {
 668           for (f = ft-1; f <= ft+1; f++) {
 669             if (r >= 0 && r < BOARD_HEIGHT && f >= BOARD_LEFT && f < BOARD_RGHT &&
 670                 board[r][f] == king) return;
 671           }
 672         }
 673       }
 674     }
 675     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
 676 }
 677
 678
 679 typedef struct {
 680     int rf, ff, rt, ft;
 681     ChessMove kind;
 682     int captures; // [HGM] losers
 683 } LegalityTestClosure;
 684
 685
 686 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
 687    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
 688    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
 689    moves that would destroy your own king.  The CASTLE_OK flags are
 690    true if castling is not yet ruled out by a move of the king or
 691    rook.  Return TRUE if the player on move is currently in check and
 692    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
 693 int GenLegal(board, flags, callback, closure)
 694      Board board;
 695      int flags;
 696      MoveCallback callback;
 697      VOIDSTAR closure;
 698 {
 699     GenLegalClosure cl;
 700     int ff, ft, k, left, right;
 701     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
 702     ChessSquare wKing = WhiteKing, bKing = BlackKing, *castlingRights = board[CASTLING];
 703
 704     cl.cb = callback;
 705     cl.cl = closure;
 706     GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl);
 707
 708     if (!ignoreCheck &&
 709         CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE;
 710
 711     /* Generate castling moves */
 712     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
 713         wKing = WhiteUnicorn; bKing = BlackUnicorn;
 714     }
 715
 716     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
 717         if ((flags & F_WHITE_ON_MOVE) &&
 718             (flags & F_WHITE_KCASTLE_OK) &&
 719             board[0][ff] == wKing &&
 720             board[0][ff + 1] == EmptySquare &&
 721             board[0][ff + 2] == EmptySquare &&
 722             board[0][BOARD_RGHT-3] == EmptySquare &&
 723             board[0][BOARD_RGHT-2] == EmptySquare &&
 724             board[0][BOARD_RGHT-1] == WhiteRook &&
 725             castlingRights[0] != NoRights && /* [HGM] check rights */
 726             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
 727             (ignoreCheck ||
 728              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
 729               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
 730               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
 731               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
 732
 733             callback(board, flags,
 734                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
 735                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
 736         }
 737         if ((flags & F_WHITE_ON_MOVE) &&
 738             (flags & F_WHITE_QCASTLE_OK) &&
 739             board[0][ff] == wKing &&
 740             board[0][ff - 1] == EmptySquare &&
 741             board[0][ff - 2] == EmptySquare &&
 742             board[0][BOARD_LEFT+2] == EmptySquare &&
 743             board[0][BOARD_LEFT+1] == EmptySquare &&
 744             board[0][BOARD_LEFT+0] == WhiteRook &&
 745             castlingRights[1] != NoRights && /* [HGM] check rights */
 746             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
 747             (ignoreCheck ||
 748              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
 749               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
 750               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
 751
 752             callback(board, flags,
 753                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
 754                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
 755         }
 756         if (!(flags & F_WHITE_ON_MOVE) &&
 757             (flags & F_BLACK_KCASTLE_OK) &&
 758             board[BOARD_HEIGHT-1][ff] == bKing &&
 759             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
 760             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
 761             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
 762             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
 763             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
 764             castlingRights[3] != NoRights && /* [HGM] check rights */
 765             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
 766             (ignoreCheck ||
 767              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
 768               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
 769               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
 770               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
 771
 772             callback(board, flags,
 773                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
 774                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
 775         }
 776         if (!(flags & F_WHITE_ON_MOVE) &&
 777             (flags & F_BLACK_QCASTLE_OK) &&
 778             board[BOARD_HEIGHT-1][ff] == bKing &&
 779             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
 780             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
 781             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
 782             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
 783             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
 784             castlingRights[4] != NoRights && /* [HGM] check rights */
 785             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
 786             (ignoreCheck ||
 787              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
 788               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
 789               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
 790
 791             callback(board, flags,
 792                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
 793                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
 794         }
 795     }
 796
 797   if(flags & F_FRC_TYPE_CASTLING) {
 798
 799     /* generate all potential FRC castling moves (KxR), ignoring flags */
 800     /* [HGM] test if the Rooks we find have castling rights */
 801
 802
 803     if ((flags & F_WHITE_ON_MOVE) != 0) {
 804         ff = castlingRights[2]; /* King file if we have any rights */
 805         if(ff != NoRights && board[0][ff] == WhiteKing) {
 806     if (appData.debugMode) {
 807         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
 808                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
 809     }
 810             ft = castlingRights[0]; /* Rook file if we have H-side rights */
 811             left  = ff+1;
 812             right = BOARD_RGHT-2;
 813             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
 814             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
 815                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
 816             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
 817                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
 818             if(ft != NoRights && board[0][ft] == WhiteRook)
 819                 callback(board, flags, WhiteHSideCastleFR, 0, ff, 0, ft, closure);
 820
 821             ft = castlingRights[1]; /* Rook file if we have A-side rights */
 822             left  = BOARD_LEFT+2;
 823             right = ff-1;
 824             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
 825             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
 826                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
 827             if(ff > BOARD_LEFT+2)
 828             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
 829                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
 830             if(ft != NoRights && board[0][ft] == WhiteRook)
 831                 callback(board, flags, WhiteASideCastleFR, 0, ff, 0, ft, closure);
 832         }
 833     } else {
 834         ff = castlingRights[5]; /* King file if we have any rights */
 835         if(ff != NoRights && board[BOARD_HEIGHT-1][ff] == BlackKing) {
 836             ft = castlingRights[3]; /* Rook file if we have H-side rights */
 837             left  = ff+1;
 838             right = BOARD_RGHT-2;
 839             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
 840             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
 841                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
 842             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
 843                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
 844             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
 845                 callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
 846
 847             ft = castlingRights[4]; /* Rook file if we have A-side rights */
 848             left  = BOARD_LEFT+2;
 849             right = ff-1;
 850             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
 851             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
 852                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
 853             if(ff > BOARD_LEFT+2)
 854             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
 855                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
 856             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
 857                 callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
 858         }
 859     }
 860
 861   }
 862
 863     return FALSE;
 864 }
 865
 866
 867 typedef struct {
 868     int rking, fking;
 869     int check;
 870 } CheckTestClosure;
 871
 872
 873 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
 874                                  int rf, int ff, int rt, int ft,
 875                                  VOIDSTAR closure));
 876
 877
 878 void CheckTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 879      Board board;
 880      int flags;
 881      ChessMove kind;
 882      int rf, ff, rt, ft;
 883      VOIDSTAR closure;
 884 {
 885     register CheckTestClosure *cl = (CheckTestClosure *) closure;
 886
 887     if (rt == cl->rking && ft == cl->fking) cl->check++;
 888 }
 889
 890
 891 /* If the player on move were to move from (rf, ff) to (rt, ft), would
 892    he leave himself in check?  Or if rf == -1, is the player on move
 893    in check now?  enPassant must be TRUE if the indicated move is an
 894    e.p. capture.  The possibility of castling out of a check along the
 895    back rank is not accounted for (i.e., we still return nonzero), as
 896    this is illegal anyway.  Return value is the number of times the
 897    king is in check. */
 898 int CheckTest(board, flags, rf, ff, rt, ft, enPassant)
 899      Board board;
 900      int flags;
 901      int rf, ff, rt, ft, enPassant;
 902 {
 903     CheckTestClosure cl;
 904     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
 905     ChessSquare captured = EmptySquare;
 906     /*  Suppress warnings on uninitialized variables    */
 907
 908     if(gameInfo.variant == VariantXiangqi)
 909         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
 910     if(gameInfo.variant == VariantKnightmate)
 911         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
 912
 913     if (rf >= 0) {
 914         if (enPassant) {
 915             captured = board[rf][ft];
 916             board[rf][ft] = EmptySquare;
 917         } else {
 918             captured = board[rt][ft];
 919         }
 920         board[rt][ft] = board[rf][ff];
 921         board[rf][ff] = EmptySquare;
 922     } else board[rt][ft] = ff; // [HGM] drop
 923
 924     /* For compatibility with ICS wild 9, we scan the board in the
 925        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
 926        and we test only whether that one is in check. */
 927     cl.check = 0;
 928     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
 929         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
 930           if (board[cl.rking][cl.fking] == king) {
 931               if(gameInfo.variant == VariantXiangqi) {
 932                   /* [HGM] In Xiangqi opposing Kings means check as well */
 933                   int i, dir;
 934                   dir = (king >= BlackPawn) ? -1 : 1;
 935                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
 936                                 board[i][cl.fking] == EmptySquare; i+=dir );
 937                   if(i>=0 && i<BOARD_HEIGHT &&
 938                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
 939                           cl.check++;
 940               }
 941
 942               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl);
 943               goto undo_move;  /* 2-level break */
 944           }
 945       }
 946
 947   undo_move:
 948
 949     if (rf >= 0) {
 950         board[rf][ff] = board[rt][ft];
 951         if (enPassant) {
 952             board[rf][ft] = captured;
 953             board[rt][ft] = EmptySquare;
 954         } else {
 955             board[rt][ft] = captured;
 956         }
 957     } else board[rt][ft] = EmptySquare; // [HGM] drop
 958
 959     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
 960 }
 961
 962 ChessMove LegalDrop(board, flags, piece, rt, ft)
 963      Board board;
 964      int flags;
 965      ChessSquare piece;
 966      int rt, ft;
 967 {   // [HGM] put drop legality testing in separate routine for clarity
 968     int n;
 969 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
 970     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
 971     n = PieceToNumber(piece);
 972     if(gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
 973         return ImpossibleMove; // piece not available
 974     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
 975         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
 976            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
 977             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
 978             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
 979         if(piece == WhitePawn || piece == BlackPawn) {
 980             int r;
 981             for(r=1; r<BOARD_HEIGHT-1; r++)
 982                 if(board[r][ft] == piece) return IllegalMove; // or there already is a Pawn in file
 983             // should still test if we mate with this Pawn
 984         }
 985     } else {
 986         if( (piece == WhitePawn || piece == BlackPawn) &&
 987             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
 988             return IllegalMove; /* no pawn drops on 1st/8th */
 989     }
 990 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
 991     if (!(flags & F_IGNORE_CHECK) &&
 992         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
 993     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
 994 }
 995
 996 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
 997                                     int rf, int ff, int rt, int ft,
 998                                     VOIDSTAR closure));
 999
1000 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1001      Board board;
1002      int flags;
1003      ChessMove kind;
1004      int rf, ff, rt, ft;
1005      VOIDSTAR closure;
1006 {
1007     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1008
1009 //    if (appData.debugMode) {
1010 //        fprintf(debugFP, "Legality test: %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1011 //    }
1012     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1013         cl->captures++; // [HGM] losers: count legal captures
1014     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1015       cl->kind = kind;
1016 }
1017
1018 ChessMove LegalityTest(board, flags, rf, ff, rt, ft, promoChar)
1019      Board board;
1020      int flags;
1021      int rf, ff, rt, ft, promoChar;
1022 {
1023     LegalityTestClosure cl; ChessSquare piece, *castlingRights = board[CASTLING];
1024
1025     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1026     piece = board[rf][ff];
1027
1028     if (appData.debugMode) {
1029         int i;
1030         for(i=0; i<6; i++) fprintf(debugFP, "%d ", castlingRights[i]);
1031         fprintf(debugFP, "Legality test? %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1032     }
1033     /* [HGM] Lance, Cobra and Falcon are wildcard pieces; consider all their moves legal */
1034     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1035     if(piece == WhiteFalcon || piece == BlackFalcon ||
1036        piece == WhiteCobra  || piece == BlackCobra  ||
1037        piece == WhiteLance  || piece == BlackLance)
1038         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1039
1040     cl.rf = rf;
1041     cl.ff = ff;
1042     cl.rt = rt;
1043     cl.ft = ft;
1044     cl.kind = IllegalMove;
1045     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1046     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl);
1047     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1048                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1049         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1050
1051     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1052     if(gameInfo.variant == VariantShogi) {
1053         /* [HGM] Shogi promotions. '=' means defer */
1054         if(rf != DROP_RANK && cl.kind == NormalMove) {
1055             ChessSquare piece = board[rf][ff];
1056
1057             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1058             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1059                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1060                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1061                   promoChar = '+'; // allowed ICS notations
1062 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1063             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1064                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1065             else if(flags & F_WHITE_ON_MOVE) {
1066                 if( (int) piece < (int) WhiteWazir &&
1067                      (rf >= BOARD_HEIGHT*2/3 || rt >= BOARD_HEIGHT*2/3) ) {
1068                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1069                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1070                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1071                     else /* promotion optional, default is defer */
1072                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1073                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1074             } else {
1075                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1076                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1077                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1078                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1079                     else /* promotion optional, default is defer */
1080                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1081                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1082             }
1083         }
1084     } else
1085     if (promoChar != NULLCHAR) {
1086         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1087         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1088             if(CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar)) == EmptySquare)
1089                 cl.kind = ImpossibleMove; // non-existing piece
1090         } else {
1091             cl.kind = IllegalMove;
1092         }
1093     }
1094     return cl.kind;
1095 }
1096
1097 typedef struct {
1098     int count;
1099 } MateTestClosure;
1100
1101 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1102                                 int rf, int ff, int rt, int ft,
1103                                 VOIDSTAR closure));
1104
1105 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1106      Board board;
1107      int flags;
1108      ChessMove kind;
1109      int rf, ff, rt, ft;
1110      VOIDSTAR closure;
1111 {
1112     register MateTestClosure *cl = (MateTestClosure *) closure;
1113
1114     cl->count++;
1115 }
1116
1117 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1118 int MateTest(board, flags)
1119      Board board;
1120      int flags;
1121 {
1122     MateTestClosure cl;
1123     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1124     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1125
1126     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1127         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1128         nrKing += (board[r][f] == king);   // stm has king
1129         if( board[r][f] != EmptySquare ) {
1130             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1131                  myPieces++;
1132             else hisPieces++;
1133         }
1134     }
1135     if(appData.debugMode) fprintf(debugFP, "MateTest: K=%d, my=%d, his=%d\n", nrKing, myPieces, hisPieces);
1136     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1137         case VariantShatranj:
1138                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1139         default:
1140                 break;
1141         case VariantAtomic:
1142                 if(nrKing == 0) return MT_NOKING;
1143                 break;
1144         case VariantLosers:
1145                 if(myPieces == 1) return MT_BARE;
1146     }
1147     cl.count = 0;
1148     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl);
1149     // [HGM] 3check: yet to do!
1150     if (cl.count > 0) {
1151         return inCheck ? MT_CHECK : MT_NONE;
1152     } else {
1153         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper || gameInfo.variant != VariantGreat) { // drop game
1154             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1155             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1156                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1157                     if(board[n][holdings] != EmptySquare) {
1158                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1159                         if(moveType == WhiteDrop || moveType == BlackDrop) return MT_CHECK; // we can resolve check by legal drop
1160                     }
1161         }
1162         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1163                 return myPieces == hisPieces ? MT_STALEMATE :
1164                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1165         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1166         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1167
1168         return inCheck ? MT_CHECKMATE
1169                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1170                           MT_STAINMATE : MT_STALEMATE;
1171     }
1172 }
1173
1174
1175 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1176                                     int rf, int ff, int rt, int ft,
1177                                     VOIDSTAR closure));
1178
1179 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1180      Board board;
1181      int flags;
1182      ChessMove kind;
1183      int rf, ff, rt, ft;
1184      VOIDSTAR closure;
1185 {
1186     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1187     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1188
1189     // [HGM] wild: for wild-card pieces rt and rf are dummies
1190     if(piece == WhiteFalcon || piece == BlackFalcon ||
1191        piece == WhiteCobra  || piece == BlackCobra  ||
1192        piece == WhiteLance  || piece == BlackLance)
1193         wildCard = TRUE;
1194
1195     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1196          || PieceToChar(board[rf][ff]) == '~'
1197               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1198                                                                       ) &&
1199         (cl->rfIn == -1 || cl->rfIn == rf) &&
1200         (cl->ffIn == -1 || cl->ffIn == ff) &&
1201         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1202         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1203
1204         cl->count++;
1205         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1206           // [HGM] oneclick: if multiple moves, be sure we remember capture
1207           cl->piece = board[rf][ff];
1208           cl->rf = rf;
1209           cl->ff = ff;
1210           cl->rt = wildCard ? cl->rtIn : rt;
1211           cl->ft = wildCard ? cl->ftIn : ft;
1212           cl->kind = kind;
1213         }
1214         cl->captures += (board[cl->rt][cl->ft] != EmptySquare); // [HGM] oneclick: count captures
1215     }
1216 }
1217
1218 void Disambiguate(board, flags, closure)
1219      Board board;
1220      int flags;
1221      DisambiguateClosure *closure;
1222 {
1223     int illegal = 0; char c = closure->promoCharIn;
1224
1225     closure->count = closure->captures = 0;
1226     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1227     closure->kind = ImpossibleMove;
1228     if (appData.debugMode) {
1229         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1230                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1231                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1232     }
1233     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure);
1234     if (closure->count == 0) {
1235         /* See if it's an illegal move due to check */
1236         illegal = 1;
1237         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure);
1238         if (closure->count == 0) {
1239             /* No, it's not even that */
1240     if (appData.debugMode) { int i, j;
1241         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1242                 for(j=0; j<BOARD_WIDTH; j++)
1243                         fprintf(debugFP, "%3d", (int) board[i][j]);
1244                 fprintf(debugFP, "\n");
1245         }
1246     }
1247             return;
1248         }
1249     }
1250
1251     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1252     if(gameInfo.variant == VariantShogi) {
1253         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1254         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1255             ChessSquare piece = closure->piece;
1256             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1257                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1258                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1259                    c = '+'; // allowed ICS notations
1260             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1261             else if(flags & F_WHITE_ON_MOVE) {
1262                 if( (int) piece < (int) WhiteWazir &&
1263                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1264                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1265                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1266                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1267                     else /* promotion optional, default is defer */
1268                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1269                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1270             } else {
1271                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1272                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1273                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1274                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1275                     else /* promotion optional, default is defer */
1276                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1277                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1278             }
1279         }
1280         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1281         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1282     } else
1283     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1284         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1285             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier || gameInfo.variant == VariantMakruk)
1286                 c = PieceToChar(BlackFerz);
1287             else if(gameInfo.variant == VariantGreat)
1288                 c = PieceToChar(BlackMan);
1289             else
1290                 c = PieceToChar(BlackQueen);
1291         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1292     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1293
1294     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1295     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1296         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1297     if (closure->count > 1) {
1298         closure->kind = AmbiguousMove;
1299     }
1300     if (illegal) {
1301         /* Note: If more than one illegal move matches, but no legal
1302            moves, we return IllegalMove, not AmbiguousMove.  Caller
1303            can look at closure->count to detect this.
1304         */
1305         closure->kind = IllegalMove;
1306     }
1307     if (appData.debugMode) {
1308         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1309         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1310         closure->promoChar >= ' ' ? closure->promoChar:'-');
1311     }
1312 }
1313
1314
1315 typedef struct {
1316     /* Input */
1317     ChessSquare piece;
1318     int rf, ff, rt, ft;
1319     /* Output */
1320     ChessMove kind;
1321     int rank;
1322     int file;
1323     int either;
1324 } CoordsToAlgebraicClosure;
1325
1326 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1327                                          ChessMove kind, int rf, int ff,
1328                                          int rt, int ft, VOIDSTAR closure));
1329
1330 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1331      Board board;
1332      int flags;
1333      ChessMove kind;
1334      int rf, ff, rt, ft;
1335      VOIDSTAR closure;
1336 {
1337     register CoordsToAlgebraicClosure *cl =
1338       (CoordsToAlgebraicClosure *) closure;
1339
1340     if (rt == cl->rt && ft == cl->ft &&
1341         (board[rf][ff] == cl->piece
1342          || PieceToChar(board[rf][ff]) == '~' &&
1343             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1344                                      ) {
1345         if (rf == cl->rf) {
1346             if (ff == cl->ff) {
1347                 cl->kind = kind; /* this is the move we want */
1348             } else {
1349                 cl->file++; /* need file to rule out this move */
1350             }
1351         } else {
1352             if (ff == cl->ff) {
1353                 cl->rank++; /* need rank to rule out this move */
1354             } else {
1355                 cl->either++; /* rank or file will rule out this move */
1356             }
1357         }
1358     }
1359 }
1360
1361 /* Convert coordinates to normal algebraic notation.
1362    promoChar must be NULLCHAR or 'x' if not a promotion.
1363 */
1364 ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out)
1365      Board board;
1366      int flags;
1367      int rf, ff, rt, ft;
1368      int promoChar;
1369      char out[MOVE_LEN];
1370 {
1371     ChessSquare piece;
1372     ChessMove kind;
1373     char *outp = out, c;
1374     CoordsToAlgebraicClosure cl;
1375
1376     if (rf == DROP_RANK) {
1377         /* Bughouse piece drop */
1378         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1379         *outp++ = '@';
1380         *outp++ = ft + AAA;
1381         if(rt+ONE <= '9')
1382            *outp++ = rt + ONE;
1383         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1384         *outp = NULLCHAR;
1385         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1386     }
1387
1388     if (promoChar == 'x') promoChar = NULLCHAR;
1389     piece = board[rf][ff];
1390     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1391
1392   if (appData.debugMode)
1393           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1394     switch (piece) {
1395       case WhitePawn:
1396       case BlackPawn:
1397         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1398         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1399             /* Keep short notation if move is illegal only because it
1400                leaves the player in check, but still return IllegalMove */
1401             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1402             if (kind == IllegalMove) break;
1403             kind = IllegalMove;
1404         }
1405         /* Pawn move */
1406         *outp++ = ff + AAA;
1407         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1408             /* Non-capture; use style "e5" */
1409             if(rt+ONE <= '9')
1410                *outp++ = rt + ONE;
1411             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1412         } else {
1413             /* Capture; use style "exd5" */
1414             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1415             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1416             *outp++ = ft + AAA;
1417             if(rt+ONE <= '9')
1418                *outp++ = rt + ONE;
1419             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1420         }
1421         /* Use promotion suffix style "=Q" */
1422         *outp = NULLCHAR;
1423   if (appData.debugMode)
1424           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1425         if (promoChar != NULLCHAR) {
1426             if(gameInfo.variant == VariantShogi) {
1427                 /* [HGM] ... but not in Shogi! */
1428                 *outp++ = promoChar == '=' ? '=' : '+';
1429             } else {
1430                 *outp++ = '=';
1431                 *outp++ = ToUpper(promoChar);
1432             }
1433             *outp = NULLCHAR;
1434         }
1435         return kind;
1436
1437
1438       case WhiteKing:
1439       case BlackKing:
1440         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1441         /* Code added by Tord:  FRC castling. */
1442         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1443            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1444           if(ft > ff)
1445             safeStrCpy(out, "O-O", MOVE_LEN);
1446           else
1447             safeStrCpy(out, "O-O-O", MOVE_LEN);
1448           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1449         }
1450         /* End of code added by Tord */
1451         /* Test for castling or ICS wild castling */
1452         /* Use style "O-O" (oh-oh) for PGN compatibility */
1453         else if (rf == rt &&
1454             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1455             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1456             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1457              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1458             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1459               safeStrCpy(out, "O-O", MOVE_LEN);
1460             else
1461               safeStrCpy(out, "O-O-O", MOVE_LEN);
1462
1463             /* This notation is always unambiguous, unless there are
1464                kings on both the d and e files, with "wild castling"
1465                possible for the king on the d file and normal castling
1466                possible for the other.  ICS rules for wild 9
1467                effectively make castling illegal for either king in
1468                this situation.  So I am not going to worry about it;
1469                I'll just generate an ambiguous O-O in this case.
1470             */
1471             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1472         }
1473
1474         /* else fall through */
1475       default:
1476         /* Piece move */
1477         cl.rf = rf;
1478         cl.ff = ff;
1479         cl.rt = rt;
1480         cl.ft = ft;
1481         cl.piece = piece;
1482         cl.kind = IllegalMove;
1483         cl.rank = cl.file = cl.either = 0;
1484         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1485
1486         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1487             /* Generate pretty moves for moving into check, but
1488                still return IllegalMove.
1489             */
1490             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1491             if (cl.kind == IllegalMove) break;
1492             cl.kind = IllegalMove;
1493         }
1494
1495         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1496            else "Ngf3" or "Ngxf7",
1497            else "N1f3" or "N5xf7",
1498            else "Ng1f3" or "Ng5xf7".
1499         */
1500         c = PieceToChar(piece) ;
1501         if( c == '~' || c == '+') {
1502            /* [HGM] print nonexistent piece as its demoted version */
1503            piece = (ChessSquare) (DEMOTED piece);
1504         }
1505         if(c=='+') *outp++ = c;
1506         *outp++ = ToUpper(PieceToChar(piece));
1507
1508         if (cl.file || (cl.either && !cl.rank)) {
1509             *outp++ = ff + AAA;
1510         }
1511         if (cl.rank) {
1512             if(rf+ONE <= '9')
1513                 *outp++ = rf + ONE;
1514             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1515         }
1516
1517         if(board[rt][ft] != EmptySquare)
1518           *outp++ = 'x';
1519
1520         *outp++ = ft + AAA;
1521         if(rt+ONE <= '9')
1522            *outp++ = rt + ONE;
1523         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1524         if (gameInfo.variant == VariantShogi) {
1525             /* [HGM] in Shogi non-pawns can promote */
1526             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1527         }
1528         *outp = NULLCHAR;
1529         return cl.kind;
1530
1531       /* [HGM] Always long notation for fairies we don't know */
1532       case WhiteFalcon:
1533       case BlackFalcon:
1534       case WhiteLance:
1535       case BlackLance:
1536       case WhiteGrasshopper:
1537       case BlackGrasshopper:
1538       case EmptySquare:
1539         /* Moving a nonexistent piece */
1540         break;
1541     }
1542
1543     /* Not a legal move, even ignoring check.
1544        If there was a piece on the from square,
1545        use style "Ng1g3" or "Ng1xe8";
1546        if there was a pawn or nothing (!),
1547        use style "g1g3" or "g1xe8".  Use "x"
1548        if a piece was on the to square, even
1549        a piece of the same color.
1550     */
1551     outp = out;
1552     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1553         *outp++ = ToUpper(PieceToChar(piece));
1554     }
1555     *outp++ = ff + AAA;
1556     if(rf+ONE <= '9')
1557        *outp++ = rf + ONE;
1558     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1559     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1560     *outp++ = ft + AAA;
1561     if(rt+ONE <= '9')
1562        *outp++ = rt + ONE;
1563     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1564     /* Use promotion suffix style "=Q" */
1565     if (promoChar != NULLCHAR && promoChar != 'x') {
1566         *outp++ = '=';
1567         *outp++ = ToUpper(promoChar);
1568     }
1569     *outp = NULLCHAR;
1570
1571     return IllegalMove;
1572 }
1573
1574 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1575
1576 typedef struct {
1577     /* Input */
1578     int rf, ff, rt, ft;
1579     /* Output */
1580     int recaptures;
1581 } ChaseClosure;
1582
1583 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1584
1585 int preyStackPointer, chaseStackPointer;
1586
1587 struct {
1588 char rf, ff, rt, ft;
1589 } chaseStack[100];
1590
1591 struct {
1592 char rank, file;
1593 } preyStack[100];
1594
1595
1596
1597
1598 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1599
1600 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1601                                 int rf, int ff, int rt, int ft,
1602                                 VOIDSTAR closure));
1603
1604 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1605      Board board;
1606      int flags;
1607      ChessMove kind;
1608      int rf, ff, rt, ft;
1609      VOIDSTAR closure;
1610 {   // For adding captures that can lead to chase indictment to the chaseStack
1611     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1612     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1613     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1614     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1615     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1616     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1617     chaseStack[chaseStackPointer].rf = rf;
1618     chaseStack[chaseStackPointer].ff = ff;
1619     chaseStack[chaseStackPointer].rt = rt;
1620     chaseStack[chaseStackPointer].ft = ft;
1621     chaseStackPointer++;
1622 }
1623
1624 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1625                                 int rf, int ff, int rt, int ft,
1626                                 VOIDSTAR closure));
1627
1628 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1629      Board board;
1630      int flags;
1631      ChessMove kind;
1632      int rf, ff, rt, ft;
1633      VOIDSTAR closure;
1634 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1635     int i;
1636     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1637
1638     if(board[rt][ft] == EmptySquare) return; // no capture
1639     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1640         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1641     }
1642     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1643     for(i=0; i<chaseStackPointer; i++) {
1644         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1645            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1646             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1647             chaseStack[i] = chaseStack[--chaseStackPointer];
1648             break;
1649         }
1650     }
1651 }
1652
1653 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1654                                 int rf, int ff, int rt, int ft,
1655                                 VOIDSTAR closure));
1656
1657 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1658      Board board;
1659      int flags;
1660      ChessMove kind;
1661      int rf, ff, rt, ft;
1662      VOIDSTAR closure;
1663 {   // for determining if a piece (given through the closure) is protected
1664     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1665
1666     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1667     if(appData.debugMode && board[rt][ft] != EmptySquare)
1668         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1669 }
1670
1671 extern char moveList[MAX_MOVES][MOVE_LEN];
1672
1673 int PerpetualChase(int first, int last)
1674 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1675     int i, j, k, tail;
1676     ChaseClosure cl;
1677     ChessSquare captured;
1678
1679     preyStackPointer = 0;        // clear stack of chased pieces
1680     for(i=first; i<last; i+=2) { // for all positions with same side to move
1681         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1682         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1683         // determine all captures possible after the move, and put them on chaseStack
1684         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl);
1685         if(appData.debugMode) { int n;
1686             for(n=0; n<chaseStackPointer; n++)
1687                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1688                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1689             fprintf(debugFP, ": all capts\n");
1690         }
1691         // determine all captures possible before the move, and delete them from chaseStack
1692         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1693         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1694         cl.rt = moveList[i][3]-ONE;
1695         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1696         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl);
1697         if(appData.debugMode) { int n;
1698             for(n=0; n<chaseStackPointer; n++)
1699                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1700                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1701             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1702         }
1703         // chaseSack now contains all captures made possible by the move
1704         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1705             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1706             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1707
1708             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1709             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1710
1711             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1712                 continue; // C or H attack on R is always chase; leave on chaseStack
1713
1714             if(attacker == victim) {
1715                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1716                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1717                         // we can capture back with equal piece, so this is no chase but a sacrifice
1718                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1719                         j--; /* ! */ continue;
1720                 }
1721
1722             }
1723
1724             // the attack is on a lower piece, or on a pinned or blocked equal one
1725             // test if the victim is protected by a true protector. First make the capture.
1726             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1727             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1728             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1729             // Then test if the opponent can recapture
1730             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1731             cl.rt = chaseStack[j].rt;
1732             cl.ft = chaseStack[j].ft;
1733             if(appData.debugMode) {
1734                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1735             }
1736             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl); // try all moves
1737             // unmake the capture
1738             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1739             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1740             // if a recapture was found, piece is protected, and we are not chasing it.
1741             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1742                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1743                 j--; /* ! */
1744             }
1745         }
1746         // chaseStack now contains all moves that chased
1747         if(appData.debugMode) { int n;
1748             for(n=0; n<chaseStackPointer; n++)
1749                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1750                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1751             fprintf(debugFP, ": chases\n");
1752         }
1753         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1754             for(j=0; j<chaseStackPointer; j++) {
1755                 preyStack[j].rank = chaseStack[j].rt;
1756                 preyStack[j].file = chaseStack[j].ft;
1757             }
1758             preyStackPointer = chaseStackPointer;
1759         }
1760         tail = 0;
1761         for(j=0; j<chaseStackPointer; j++) {
1762             for(k=0; k<preyStackPointer; k++) {
1763                 // search the victim of each chase move on the preyStack (first occurrence)
1764                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1765                     if(k < tail) break; // piece was already identified as still being chased
1766                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1767                     preyStack[tail] = preyStack[k];                // by swapping
1768                     preyStack[k] = preyStack[preyStackPointer];
1769                     tail++;
1770                     break;
1771                 }
1772             }
1773         }
1774         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1775         if(appData.debugMode) { int n;
1776             for(n=0; n<preyStackPointer; n++)
1777                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1778             fprintf(debugFP, "always chased upto ply %d\n", i);
1779         }
1780         // now adjust the location of the chased pieces according to opponent move
1781         for(j=0; j<preyStackPointer; j++) {
1782             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1783                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1784                 preyStack[j].rank = moveList[i+1][3]-ONE;
1785                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1786                 break;
1787             }
1788         }
1789     }
1790     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1791 }