moves.c

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