moves.c

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