moves.c

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