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