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