moves.c

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