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