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-4 || rt > BOARD_HEIGHT-4) ) {
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 < 3 || rt < 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.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1223                 return myPieces == hisPieces ? MT_STALEMATE :
1224                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1225         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1226         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1227
1228         return inCheck ? MT_CHECKMATE
1229                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1230                           MT_STAINMATE : MT_STALEMATE;
1231     }
1232 }
1233
1234
1235 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1236                                     int rf, int ff, int rt, int ft,
1237                                     VOIDSTAR closure));
1238
1239 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1240      Board board;
1241      int flags;
1242      ChessMove kind;
1243      int rf, ff, rt, ft;
1244      VOIDSTAR closure;
1245 {
1246     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1247     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1248
1249     // [HGM] wild: for wild-card pieces rt and rf are dummies
1250     if(piece == WhiteFalcon || piece == BlackFalcon ||
1251        piece == WhiteCobra  || piece == BlackCobra  ||
1252        piece == WhiteLance  || piece == BlackLance)
1253         wildCard = TRUE;
1254
1255     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1256          || PieceToChar(board[rf][ff]) == '~'
1257               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1258                                                                       ) &&
1259         (cl->rfIn == -1 || cl->rfIn == rf) &&
1260         (cl->ffIn == -1 || cl->ffIn == ff) &&
1261         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1262         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1263
1264         cl->count++;
1265         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1266           // [HGM] oneclick: if multiple moves, be sure we remember capture
1267           cl->piece = board[rf][ff];
1268           cl->rf = rf;
1269           cl->ff = ff;
1270           cl->rt = wildCard ? cl->rtIn : rt;
1271           cl->ft = wildCard ? cl->ftIn : ft;
1272           cl->kind = kind;
1273         }
1274         cl->captures += (board[cl->rt][cl->ft] != EmptySquare); // [HGM] oneclick: count captures
1275     }
1276 }
1277
1278 void Disambiguate(board, flags, closure)
1279      Board board;
1280      int flags;
1281      DisambiguateClosure *closure;
1282 {
1283     int illegal = 0; char c = closure->promoCharIn;
1284
1285     closure->count = closure->captures = 0;
1286     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1287     closure->kind = ImpossibleMove;
1288     if (appData.debugMode) {
1289         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1290                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1291                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1292     }
1293     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure);
1294     if (closure->count == 0) {
1295         /* See if it's an illegal move due to check */
1296         illegal = 1;
1297         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure);
1298         if (closure->count == 0) {
1299             /* No, it's not even that */
1300     if (appData.debugMode) { int i, j;
1301         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1302                 for(j=0; j<BOARD_WIDTH; j++)
1303                         fprintf(debugFP, "%3d", (int) board[i][j]);
1304                 fprintf(debugFP, "\n");
1305         }
1306     }
1307             return;
1308         }
1309     }
1310
1311     if(gameInfo.variant == VariantShogi) {
1312         /* [HGM] Shogi promotions. '=' means defer */
1313         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1314             ChessSquare piece = closure->piece;
1315             if(c != NULLCHAR && c != 'x' && c != '+' && c != '=' &&
1316                ToUpper(PieceToChar(PROMOTED piece)) != ToUpper(c) )
1317                     closure->kind = IllegalMove;
1318             else if(flags & F_WHITE_ON_MOVE) {
1319                 if( (int) piece < (int) WhiteWazir &&
1320                      (closure->rf > BOARD_HEIGHT-4 || closure->rt > BOARD_HEIGHT-4) ) {
1321                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1322                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1323                              closure->kind = c == '=' ? IllegalMove : WhitePromotionKnight;
1324                     else /* promotion optional, default is promote */
1325                              closure->kind = c == '=' ? NormalMove  : WhitePromotionQueen;
1326                     if(c != '=') closure->promoCharIn = 'q';
1327                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1328                                             NormalMove : IllegalMove;
1329             } else {
1330                 if( (int) piece < (int) BlackWazir && (closure->rf < 3 || closure->rt < 3) ) {
1331                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1332                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1333                              closure->kind = c == '=' ? IllegalMove : BlackPromotionKnight;
1334                     else /* promotion optional, default is promote */
1335                              closure->kind = c == '=' ? NormalMove  : BlackPromotionQueen;
1336                     if(c != '=') closure->promoCharIn = 'q';
1337                 } else closure->kind = (c == NULLCHAR || c == 'x' || c == '=') ?
1338                                             NormalMove : IllegalMove;
1339             }
1340         }
1341     } else
1342     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
1343         if (closure->kind == WhitePromotionQueen
1344             || closure->kind == BlackPromotionQueen) {
1345             closure->kind =
1346               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
1347                                   closure->promoCharIn);
1348         } else {
1349             closure->kind = IllegalMove;
1350         }
1351     }
1352     /* [HGM] returns 'q' for optional promotion, 'n' for mandatory */
1353     if(closure->promoCharIn != '=')
1354         closure->promoChar = ToLower(closure->promoCharIn);
1355     else closure->promoChar = '=';
1356     if (closure->promoChar == 'x') closure->promoChar = NULLCHAR;
1357     if (closure->count > 1) {
1358         closure->kind = AmbiguousMove;
1359     }
1360     if (illegal) {
1361         /* Note: If more than one illegal move matches, but no legal
1362            moves, we return IllegalMove, not AmbiguousMove.  Caller
1363            can look at closure->count to detect this.
1364         */
1365         closure->kind = IllegalMove;
1366     }
1367     if(closure->kind == IllegalMove)
1368     /* [HGM] might be a variant we don't understand, pass on promotion info */
1369         closure->promoChar = ToLower(closure->promoCharIn);
1370     if (appData.debugMode) {
1371         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1372         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1373         closure->promoChar >= ' ' ? closure->promoChar:'-');
1374     }
1375 }
1376
1377
1378 typedef struct {
1379     /* Input */
1380     ChessSquare piece;
1381     int rf, ff, rt, ft;
1382     /* Output */
1383     ChessMove kind;
1384     int rank;
1385     int file;
1386     int either;
1387 } CoordsToAlgebraicClosure;
1388
1389 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1390                                          ChessMove kind, int rf, int ff,
1391                                          int rt, int ft, VOIDSTAR closure));
1392
1393 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1394      Board board;
1395      int flags;
1396      ChessMove kind;
1397      int rf, ff, rt, ft;
1398      VOIDSTAR closure;
1399 {
1400     register CoordsToAlgebraicClosure *cl =
1401       (CoordsToAlgebraicClosure *) closure;
1402
1403     if (rt == cl->rt && ft == cl->ft &&
1404         (board[rf][ff] == cl->piece
1405          || PieceToChar(board[rf][ff]) == '~' &&
1406             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1407                                      ) {
1408         if (rf == cl->rf) {
1409             if (ff == cl->ff) {
1410                 cl->kind = kind; /* this is the move we want */
1411             } else {
1412                 cl->file++; /* need file to rule out this move */
1413             }
1414         } else {
1415             if (ff == cl->ff) {
1416                 cl->rank++; /* need rank to rule out this move */
1417             } else {
1418                 cl->either++; /* rank or file will rule out this move */
1419             }
1420         }
1421     }
1422 }
1423
1424 /* Convert coordinates to normal algebraic notation.
1425    promoChar must be NULLCHAR or 'x' if not a promotion.
1426 */
1427 ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out)
1428      Board board;
1429      int flags;
1430      int rf, ff, rt, ft;
1431      int promoChar;
1432      char out[MOVE_LEN];
1433 {
1434     ChessSquare piece;
1435     ChessMove kind;
1436     char *outp = out, c;
1437     CoordsToAlgebraicClosure cl;
1438
1439     if (rf == DROP_RANK) {
1440         /* Bughouse piece drop */
1441         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1442         *outp++ = '@';
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         *outp = NULLCHAR;
1448         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1449     }
1450
1451     if (promoChar == 'x') promoChar = NULLCHAR;
1452     piece = board[rf][ff];
1453     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1454
1455   if (appData.debugMode)
1456           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1457     switch (piece) {
1458       case WhitePawn:
1459       case BlackPawn:
1460         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1461         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1462             /* Keep short notation if move is illegal only because it
1463                leaves the player in check, but still return IllegalMove */
1464             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1465             if (kind == IllegalMove) break;
1466             kind = IllegalMove;
1467         }
1468         /* Pawn move */
1469         *outp++ = ff + AAA;
1470         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1471             /* Non-capture; use style "e5" */
1472             if(rt+ONE <= '9')
1473                *outp++ = rt + ONE;
1474             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1475         } else {
1476             /* Capture; use style "exd5" */
1477             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1478             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1479             *outp++ = ft + AAA;
1480             if(rt+ONE <= '9')
1481                *outp++ = rt + ONE;
1482             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1483         }
1484         /* Use promotion suffix style "=Q" */
1485         *outp = NULLCHAR;
1486   if (appData.debugMode)
1487           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1488         if (promoChar != NULLCHAR) {
1489             if(gameInfo.variant == VariantShogi) {
1490                 /* [HGM] ... but not in Shogi! */
1491                 *outp++ = promoChar == '=' ? '=' : '+';
1492             } else {
1493                 *outp++ = '=';
1494                 *outp++ = ToUpper(promoChar);
1495             }
1496             *outp = NULLCHAR;
1497         }
1498         return kind;
1499
1500
1501       case WhiteKing:
1502       case BlackKing:
1503         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1504         /* Code added by Tord:  FRC castling. */
1505         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1506            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1507           if(ft > ff) strcpy(out, "O-O"); else strcpy(out, "O-O-O");
1508             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1509         }
1510         /* End of code added by Tord */
1511         /* Test for castling or ICS wild castling */
1512         /* Use style "O-O" (oh-oh) for PGN compatibility */
1513         else if (rf == rt &&
1514             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1515             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1516              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1517             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1518                 strcpy(out, "O-O");
1519             else
1520                 strcpy(out, "O-O-O");
1521
1522             /* This notation is always unambiguous, unless there are
1523                kings on both the d and e files, with "wild castling"
1524                possible for the king on the d file and normal castling
1525                possible for the other.  ICS rules for wild 9
1526                effectively make castling illegal for either king in
1527                this situation.  So I am not going to worry about it;
1528                I'll just generate an ambiguous O-O in this case.
1529             */
1530             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1531         }
1532
1533         /* else fall through */
1534       default:
1535         /* Piece move */
1536         cl.rf = rf;
1537         cl.ff = ff;
1538         cl.rt = rt;
1539         cl.ft = ft;
1540         cl.piece = piece;
1541         cl.kind = IllegalMove;
1542         cl.rank = cl.file = cl.either = 0;
1543         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1544
1545         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1546             /* Generate pretty moves for moving into check, but
1547                still return IllegalMove.
1548             */
1549             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
1550             if (cl.kind == IllegalMove) break;
1551             cl.kind = IllegalMove;
1552         }
1553
1554         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1555            else "Ngf3" or "Ngxf7",
1556            else "N1f3" or "N5xf7",
1557            else "Ng1f3" or "Ng5xf7".
1558         */
1559         c = PieceToChar(piece) ;
1560         if( c == '~' || c == '+') {
1561            /* [HGM] print nonexistent piece as its demoted version */
1562            piece = (ChessSquare) (DEMOTED piece);
1563         }
1564         if(c=='+') *outp++ = c;
1565         *outp++ = ToUpper(PieceToChar(piece));
1566
1567         if (cl.file || (cl.either && !cl.rank)) {
1568             *outp++ = ff + AAA;
1569         }
1570         if (cl.rank) {
1571             if(rf+ONE <= '9')
1572                 *outp++ = rf + ONE;
1573             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1574         }
1575
1576         if(board[rt][ft] != EmptySquare)
1577           *outp++ = 'x';
1578
1579         *outp++ = ft + AAA;
1580         if(rt+ONE <= '9')
1581            *outp++ = rt + ONE;
1582         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1583         *outp = NULLCHAR;
1584         if (gameInfo.variant == VariantShogi) {
1585             /* [HGM] in Shogi non-pawns can promote */
1586             if(flags & F_WHITE_ON_MOVE) {
1587                 if( (int) cl.piece < (int) WhiteWazir &&
1588                      (rf > BOARD_HEIGHT-4 || rt > BOARD_HEIGHT-4) ) {
1589                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1590                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1591                              cl.kind = promoChar == '=' ? IllegalMove : WhitePromotionKnight;
1592                     else cl.kind =  WhitePromotionQueen; /* promotion optional */
1593
1594                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1595                                             NormalMove : IllegalMove;
1596             } else {
1597                 if( (int) cl.piece < (int) BlackWazir && (rf < 3 || rt < 3) ) {
1598                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1599                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1600                              cl.kind = promoChar == '=' ? IllegalMove : BlackPromotionKnight;
1601                     else cl.kind =  BlackPromotionQueen; /* promotion optional */
1602                 } else cl.kind = (promoChar == NULLCHAR || promoChar == 'x' || promoChar == '=') ?
1603                                             NormalMove : IllegalMove;
1604             }
1605             if(cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
1606                 /* for optional promotions append '+' or '=' */
1607                 if(promoChar == '=') {
1608                     *outp++ = '=';
1609                     cl.kind = NormalMove;
1610                 } else *outp++ = '+';
1611                 *outp = NULLCHAR;
1612             } else if(cl.kind == IllegalMove) {
1613                 /* Illegal move specifies any given promotion */
1614                 if(promoChar != NULLCHAR && promoChar != 'x') {
1615                     *outp++ = '=';
1616                     *outp++ = ToUpper(promoChar);
1617                     *outp = NULLCHAR;
1618                 }
1619             }
1620         }
1621         return cl.kind;
1622
1623       /* [HGM] Always long notation for fairies we don't know */
1624       case WhiteFalcon:
1625       case BlackFalcon:
1626       case WhiteLance:
1627       case BlackLance:
1628       case WhiteGrasshopper:
1629       case BlackGrasshopper:
1630       case EmptySquare:
1631         /* Moving a nonexistent piece */
1632         break;
1633     }
1634
1635     /* Not a legal move, even ignoring check.
1636        If there was a piece on the from square,
1637        use style "Ng1g3" or "Ng1xe8";
1638        if there was a pawn or nothing (!),
1639        use style "g1g3" or "g1xe8".  Use "x"
1640        if a piece was on the to square, even
1641        a piece of the same color.
1642     */
1643     outp = out;
1644     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1645         *outp++ = ToUpper(PieceToChar(piece));
1646     }
1647     *outp++ = ff + AAA;
1648     if(rf+ONE <= '9')
1649        *outp++ = rf + ONE;
1650     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1651     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1652     *outp++ = ft + AAA;
1653     if(rt+ONE <= '9')
1654        *outp++ = rt + ONE;
1655     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1656     /* Use promotion suffix style "=Q" */
1657     if (promoChar != NULLCHAR && promoChar != 'x') {
1658         *outp++ = '=';
1659         *outp++ = ToUpper(promoChar);
1660     }
1661     *outp = NULLCHAR;
1662
1663     return IllegalMove;
1664 }
1665
1666 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1667
1668 typedef struct {
1669     /* Input */
1670     int rf, ff, rt, ft;
1671     /* Output */
1672     int recaptures;
1673 } ChaseClosure;
1674
1675 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1676
1677 int preyStackPointer, chaseStackPointer;
1678
1679 struct {
1680 char rf, ff, rt, ft;
1681 } chaseStack[100];
1682
1683 struct {
1684 char rank, file;
1685 } preyStack[100];
1686
1687
1688
1689
1690 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1691
1692 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1693                                 int rf, int ff, int rt, int ft,
1694                                 VOIDSTAR closure));
1695
1696 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1697      Board board;
1698      int flags;
1699      ChessMove kind;
1700      int rf, ff, rt, ft;
1701      VOIDSTAR closure;
1702 {   // For adding captures that can lead to chase indictment to the chaseStack
1703     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1704     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1705     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1706     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1707     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1708     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1709     chaseStack[chaseStackPointer].rf = rf;
1710     chaseStack[chaseStackPointer].ff = ff;
1711     chaseStack[chaseStackPointer].rt = rt;
1712     chaseStack[chaseStackPointer].ft = ft;
1713     chaseStackPointer++;
1714 }
1715
1716 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1717                                 int rf, int ff, int rt, int ft,
1718                                 VOIDSTAR closure));
1719
1720 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1721      Board board;
1722      int flags;
1723      ChessMove kind;
1724      int rf, ff, rt, ft;
1725      VOIDSTAR closure;
1726 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1727     int i;
1728     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1729
1730     if(board[rt][ft] == EmptySquare) return; // no capture
1731     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1732         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1733     }
1734     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1735     for(i=0; i<chaseStackPointer; i++) {
1736         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1737            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1738             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1739             chaseStack[i] = chaseStack[--chaseStackPointer];
1740             break;
1741         }
1742     }
1743 }
1744
1745 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1746                                 int rf, int ff, int rt, int ft,
1747                                 VOIDSTAR closure));
1748
1749 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1750      Board board;
1751      int flags;
1752      ChessMove kind;
1753      int rf, ff, rt, ft;
1754      VOIDSTAR closure;
1755 {   // for determining if a piece (given through the closure) is protected
1756     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1757
1758     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1759     if(appData.debugMode && board[rt][ft] != EmptySquare)
1760         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1761 }
1762
1763 extern char moveList[MAX_MOVES][MOVE_LEN];
1764
1765 int PerpetualChase(int first, int last)
1766 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1767     int i, j, k, tail;
1768     ChaseClosure cl;
1769     ChessSquare captured;
1770
1771     preyStackPointer = 0;        // clear stack of chased pieces
1772     for(i=first; i<last; i+=2) { // for all positions with same side to move
1773         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1774         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1775         // determine all captures possible after the move, and put them on chaseStack
1776         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl);
1777         if(appData.debugMode) { int n;
1778             for(n=0; n<chaseStackPointer; n++)
1779                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1780                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1781             fprintf(debugFP, ": all capts\n");
1782         }
1783         // determine all captures possible before the move, and delete them from chaseStack
1784         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1785         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1786         cl.rt = moveList[i][3]-ONE;
1787         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1788         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl);
1789         if(appData.debugMode) { int n;
1790             for(n=0; n<chaseStackPointer; n++)
1791                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1792                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1793             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1794         }
1795         // chaseSack now contains all captures made possible by the move
1796         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1797             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1798             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1799
1800             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1801             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1802
1803             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1804                 continue; // C or H attack on R is always chase; leave on chaseStack
1805
1806             if(attacker == victim) {
1807                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1808                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1809                         // we can capture back with equal piece, so this is no chase but a sacrifice
1810                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1811                         j--; /* ! */ continue;
1812                 }
1813
1814             }
1815
1816             // the attack is on a lower piece, or on a pinned or blocked equal one
1817             // test if the victim is protected by a true protector. First make the capture.
1818             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1819             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1820             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1821             // Then test if the opponent can recapture
1822             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1823             cl.rt = chaseStack[j].rt;
1824             cl.ft = chaseStack[j].ft;
1825             if(appData.debugMode) {
1826                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1827             }
1828             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl); // try all moves
1829             // unmake the capture
1830             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1831             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1832             // if a recapture was found, piece is protected, and we are not chasing it.
1833             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1834                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1835                 j--; /* ! */
1836             }
1837         }
1838         // chaseStack now contains all moves that chased
1839         if(appData.debugMode) { int n;
1840             for(n=0; n<chaseStackPointer; n++)
1841                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1842                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1843             fprintf(debugFP, ": chases\n");
1844         }
1845         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1846             for(j=0; j<chaseStackPointer; j++) {
1847                 preyStack[j].rank = chaseStack[j].rt;
1848                 preyStack[j].file = chaseStack[j].ft;
1849             }
1850             preyStackPointer = chaseStackPointer;
1851         }
1852         tail = 0;
1853         for(j=0; j<chaseStackPointer; j++) {
1854             for(k=0; k<preyStackPointer; k++) {
1855                 // search the victim of each chase move on the preyStack (first occurrence)
1856                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1857                     if(k < tail) break; // piece was already identified as still being chased
1858                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1859                     preyStack[tail] = preyStack[k];                // by swapping
1860                     preyStack[k] = preyStack[preyStackPointer];
1861                     tail++;
1862                     break;
1863                 }
1864             }
1865         }
1866         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1867         if(appData.debugMode) { int n;
1868             for(n=0; n<preyStackPointer; n++)
1869                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1870             fprintf(debugFP, "always chased upto ply %d\n", i);
1871         }
1872         // now adjust the location of the chased pieces according to opponent move
1873         for(j=0; j<preyStackPointer; j++) {
1874             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1875                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1876                 preyStack[j].rank = moveList[i+1][3]-ONE;
1877                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1878                 break;
1879             }
1880         }
1881     }
1882     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1883 }