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