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