moves.c

   1 /*
   2  * moves.c - Move generation and checking
   3  *
   4  * Copyright 1991 by Digital Equipment Corporation, Maynard,
   5  * Massachusetts.
   6  *
   7  * Enhancements Copyright 1992-2001, 2002, 2003, 2004, 2005, 2006,
   8  * 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   9  *
  10  * Enhancements Copyright 2005 Alessandro Scotti
  11  *
  12  * The following terms apply to Digital Equipment Corporation's copyright
  13  * interest in XBoard:
  14  * ------------------------------------------------------------------------
  15  * All Rights Reserved
  16  *
  17  * Permission to use, copy, modify, and distribute this software and its
  18  * documentation for any purpose and without fee is hereby granted,
  19  * provided that the above copyright notice appear in all copies and that
  20  * both that copyright notice and this permission notice appear in
  21  * supporting documentation, and that the name of Digital not be
  22  * used in advertising or publicity pertaining to distribution of the
  23  * software without specific, written prior permission.
  24  *
  25  * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  26  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  27  * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  28  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  29  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  30  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  31  * SOFTWARE.
  32  * ------------------------------------------------------------------------
  33  *
  34  * The following terms apply to the enhanced version of XBoard
  35  * distributed by the Free Software Foundation:
  36  * ------------------------------------------------------------------------
  37  *
  38  * GNU XBoard is free software: you can redistribute it and/or modify
  39  * it under the terms of the GNU General Public License as published by
  40  * the Free Software Foundation, either version 3 of the License, or (at
  41  * your option) any later version.
  42  *
  43  * GNU XBoard is distributed in the hope that it will be useful, but
  44  * WITHOUT ANY WARRANTY; without even the implied warranty of
  45  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  46  * General Public License for more details.
  47  *
  48  * You should have received a copy of the GNU General Public License
  49  * along with this program. If not, see http://www.gnu.org/licenses/.  *
  50  *
  51  *------------------------------------------------------------------------
  52  ** See the file ChangeLog for a revision history.  */
  53
  54 #include "config.h"
  55
  56 #include <stdio.h>
  57 #if HAVE_STRING_H
  58 # include <string.h>
  59 #else /* not HAVE_STRING_H */
  60 # include <strings.h>
  61 #endif /* not HAVE_STRING_H */
  62 #include "common.h"
  63 #include "backend.h"
  64 #include "moves.h"
  65 #include "parser.h"
  66
  67 int WhitePiece P((ChessSquare));
  68 int BlackPiece P((ChessSquare));
  69 int SameColor P((ChessSquare, ChessSquare));
  70 int PosFlags(int index);
  71
  72 extern signed char initialRights[BOARD_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         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1227           // [HGM] oneclick: if multiple moves, be sure we remember capture
1228           cl->piece = board[rf][ff];
1229           cl->rf = rf;
1230           cl->ff = ff;
1231           cl->rt = wildCard ? cl->rtIn : rt;
1232           cl->ft = wildCard ? cl->ftIn : ft;
1233           cl->kind = kind;
1234         }
1235         cl->captures += (board[cl->rt][cl->ft] != EmptySquare); // [HGM] oneclick: count captures
1236     }
1237 }
1238
1239 void Disambiguate(board, flags, closure)
1240      Board board;
1241      int flags;
1242      DisambiguateClosure *closure;
1243 {
1244     int illegal = 0; char c = closure->promoCharIn;
1245
1246     closure->count = closure->captures = 0;
1247     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1248     closure->kind = ImpossibleMove;
1249     if (appData.debugMode) {
1250         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1251                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1252                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1253     }
1254     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure);
1255     if (closure->count == 0) {
1256         /* See if it's an illegal move due to check */
1257         illegal = 1;
1258         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure);
1259         if (closure->count == 0) {
1260             /* No, it's not even that */
1261     if (appData.debugMode) { int i, j;
1262         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1263                 for(j=0; j<BOARD_WIDTH; j++)
1264                         fprintf(debugFP, "%3d", (int) board[i][j]);
1265                 fprintf(debugFP, "\n");
1266         }
1267     }
1268             return;
1269         }
1270     }
1271
1272     if(gameInfo.variant == VariantShogi) {
1273         /* [HGM] Shogi promotions. '=' means defer */
1274         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1275             ChessSquare piece = closure->piece;
1276             if(c != NULLCHAR && c != 'x' && c != '+' && c != '=' &&
1277                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(c) )
1278                     closure->kind = IllegalMove;
1279             else if(flags & F_WHITE_ON_MOVE) {
1280                 if( (int) piece < (int) WhiteWazir &&
1281                      (closure->rf > BOARD_HEIGHT-4 || closure->rt > BOARD_HEIGHT-4) ) {
1282                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1283                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1284                              closure->kind = c == '=' ? IllegalMove : WhitePromotionKnight;
1285                     else /* promotion optional, default is promote */
1286                              closure->kind = c == '=' ? NormalMove  : WhitePromotionQueen;
1287
1288                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1289                                             NormalMove : IllegalMove;
1290             } else {
1291                 if( (int) piece < (int) BlackWazir && (closure->rf < 3 || closure->rt < 3) ) {
1292                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1293                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1294                              closure->kind = c == '=' ? IllegalMove : BlackPromotionKnight;
1295                     else /* promotion optional, default is promote */
1296                              closure->kind = c == '=' ? NormalMove  : BlackPromotionQueen;
1297
1298                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1299                                             NormalMove : IllegalMove;
1300             }
1301         }
1302     } else
1303     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
1304         if (closure->kind == WhitePromotionQueen
1305             || closure->kind == BlackPromotionQueen) {
1306             closure->kind =
1307               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
1308                                   closure->promoCharIn);
1309         } else {
1310             closure->kind = IllegalMove;
1311         }
1312     }
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, rf, ff, rt, ft, promoChar, out)
1389      Board board;
1390      int flags;
1391      int rf, ff, rt, ft;
1392      int promoChar;
1393      char out[MOVE_LEN];
1394 {
1395     ChessSquare piece;
1396     ChessMove kind;
1397     char *outp = out, c;
1398     CoordsToAlgebraicClosure cl;
1399
1400     if (rf == DROP_RANK) {
1401         /* Bughouse piece drop */
1402         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1403         *outp++ = '@';
1404         *outp++ = ft + AAA;
1405         if(rt+ONE <= '9')
1406            *outp++ = rt + ONE;
1407         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1408         *outp = NULLCHAR;
1409         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1410     }
1411
1412     if (promoChar == 'x') promoChar = NULLCHAR;
1413     piece = board[rf][ff];
1414     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1415
1416   if (appData.debugMode)
1417           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1418     switch (piece) {
1419       case WhitePawn:
1420       case BlackPawn:
1421         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1422         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1423             /* Keep short notation if move is illegal only because it
1424                leaves the player in check, but still return IllegalMove */
1425             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1426             if (kind == IllegalMove) break;
1427             kind = IllegalMove;
1428         }
1429         /* Pawn move */
1430         *outp++ = ff + AAA;
1431         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1432             /* Non-capture; use style "e5" */
1433             if(rt+ONE <= '9')
1434                *outp++ = rt + ONE;
1435             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1436         } else {
1437             /* Capture; use style "exd5" */
1438             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1439             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1440             *outp++ = ft + AAA;
1441             if(rt+ONE <= '9')
1442                *outp++ = rt + ONE;
1443             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1444         }
1445         /* Use promotion suffix style "=Q" */
1446         *outp = NULLCHAR;
1447   if (appData.debugMode)
1448           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1449         if (promoChar != NULLCHAR) {
1450             if(gameInfo.variant == VariantShogi) {
1451                 /* [HGM] ... but not in Shogi! */
1452                 *outp++ = promoChar == '=' ? '=' : '+';
1453             } else {
1454                 *outp++ = '=';
1455                 *outp++ = ToUpper(promoChar);
1456             }
1457             *outp = NULLCHAR;
1458         }
1459         return kind;
1460
1461
1462       case WhiteKing:
1463       case BlackKing:
1464         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1465         /* Code added by Tord:  FRC castling. */
1466         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1467            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1468           if(ft > ff) strcpy(out, "O-O"); else strcpy(out, "O-O-O");
1469             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1470         }
1471         /* End of code added by Tord */
1472         /* Test for castling or ICS wild castling */
1473         /* Use style "O-O" (oh-oh) for PGN compatibility */
1474         else if (rf == rt &&
1475             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1476             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1477              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1478             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1479                 strcpy(out, "O-O");
1480             else
1481                 strcpy(out, "O-O-O");
1482
1483             /* This notation is always unambiguous, unless there are
1484                kings on both the d and e files, with "wild castling"
1485                possible for the king on the d file and normal castling
1486                possible for the other.  ICS rules for wild 9
1487                effectively make castling illegal for either king in
1488                this situation.  So I am not going to worry about it;
1489                I'll just generate an ambiguous O-O in this case.
1490             */
1491             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1492         }
1493
1494         /* else fall through */
1495       default:
1496         /* Piece move */
1497         cl.rf = rf;
1498         cl.ff = ff;
1499         cl.rt = rt;
1500         cl.ft = ft;
1501         cl.piece = piece;
1502         cl.kind = IllegalMove;
1503         cl.rank = cl.file = cl.either = 0;
1504         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1505
1506         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1507             /* Generate pretty moves for moving into check, but
1508                still return IllegalMove.
1509             */
1510             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1511             if (cl.kind == IllegalMove) break;
1512             cl.kind = IllegalMove;
1513         }
1514
1515         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1516            else "Ngf3" or "Ngxf7",
1517            else "N1f3" or "N5xf7",
1518            else "Ng1f3" or "Ng5xf7".
1519         */
1520         c = PieceToChar(piece) ;
1521         if( c == '~' || c == '+') {
1522            /* [HGM] print nonexistent piece as its demoted version */
1523            piece = (ChessSquare) (DEMOTED piece);
1524         }
1525         if(c=='+') *outp++ = c;
1526         *outp++ = ToUpper(PieceToChar(piece));
1527
1528         if (cl.file || (cl.either && !cl.rank)) {
1529             *outp++ = ff + AAA;
1530         }
1531         if (cl.rank) {
1532             if(rf+ONE <= '9')
1533                 *outp++ = rf + ONE;
1534             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1535         }
1536
1537         if(board[rt][ft] != EmptySquare)
1538           *outp++ = 'x';
1539
1540         *outp++ = ft + AAA;
1541         if(rt+ONE <= '9')
1542            *outp++ = rt + ONE;
1543         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1544         *outp = NULLCHAR;
1545         if (gameInfo.variant == VariantShogi) {
1546             /* [HGM] in Shogi non-pawns can promote */
1547             if(flags & F_WHITE_ON_MOVE) {
1548                 if( (int) cl.piece < (int) WhiteWazir &&
1549                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1550                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1551                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1552                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1553                     else cl.kind =  WhitePromotionQueen; /* promotion optional */
1554
1555                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1556                                             NormalMove : IllegalMove;
1557             } else {
1558                 if( (int) cl.piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1559                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1560                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1561                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1562                     else cl.kind =  BlackPromotionQueen; /* promotion optional */
1563                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1564                                             NormalMove : IllegalMove;
1565             }
1566             if(cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1567                 /* for optional promotions append '+' or '=' */
1568                 if(promoChar == '=') {
1569                     *outp++ = '=';
1570                     cl.kind = NormalMove;
1571                 } else *outp++ = '+';
1572                 *outp = NULLCHAR;
1573             } else if(cl.kind == IllegalMove) {
1574                 /* Illegal move specifies any given promotion */
1575                 if(promoChar != NULLCHAR && promoChar != 'x') {
1576                     *outp++ = '=';
1577                     *outp++ = ToUpper(promoChar);
1578                     *outp = NULLCHAR;
1579                 }
1580             }
1581         }
1582         return cl.kind;
1583
1584       /* [HGM] Always long notation for fairies we don't know */
1585       case WhiteFalcon:
1586       case BlackFalcon:
1587       case WhiteLance:
1588       case BlackLance:
1589       case WhiteGrasshopper:
1590       case BlackGrasshopper:
1591       case EmptySquare:
1592         /* Moving a nonexistent piece */
1593         break;
1594     }
1595
1596     /* Not a legal move, even ignoring check.
1597        If there was a piece on the from square,
1598        use style "Ng1g3" or "Ng1xe8";
1599        if there was a pawn or nothing (!),
1600        use style "g1g3" or "g1xe8".  Use "x"
1601        if a piece was on the to square, even
1602        a piece of the same color.
1603     */
1604     outp = out;
1605     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1606         *outp++ = ToUpper(PieceToChar(piece));
1607     }
1608     *outp++ = ff + AAA;
1609     if(rf+ONE <= '9')
1610        *outp++ = rf + ONE;
1611     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1612     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1613     *outp++ = ft + AAA;
1614     if(rt+ONE <= '9')
1615        *outp++ = rt + ONE;
1616     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1617     /* Use promotion suffix style "=Q" */
1618     if (promoChar != NULLCHAR && promoChar != 'x') {
1619         *outp++ = '=';
1620         *outp++ = ToUpper(promoChar);
1621     }
1622     *outp = NULLCHAR;
1623
1624     return IllegalMove;
1625 }
1626
1627 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1628
1629 typedef struct {
1630     /* Input */
1631     int rf, ff, rt, ft;
1632     /* Output */
1633     int recaptures;
1634 } ChaseClosure;
1635
1636 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1637
1638 int preyStackPointer, chaseStackPointer;
1639
1640 struct {
1641 char rf, ff, rt, ft;
1642 } chaseStack[100];
1643
1644 struct {
1645 char rank, file;
1646 } preyStack[100];
1647
1648
1649
1650
1651 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1652
1653 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1654                                 int rf, int ff, int rt, int ft,
1655                                 VOIDSTAR closure));
1656
1657 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1658      Board board;
1659      int flags;
1660      ChessMove kind;
1661      int rf, ff, rt, ft;
1662      VOIDSTAR closure;
1663 {   // For adding captures that can lead to chase indictment to the chaseStack
1664     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1665     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1666     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1667     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1668     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1669     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1670     chaseStack[chaseStackPointer].rf = rf;
1671     chaseStack[chaseStackPointer].ff = ff;
1672     chaseStack[chaseStackPointer].rt = rt;
1673     chaseStack[chaseStackPointer].ft = ft;
1674     chaseStackPointer++;
1675 }
1676
1677 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1678                                 int rf, int ff, int rt, int ft,
1679                                 VOIDSTAR closure));
1680
1681 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1682      Board board;
1683      int flags;
1684      ChessMove kind;
1685      int rf, ff, rt, ft;
1686      VOIDSTAR closure;
1687 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1688     int i;
1689     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1690
1691     if(board[rt][ft] == EmptySquare) return; // no capture
1692     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1693         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1694     }
1695     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1696     for(i=0; i<chaseStackPointer; i++) {
1697         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1698            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1699             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1700             chaseStack[i] = chaseStack[--chaseStackPointer];
1701             break;
1702         }
1703     }
1704 }
1705
1706 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1707                                 int rf, int ff, int rt, int ft,
1708                                 VOIDSTAR closure));
1709
1710 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1711      Board board;
1712      int flags;
1713      ChessMove kind;
1714      int rf, ff, rt, ft;
1715      VOIDSTAR closure;
1716 {   // for determining if a piece (given through the closure) is protected
1717     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1718
1719     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1720     if(appData.debugMode && board[rt][ft] != EmptySquare)
1721         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1722 }
1723
1724 extern char moveList[MAX_MOVES][MOVE_LEN];
1725
1726 int PerpetualChase(int first, int last)
1727 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1728     int i, j, k, tail;
1729     ChaseClosure cl;
1730     ChessSquare captured;
1731
1732     preyStackPointer = 0;        // clear stack of chased pieces
1733     for(i=first; i<last; i+=2) { // for all positions with same side to move
1734         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1735         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1736         // determine all captures possible after the move, and put them on chaseStack
1737         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl);
1738         if(appData.debugMode) { int n;
1739             for(n=0; n<chaseStackPointer; n++)
1740                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1741                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1742             fprintf(debugFP, ": all capts\n");
1743         }
1744         // determine all captures possible before the move, and delete them from chaseStack
1745         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1746         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1747         cl.rt = moveList[i][3]-ONE;
1748         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1749         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl);
1750         if(appData.debugMode) { int n;
1751             for(n=0; n<chaseStackPointer; n++)
1752                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1753                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1754             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1755         }
1756         // chaseSack now contains all captures made possible by the move
1757         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1758             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1759             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1760
1761             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1762             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1763
1764             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1765                 continue; // C or H attack on R is always chase; leave on chaseStack
1766
1767             if(attacker == victim) {
1768                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1769                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1770                         // we can capture back with equal piece, so this is no chase but a sacrifice
1771                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1772                         j--; /* ! */ continue;
1773                 }
1774
1775             }
1776
1777             // the attack is on a lower piece, or on a pinned or blocked equal one
1778             // test if the victim is protected by a true protector. First make the capture.
1779             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1780             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1781             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1782             // Then test if the opponent can recapture
1783             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1784             cl.rt = chaseStack[j].rt;
1785             cl.ft = chaseStack[j].ft;
1786             if(appData.debugMode) {
1787                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1788             }
1789             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl); // try all moves
1790             // unmake the capture
1791             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1792             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1793             // if a recapture was found, piece is protected, and we are not chasing it.
1794             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1795                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1796                 j--; /* ! */
1797             }
1798         }
1799         // chaseStack now contains all moves that chased
1800         if(appData.debugMode) { int n;
1801             for(n=0; n<chaseStackPointer; n++)
1802                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1803                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1804             fprintf(debugFP, ": chases\n");
1805         }
1806         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1807             for(j=0; j<chaseStackPointer; j++) {
1808                 preyStack[j].rank = chaseStack[j].rt;
1809                 preyStack[j].file = chaseStack[j].ft;
1810             }
1811             preyStackPointer = chaseStackPointer;
1812         }
1813         tail = 0;
1814         for(j=0; j<chaseStackPointer; j++) {
1815             for(k=0; k<preyStackPointer; k++) {
1816                 // search the victim of each chase move on the preyStack (first occurrence)
1817                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1818                     if(k < tail) break; // piece was already identified as still being chased
1819                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1820                     preyStack[tail] = preyStack[k];                // by swapping
1821                     preyStack[k] = preyStack[preyStackPointer];
1822                     tail++;
1823                     break;
1824                 }
1825             }
1826         }
1827         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1828         if(appData.debugMode) { int n;
1829             for(n=0; n<preyStackPointer; n++)
1830                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1831             fprintf(debugFP, "always chased upto ply %d\n", i);
1832         }
1833         // now adjust the location of the chased pieces according to opponent move
1834         for(j=0; j<preyStackPointer; j++) {
1835             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1836                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1837                 preyStack[j].rank = moveList[i+1][3]-ONE;
1838                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1839                 break;
1840             }
1841         }
1842     }
1843     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1844 }