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