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