moves.c

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