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     int captures; // [HGM] losers
 731 } LegalityTestClosure;
 732
 733
 734 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
 735    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
 736    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
 737    moves that would destroy your own king.  The CASTLE_OK flags are
 738    true if castling is not yet ruled out by a move of the king or
 739    rook.  Return TRUE if the player on move is currently in check and
 740    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
 741 int GenLegal(board, flags, epfile, castlingRights, callback, closure)
 742      Board board;
 743      int flags;
 744      int epfile;
 745      char castlingRights[];
 746      MoveCallback callback;
 747      VOIDSTAR closure;
 748 {
 749     GenLegalClosure cl;
 750     int ff, ft, k, left, right;
 751     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
 752     ChessSquare wKing = WhiteKing, bKing = BlackKing;
 753
 754     cl.cb = callback;
 755     cl.cl = closure;
 756     GenPseudoLegal(board, flags, epfile, GenLegalCallback, (VOIDSTAR) &cl);
 757
 758     if (!ignoreCheck &&
 759         CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE;
 760
 761     /* Generate castling moves */
 762     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
 763         wKing = WhiteUnicorn; bKing = BlackUnicorn;
 764     }
 765
 766     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
 767         if ((flags & F_WHITE_ON_MOVE) &&
 768             (flags & F_WHITE_KCASTLE_OK) &&
 769             board[0][ff] == wKing &&
 770             board[0][ff + 1] == EmptySquare &&
 771             board[0][ff + 2] == EmptySquare &&
 772             board[0][BOARD_RGHT-3] == EmptySquare &&
 773             board[0][BOARD_RGHT-2] == EmptySquare &&
 774             board[0][BOARD_RGHT-1] == WhiteRook &&
 775             castlingRights[0] >= 0 && /* [HGM] check rights */
 776             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
 777             (ignoreCheck ||
 778              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
 779               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
 780               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
 781               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
 782
 783             callback(board, flags,
 784                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
 785                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
 786         }
 787         if ((flags & F_WHITE_ON_MOVE) &&
 788             (flags & F_WHITE_QCASTLE_OK) &&
 789             board[0][ff] == wKing &&
 790             board[0][ff - 1] == EmptySquare &&
 791             board[0][ff - 2] == EmptySquare &&
 792             board[0][BOARD_LEFT+2] == EmptySquare &&
 793             board[0][BOARD_LEFT+1] == EmptySquare &&
 794             board[0][BOARD_LEFT+0] == WhiteRook &&
 795             castlingRights[1] >= 0 && /* [HGM] check rights */
 796             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
 797             (ignoreCheck ||
 798              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
 799               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
 800               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
 801
 802             callback(board, flags,
 803                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
 804                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
 805         }
 806         if (!(flags & F_WHITE_ON_MOVE) &&
 807             (flags & F_BLACK_KCASTLE_OK) &&
 808             board[BOARD_HEIGHT-1][ff] == bKing &&
 809             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
 810             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
 811             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
 812             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
 813             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
 814             castlingRights[3] >= 0 && /* [HGM] check rights */
 815             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
 816             (ignoreCheck ||
 817              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
 818               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
 819               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
 820               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
 821
 822             callback(board, flags,
 823                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
 824                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
 825         }
 826         if (!(flags & F_WHITE_ON_MOVE) &&
 827             (flags & F_BLACK_QCASTLE_OK) &&
 828             board[BOARD_HEIGHT-1][ff] == bKing &&
 829             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
 830             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
 831             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
 832             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
 833             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
 834             castlingRights[4] >= 0 && /* [HGM] check rights */
 835             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
 836             (ignoreCheck ||
 837              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
 838               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
 839               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
 840
 841             callback(board, flags,
 842                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
 843                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
 844         }
 845     }
 846
 847   if(gameInfo.variant == VariantFischeRandom) {
 848
 849     /* generate all potential FRC castling moves (KxR), ignoring flags */
 850     /* [HGM] test if the Rooks we find have castling rights */
 851
 852
 853     if ((flags & F_WHITE_ON_MOVE) != 0) {
 854         ff = castlingRights[2]; /* King file if we have any rights */
 855         if(ff > 0 && board[0][ff] == WhiteKing) {
 856     if (appData.debugMode) {
 857         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
 858                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
 859     }
 860             ft = castlingRights[0]; /* Rook file if we have H-side rights */
 861             left  = ff+1;
 862             right = BOARD_RGHT-2;
 863             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
 864             for(k=left; k<=right && ft >= 0; k++) /* first test if blocked */
 865                 if(k != ft && board[0][k] != EmptySquare) ft = -1;
 866             for(k=left; k<right && ft >= 0; k++) /* then if not checked */
 867                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = -1;
 868             if(ft >= 0 && board[0][ft] == WhiteRook)
 869                 callback(board, flags, WhiteHSideCastleFR, 0, ff, 0, ft, closure);
 870
 871             ft = castlingRights[1]; /* Rook file if we have A-side rights */
 872             left  = BOARD_LEFT+2;
 873             right = ff-1;
 874             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
 875             for(k=left; k<=right && ft >= 0; k++) /* first test if blocked */
 876                 if(k != ft && board[0][k] != EmptySquare) ft = -1;
 877             if(ff > BOARD_LEFT+2)
 878             for(k=left+1; k<=right && ft >= 0; k++) /* then if not checked */
 879                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = -1;
 880             if(ft >= 0 && board[0][ft] == WhiteRook)
 881                 callback(board, flags, WhiteASideCastleFR, 0, ff, 0, ft, closure);
 882         }
 883     } else {
 884         ff = castlingRights[5]; /* King file if we have any rights */
 885         if(ff > 0 && board[BOARD_HEIGHT-1][ff] == BlackKing) {
 886             ft = castlingRights[3]; /* Rook file if we have H-side rights */
 887             left  = ff+1;
 888             right = BOARD_RGHT-2;
 889             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
 890             for(k=left; k<=right && ft >= 0; k++) /* first test if blocked */
 891                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = -1;
 892             for(k=left; k<right && ft >= 0; k++) /* then if not checked */
 893                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = -1;
 894             if(ft >= 0 && board[BOARD_HEIGHT-1][ft] == BlackRook)
 895                 callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
 896
 897             ft = castlingRights[4]; /* Rook file if we have A-side rights */
 898             left  = BOARD_LEFT+2;
 899             right = ff-1;
 900             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
 901             for(k=left; k<=right && ft >= 0; k++) /* first test if blocked */
 902                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = -1;
 903             if(ff > BOARD_LEFT+2)
 904             for(k=left+1; k<=right && ft >= 0; k++) /* then if not checked */
 905                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = -1;
 906             if(ft >= 0 && board[BOARD_HEIGHT-1][ft] == BlackRook)
 907                 callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ft, closure);
 908         }
 909     }
 910
 911   }
 912
 913     return FALSE;
 914 }
 915
 916
 917 typedef struct {
 918     int rking, fking;
 919     int check;
 920 } CheckTestClosure;
 921
 922
 923 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
 924                                  int rf, int ff, int rt, int ft,
 925                                  VOIDSTAR closure));
 926
 927
 928 void CheckTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 929      Board board;
 930      int flags;
 931      ChessMove kind;
 932      int rf, ff, rt, ft;
 933      VOIDSTAR closure;
 934 {
 935     register CheckTestClosure *cl = (CheckTestClosure *) closure;
 936
 937     if (rt == cl->rking && ft == cl->fking) cl->check++;
 938 }
 939
 940
 941 /* If the player on move were to move from (rf, ff) to (rt, ft), would
 942    he leave himself in check?  Or if rf == -1, is the player on move
 943    in check now?  enPassant must be TRUE if the indicated move is an
 944    e.p. capture.  The possibility of castling out of a check along the
 945    back rank is not accounted for (i.e., we still return nonzero), as
 946    this is illegal anyway.  Return value is the number of times the
 947    king is in check. */
 948 int CheckTest(board, flags, rf, ff, rt, ft, enPassant)
 949      Board board;
 950      int flags;
 951      int rf, ff, rt, ft, enPassant;
 952 {
 953     CheckTestClosure cl;
 954     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
 955     ChessSquare captured = EmptySquare;
 956     /*  Suppress warnings on uninitialized variables    */
 957
 958     if(gameInfo.variant == VariantXiangqi)
 959         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
 960     if(gameInfo.variant == VariantKnightmate)
 961         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
 962
 963     if (rf >= 0) {
 964         if (enPassant) {
 965             captured = board[rf][ft];
 966             board[rf][ft] = EmptySquare;
 967         } else {
 968             captured = board[rt][ft];
 969         }
 970         board[rt][ft] = board[rf][ff];
 971         board[rf][ff] = EmptySquare;
 972     }
 973
 974     /* For compatibility with ICS wild 9, we scan the board in the
 975        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
 976        and we test only whether that one is in check. */
 977     cl.check = 0;
 978     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
 979         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
 980           if (board[cl.rking][cl.fking] == king) {
 981               if(gameInfo.variant == VariantXiangqi) {
 982                   /* [HGM] In Xiangqi opposing Kings means check as well */
 983                   int i, dir;
 984                   dir = (king >= BlackPawn) ? -1 : 1;
 985                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
 986                                 board[i][cl.fking] == EmptySquare; i+=dir );
 987                   if(i>=0 && i<BOARD_HEIGHT &&
 988                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
 989                           cl.check++;
 990               }
 991
 992               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, -1,
 993                              CheckTestCallback, (VOIDSTAR) &cl);
 994               goto undo_move;  /* 2-level break */
 995           }
 996       }
 997
 998   undo_move:
 999
1000     if (rf >= 0) {
1001         board[rf][ff] = board[rt][ft];
1002         if (enPassant) {
1003             board[rf][ft] = captured;
1004             board[rt][ft] = EmptySquare;
1005         } else {
1006             board[rt][ft] = captured;
1007         }
1008     }
1009
1010     return cl.check;
1011 }
1012
1013
1014 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1015                                     int rf, int ff, int rt, int ft,
1016                                     VOIDSTAR closure));
1017
1018 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1019      Board board;
1020      int flags;
1021      ChessMove kind;
1022      int rf, ff, rt, ft;
1023      VOIDSTAR closure;
1024 {
1025     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1026
1027 //    if (appData.debugMode) {
1028 //        fprintf(debugFP, "Legality test: %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1029 //    }
1030     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1031         cl->captures++; // [HGM] losers: count legal captures
1032     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1033       cl->kind = kind;
1034 }
1035
1036 ChessMove LegalityTest(board, flags, epfile, castlingRights, rf, ff, rt, ft, promoChar)
1037      Board board;
1038      int flags, epfile;
1039      int rf, ff, rt, ft, promoChar;
1040      char castlingRights[];
1041 {
1042     LegalityTestClosure cl; ChessSquare piece = board[rf][ff];
1043
1044     if (appData.debugMode) {
1045         int i;
1046         for(i=0; i<6; i++) fprintf(debugFP, "%d ", castlingRights[i]);
1047         fprintf(debugFP, "Legality test? %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1048     }
1049     /* [HGM] Lance, Cobra and Falcon are wildcard pieces; consider all their moves legal */
1050     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1051     if(piece == WhiteFalcon || piece == BlackFalcon ||
1052        piece == WhiteCobra  || piece == BlackCobra  ||
1053        piece == WhiteLance  || piece == BlackLance)
1054         return NormalMove;
1055
1056     cl.rf = rf;
1057     cl.ff = ff;
1058     cl.rt = rt;
1059     cl.ft = ft;
1060     cl.kind = IllegalMove;
1061     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1062     GenLegal(board, flags, epfile, castlingRights, LegalityTestCallback, (VOIDSTAR) &cl);
1063     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1064                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1065         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1066
1067     if(gameInfo.variant == VariantShogi) {
1068         /* [HGM] Shogi promotions. '=' means defer */
1069         if(rf != DROP_RANK && cl.kind == NormalMove) {
1070             ChessSquare piece = board[rf][ff];
1071
1072             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1073             if(promoChar != NULLCHAR && promoChar != 'x' &&
1074                promoChar != '+' && promoChar != '=' &&
1075                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(promoChar) )
1076                     cl.kind = IllegalMove;
1077             else if(flags & F_WHITE_ON_MOVE) {
1078                 if( (int) piece < (int) WhiteWazir &&
1079                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1080                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1081                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1082                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1083                     else /* promotion optional, default is promote */
1084                              cl.kind = promoChar == '=' ? NormalMove  : WhitePromotionQueen;
1085
1086                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1087                                             NormalMove : IllegalMove;
1088             } else {
1089                 if( (int) piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1090                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1091                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1092                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1093                     else /* promotion optional, default is promote */
1094                              cl.kind = promoChar == '=' ? NormalMove  : BlackPromotionQueen;
1095
1096                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1097                                             NormalMove : IllegalMove;
1098             }
1099         }
1100     } else
1101     if (promoChar != NULLCHAR && promoChar != 'x') {
1102         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1103         if (cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1104             cl.kind =
1105               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0, promoChar);
1106         } else {
1107             cl.kind = IllegalMove;
1108         }
1109     }
1110     /* [HGM] For promotions, 'ToQueen' = optional, 'ToKnight' = mandatory */
1111     return cl.kind;
1112 }
1113
1114 typedef struct {
1115     int count;
1116 } MateTestClosure;
1117
1118 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1119                                 int rf, int ff, int rt, int ft,
1120                                 VOIDSTAR closure));
1121
1122 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1123      Board board;
1124      int flags;
1125      ChessMove kind;
1126      int rf, ff, rt, ft;
1127      VOIDSTAR closure;
1128 {
1129     register MateTestClosure *cl = (MateTestClosure *) closure;
1130
1131     cl->count++;
1132 }
1133
1134 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1135 int MateTest(board, flags, epfile, castlingRights)
1136      Board board;
1137      int flags, epfile;
1138      char castlingRights[];
1139 {
1140     MateTestClosure cl;
1141     int inCheck;
1142
1143     cl.count = 0;
1144     inCheck = GenLegal(board, flags, epfile, castlingRights, MateTestCallback, (VOIDSTAR) &cl);
1145     if (cl.count > 0) {
1146         return inCheck ? MT_CHECK : MT_NONE;
1147     } else {
1148         return inCheck ? MT_CHECKMATE
1149                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1150                           MT_STAINMATE : MT_STALEMATE;
1151     }
1152 }
1153
1154
1155 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1156                                     int rf, int ff, int rt, int ft,
1157                                     VOIDSTAR closure));
1158
1159 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1160      Board board;
1161      int flags;
1162      ChessMove kind;
1163      int rf, ff, rt, ft;
1164      VOIDSTAR closure;
1165 {
1166     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1167
1168     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1169          || PieceToChar(board[rf][ff]) == '~'
1170               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1171                                                                       ) &&
1172         (cl->rfIn == -1 || cl->rfIn == rf) &&
1173         (cl->ffIn == -1 || cl->ffIn == ff) &&
1174         (cl->rtIn == -1 || cl->rtIn == rt) &&
1175         (cl->ftIn == -1 || cl->ftIn == ft)) {
1176
1177         cl->count++;
1178         cl->piece = board[rf][ff];
1179         cl->rf = rf;
1180         cl->ff = ff;
1181         cl->rt = rt;
1182         cl->ft = ft;
1183         cl->kind = kind;
1184     }
1185 }
1186
1187 void Disambiguate(board, flags, epfile, closure)
1188      Board board;
1189      int flags, epfile;
1190      DisambiguateClosure *closure;
1191 {
1192     int illegal = 0; char c = closure->promoCharIn;
1193     closure->count = 0;
1194     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1195     closure->kind = ImpossibleMove;
1196     if (appData.debugMode) {
1197         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1198                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1199                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1200     }
1201     GenLegal(board, flags, epfile, initialRights, DisambiguateCallback, (VOIDSTAR) closure);
1202     if (closure->count == 0) {
1203         /* See if it's an illegal move due to check */
1204         illegal = 1;
1205         GenLegal(board, flags|F_IGNORE_CHECK, epfile, initialRights, DisambiguateCallback,
1206                  (VOIDSTAR) closure);
1207         if (closure->count == 0) {
1208             /* No, it's not even that */
1209     if (appData.debugMode) { int i, j;
1210         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1211                 for(j=0; j<BOARD_WIDTH; j++)
1212                         fprintf(debugFP, "%3d", (int) board[i][j]);
1213                 fprintf(debugFP, "\n");
1214         }
1215     }
1216             return;
1217         }
1218     }
1219
1220     if(gameInfo.variant == VariantShogi) {
1221         /* [HGM] Shogi promotions. '=' means defer */
1222         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1223             ChessSquare piece = closure->piece;
1224 #if 0
1225     if (appData.debugMode) {
1226         fprintf(debugFP, "Disambiguate A:   %d(%d,%d)-(%d,%d) = %d (%c)\n",
1227                           closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1228                           closure->promoCharIn,closure->promoCharIn);
1229     }
1230 #endif
1231             if(c != NULLCHAR && c != 'x' && c != '+' && c != '=' &&
1232                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(c) )
1233                     closure->kind = IllegalMove;
1234             else if(flags & F_WHITE_ON_MOVE) {
1235 #if 0
1236     if (appData.debugMode) {
1237         fprintf(debugFP, "Disambiguate B:   %d(%d,%d)-(%d,%d) = %d (%c)\n",
1238                           closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1239                           closure->promoCharIn,closure->promoCharIn);
1240     }
1241 #endif
1242                 if( (int) piece < (int) WhiteWazir &&
1243                      (closure->rf > BOARD_HEIGHT-4 || closure->rt > BOARD_HEIGHT-4) ) {
1244                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1245                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1246                              closure->kind = c == '=' ? IllegalMove : WhitePromotionKnight;
1247                     else /* promotion optional, default is promote */
1248                              closure->kind = c == '=' ? NormalMove  : WhitePromotionQueen;
1249
1250                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1251                                             NormalMove : IllegalMove;
1252             } else {
1253                 if( (int) piece < (int) BlackWazir && (closure->rf < 3 || closure->rt < 3) ) {
1254                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1255                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1256                              closure->kind = c == '=' ? IllegalMove : BlackPromotionKnight;
1257                     else /* promotion optional, default is promote */
1258                              closure->kind = c == '=' ? NormalMove  : BlackPromotionQueen;
1259
1260                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1261                                             NormalMove : IllegalMove;
1262             }
1263         }
1264     } else
1265     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
1266         if (closure->kind == WhitePromotionQueen
1267             || closure->kind == BlackPromotionQueen) {
1268             closure->kind =
1269               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
1270                                   closure->promoCharIn);
1271         } else {
1272             closure->kind = IllegalMove;
1273         }
1274     }
1275 #if 0
1276     if (appData.debugMode) {
1277         fprintf(debugFP, "Disambiguate C:   %d(%d,%d)-(%d,%d) = %d (%c)\n",
1278                           closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1279                           closure->promoCharIn,closure->promoCharIn);
1280     }
1281 #endif
1282     /* [HGM] returns 'q' for optional promotion, 'n' for mandatory */
1283     if(closure->promoCharIn != '=')
1284         closure->promoChar = ToLower(closure->promoCharIn);
1285     else closure->promoChar = '=';
1286     if (closure->promoChar == 'x') closure->promoChar = NULLCHAR;
1287     if (closure->count > 1) {
1288         closure->kind = AmbiguousMove;
1289     }
1290     if (illegal) {
1291         /* Note: If more than one illegal move matches, but no legal
1292            moves, we return IllegalMove, not AmbiguousMove.  Caller
1293            can look at closure->count to detect this.
1294         */
1295         closure->kind = IllegalMove;
1296     }
1297     if(closure->kind == IllegalMove)
1298     /* [HGM] might be a variant we don't understand, pass on promotion info */
1299         closure->promoChar = ToLower(closure->promoCharIn);
1300     if (appData.debugMode) {
1301         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1302         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1303         closure->promoChar >= ' ' ? closure->promoChar:'-');
1304     }
1305 }
1306
1307
1308 typedef struct {
1309     /* Input */
1310     ChessSquare piece;
1311     int rf, ff, rt, ft;
1312     /* Output */
1313     ChessMove kind;
1314     int rank;
1315     int file;
1316     int either;
1317 } CoordsToAlgebraicClosure;
1318
1319 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1320                                          ChessMove kind, int rf, int ff,
1321                                          int rt, int ft, VOIDSTAR closure));
1322
1323 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1324      Board board;
1325      int flags;
1326      ChessMove kind;
1327      int rf, ff, rt, ft;
1328      VOIDSTAR closure;
1329 {
1330     register CoordsToAlgebraicClosure *cl =
1331       (CoordsToAlgebraicClosure *) closure;
1332
1333     if (rt == cl->rt && ft == cl->ft &&
1334         (board[rf][ff] == cl->piece
1335          || PieceToChar(board[rf][ff]) == '~' &&
1336             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1337                                      ) {
1338         if (rf == cl->rf) {
1339             if (ff == cl->ff) {
1340                 cl->kind = kind; /* this is the move we want */
1341             } else {
1342                 cl->file++; /* need file to rule out this move */
1343             }
1344         } else {
1345             if (ff == cl->ff) {
1346                 cl->rank++; /* need rank to rule out this move */
1347             } else {
1348                 cl->either++; /* rank or file will rule out this move */
1349             }
1350         }
1351     }
1352 }
1353
1354 /* Convert coordinates to normal algebraic notation.
1355    promoChar must be NULLCHAR or 'x' if not a promotion.
1356 */
1357 ChessMove CoordsToAlgebraic(board, flags, epfile,
1358                             rf, ff, rt, ft, promoChar, out)
1359      Board board;
1360      int flags, epfile;
1361      int rf, ff, rt, ft;
1362      int promoChar;
1363      char out[MOVE_LEN];
1364 {
1365     ChessSquare piece;
1366     ChessMove kind;
1367     char *outp = out, c;
1368     CoordsToAlgebraicClosure cl;
1369
1370     if (rf == DROP_RANK) {
1371         /* Bughouse piece drop */
1372         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1373         *outp++ = '@';
1374         *outp++ = ft + AAA;
1375         if(rt+ONE <= '9')
1376            *outp++ = rt + ONE;
1377         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1378         *outp = NULLCHAR;
1379         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1380     }
1381
1382     if (promoChar == 'x') promoChar = NULLCHAR;
1383     piece = board[rf][ff];
1384     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1385
1386   if (appData.debugMode)
1387           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1388     switch (piece) {
1389       case WhitePawn:
1390       case BlackPawn:
1391         kind = LegalityTest(board, flags, epfile, initialRights, rf, ff, rt, ft, promoChar);
1392         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1393             /* Keep short notation if move is illegal only because it
1394                leaves the player in check, but still return IllegalMove */
1395             kind = LegalityTest(board, flags|F_IGNORE_CHECK, epfile, initialRights,
1396                                rf, ff, rt, ft, promoChar);
1397             if (kind == IllegalMove) break;
1398             kind = IllegalMove;
1399         }
1400         /* Pawn move */
1401         *outp++ = ff + AAA;
1402         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1403             /* Non-capture; use style "e5" */
1404             if(rt+ONE <= '9')
1405                *outp++ = rt + ONE;
1406             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1407         } else {
1408             /* Capture; use style "exd5" */
1409             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1410             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1411             *outp++ = ft + AAA;
1412             if(rt+ONE <= '9')
1413                *outp++ = rt + ONE;
1414             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1415         }
1416         /* Use promotion suffix style "=Q" */
1417         *outp = NULLCHAR;
1418   if (appData.debugMode)
1419           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1420         if (promoChar != NULLCHAR) {
1421             if(gameInfo.variant == VariantShogi) {
1422                 /* [HGM] ... but not in Shogi! */
1423                 *outp++ = promoChar == '=' ? '=' : '+';
1424             } else {
1425                 *outp++ = '=';
1426                 *outp++ = ToUpper(promoChar);
1427             }
1428             *outp = NULLCHAR;
1429         }
1430         return kind;
1431
1432
1433       case WhiteKing:
1434       case BlackKing:
1435         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1436         /* Code added by Tord:  FRC castling. */
1437         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1438            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1439           if(ft > ff) strcpy(out, "O-O"); else strcpy(out, "O-O-O");
1440             return LegalityTest(board, flags, epfile, initialRights,
1441                                 rf, ff, rt, ft, promoChar);
1442         }
1443         /* End of code added by Tord */
1444         /* Test for castling or ICS wild castling */
1445         /* Use style "O-O" (oh-oh) for PGN compatibility */
1446         else if (rf == rt &&
1447             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1448             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1449              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1450             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1451                 strcpy(out, "O-O");
1452             else
1453                 strcpy(out, "O-O-O");
1454
1455             /* This notation is always unambiguous, unless there are
1456                kings on both the d and e files, with "wild castling"
1457                possible for the king on the d file and normal castling
1458                possible for the other.  ICS rules for wild 9
1459                effectively make castling illegal for either king in
1460                this situation.  So I am not going to worry about it;
1461                I'll just generate an ambiguous O-O in this case.
1462             */
1463             return LegalityTest(board, flags, epfile, initialRights,
1464                                 rf, ff, rt, ft, promoChar);
1465         }
1466
1467         /* else fall through */
1468       default:
1469         /* Piece move */
1470         cl.rf = rf;
1471         cl.ff = ff;
1472         cl.rt = rt;
1473         cl.ft = ft;
1474         cl.piece = piece;
1475         cl.kind = IllegalMove;
1476         cl.rank = cl.file = cl.either = 0;
1477         GenLegal(board, flags, epfile, initialRights,
1478                  CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1479
1480         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1481             /* Generate pretty moves for moving into check, but
1482                still return IllegalMove.
1483             */
1484             GenLegal(board, flags|F_IGNORE_CHECK, epfile, initialRights,
1485                      CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1486             if (cl.kind == IllegalMove) break;
1487             cl.kind = IllegalMove;
1488         }
1489
1490         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1491            else "Ngf3" or "Ngxf7",
1492            else "N1f3" or "N5xf7",
1493            else "Ng1f3" or "Ng5xf7".
1494         */
1495         c = PieceToChar(piece) ;
1496         if( c == '~' || c == '+') {
1497            /* [HGM] print nonexistent piece as its demoted version */
1498            piece = (ChessSquare) (DEMOTED piece);
1499         }
1500         if(c=='+') *outp++ = c;
1501         *outp++ = ToUpper(PieceToChar(piece));
1502
1503         if (cl.file || (cl.either && !cl.rank)) {
1504             *outp++ = ff + AAA;
1505         }
1506         if (cl.rank) {
1507             if(rf+ONE <= '9')
1508                 *outp++ = rf + ONE;
1509             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1510         }
1511
1512         if(board[rt][ft] != EmptySquare)
1513           *outp++ = 'x';
1514
1515         *outp++ = ft + AAA;
1516         if(rt+ONE <= '9')
1517            *outp++ = rt + ONE;
1518         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1519         *outp = NULLCHAR;
1520         if (gameInfo.variant == VariantShogi) {
1521             /* [HGM] in Shogi non-pawns can promote */
1522             if(flags & F_WHITE_ON_MOVE) {
1523                 if( (int) cl.piece < (int) WhiteWazir &&
1524                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1525                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1526                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1527                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1528                     else cl.kind =  WhitePromotionQueen; /* promotion optional */
1529
1530                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1531                                             NormalMove : IllegalMove;
1532             } else {
1533                 if( (int) cl.piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1534                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1535                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1536                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1537                     else cl.kind =  BlackPromotionQueen; /* promotion optional */
1538                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1539                                             NormalMove : IllegalMove;
1540             }
1541             if(cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1542                 /* for optional promotions append '+' or '=' */
1543                 if(promoChar == '=') {
1544                     *outp++ = '=';
1545                     cl.kind = NormalMove;
1546                 } else *outp++ = '+';
1547                 *outp = NULLCHAR;
1548             } else if(cl.kind == IllegalMove) {
1549                 /* Illegal move specifies any given promotion */
1550                 if(promoChar != NULLCHAR && promoChar != 'x') {
1551                     *outp++ = '=';
1552                     *outp++ = ToUpper(promoChar);
1553                     *outp = NULLCHAR;
1554                 }
1555             }
1556         }
1557         return cl.kind;
1558
1559       /* [HGM] Always long notation for fairies we don't know */
1560       case WhiteFalcon:
1561       case BlackFalcon:
1562       case WhiteLance:
1563       case BlackLance:
1564       case WhiteGrasshopper:
1565       case BlackGrasshopper:
1566       case EmptySquare:
1567         /* Moving a nonexistent piece */
1568         break;
1569     }
1570
1571     /* Not a legal move, even ignoring check.
1572        If there was a piece on the from square,
1573        use style "Ng1g3" or "Ng1xe8";
1574        if there was a pawn or nothing (!),
1575        use style "g1g3" or "g1xe8".  Use "x"
1576        if a piece was on the to square, even
1577        a piece of the same color.
1578     */
1579     outp = out;
1580     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1581         *outp++ = ToUpper(PieceToChar(piece));
1582     }
1583     *outp++ = ff + AAA;
1584     if(rf+ONE <= '9')
1585        *outp++ = rf + ONE;
1586     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1587     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1588     *outp++ = ft + AAA;
1589     if(rt+ONE <= '9')
1590        *outp++ = rt + ONE;
1591     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1592     /* Use promotion suffix style "=Q" */
1593     if (promoChar != NULLCHAR && promoChar != 'x') {
1594         *outp++ = '=';
1595         *outp++ = ToUpper(promoChar);
1596     }
1597     *outp = NULLCHAR;
1598
1599     return IllegalMove;
1600 }
1601
1602 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1603
1604 typedef struct {
1605     /* Input */
1606     int rf, ff, rt, ft;
1607     /* Output */
1608     int recaptures;
1609 } ChaseClosure;
1610
1611 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1612
1613 int preyStackPointer, chaseStackPointer;
1614
1615 struct {
1616 char rf, ff, rt, ft;
1617 } chaseStack[100];
1618
1619 struct {
1620 char rank, file;
1621 } preyStack[100];
1622
1623
1624
1625
1626 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1627
1628 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1629                                 int rf, int ff, int rt, int ft,
1630                                 VOIDSTAR closure));
1631
1632 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1633      Board board;
1634      int flags;
1635      ChessMove kind;
1636      int rf, ff, rt, ft;
1637      VOIDSTAR closure;
1638 {   // For adding captures that can lead to chase indictment to the chaseStack
1639     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1640     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1641     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1642     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1643     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1644     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1645     chaseStack[chaseStackPointer].rf = rf;
1646     chaseStack[chaseStackPointer].ff = ff;
1647     chaseStack[chaseStackPointer].rt = rt;
1648     chaseStack[chaseStackPointer].ft = ft;
1649     chaseStackPointer++;
1650 }
1651
1652 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1653                                 int rf, int ff, int rt, int ft,
1654                                 VOIDSTAR closure));
1655
1656 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1657      Board board;
1658      int flags;
1659      ChessMove kind;
1660      int rf, ff, rt, ft;
1661      VOIDSTAR closure;
1662 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1663     int i;
1664     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1665
1666     if(board[rt][ft] == EmptySquare) return; // no capture
1667     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1668         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1669     }
1670     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1671     for(i=0; i<chaseStackPointer; i++) {
1672         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1673            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1674             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1675             chaseStack[i] = chaseStack[--chaseStackPointer];
1676             break;
1677         }
1678     }
1679 }
1680
1681 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1682                                 int rf, int ff, int rt, int ft,
1683                                 VOIDSTAR closure));
1684
1685 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1686      Board board;
1687      int flags;
1688      ChessMove kind;
1689      int rf, ff, rt, ft;
1690      VOIDSTAR closure;
1691 {   // for determining if a piece (given through the closure) is protected
1692     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1693
1694     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1695     if(appData.debugMode && board[rt][ft] != EmptySquare)
1696         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1697 }
1698
1699 extern char moveList[MAX_MOVES][MOVE_LEN];
1700
1701 int PerpetualChase(int first, int last)
1702 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1703     int i, j, k, tail;
1704     ChaseClosure cl;
1705     ChessSquare captured;
1706
1707     preyStackPointer = 0;        // clear stack of chased pieces
1708     for(i=first; i<last; i+=2) { // for all positions with same side to move
1709         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1710         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1711         // determine all captures possible after the move, and put them on chaseStack
1712         GenLegal(boards[i+1], PosFlags(i), EP_NONE, initialRights, AttacksCallback, &cl);
1713         if(appData.debugMode) { int n;
1714             for(n=0; n<chaseStackPointer; n++)
1715                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1716                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1717             fprintf(debugFP, ": all capts\n");
1718         }
1719         // determine all captures possible before the move, and delete them from chaseStack
1720         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1721         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1722         cl.rt = moveList[i][3]-ONE;
1723         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1724         GenLegal(boards[i],   PosFlags(i), EP_NONE, initialRights, ExistingAttacksCallback, &cl);
1725         if(appData.debugMode) { int n;
1726             for(n=0; n<chaseStackPointer; n++)
1727                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1728                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1729             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1730         }
1731         // chaseSack now contains all captures made possible by the move
1732         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1733             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1734             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1735
1736             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1737             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1738
1739             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1740                 continue; // C or H attack on R is always chase; leave on chaseStack
1741
1742             if(attacker == victim) {
1743                 if(LegalityTest(boards[i+1], PosFlags(i+1), EP_NONE, initialRights, chaseStack[j].rt,
1744                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1745                         // we can capture back with equal piece, so this is no chase but a sacrifice
1746                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1747                         j--; /* ! */ continue;
1748                 }
1749
1750             }
1751
1752             // the attack is on a lower piece, or on a pinned or blocked equal one
1753             // test if the victim is protected by a true protector. First make the capture.
1754             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1755             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1756             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1757             // Then test if the opponent can recapture
1758             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1759             cl.rt = chaseStack[j].rt;
1760             cl.ft = chaseStack[j].ft;
1761             if(appData.debugMode) {
1762                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1763             }
1764             GenLegal(boards[i+1], PosFlags(i+1), EP_NONE, initialRights, ProtectedCallback, &cl); // try all moves
1765             // unmake the capture
1766             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1767             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1768             // if a recapture was found, piece is protected, and we are not chasing it.
1769             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1770                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1771                 j--; /* ! */
1772             }
1773         }
1774         // chaseStack now contains all moves that chased
1775         if(appData.debugMode) { int n;
1776             for(n=0; n<chaseStackPointer; n++)
1777                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1778                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1779             fprintf(debugFP, ": chases\n");
1780         }
1781         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1782             for(j=0; j<chaseStackPointer; j++) {
1783                 preyStack[j].rank = chaseStack[j].rt;
1784                 preyStack[j].file = chaseStack[j].ft;
1785             }
1786             preyStackPointer = chaseStackPointer;
1787         }
1788         tail = 0;
1789         for(j=0; j<chaseStackPointer; j++) {
1790             for(k=0; k<preyStackPointer; k++) {
1791                 // search the victim of each chase move on the preyStack (first occurrence)
1792                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1793                     if(k < tail) break; // piece was already identified as still being chased
1794                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1795                     preyStack[tail] = preyStack[k];                // by swapping
1796                     preyStack[k] = preyStack[preyStackPointer];
1797                     tail++;
1798                     break;
1799                 }
1800             }
1801         }
1802         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1803         if(appData.debugMode) { int n;
1804             for(n=0; n<preyStackPointer; n++)
1805                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1806             fprintf(debugFP, "always chased upto ply %d\n", i);
1807         }
1808         // now adjust the location of the chased pieces according to opponent move
1809         for(j=0; j<preyStackPointer; j++) {
1810             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1811                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1812                 preyStack[j].rank = moveList[i+1][3]-ONE;
1813                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1814                 break;
1815             }
1816         }
1817     }
1818     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1819 }