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(promoChar) == EmptySquare) cl.kind = ImpossibleMove; // non-existing piece
1089         } else {
1090             cl.kind = IllegalMove;
1091         }
1092     }
1093     return cl.kind;
1094 }
1095
1096 typedef struct {
1097     int count;
1098 } MateTestClosure;
1099
1100 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1101                                 int rf, int ff, int rt, int ft,
1102                                 VOIDSTAR closure));
1103
1104 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1105      Board board;
1106      int flags;
1107      ChessMove kind;
1108      int rf, ff, rt, ft;
1109      VOIDSTAR closure;
1110 {
1111     register MateTestClosure *cl = (MateTestClosure *) closure;
1112
1113     cl->count++;
1114 }
1115
1116 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1117 int MateTest(board, flags)
1118      Board board;
1119      int flags;
1120 {
1121     MateTestClosure cl;
1122     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1123     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1124
1125     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1126         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1127         nrKing += (board[r][f] == king);   // stm has king
1128         if( board[r][f] != EmptySquare ) {
1129             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1130                  myPieces++;
1131             else hisPieces++;
1132         }
1133     }
1134     if(appData.debugMode) fprintf(debugFP, "MateTest: K=%d, my=%d, his=%d\n", nrKing, myPieces, hisPieces);
1135     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1136         case VariantShatranj:
1137                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1138         default:
1139                 break;
1140         case VariantAtomic:
1141                 if(nrKing == 0) return MT_NOKING;
1142                 break;
1143         case VariantLosers:
1144                 if(myPieces == 1) return MT_BARE;
1145     }
1146     cl.count = 0;
1147     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl);
1148     // [HGM] 3check: yet to do!
1149     if (cl.count > 0) {
1150         return inCheck ? MT_CHECK : MT_NONE;
1151     } else {
1152         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper || gameInfo.variant != VariantGreat) { // drop game
1153             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1154             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1155                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1156                     if(board[n][holdings] != EmptySquare) {
1157                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1158                         if(moveType == WhiteDrop || moveType == BlackDrop) return MT_CHECK; // we can resolve check by legal drop
1159                     }
1160         }
1161         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1162                 return myPieces == hisPieces ? MT_STALEMATE :
1163                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1164         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1165         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1166
1167         return inCheck ? MT_CHECKMATE
1168                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1169                           MT_STAINMATE : MT_STALEMATE;
1170     }
1171 }
1172
1173
1174 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1175                                     int rf, int ff, int rt, int ft,
1176                                     VOIDSTAR closure));
1177
1178 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1179      Board board;
1180      int flags;
1181      ChessMove kind;
1182      int rf, ff, rt, ft;
1183      VOIDSTAR closure;
1184 {
1185     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1186     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1187
1188     // [HGM] wild: for wild-card pieces rt and rf are dummies
1189     if(piece == WhiteFalcon || piece == BlackFalcon ||
1190        piece == WhiteCobra  || piece == BlackCobra  ||
1191        piece == WhiteLance  || piece == BlackLance)
1192         wildCard = TRUE;
1193
1194     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1195          || PieceToChar(board[rf][ff]) == '~'
1196               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1197                                                                       ) &&
1198         (cl->rfIn == -1 || cl->rfIn == rf) &&
1199         (cl->ffIn == -1 || cl->ffIn == ff) &&
1200         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1201         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1202
1203         cl->count++;
1204         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1205           // [HGM] oneclick: if multiple moves, be sure we remember capture
1206           cl->piece = board[rf][ff];
1207           cl->rf = rf;
1208           cl->ff = ff;
1209           cl->rt = wildCard ? cl->rtIn : rt;
1210           cl->ft = wildCard ? cl->ftIn : ft;
1211           cl->kind = kind;
1212         }
1213         cl->captures += (board[cl->rt][cl->ft] != EmptySquare); // [HGM] oneclick: count captures
1214     }
1215 }
1216
1217 void Disambiguate(board, flags, closure)
1218      Board board;
1219      int flags;
1220      DisambiguateClosure *closure;
1221 {
1222     int illegal = 0; char c = closure->promoCharIn;
1223
1224     closure->count = closure->captures = 0;
1225     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1226     closure->kind = ImpossibleMove;
1227     if (appData.debugMode) {
1228         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1229                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1230                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1231     }
1232     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure);
1233     if (closure->count == 0) {
1234         /* See if it's an illegal move due to check */
1235         illegal = 1;
1236         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure);
1237         if (closure->count == 0) {
1238             /* No, it's not even that */
1239     if (appData.debugMode) { int i, j;
1240         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1241                 for(j=0; j<BOARD_WIDTH; j++)
1242                         fprintf(debugFP, "%3d", (int) board[i][j]);
1243                 fprintf(debugFP, "\n");
1244         }
1245     }
1246             return;
1247         }
1248     }
1249
1250     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1251     if(gameInfo.variant == VariantShogi) {
1252         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1253         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1254             ChessSquare piece = closure->piece;
1255             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1256                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1257                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1258                    c = '+'; // allowed ICS notations
1259             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1260             else if(flags & F_WHITE_ON_MOVE) {
1261                 if( (int) piece < (int) WhiteWazir &&
1262                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1263                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1264                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1265                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1266                     else /* promotion optional, default is defer */
1267                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1268                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1269             } else {
1270                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1271                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1272                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1273                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1274                     else /* promotion optional, default is defer */
1275                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1276                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1277             }
1278         }
1279         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1280         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1281     } else
1282     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1283         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1284             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier || gameInfo.variant == VariantMakruk)
1285                 c = PieceToChar(BlackFerz);
1286             else if(gameInfo.variant == VariantGreat)
1287                 c = PieceToChar(BlackMan);
1288             else
1289                 c = PieceToChar(BlackQueen);
1290         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1291     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1292
1293     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1294     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(c) == EmptySquare)
1295         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1296     if (closure->count > 1) {
1297         closure->kind = AmbiguousMove;
1298     }
1299     if (illegal) {
1300         /* Note: If more than one illegal move matches, but no legal
1301            moves, we return IllegalMove, not AmbiguousMove.  Caller
1302            can look at closure->count to detect this.
1303         */
1304         closure->kind = IllegalMove;
1305     }
1306     if (appData.debugMode) {
1307         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1308         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1309         closure->promoChar >= ' ' ? closure->promoChar:'-');
1310     }
1311 }
1312
1313
1314 typedef struct {
1315     /* Input */
1316     ChessSquare piece;
1317     int rf, ff, rt, ft;
1318     /* Output */
1319     ChessMove kind;
1320     int rank;
1321     int file;
1322     int either;
1323 } CoordsToAlgebraicClosure;
1324
1325 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1326                                          ChessMove kind, int rf, int ff,
1327                                          int rt, int ft, VOIDSTAR closure));
1328
1329 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1330      Board board;
1331      int flags;
1332      ChessMove kind;
1333      int rf, ff, rt, ft;
1334      VOIDSTAR closure;
1335 {
1336     register CoordsToAlgebraicClosure *cl =
1337       (CoordsToAlgebraicClosure *) closure;
1338
1339     if (rt == cl->rt && ft == cl->ft &&
1340         (board[rf][ff] == cl->piece
1341          || PieceToChar(board[rf][ff]) == '~' &&
1342             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1343                                      ) {
1344         if (rf == cl->rf) {
1345             if (ff == cl->ff) {
1346                 cl->kind = kind; /* this is the move we want */
1347             } else {
1348                 cl->file++; /* need file to rule out this move */
1349             }
1350         } else {
1351             if (ff == cl->ff) {
1352                 cl->rank++; /* need rank to rule out this move */
1353             } else {
1354                 cl->either++; /* rank or file will rule out this move */
1355             }
1356         }
1357     }
1358 }
1359
1360 /* Convert coordinates to normal algebraic notation.
1361    promoChar must be NULLCHAR or 'x' if not a promotion.
1362 */
1363 ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out)
1364      Board board;
1365      int flags;
1366      int rf, ff, rt, ft;
1367      int promoChar;
1368      char out[MOVE_LEN];
1369 {
1370     ChessSquare piece;
1371     ChessMove kind;
1372     char *outp = out, c;
1373     CoordsToAlgebraicClosure cl;
1374
1375     if (rf == DROP_RANK) {
1376         /* Bughouse piece drop */
1377         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1378         *outp++ = '@';
1379         *outp++ = ft + AAA;
1380         if(rt+ONE <= '9')
1381            *outp++ = rt + ONE;
1382         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1383         *outp = NULLCHAR;
1384         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1385     }
1386
1387     if (promoChar == 'x') promoChar = NULLCHAR;
1388     piece = board[rf][ff];
1389     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1390
1391   if (appData.debugMode)
1392           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1393     switch (piece) {
1394       case WhitePawn:
1395       case BlackPawn:
1396         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1397         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1398             /* Keep short notation if move is illegal only because it
1399                leaves the player in check, but still return IllegalMove */
1400             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1401             if (kind == IllegalMove) break;
1402             kind = IllegalMove;
1403         }
1404         /* Pawn move */
1405         *outp++ = ff + AAA;
1406         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1407             /* Non-capture; use style "e5" */
1408             if(rt+ONE <= '9')
1409                *outp++ = rt + ONE;
1410             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1411         } else {
1412             /* Capture; use style "exd5" */
1413             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1414             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1415             *outp++ = ft + AAA;
1416             if(rt+ONE <= '9')
1417                *outp++ = rt + ONE;
1418             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1419         }
1420         /* Use promotion suffix style "=Q" */
1421         *outp = NULLCHAR;
1422   if (appData.debugMode)
1423           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1424         if (promoChar != NULLCHAR) {
1425             if(gameInfo.variant == VariantShogi) {
1426                 /* [HGM] ... but not in Shogi! */
1427                 *outp++ = promoChar == '=' ? '=' : '+';
1428             } else {
1429                 *outp++ = '=';
1430                 *outp++ = ToUpper(promoChar);
1431             }
1432             *outp = NULLCHAR;
1433         }
1434         return kind;
1435
1436
1437       case WhiteKing:
1438       case BlackKing:
1439         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1440         /* Code added by Tord:  FRC castling. */
1441         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1442            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1443           if(ft > ff)
1444             safeStrCpy(out, "O-O", MOVE_LEN);
1445           else
1446             safeStrCpy(out, "O-O-O", MOVE_LEN);
1447           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1448         }
1449         /* End of code added by Tord */
1450         /* Test for castling or ICS wild castling */
1451         /* Use style "O-O" (oh-oh) for PGN compatibility */
1452         else if (rf == rt &&
1453             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1454             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1455             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1456              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1457             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1458               safeStrCpy(out, "O-O", MOVE_LEN);
1459             else
1460               safeStrCpy(out, "O-O-O", MOVE_LEN);
1461
1462             /* This notation is always unambiguous, unless there are
1463                kings on both the d and e files, with "wild castling"
1464                possible for the king on the d file and normal castling
1465                possible for the other.  ICS rules for wild 9
1466                effectively make castling illegal for either king in
1467                this situation.  So I am not going to worry about it;
1468                I'll just generate an ambiguous O-O in this case.
1469             */
1470             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1471         }
1472
1473         /* else fall through */
1474       default:
1475         /* Piece move */
1476         cl.rf = rf;
1477         cl.ff = ff;
1478         cl.rt = rt;
1479         cl.ft = ft;
1480         cl.piece = piece;
1481         cl.kind = IllegalMove;
1482         cl.rank = cl.file = cl.either = 0;
1483         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1484
1485         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1486             /* Generate pretty moves for moving into check, but
1487                still return IllegalMove.
1488             */
1489             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1490             if (cl.kind == IllegalMove) break;
1491             cl.kind = IllegalMove;
1492         }
1493
1494         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1495            else "Ngf3" or "Ngxf7",
1496            else "N1f3" or "N5xf7",
1497            else "Ng1f3" or "Ng5xf7".
1498         */
1499         c = PieceToChar(piece) ;
1500         if( c == '~' || c == '+') {
1501            /* [HGM] print nonexistent piece as its demoted version */
1502            piece = (ChessSquare) (DEMOTED piece);
1503         }
1504         if(c=='+') *outp++ = c;
1505         *outp++ = ToUpper(PieceToChar(piece));
1506
1507         if (cl.file || (cl.either && !cl.rank)) {
1508             *outp++ = ff + AAA;
1509         }
1510         if (cl.rank) {
1511             if(rf+ONE <= '9')
1512                 *outp++ = rf + ONE;
1513             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1514         }
1515
1516         if(board[rt][ft] != EmptySquare)
1517           *outp++ = 'x';
1518
1519         *outp++ = ft + AAA;
1520         if(rt+ONE <= '9')
1521            *outp++ = rt + ONE;
1522         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1523         if (gameInfo.variant == VariantShogi) {
1524             /* [HGM] in Shogi non-pawns can promote */
1525             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1526         }
1527         *outp = NULLCHAR;
1528         return cl.kind;
1529
1530       /* [HGM] Always long notation for fairies we don't know */
1531       case WhiteFalcon:
1532       case BlackFalcon:
1533       case WhiteLance:
1534       case BlackLance:
1535       case WhiteGrasshopper:
1536       case BlackGrasshopper:
1537       case EmptySquare:
1538         /* Moving a nonexistent piece */
1539         break;
1540     }
1541
1542     /* Not a legal move, even ignoring check.
1543        If there was a piece on the from square,
1544        use style "Ng1g3" or "Ng1xe8";
1545        if there was a pawn or nothing (!),
1546        use style "g1g3" or "g1xe8".  Use "x"
1547        if a piece was on the to square, even
1548        a piece of the same color.
1549     */
1550     outp = out;
1551     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1552         *outp++ = ToUpper(PieceToChar(piece));
1553     }
1554     *outp++ = ff + AAA;
1555     if(rf+ONE <= '9')
1556        *outp++ = rf + ONE;
1557     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1558     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1559     *outp++ = ft + AAA;
1560     if(rt+ONE <= '9')
1561        *outp++ = rt + ONE;
1562     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1563     /* Use promotion suffix style "=Q" */
1564     if (promoChar != NULLCHAR && promoChar != 'x') {
1565         *outp++ = '=';
1566         *outp++ = ToUpper(promoChar);
1567     }
1568     *outp = NULLCHAR;
1569
1570     return IllegalMove;
1571 }
1572
1573 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1574
1575 typedef struct {
1576     /* Input */
1577     int rf, ff, rt, ft;
1578     /* Output */
1579     int recaptures;
1580 } ChaseClosure;
1581
1582 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1583
1584 int preyStackPointer, chaseStackPointer;
1585
1586 struct {
1587 char rf, ff, rt, ft;
1588 } chaseStack[100];
1589
1590 struct {
1591 char rank, file;
1592 } preyStack[100];
1593
1594
1595
1596
1597 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1598
1599 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1600                                 int rf, int ff, int rt, int ft,
1601                                 VOIDSTAR closure));
1602
1603 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1604      Board board;
1605      int flags;
1606      ChessMove kind;
1607      int rf, ff, rt, ft;
1608      VOIDSTAR closure;
1609 {   // For adding captures that can lead to chase indictment to the chaseStack
1610     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1611     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1612     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1613     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1614     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1615     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1616     chaseStack[chaseStackPointer].rf = rf;
1617     chaseStack[chaseStackPointer].ff = ff;
1618     chaseStack[chaseStackPointer].rt = rt;
1619     chaseStack[chaseStackPointer].ft = ft;
1620     chaseStackPointer++;
1621 }
1622
1623 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1624                                 int rf, int ff, int rt, int ft,
1625                                 VOIDSTAR closure));
1626
1627 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1628      Board board;
1629      int flags;
1630      ChessMove kind;
1631      int rf, ff, rt, ft;
1632      VOIDSTAR closure;
1633 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1634     int i;
1635     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1636
1637     if(board[rt][ft] == EmptySquare) return; // no capture
1638     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1639         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1640     }
1641     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1642     for(i=0; i<chaseStackPointer; i++) {
1643         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1644            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1645             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1646             chaseStack[i] = chaseStack[--chaseStackPointer];
1647             break;
1648         }
1649     }
1650 }
1651
1652 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1653                                 int rf, int ff, int rt, int ft,
1654                                 VOIDSTAR closure));
1655
1656 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1657      Board board;
1658      int flags;
1659      ChessMove kind;
1660      int rf, ff, rt, ft;
1661      VOIDSTAR closure;
1662 {   // for determining if a piece (given through the closure) is protected
1663     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1664
1665     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1666     if(appData.debugMode && board[rt][ft] != EmptySquare)
1667         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1668 }
1669
1670 extern char moveList[MAX_MOVES][MOVE_LEN];
1671
1672 int PerpetualChase(int first, int last)
1673 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1674     int i, j, k, tail;
1675     ChaseClosure cl;
1676     ChessSquare captured;
1677
1678     preyStackPointer = 0;        // clear stack of chased pieces
1679     for(i=first; i<last; i+=2) { // for all positions with same side to move
1680         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1681         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1682         // determine all captures possible after the move, and put them on chaseStack
1683         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl);
1684         if(appData.debugMode) { int n;
1685             for(n=0; n<chaseStackPointer; n++)
1686                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1687                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1688             fprintf(debugFP, ": all capts\n");
1689         }
1690         // determine all captures possible before the move, and delete them from chaseStack
1691         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1692         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1693         cl.rt = moveList[i][3]-ONE;
1694         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1695         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl);
1696         if(appData.debugMode) { int n;
1697             for(n=0; n<chaseStackPointer; n++)
1698                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1699                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1700             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1701         }
1702         // chaseSack now contains all captures made possible by the move
1703         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1704             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1705             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1706
1707             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1708             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1709
1710             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1711                 continue; // C or H attack on R is always chase; leave on chaseStack
1712
1713             if(attacker == victim) {
1714                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1715                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1716                         // we can capture back with equal piece, so this is no chase but a sacrifice
1717                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1718                         j--; /* ! */ continue;
1719                 }
1720
1721             }
1722
1723             // the attack is on a lower piece, or on a pinned or blocked equal one
1724             // test if the victim is protected by a true protector. First make the capture.
1725             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1726             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1727             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1728             // Then test if the opponent can recapture
1729             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1730             cl.rt = chaseStack[j].rt;
1731             cl.ft = chaseStack[j].ft;
1732             if(appData.debugMode) {
1733                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1734             }
1735             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl); // try all moves
1736             // unmake the capture
1737             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1738             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1739             // if a recapture was found, piece is protected, and we are not chasing it.
1740             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1741                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1742                 j--; /* ! */
1743             }
1744         }
1745         // chaseStack now contains all moves that chased
1746         if(appData.debugMode) { int n;
1747             for(n=0; n<chaseStackPointer; n++)
1748                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1749                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1750             fprintf(debugFP, ": chases\n");
1751         }
1752         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1753             for(j=0; j<chaseStackPointer; j++) {
1754                 preyStack[j].rank = chaseStack[j].rt;
1755                 preyStack[j].file = chaseStack[j].ft;
1756             }
1757             preyStackPointer = chaseStackPointer;
1758         }
1759         tail = 0;
1760         for(j=0; j<chaseStackPointer; j++) {
1761             for(k=0; k<preyStackPointer; k++) {
1762                 // search the victim of each chase move on the preyStack (first occurrence)
1763                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1764                     if(k < tail) break; // piece was already identified as still being chased
1765                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1766                     preyStack[tail] = preyStack[k];                // by swapping
1767                     preyStack[k] = preyStack[preyStackPointer];
1768                     tail++;
1769                     break;
1770                 }
1771             }
1772         }
1773         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1774         if(appData.debugMode) { int n;
1775             for(n=0; n<preyStackPointer; n++)
1776                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1777             fprintf(debugFP, "always chased upto ply %d\n", i);
1778         }
1779         // now adjust the location of the chased pieces according to opponent move
1780         for(j=0; j<preyStackPointer; j++) {
1781             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1782                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1783                 preyStack[j].rank = moveList[i+1][3]-ONE;
1784                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1785                 break;
1786             }
1787         }
1788     }
1789     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1790 }