moves.c

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