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     }
 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     }
1026
1027     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1028 }
1029
1030
1031 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1032                                     int rf, int ff, int rt, int ft,
1033                                     VOIDSTAR closure));
1034
1035 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1036      Board board;
1037      int flags;
1038      ChessMove kind;
1039      int rf, ff, rt, ft;
1040      VOIDSTAR closure;
1041 {
1042     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1043
1044 //    if (appData.debugMode) {
1045 //        fprintf(debugFP, "Legality test: %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1046 //    }
1047     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1048         cl->captures++; // [HGM] losers: count legal captures
1049     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1050       cl->kind = kind;
1051 }
1052
1053 ChessMove LegalityTest(board, flags, rf, ff, rt, ft, promoChar)
1054      Board board;
1055      int flags;
1056      int rf, ff, rt, ft, promoChar;
1057 {
1058     LegalityTestClosure cl; ChessSquare piece = board[rf][ff], *castlingRights = board[CASTLING];
1059
1060     if (appData.debugMode) {
1061         int i;
1062         for(i=0; i<6; i++) fprintf(debugFP, "%d ", castlingRights[i]);
1063         fprintf(debugFP, "Legality test? %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1064     }
1065     /* [HGM] Lance, Cobra and Falcon are wildcard pieces; consider all their moves legal */
1066     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1067     if(piece == WhiteFalcon || piece == BlackFalcon ||
1068        piece == WhiteCobra  || piece == BlackCobra  ||
1069        piece == WhiteLance  || piece == BlackLance)
1070         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1071
1072     cl.rf = rf;
1073     cl.ff = ff;
1074     cl.rt = rt;
1075     cl.ft = ft;
1076     cl.kind = IllegalMove;
1077     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1078     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl);
1079     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1080                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1081         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1082
1083     if(gameInfo.variant == VariantShogi) {
1084         /* [HGM] Shogi promotions. '=' means defer */
1085         if(rf != DROP_RANK && cl.kind == NormalMove) {
1086             ChessSquare piece = board[rf][ff];
1087
1088             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1089             if(promoChar != NULLCHAR && promoChar != 'x' &&
1090                promoChar != '+' && promoChar != '=' &&
1091                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(promoChar) )
1092                     cl.kind = IllegalMove;
1093             else if(flags & F_WHITE_ON_MOVE) {
1094                 if( (int) piece < (int) WhiteWazir &&
1095                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1096                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1097                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1098                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1099                     else /* promotion optional, default is promote */
1100                              cl.kind = promoChar == '=' ? WhiteNonPromotion : WhitePromotionQueen;
1101
1102                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1103                                             NormalMove : IllegalMove;
1104             } else {
1105                 if( (int) piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1106                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1107                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1108                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1109                     else /* promotion optional, default is promote */
1110                              cl.kind = promoChar == '=' ? BlackNonPromotion : BlackPromotionQueen;
1111
1112                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1113                                             NormalMove : IllegalMove;
1114             }
1115         }
1116     } else
1117     if (promoChar != NULLCHAR && promoChar != 'x') {
1118         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1119         if (cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1120             cl.kind =
1121               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0, promoChar);
1122         } else {
1123             cl.kind = IllegalMove;
1124         }
1125     }
1126     /* [HGM] For promotions, 'ToQueen' = optional, 'ToKnight' = mandatory */
1127     return cl.kind;
1128 }
1129
1130 typedef struct {
1131     int count;
1132 } MateTestClosure;
1133
1134 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1135                                 int rf, int ff, int rt, int ft,
1136                                 VOIDSTAR closure));
1137
1138 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1139      Board board;
1140      int flags;
1141      ChessMove kind;
1142      int rf, ff, rt, ft;
1143      VOIDSTAR closure;
1144 {
1145     register MateTestClosure *cl = (MateTestClosure *) closure;
1146
1147     cl->count++;
1148 }
1149
1150 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1151 int MateTest(board, flags)
1152      Board board;
1153      int flags;
1154 {
1155     MateTestClosure cl;
1156     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1157     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1158
1159     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1160         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1161         nrKing += (board[r][f] == king);   // stm has king
1162         if( board[r][f] != EmptySquare ) {
1163             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1164                  myPieces++;
1165             else hisPieces++;
1166         }
1167     }
1168     if(appData.debugMode) fprintf(debugFP, "MateTest: K=%d, my=%d, his=%d\n", nrKing, myPieces, hisPieces);
1169     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1170         case VariantShatranj:
1171                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1172         default:
1173                 break;
1174         case VariantAtomic:
1175                 if(nrKing == 0) return MT_NOKING;
1176                 break;
1177         case VariantLosers:
1178                 if(myPieces == 1) return MT_BARE;
1179     }
1180     cl.count = 0;
1181     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl);
1182     // [HGM] 3check: yet to do!
1183     if (cl.count > 0) {
1184         return inCheck ? MT_CHECK : MT_NONE;
1185     } else {
1186         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1187                 return myPieces == hisPieces ? MT_STALEMATE :
1188                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1189         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1190         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1191
1192         return inCheck ? MT_CHECKMATE
1193                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1194                           MT_STAINMATE : MT_STALEMATE;
1195     }
1196 }
1197
1198
1199 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1200                                     int rf, int ff, int rt, int ft,
1201                                     VOIDSTAR closure));
1202
1203 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1204      Board board;
1205      int flags;
1206      ChessMove kind;
1207      int rf, ff, rt, ft;
1208      VOIDSTAR closure;
1209 {
1210     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1211     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1212
1213     // [HGM] wild: for wild-card pieces rt and rf are dummies
1214     if(piece == WhiteFalcon || piece == BlackFalcon ||
1215        piece == WhiteCobra  || piece == BlackCobra  ||
1216        piece == WhiteLance  || piece == BlackLance)
1217         wildCard = TRUE;
1218
1219     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1220          || PieceToChar(board[rf][ff]) == '~'
1221               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1222                                                                       ) &&
1223         (cl->rfIn == -1 || cl->rfIn == rf) &&
1224         (cl->ffIn == -1 || cl->ffIn == ff) &&
1225         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1226         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1227
1228         cl->count++;
1229         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1230           // [HGM] oneclick: if multiple moves, be sure we remember capture
1231           cl->piece = board[rf][ff];
1232           cl->rf = rf;
1233           cl->ff = ff;
1234           cl->rt = wildCard ? cl->rtIn : rt;
1235           cl->ft = wildCard ? cl->ftIn : ft;
1236           cl->kind = kind;
1237         }
1238         cl->captures += (board[cl->rt][cl->ft] != EmptySquare); // [HGM] oneclick: count captures
1239     }
1240 }
1241
1242 void Disambiguate(board, flags, closure)
1243      Board board;
1244      int flags;
1245      DisambiguateClosure *closure;
1246 {
1247     int illegal = 0; char c = closure->promoCharIn;
1248
1249     closure->count = closure->captures = 0;
1250     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1251     closure->kind = ImpossibleMove;
1252     if (appData.debugMode) {
1253         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1254                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1255                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1256     }
1257     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure);
1258     if (closure->count == 0) {
1259         /* See if it's an illegal move due to check */
1260         illegal = 1;
1261         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure);
1262         if (closure->count == 0) {
1263             /* No, it's not even that */
1264     if (appData.debugMode) { int i, j;
1265         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1266                 for(j=0; j<BOARD_WIDTH; j++)
1267                         fprintf(debugFP, "%3d", (int) board[i][j]);
1268                 fprintf(debugFP, "\n");
1269         }
1270     }
1271             return;
1272         }
1273     }
1274
1275     if(gameInfo.variant == VariantShogi) {
1276         /* [HGM] Shogi promotions. '=' means defer */
1277         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1278             ChessSquare piece = closure->piece;
1279             if(c != NULLCHAR && c != 'x' && c != '+' && c != '=' &&
1280                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(c) )
1281                     closure->kind = IllegalMove;
1282             else if(flags & F_WHITE_ON_MOVE) {
1283                 if( (int) piece < (int) WhiteWazir &&
1284                      (closure->rf > BOARD_HEIGHT-4 || closure->rt > BOARD_HEIGHT-4) ) {
1285                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1286                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1287                              closure->kind = c == '=' ? IllegalMove : WhitePromotionKnight;
1288                     else /* promotion optional, default is promote */
1289                              closure->kind = c == '=' ? NormalMove  : WhitePromotionQueen;
1290                     if(c != '=') closure->promoCharIn = 'q';
1291                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1292                                             NormalMove : IllegalMove;
1293             } else {
1294                 if( (int) piece < (int) BlackWazir && (closure->rf < 3 || closure->rt < 3) ) {
1295                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1296                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1297                              closure->kind = c == '=' ? IllegalMove : BlackPromotionKnight;
1298                     else /* promotion optional, default is promote */
1299                              closure->kind = c == '=' ? NormalMove  : BlackPromotionQueen;
1300                     if(c != '=') closure->promoCharIn = 'q';
1301                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1302                                             NormalMove : IllegalMove;
1303             }
1304         }
1305     } else
1306     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
1307         if (closure->kind == WhitePromotionQueen
1308             || closure->kind == BlackPromotionQueen) {
1309             closure->kind =
1310               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
1311                                   closure->promoCharIn);
1312         } else {
1313             closure->kind = IllegalMove;
1314         }
1315     }
1316     /* [HGM] returns 'q' for optional promotion, 'n' for mandatory */
1317     if(closure->promoCharIn != '=')
1318         closure->promoChar = ToLower(closure->promoCharIn);
1319     else closure->promoChar = '=';
1320     if (closure->promoChar == 'x') closure->promoChar = NULLCHAR;
1321     if (closure->count > 1) {
1322         closure->kind = AmbiguousMove;
1323     }
1324     if (illegal) {
1325         /* Note: If more than one illegal move matches, but no legal
1326            moves, we return IllegalMove, not AmbiguousMove.  Caller
1327            can look at closure->count to detect this.
1328         */
1329         closure->kind = IllegalMove;
1330     }
1331     if(closure->kind == IllegalMove)
1332     /* [HGM] might be a variant we don't understand, pass on promotion info */
1333         closure->promoChar = ToLower(closure->promoCharIn);
1334     if (appData.debugMode) {
1335         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1336         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1337         closure->promoChar >= ' ' ? closure->promoChar:'-');
1338     }
1339 }
1340
1341
1342 typedef struct {
1343     /* Input */
1344     ChessSquare piece;
1345     int rf, ff, rt, ft;
1346     /* Output */
1347     ChessMove kind;
1348     int rank;
1349     int file;
1350     int either;
1351 } CoordsToAlgebraicClosure;
1352
1353 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1354                                          ChessMove kind, int rf, int ff,
1355                                          int rt, int ft, VOIDSTAR closure));
1356
1357 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1358      Board board;
1359      int flags;
1360      ChessMove kind;
1361      int rf, ff, rt, ft;
1362      VOIDSTAR closure;
1363 {
1364     register CoordsToAlgebraicClosure *cl =
1365       (CoordsToAlgebraicClosure *) closure;
1366
1367     if (rt == cl->rt && ft == cl->ft &&
1368         (board[rf][ff] == cl->piece
1369          || PieceToChar(board[rf][ff]) == '~' &&
1370             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1371                                      ) {
1372         if (rf == cl->rf) {
1373             if (ff == cl->ff) {
1374                 cl->kind = kind; /* this is the move we want */
1375             } else {
1376                 cl->file++; /* need file to rule out this move */
1377             }
1378         } else {
1379             if (ff == cl->ff) {
1380                 cl->rank++; /* need rank to rule out this move */
1381             } else {
1382                 cl->either++; /* rank or file will rule out this move */
1383             }
1384         }
1385     }
1386 }
1387
1388 /* Convert coordinates to normal algebraic notation.
1389    promoChar must be NULLCHAR or 'x' if not a promotion.
1390 */
1391 ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out)
1392      Board board;
1393      int flags;
1394      int rf, ff, rt, ft;
1395      int promoChar;
1396      char out[MOVE_LEN];
1397 {
1398     ChessSquare piece;
1399     ChessMove kind;
1400     char *outp = out, c;
1401     CoordsToAlgebraicClosure cl;
1402
1403     if (rf == DROP_RANK) {
1404         /* Bughouse piece drop */
1405         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1406         *outp++ = '@';
1407         *outp++ = ft + AAA;
1408         if(rt+ONE <= '9')
1409            *outp++ = rt + ONE;
1410         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1411         *outp = NULLCHAR;
1412         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1413     }
1414
1415     if (promoChar == 'x') promoChar = NULLCHAR;
1416     piece = board[rf][ff];
1417     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1418
1419   if (appData.debugMode)
1420           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1421     switch (piece) {
1422       case WhitePawn:
1423       case BlackPawn:
1424         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1425         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1426             /* Keep short notation if move is illegal only because it
1427                leaves the player in check, but still return IllegalMove */
1428             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1429             if (kind == IllegalMove) break;
1430             kind = IllegalMove;
1431         }
1432         /* Pawn move */
1433         *outp++ = ff + AAA;
1434         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1435             /* Non-capture; use style "e5" */
1436             if(rt+ONE <= '9')
1437                *outp++ = rt + ONE;
1438             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1439         } else {
1440             /* Capture; use style "exd5" */
1441             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1442             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1443             *outp++ = ft + AAA;
1444             if(rt+ONE <= '9')
1445                *outp++ = rt + ONE;
1446             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1447         }
1448         /* Use promotion suffix style "=Q" */
1449         *outp = NULLCHAR;
1450   if (appData.debugMode)
1451           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1452         if (promoChar != NULLCHAR) {
1453             if(gameInfo.variant == VariantShogi) {
1454                 /* [HGM] ... but not in Shogi! */
1455                 *outp++ = promoChar == '=' ? '=' : '+';
1456             } else {
1457                 *outp++ = '=';
1458                 *outp++ = ToUpper(promoChar);
1459             }
1460             *outp = NULLCHAR;
1461         }
1462         return kind;
1463
1464
1465       case WhiteKing:
1466       case BlackKing:
1467         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1468         /* Code added by Tord:  FRC castling. */
1469         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1470            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1471           if(ft > ff) strcpy(out, "O-O"); else strcpy(out, "O-O-O");
1472             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1473         }
1474         /* End of code added by Tord */
1475         /* Test for castling or ICS wild castling */
1476         /* Use style "O-O" (oh-oh) for PGN compatibility */
1477         else if (rf == rt &&
1478             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1479             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1480              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1481             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1482                 strcpy(out, "O-O");
1483             else
1484                 strcpy(out, "O-O-O");
1485
1486             /* This notation is always unambiguous, unless there are
1487                kings on both the d and e files, with "wild castling"
1488                possible for the king on the d file and normal castling
1489                possible for the other.  ICS rules for wild 9
1490                effectively make castling illegal for either king in
1491                this situation.  So I am not going to worry about it;
1492                I'll just generate an ambiguous O-O in this case.
1493             */
1494             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1495         }
1496
1497         /* else fall through */
1498       default:
1499         /* Piece move */
1500         cl.rf = rf;
1501         cl.ff = ff;
1502         cl.rt = rt;
1503         cl.ft = ft;
1504         cl.piece = piece;
1505         cl.kind = IllegalMove;
1506         cl.rank = cl.file = cl.either = 0;
1507         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1508
1509         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1510             /* Generate pretty moves for moving into check, but
1511                still return IllegalMove.
1512             */
1513             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1514             if (cl.kind == IllegalMove) break;
1515             cl.kind = IllegalMove;
1516         }
1517
1518         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1519            else "Ngf3" or "Ngxf7",
1520            else "N1f3" or "N5xf7",
1521            else "Ng1f3" or "Ng5xf7".
1522         */
1523         c = PieceToChar(piece) ;
1524         if( c == '~' || c == '+') {
1525            /* [HGM] print nonexistent piece as its demoted version */
1526            piece = (ChessSquare) (DEMOTED piece);
1527         }
1528         if(c=='+') *outp++ = c;
1529         *outp++ = ToUpper(PieceToChar(piece));
1530
1531         if (cl.file || (cl.either && !cl.rank)) {
1532             *outp++ = ff + AAA;
1533         }
1534         if (cl.rank) {
1535             if(rf+ONE <= '9')
1536                 *outp++ = rf + ONE;
1537             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1538         }
1539
1540         if(board[rt][ft] != EmptySquare)
1541           *outp++ = 'x';
1542
1543         *outp++ = ft + AAA;
1544         if(rt+ONE <= '9')
1545            *outp++ = rt + ONE;
1546         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1547         *outp = NULLCHAR;
1548         if (gameInfo.variant == VariantShogi) {
1549             /* [HGM] in Shogi non-pawns can promote */
1550             if(flags & F_WHITE_ON_MOVE) {
1551                 if( (int) cl.piece < (int) WhiteWazir &&
1552                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1553                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1554                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1555                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1556                     else cl.kind =  WhitePromotionQueen; /* promotion optional */
1557
1558                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1559                                             NormalMove : IllegalMove;
1560             } else {
1561                 if( (int) cl.piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1562                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1563                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1564                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1565                     else cl.kind =  BlackPromotionQueen; /* promotion optional */
1566                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1567                                             NormalMove : IllegalMove;
1568             }
1569             if(cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1570                 /* for optional promotions append '+' or '=' */
1571                 if(promoChar == '=') {
1572                     *outp++ = '=';
1573                     cl.kind = NormalMove;
1574                 } else *outp++ = '+';
1575                 *outp = NULLCHAR;
1576             } else if(cl.kind == IllegalMove) {
1577                 /* Illegal move specifies any given promotion */
1578                 if(promoChar != NULLCHAR && promoChar != 'x') {
1579                     *outp++ = '=';
1580                     *outp++ = ToUpper(promoChar);
1581                     *outp = NULLCHAR;
1582                 }
1583             }
1584         }
1585         return cl.kind;
1586
1587       /* [HGM] Always long notation for fairies we don't know */
1588       case WhiteFalcon:
1589       case BlackFalcon:
1590       case WhiteLance:
1591       case BlackLance:
1592       case WhiteGrasshopper:
1593       case BlackGrasshopper:
1594       case EmptySquare:
1595         /* Moving a nonexistent piece */
1596         break;
1597     }
1598
1599     /* Not a legal move, even ignoring check.
1600        If there was a piece on the from square,
1601        use style "Ng1g3" or "Ng1xe8";
1602        if there was a pawn or nothing (!),
1603        use style "g1g3" or "g1xe8".  Use "x"
1604        if a piece was on the to square, even
1605        a piece of the same color.
1606     */
1607     outp = out;
1608     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1609         *outp++ = ToUpper(PieceToChar(piece));
1610     }
1611     *outp++ = ff + AAA;
1612     if(rf+ONE <= '9')
1613        *outp++ = rf + ONE;
1614     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1615     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1616     *outp++ = ft + AAA;
1617     if(rt+ONE <= '9')
1618        *outp++ = rt + ONE;
1619     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1620     /* Use promotion suffix style "=Q" */
1621     if (promoChar != NULLCHAR && promoChar != 'x') {
1622         *outp++ = '=';
1623         *outp++ = ToUpper(promoChar);
1624     }
1625     *outp = NULLCHAR;
1626
1627     return IllegalMove;
1628 }
1629
1630 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1631
1632 typedef struct {
1633     /* Input */
1634     int rf, ff, rt, ft;
1635     /* Output */
1636     int recaptures;
1637 } ChaseClosure;
1638
1639 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1640
1641 int preyStackPointer, chaseStackPointer;
1642
1643 struct {
1644 char rf, ff, rt, ft;
1645 } chaseStack[100];
1646
1647 struct {
1648 char rank, file;
1649 } preyStack[100];
1650
1651
1652
1653
1654 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1655
1656 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1657                                 int rf, int ff, int rt, int ft,
1658                                 VOIDSTAR closure));
1659
1660 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1661      Board board;
1662      int flags;
1663      ChessMove kind;
1664      int rf, ff, rt, ft;
1665      VOIDSTAR closure;
1666 {   // For adding captures that can lead to chase indictment to the chaseStack
1667     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1668     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1669     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1670     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1671     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1672     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1673     chaseStack[chaseStackPointer].rf = rf;
1674     chaseStack[chaseStackPointer].ff = ff;
1675     chaseStack[chaseStackPointer].rt = rt;
1676     chaseStack[chaseStackPointer].ft = ft;
1677     chaseStackPointer++;
1678 }
1679
1680 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1681                                 int rf, int ff, int rt, int ft,
1682                                 VOIDSTAR closure));
1683
1684 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1685      Board board;
1686      int flags;
1687      ChessMove kind;
1688      int rf, ff, rt, ft;
1689      VOIDSTAR closure;
1690 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1691     int i;
1692     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1693
1694     if(board[rt][ft] == EmptySquare) return; // no capture
1695     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1696         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1697     }
1698     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1699     for(i=0; i<chaseStackPointer; i++) {
1700         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1701            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1702             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1703             chaseStack[i] = chaseStack[--chaseStackPointer];
1704             break;
1705         }
1706     }
1707 }
1708
1709 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1710                                 int rf, int ff, int rt, int ft,
1711                                 VOIDSTAR closure));
1712
1713 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1714      Board board;
1715      int flags;
1716      ChessMove kind;
1717      int rf, ff, rt, ft;
1718      VOIDSTAR closure;
1719 {   // for determining if a piece (given through the closure) is protected
1720     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1721
1722     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1723     if(appData.debugMode && board[rt][ft] != EmptySquare)
1724         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1725 }
1726
1727 extern char moveList[MAX_MOVES][MOVE_LEN];
1728
1729 int PerpetualChase(int first, int last)
1730 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1731     int i, j, k, tail;
1732     ChaseClosure cl;
1733     ChessSquare captured;
1734
1735     preyStackPointer = 0;        // clear stack of chased pieces
1736     for(i=first; i<last; i+=2) { // for all positions with same side to move
1737         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1738         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1739         // determine all captures possible after the move, and put them on chaseStack
1740         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl);
1741         if(appData.debugMode) { int n;
1742             for(n=0; n<chaseStackPointer; n++)
1743                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1744                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1745             fprintf(debugFP, ": all capts\n");
1746         }
1747         // determine all captures possible before the move, and delete them from chaseStack
1748         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1749         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1750         cl.rt = moveList[i][3]-ONE;
1751         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1752         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl);
1753         if(appData.debugMode) { int n;
1754             for(n=0; n<chaseStackPointer; n++)
1755                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1756                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1757             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1758         }
1759         // chaseSack now contains all captures made possible by the move
1760         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1761             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1762             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1763
1764             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1765             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1766
1767             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1768                 continue; // C or H attack on R is always chase; leave on chaseStack
1769
1770             if(attacker == victim) {
1771                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1772                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1773                         // we can capture back with equal piece, so this is no chase but a sacrifice
1774                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1775                         j--; /* ! */ continue;
1776                 }
1777
1778             }
1779
1780             // the attack is on a lower piece, or on a pinned or blocked equal one
1781             // test if the victim is protected by a true protector. First make the capture.
1782             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1783             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1784             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1785             // Then test if the opponent can recapture
1786             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1787             cl.rt = chaseStack[j].rt;
1788             cl.ft = chaseStack[j].ft;
1789             if(appData.debugMode) {
1790                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1791             }
1792             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl); // try all moves
1793             // unmake the capture
1794             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1795             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1796             // if a recapture was found, piece is protected, and we are not chasing it.
1797             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1798                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1799                 j--; /* ! */
1800             }
1801         }
1802         // chaseStack now contains all moves that chased
1803         if(appData.debugMode) { int n;
1804             for(n=0; n<chaseStackPointer; n++)
1805                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1806                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1807             fprintf(debugFP, ": chases\n");
1808         }
1809         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1810             for(j=0; j<chaseStackPointer; j++) {
1811                 preyStack[j].rank = chaseStack[j].rt;
1812                 preyStack[j].file = chaseStack[j].ft;
1813             }
1814             preyStackPointer = chaseStackPointer;
1815         }
1816         tail = 0;
1817         for(j=0; j<chaseStackPointer; j++) {
1818             for(k=0; k<preyStackPointer; k++) {
1819                 // search the victim of each chase move on the preyStack (first occurrence)
1820                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1821                     if(k < tail) break; // piece was already identified as still being chased
1822                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1823                     preyStack[tail] = preyStack[k];                // by swapping
1824                     preyStack[k] = preyStack[preyStackPointer];
1825                     tail++;
1826                     break;
1827                 }
1828             }
1829         }
1830         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1831         if(appData.debugMode) { int n;
1832             for(n=0; n<preyStackPointer; n++)
1833                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1834             fprintf(debugFP, "always chased upto ply %d\n", i);
1835         }
1836         // now adjust the location of the chased pieces according to opponent move
1837         for(j=0; j<preyStackPointer; j++) {
1838             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1839                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1840                 preyStack[j].rank = moveList[i+1][3]-ONE;
1841                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1842                 break;
1843             }
1844         }
1845     }
1846     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1847 }