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, 2011, 2012, 2013 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 int quickFlag;
  74
  75 int
  76 WhitePiece (ChessSquare piece)
  77 {
  78     return (int) piece >= (int) WhitePawn && (int) piece < (int) BlackPawn;
  79 }
  80
  81 int
  82 BlackPiece (ChessSquare piece)
  83 {
  84     return (int) piece >= (int) BlackPawn && (int) piece < (int) EmptySquare;
  85 }
  86
  87 #if 0
  88 int
  89 SameColor (ChessSquare piece1, ChessSquare piece2)
  90 {
  91     return ((int) piece1 >= (int) WhitePawn &&   /* [HGM] can be > King ! */
  92             (int) piece1 <  (int) BlackPawn &&
  93             (int) piece2 >= (int) WhitePawn &&
  94             (int) piece2 <  (int) BlackPawn)
  95       ||   ((int) piece1 >= (int) BlackPawn &&
  96             (int) piece1 <  (int) EmptySquare &&
  97             (int) piece2 >= (int) BlackPawn &&
  98             (int) piece2 <  (int) EmptySquare);
  99 }
 100 #else
 101 #define SameColor(piece1, piece2) (piece1 < EmptySquare && piece2 < EmptySquare && (piece1 < BlackPawn) == (piece2 < BlackPawn) || piece1 == DarkSquare || piece2 == DarkSquare)
 102 #endif
 103
 104 char pieceToChar[] = {
 105                         'P', 'N', 'B', 'R', 'Q', 'F', 'E', 'A', 'C', 'W', 'M',
 106                         'O', 'H', 'I', 'J', 'G', 'D', 'V', 'L', 'S', 'U', 'K',
 107                         'p', 'n', 'b', 'r', 'q', 'f', 'e', 'a', 'c', 'w', 'm',
 108                         'o', 'h', 'i', 'j', 'g', 'd', 'v', 'l', 's', 'u', 'k',
 109                         'x' };
 110 char pieceNickName[EmptySquare];
 111
 112 char
 113 PieceToChar (ChessSquare p)
 114 {
 115     if((int)p < 0 || (int)p >= (int)EmptySquare) return('x'); /* [HGM] for safety */
 116     return pieceToChar[(int) p];
 117 }
 118
 119 int
 120 PieceToNumber (ChessSquare p)  /* [HGM] holdings: count piece type, ignoring non-participating piece types */
 121 {
 122     int i=0;
 123     ChessSquare start = (int)p >= (int)BlackPawn ? BlackPawn : WhitePawn;
 124
 125     while(start++ != p) if(pieceToChar[(int)start-1] != '.') i++;
 126     return i;
 127 }
 128
 129 ChessSquare
 130 CharToPiece (int c)
 131 {
 132      int i;
 133      if(c == '.') return EmptySquare;
 134      for(i=0; i< (int) EmptySquare; i++)
 135           if(pieceNickName[i] == c) return (ChessSquare) i;
 136      for(i=0; i< (int) EmptySquare; i++)
 137           if(pieceToChar[i] == c) return (ChessSquare) i;
 138      return EmptySquare;
 139 }
 140
 141 void
 142 CopyBoard (Board to, Board from)
 143 {
 144     int i, j;
 145
 146     for (i = 0; i < BOARD_HEIGHT; i++)
 147       for (j = 0; j < BOARD_WIDTH; j++)
 148         to[i][j] = from[i][j];
 149     for (j = 0; j < BOARD_FILES; j++) // [HGM] gamestate: copy castling rights and ep status
 150         to[VIRGIN][j] = from[VIRGIN][j],
 151         to[CASTLING][j] = from[CASTLING][j];
 152     to[HOLDINGS_SET] = 0; // flag used in ICS play
 153 }
 154
 155 int
 156 CompareBoards (Board board1, Board board2)
 157 {
 158     int i, j;
 159
 160     for (i = 0; i < BOARD_HEIGHT; i++)
 161       for (j = 0; j < BOARD_WIDTH; j++) {
 162           if (board1[i][j] != board2[i][j])
 163             return FALSE;
 164     }
 165     return TRUE;
 166 }
 167
 168 // [HGM] move generation now based on hierarchy of subroutines for rays and combinations of rays
 169
 170 void
 171 SlideForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 172 {
 173   int i, rt, ft = ff;
 174   for (i = 1;; i++) {
 175       rt = rf + i;
 176       if (rt >= BOARD_HEIGHT) break;
 177       if (SameColor(board[rf][ff], board[rt][ft])) break;
 178       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 179       if (board[rt][ft] != EmptySquare) break;
 180   }
 181 }
 182
 183 void
 184 SlideBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 185 {
 186   int i, rt, ft = ff;
 187   for (i = 1;; i++) {
 188       rt = rf - i;
 189       if (rt < 0) break;
 190       if (SameColor(board[rf][ff], board[rt][ft])) break;
 191       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 192       if (board[rt][ft] != EmptySquare) break;
 193   }
 194 }
 195
 196 void
 197 SlideVertical (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 198 {
 199   SlideForward(board, flags, rf, ff, callback, closure);
 200   SlideBackward(board, flags, rf, ff, callback, closure);
 201 }
 202
 203 void
 204 SlideSideways (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 205 {
 206   int i, s, rt = rf, ft;
 207   for(s = -1; s <= 1; s+= 2) {
 208     for (i = 1;; i++) {
 209       ft = ff + i*s;
 210       if (ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 211       if (SameColor(board[rf][ff], board[rt][ft])) break;
 212       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 213       if (board[rt][ft] != EmptySquare) break;
 214     }
 215   }
 216 }
 217
 218 void
 219 SlideDiagForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 220 {
 221   int i, s, rt, ft;
 222   for(s = -1; s <= 1; s+= 2) {
 223     for (i = 1;; i++) {
 224       rt = rf + i;
 225       ft = ff + i * s;
 226       if (rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 227       if (SameColor(board[rf][ff], board[rt][ft])) break;
 228       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 229       if (board[rt][ft] != EmptySquare) break;
 230     }
 231   }
 232 }
 233
 234 void
 235 SlideDiagBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 236 {
 237   int i, s, rt, ft;
 238   for(s = -1; s <= 1; s+= 2) {
 239     for (i = 1;; i++) {
 240       rt = rf - i;
 241       ft = ff + i * s;
 242       if (rt < 0 || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 243       if (SameColor(board[rf][ff], board[rt][ft])) break;
 244       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 245       if (board[rt][ft] != EmptySquare) break;
 246     }
 247   }
 248 }
 249
 250 void
 251 Rook (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 252 {
 253   SlideVertical(board, flags, rf, ff, callback, closure);
 254   SlideSideways(board, flags, rf, ff, callback, closure);
 255 }
 256
 257 void
 258 Bishop (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 259 {
 260   SlideDiagForward(board, flags, rf, ff, callback, closure);
 261   SlideDiagBackward(board, flags, rf, ff, callback, closure);
 262 }
 263
 264 void
 265 Sting (Board board, int flags, int rf, int ff, int dy, int dx, MoveCallback callback, VOIDSTAR closure)
 266 { // Lion-like move of Horned Falcon and Souring Eagle
 267   int ft = ff + dx, rt = rf + dy;
 268   if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) return;
 269   if (!SameColor(board[rf][ff], board[rt][ft]))
 270     callback(board, flags, board[rt][ft] != EmptySquare ? FirstLeg : NormalMove, rf, ff, rt, ft, closure);
 271   ft += dx; rt += dy;
 272   if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) return;
 273   if (!SameColor(board[rf][ff], board[rt][ft]))
 274     callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 275 }
 276
 277 void
 278 StepForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 279 {
 280   int ft = ff, rt = rf + 1;
 281   if (rt >= BOARD_HEIGHT) return;
 282   if (SameColor(board[rf][ff], board[rt][ft])) return;
 283   callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 284 }
 285
 286 void
 287 StepBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 288 {
 289   int ft = ff, rt = rf - 1;
 290   if (rt < 0) return;
 291   if (SameColor(board[rf][ff], board[rt][ft])) return;
 292   callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 293 }
 294
 295 void
 296 StepSideways (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 297 {
 298   int ft, rt = rf;
 299   ft = ff + 1;
 300   if (!(rt >= BOARD_HEIGHT || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 301       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 302   ft = ff - 1;
 303   if (!(rt >= BOARD_HEIGHT || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 304       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 305 }
 306
 307 void
 308 StepDiagForward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 309 {
 310   int ft, rt = rf + 1;
 311   if (rt >= BOARD_HEIGHT) return;
 312   ft = ff + 1;
 313   if (!(rt >= BOARD_HEIGHT || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 314       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 315   ft = ff - 1;
 316   if (!(rt >= BOARD_HEIGHT || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 317       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 318 }
 319
 320 void
 321 StepDiagBackward (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 322 {
 323   int ft, rt = rf - 1;
 324   if(rt < 0) return;
 325   ft = ff + 1;
 326   if (!(rt < 0 || ft >= BOARD_RGHT) && !SameColor(board[rf][ff], board[rt][ft]))
 327       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 328   ft = ff - 1;
 329   if (!(rt < 0 || ft < BOARD_LEFT) && !SameColor(board[rf][ff], board[rt][ft]))
 330       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 331 }
 332
 333 void
 334 StepVertical (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 335 {
 336   StepForward(board, flags, rf, ff, callback, closure);
 337   StepBackward(board, flags, rf, ff, callback, closure);
 338 }
 339
 340 void
 341 Ferz (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 342 {
 343   StepDiagForward(board, flags, rf, ff, callback, closure);
 344   StepDiagBackward(board, flags, rf, ff, callback, closure);
 345 }
 346
 347 void
 348 Wazir (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 349 {
 350   StepVertical(board, flags, rf, ff, callback, closure);
 351   StepSideways(board, flags, rf, ff, callback, closure);
 352 }
 353
 354 void
 355 Knight (Board board, int flags, int rf, int ff, MoveCallback callback, VOIDSTAR closure)
 356 {
 357     int i, j, s, rt, ft;
 358     for (i = -1; i <= 1; i += 2)
 359         for (j = -1; j <= 1; j += 2)
 360             for (s = 1; s <= 2; s++) {
 361                 rt = rf + i*s;
 362                 ft = ff + j*(3-s);
 363                 if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 364                     && ( gameInfo.variant != VariantXiangqi || board[rf+i*(s-1)][ff+j*(2-s)] == EmptySquare)
 365                     && !SameColor(board[rf][ff], board[rt][ft]))
 366                     callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 367             }
 368 }
 369
 370 /* Call callback once for each pseudo-legal move in the given
 371    position, except castling moves. A move is pseudo-legal if it is
 372    legal, or if it would be legal except that it leaves the king in
 373    check.  In the arguments, epfile is EP_NONE if the previous move
 374    was not a double pawn push, or the file 0..7 if it was, or
 375    EP_UNKNOWN if we don't know and want to allow all e.p. captures.
 376    Promotion moves generated are to Queen only.
 377 */
 378 void
 379 GenPseudoLegal (Board board, int flags, MoveCallback callback, VOIDSTAR closure, ChessSquare filter)
 380 // speed: only do moves with this piece type
 381 {
 382     int rf, ff;
 383     int i, j, d, s, fs, rs, rt, ft, m;
 384     int epfile = (signed char)board[EP_STATUS]; // [HGM] gamestate: extract ep status from board
 385     int promoRank = gameInfo.variant == VariantMakruk || gameInfo.variant == VariantGrand ? 3 : 1;
 386
 387     for (rf = 0; rf < BOARD_HEIGHT; rf++)
 388       for (ff = BOARD_LEFT; ff < BOARD_RGHT; ff++) {
 389           ChessSquare piece;
 390           int rookRange;
 391
 392           if(board[rf][ff] == EmptySquare) continue;
 393           if ((flags & F_WHITE_ON_MOVE) != (board[rf][ff] < BlackPawn)) continue; // [HGM] speed: wrong color
 394           rookRange = 1000;
 395           m = 0; piece = board[rf][ff];
 396           if(PieceToChar(piece) == '~')
 397                  piece = (ChessSquare) ( DEMOTED piece );
 398           if(filter != EmptySquare && piece != filter) continue;
 399           if(IS_SHOGI(gameInfo.variant))
 400                  piece = (ChessSquare) ( SHOGI piece );
 401
 402           switch ((int)piece) {
 403             /* case EmptySquare: [HGM] this is nonsense, and conflicts with Shogi cases */
 404             default:
 405               /* can't happen ([HGM] except for faries...) */
 406               break;
 407
 408              case WhitePawn:
 409               if(gameInfo.variant == VariantXiangqi) {
 410                   /* [HGM] capture and move straight ahead in Xiangqi */
 411                   if (rf < BOARD_HEIGHT-1 &&
 412                            !SameColor(board[rf][ff], board[rf + 1][ff]) ) {
 413                            callback(board, flags, NormalMove,
 414                                     rf, ff, rf + 1, ff, closure);
 415                   }
 416                   /* and move sideways when across the river */
 417                   for (s = -1; s <= 1; s += 2) {
 418                       if (rf >= BOARD_HEIGHT>>1 &&
 419                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 420                           !WhitePiece(board[rf][ff+s]) ) {
 421                            callback(board, flags, NormalMove,
 422                                     rf, ff, rf, ff+s, closure);
 423                       }
 424                   }
 425                   break;
 426               }
 427               if (rf < BOARD_HEIGHT-1 && board[rf + 1][ff] == EmptySquare) {
 428                   callback(board, flags,
 429                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 430                            rf, ff, rf + 1, ff, closure);
 431               }
 432               if (rf <= (BOARD_HEIGHT>>1)-3 && board[rf+1][ff] == EmptySquare && // [HGM] grand: also on 3rd rank on 10-board
 433                   gameInfo.variant != VariantShatranj && /* [HGM] */
 434                   gameInfo.variant != VariantCourier  && /* [HGM] */
 435                   board[rf+2][ff] == EmptySquare ) {
 436                       callback(board, flags, NormalMove,
 437                                rf, ff, rf+2, ff, closure);
 438               }
 439               for (s = -1; s <= 1; s += 2) {
 440                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 441                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 442                        BlackPiece(board[rf + 1][ff + s]))) {
 443                       callback(board, flags,
 444                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 445                                rf, ff, rf + 1, ff + s, closure);
 446                   }
 447                   if (rf >= BOARD_HEIGHT+1>>1) {// [HGM] grand: 4th & 5th rank on 10-board
 448                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 449                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf < BOARD_HEIGHT-3 &&
 450                           board[rf][ff + s] == BlackPawn &&
 451                           board[rf+1][ff + s] == EmptySquare) {
 452                           callback(board, flags, WhiteCapturesEnPassant,
 453                                    rf, ff, rf+1, ff + s, closure);
 454                       }
 455                   }
 456               }
 457               break;
 458
 459             case BlackPawn:
 460               if(gameInfo.variant == VariantXiangqi) {
 461                   /* [HGM] capture straight ahead in Xiangqi */
 462                   if (rf > 0 && !SameColor(board[rf][ff], board[rf - 1][ff]) ) {
 463                            callback(board, flags, NormalMove,
 464                                     rf, ff, rf - 1, ff, closure);
 465                   }
 466                   /* and move sideways when across the river */
 467                   for (s = -1; s <= 1; s += 2) {
 468                       if (rf < BOARD_HEIGHT>>1 &&
 469                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 470                           !BlackPiece(board[rf][ff+s]) ) {
 471                            callback(board, flags, NormalMove,
 472                                     rf, ff, rf, ff+s, closure);
 473                       }
 474                   }
 475                   break;
 476               }
 477               if (rf > 0 && board[rf - 1][ff] == EmptySquare) {
 478                   callback(board, flags,
 479                            rf <= promoRank ? BlackPromotion : NormalMove,
 480                            rf, ff, rf - 1, ff, closure);
 481               }
 482               if (rf >= (BOARD_HEIGHT+1>>1)+2 && board[rf-1][ff] == EmptySquare && // [HGM] grand
 483                   gameInfo.variant != VariantShatranj && /* [HGM] */
 484                   gameInfo.variant != VariantCourier  && /* [HGM] */
 485                   board[rf-2][ff] == EmptySquare) {
 486                   callback(board, flags, NormalMove,
 487                            rf, ff, rf-2, ff, closure);
 488               }
 489               for (s = -1; s <= 1; s += 2) {
 490                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 491                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 492                        WhitePiece(board[rf - 1][ff + s]))) {
 493                       callback(board, flags,
 494                                rf <= promoRank ? BlackPromotion : NormalMove,
 495                                rf, ff, rf - 1, ff + s, closure);
 496                   }
 497                   if (rf < BOARD_HEIGHT>>1) {
 498                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 499                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf > 2 &&
 500                           board[rf][ff + s] == WhitePawn &&
 501                           board[rf-1][ff + s] == EmptySquare) {
 502                           callback(board, flags, BlackCapturesEnPassant,
 503                                    rf, ff, rf-1, ff + s, closure);
 504                       }
 505                   }
 506               }
 507               break;
 508
 509             case WhiteUnicorn:
 510             case BlackUnicorn:
 511             case WhiteKnight:
 512             case BlackKnight:
 513               for (i = -1; i <= 1; i += 2)
 514                 for (j = -1; j <= 1; j += 2)
 515                   for (s = 1; s <= 2; s++) {
 516                       rt = rf + i*s;
 517                       ft = ff + j*(3-s);
 518                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 519                           && ( gameInfo.variant != VariantXiangqi || board[rf+i*(s-1)][ff+j*(2-s)] == EmptySquare)
 520                           && !SameColor(board[rf][ff], board[rt][ft]))
 521                       callback(board, flags, NormalMove,
 522                                rf, ff, rt, ft, closure);
 523                   }
 524               break;
 525
 526             case SHOGI WhiteKnight:
 527               for (s = -1; s <= 1; s += 2) {
 528                   if (rf < BOARD_HEIGHT-2 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 529                       !SameColor(board[rf][ff], board[rf + 2][ff + s])) {
 530                       callback(board, flags, NormalMove,
 531                                rf, ff, rf + 2, ff + s, closure);
 532                   }
 533               }
 534               break;
 535
 536             case SHOGI BlackKnight:
 537               for (s = -1; s <= 1; s += 2) {
 538                   if (rf > 1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
 539                       !SameColor(board[rf][ff], board[rf - 2][ff + s])) {
 540                       callback(board, flags, NormalMove,
 541                                rf, ff, rf - 2, ff + s, closure);
 542                   }
 543               }
 544               break;
 545
 546             case WhiteCannon:
 547             case BlackCannon:
 548               for (d = 0; d <= 1; d++)
 549                 for (s = -1; s <= 1; s += 2) {
 550                   m = 0;
 551                   for (i = 1;; i++) {
 552                       rt = rf + (i * s) * d;
 553                       ft = ff + (i * s) * (1 - d);
 554                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 555                       if (m == 0 && board[rt][ft] == EmptySquare)
 556                                  callback(board, flags, NormalMove,
 557                                           rf, ff, rt, ft, closure);
 558                       if (m == 1 && board[rt][ft] != EmptySquare &&
 559                           !SameColor(board[rf][ff], board[rt][ft]) )
 560                                  callback(board, flags, NormalMove,
 561                                           rf, ff, rt, ft, closure);
 562                       if (board[rt][ft] != EmptySquare && m++) break;
 563                   }
 564                 }
 565               break;
 566
 567             /* Gold General (and all its promoted versions) . First do the */
 568             /* diagonal forward steps, then proceed as normal Wazir        */
 569             case SHOGI (PROMOTED WhitePawn):
 570                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 571             case SHOGI (PROMOTED BlackPawn):
 572                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 573                 SlideVertical(board, flags, rf, ff, callback, closure);
 574                 break;
 575
 576             case SHOGI (PROMOTED WhiteKnight):
 577                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 578             case SHOGI BlackDrunk:
 579             case SHOGI BlackAlfil:
 580                 Ferz(board, flags, rf, ff, callback, closure);
 581                 StepSideways(board, flags, rf, ff, callback, closure);
 582                 StepBackward(board, flags, rf, ff, callback, closure);
 583                 break;
 584
 585             case SHOGI (PROMOTED BlackKnight):
 586                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 587             case SHOGI WhiteDrunk:
 588             case SHOGI WhiteAlfil:
 589                 Ferz(board, flags, rf, ff, callback, closure);
 590                 StepSideways(board, flags, rf, ff, callback, closure);
 591                 StepForward(board, flags, rf, ff, callback, closure);
 592                 break;
 593
 594
 595             case SHOGI WhiteStag:
 596             case SHOGI BlackStag:
 597                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 598                 SlideVertical(board, flags, rf, ff, callback, closure);
 599                 Ferz(board, flags, rf, ff, callback, closure);
 600                 StepSideways(board, flags, rf, ff, callback, closure);
 601                 break;
 602
 603             case SHOGI (PROMOTED WhiteQueen):
 604             case SHOGI WhiteTokin:
 605             case SHOGI WhiteWazir:
 606             WhiteGold:
 607                 StepDiagForward(board, flags, rf, ff, callback, closure);
 608                 Wazir(board, flags, rf, ff, callback, closure);
 609                 break;
 610
 611             case SHOGI (PROMOTED BlackQueen):
 612             case SHOGI BlackTokin:
 613             case SHOGI BlackWazir:
 614             BlackGold:
 615                 StepDiagBackward(board, flags, rf, ff, callback, closure);
 616                 Wazir(board, flags, rf, ff, callback, closure);
 617                 break;
 618
 619             case WhiteWazir:
 620             case BlackWazir:
 621                 Wazir(board, flags, rf, ff, callback, closure);
 622                 break;
 623
 624             case SHOGI WhiteMarshall:
 625             case SHOGI BlackMarshall:
 626                 Ferz(board, flags, rf, ff, callback, closure);
 627                 for (d = 0; d <= 1; d++)
 628                     for (s = -2; s <= 2; s += 4) {
 629                         rt = rf + s * d;
 630                         ft = ff + s * (1 - d);
 631                         if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 632                         if (!SameColor(board[rf][ff], board[rt][ft]) )
 633                             callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 634                     }
 635                 break;
 636
 637             case SHOGI WhiteAngel:
 638             case SHOGI BlackAngel:
 639                 Wazir(board, flags, rf, ff, callback, closure);
 640
 641             case WhiteAlfil:
 642             case BlackAlfil:
 643                 /* [HGM] support Shatranj pieces */
 644                 for (rs = -1; rs <= 1; rs += 2)
 645                   for (fs = -1; fs <= 1; fs += 2) {
 646                       rt = rf + 2 * rs;
 647                       ft = ff + 2 * fs;
 648                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 649                           && ( gameInfo.variant != VariantXiangqi ||
 650                                board[rf+rs][ff+fs] == EmptySquare && (2*rf < BOARD_HEIGHT) == (2*rt < BOARD_HEIGHT) )
 651
 652                           && !SameColor(board[rf][ff], board[rt][ft]))
 653                                callback(board, flags, NormalMove,
 654                                         rf, ff, rt, ft, closure);
 655                       if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
 656                          gameInfo.variant == VariantChu      || gameInfo.variant == VariantXiangqi) continue; // classical Alfil
 657                       rt = rf + rs; // in unknown variant we assume Modern Elephant, which can also do one step
 658                       ft = ff + fs;
 659                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
 660                           && !SameColor(board[rf][ff], board[rt][ft]))
 661                                callback(board, flags, NormalMove,
 662                                         rf, ff, rt, ft, closure);
 663                   }
 664                 if(gameInfo.variant == VariantSpartan)
 665                    for(fs = -1; fs <= 1; fs += 2) {
 666                       ft = ff + fs;
 667                       if (!(ft < BOARD_LEFT || ft >= BOARD_RGHT) && board[rf][ft] == EmptySquare)
 668                                callback(board, flags, NormalMove, rf, ff, rf, ft, closure);
 669                    }
 670                 break;
 671
 672             /* Make Dragon-Horse also do Dababba moves outside Shogi, for better disambiguation in variant Fairy */
 673             case WhiteCardinal:
 674             case BlackCardinal:
 675               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
 676                 for (s = -2; s <= 2; s += 4) {
 677                       rt = rf + s * d;
 678                       ft = ff + s * (1 - d);
 679                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 680                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
 681                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 682                   }
 683
 684             /* Shogi Dragon Horse has to continue with Wazir after Bishop */
 685             case SHOGI WhiteCardinal:
 686             case SHOGI BlackCardinal:
 687             case SHOGI WhitePCardinal:
 688             case SHOGI BlackPCardinal:
 689                 Bishop(board, flags, rf, ff, callback, closure);
 690                 Wazir(board, flags, rf, ff, callback, closure);
 691                 break;
 692
 693             /* Capablanca Archbishop continues as Knight                  */
 694             case WhiteAngel:
 695             case BlackAngel:
 696                 Knight(board, flags, rf, ff, callback, closure);
 697
 698             /* Shogi Bishops are ordinary Bishops */
 699             case SHOGI WhiteBishop:
 700             case SHOGI BlackBishop:
 701             case SHOGI WhitePBishop:
 702             case SHOGI BlackPBishop:
 703             case WhiteBishop:
 704             case BlackBishop:
 705                 Bishop(board, flags, rf, ff, callback, closure);
 706                 break;
 707
 708             /* Shogi Lance is unlike anything, and asymmetric at that */
 709             case SHOGI WhiteQueen:
 710               if(gameInfo.variant == VariantChu) goto doQueen;
 711               for(i = 1;; i++) {
 712                       rt = rf + i;
 713                       ft = ff;
 714                       if (rt >= BOARD_HEIGHT) break;
 715                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 716                       callback(board, flags, NormalMove,
 717                                rf, ff, rt, ft, closure);
 718                       if (board[rt][ft] != EmptySquare) break;
 719               }
 720               break;
 721
 722             case SHOGI BlackQueen:
 723               if(gameInfo.variant == VariantChu) goto doQueen;
 724               for(i = 1;; i++) {
 725                       rt = rf - i;
 726                       ft = ff;
 727                       if (rt < 0) break;
 728                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 729                       callback(board, flags, NormalMove,
 730                                rf, ff, rt, ft, closure);
 731                       if (board[rt][ft] != EmptySquare) break;
 732               }
 733               break;
 734
 735             /* Make Dragon-King Dababba & Rook-like outside Shogi, for better disambiguation in variant Fairy */
 736             case WhiteDragon:
 737             case BlackDragon:
 738               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
 739                 for (s = -2; s <= 2; s += 4) {
 740                       rt = rf + s * d;
 741                       ft = ff + s * (1 - d);
 742                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT || board[rf+rt>>1][ff+ft>>1] == EmptySquare) continue;
 743                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
 744                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 745                   }
 746               if(gameInfo.variant == VariantSpartan) rookRange = 2; // in Spartan Chess restrict range to modern Dababba
 747               goto doRook;
 748
 749             /* Shogi Dragon King has to continue as Ferz after Rook moves */
 750             case SHOGI WhiteDragon:
 751             case SHOGI BlackDragon:
 752             case SHOGI WhitePDragon:
 753             case SHOGI BlackPDragon:
 754                 Rook(board, flags, rf, ff, callback, closure);
 755                 Ferz(board, flags, rf, ff, callback, closure);
 756                 break;
 757               m++;
 758
 759             /* Capablanca Chancellor sets flag to continue as Knight      */
 760             case WhiteMarshall:
 761             case BlackMarshall:
 762                 Rook(board, flags, rf, ff, callback, closure);
 763                 if(gameInfo.variant == VariantSpartan) // in Spartan Chess Chancellor is used for Dragon King.
 764                     Ferz(board, flags, rf, ff, callback, closure);
 765                 else
 766                     Knight(board, flags, rf, ff, callback, closure);
 767                 break;
 768
 769             /* Shogi Rooks are ordinary Rooks */
 770             case SHOGI WhiteRook:
 771             case SHOGI BlackRook:
 772             case SHOGI WhitePRook:
 773             case SHOGI BlackPRook:
 774             case WhiteRook:
 775             case BlackRook:
 776           doRook:
 777                 Rook(board, flags, rf, ff, callback, closure);
 778                 break;
 779
 780             case WhiteQueen:
 781             case BlackQueen:
 782             case SHOGI WhiteMother:
 783             case SHOGI BlackMother:
 784             doQueen:
 785                 Rook(board, flags, rf, ff, callback, closure);
 786                 Bishop(board, flags, rf, ff, callback, closure);
 787                 break;
 788
 789            case SHOGI WhitePawn:
 790                 StepForward(board, flags, rf, ff, callback, closure);
 791                 break;
 792
 793             case SHOGI BlackPawn:
 794                 StepBackward(board, flags, rf, ff, callback, closure);
 795                 break;
 796
 797             case WhiteMan:
 798                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
 799             case SHOGI WhiteFerz:
 800                 Ferz(board, flags, rf, ff, callback, closure);
 801                 StepForward(board, flags, rf, ff, callback, closure);
 802                 break;
 803
 804             case BlackMan:
 805                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
 806             case SHOGI BlackFerz:
 807                 StepBackward(board, flags, rf, ff, callback, closure);
 808
 809             case WhiteFerz:
 810             case BlackFerz:
 811                 /* [HGM] support Shatranj pieces */
 812                 Ferz(board, flags, rf, ff, callback, closure);
 813                 break;
 814
 815             case WhiteSilver:
 816             case BlackSilver:
 817                 Knight(board, flags, rf, ff, callback, closure); // [HGM] superchess: use for Centaur
 818
 819             commoner:
 820             case SHOGI WhiteMonarch:
 821             case SHOGI BlackMonarch:
 822             case SHOGI WhiteKing:
 823             case SHOGI BlackKing:
 824             case WhiteKing:
 825             case BlackKing:
 826                 Ferz(board, flags, rf, ff, callback, closure);
 827                 Wazir(board, flags, rf, ff, callback, closure);
 828                 break;
 829
 830             case WhiteNightrider:
 831             case BlackNightrider:
 832               for (i = -1; i <= 1; i += 2)
 833                 for (j = -1; j <= 1; j += 2)
 834                   for (s = 1; s <= 2; s++) {  int k;
 835                     for(k=1;; k++) {
 836                       rt = rf + k*i*s;
 837                       ft = ff + k*j*(3-s);
 838                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 839                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 840                       callback(board, flags, NormalMove,
 841                                rf, ff, rt, ft, closure);
 842                       if (board[rt][ft] != EmptySquare) break;
 843                     }
 844                   }
 845               break;
 846
 847             Amazon:
 848                 Bishop(board, flags, rf, ff, callback, closure);
 849                 Rook(board, flags, rf, ff, callback, closure);
 850                 Knight(board, flags, rf, ff, callback, closure);
 851                 break;
 852
 853             // Use Lance as Berolina / Spartan Pawn.
 854             case WhiteLance:
 855               if(gameInfo.variant == VariantSuper) goto Amazon;
 856               if (rf < BOARD_HEIGHT-1 && BlackPiece(board[rf + 1][ff]))
 857                   callback(board, flags,
 858                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 859                            rf, ff, rf + 1, ff, closure);
 860               for (s = -1; s <= 1; s += 2) {
 861                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf + 1][ff + s] == EmptySquare)
 862                       callback(board, flags,
 863                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 864                                rf, ff, rf + 1, ff + s, closure);
 865                   if (rf == 1 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[3][ff + 2*s] == EmptySquare )
 866                       callback(board, flags, NormalMove, rf, ff, 3, ff + 2*s, closure);
 867               }
 868               break;
 869
 870             case BlackLance:
 871               if(gameInfo.variant == VariantSuper) goto Amazon;
 872               if (rf > 0 && WhitePiece(board[rf - 1][ff]))
 873                   callback(board, flags,
 874                            rf <= promoRank ? BlackPromotion : NormalMove,
 875                            rf, ff, rf - 1, ff, closure);
 876               for (s = -1; s <= 1; s += 2) {
 877                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf - 1][ff + s] == EmptySquare)
 878                       callback(board, flags,
 879                                rf <= promoRank ? BlackPromotion : NormalMove,
 880                                rf, ff, rf - 1, ff + s, closure);
 881                   if (rf == BOARD_HEIGHT-2 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[rf-2][ff + 2*s] == EmptySquare )
 882                       callback(board, flags, NormalMove, rf, ff, rf-2, ff + 2*s, closure);
 883               }
 884             break;
 885
 886             case SHOGI WhiteNothing:
 887             case SHOGI BlackNothing:
 888             case SHOGI WhiteLion:
 889             case SHOGI BlackLion:
 890             case WhiteLion:
 891             case BlackLion:
 892               for(rt = rf - 2; rt <= rf + 2; rt++) for(ft = ff - 2; ft <= ff + 2; ft++) {
 893                 if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 894                 if (!(ff == ft && rf == rt) && SameColor(board[rf][ff], board[rt][ft])) continue;
 895                 callback(board, flags, (rt-rf)*(rt-rf) + (ff-ft)*(ff-ft) < 3 && board[rt][ft] != EmptySquare ? FirstLeg : NormalMove,
 896                          rf, ff, rt, ft, closure);
 897               }
 898               break;
 899
 900             case SHOGI WhiteFalcon:
 901             case SHOGI BlackFalcon:
 902             case SHOGI WhitePDagger:
 903             case SHOGI BlackPDagger:
 904                 SlideSideways(board, flags, rf, ff, callback, closure);
 905                 StepVertical(board, flags, rf, ff, callback, closure);
 906                 break;
 907
 908             case SHOGI WhiteCobra:
 909             case SHOGI BlackCobra:
 910                 StepVertical(board, flags, rf, ff, callback, closure);
 911                 break;
 912
 913             case SHOGI (PROMOTED WhiteFerz):
 914                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 915             case SHOGI (PROMOTED BlackFerz):
 916                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 917             case SHOGI WhitePSword:
 918             case SHOGI BlackPSword:
 919                 SlideVertical(board, flags, rf, ff, callback, closure);
 920                 StepSideways(board, flags, rf, ff, callback, closure);
 921                 break;
 922
 923             case SHOGI WhiteUnicorn:
 924             case SHOGI BlackUnicorn:
 925                 Ferz(board, flags, rf, ff, callback, closure);
 926                 StepVertical(board, flags, rf, ff, callback, closure);
 927                 break;
 928
 929             case SHOGI WhiteMan:
 930                 StepDiagForward(board, flags, rf, ff, callback, closure);
 931                 StepVertical(board, flags, rf, ff, callback, closure);
 932                 break;
 933
 934             case SHOGI BlackMan:
 935                 StepDiagBackward(board, flags, rf, ff, callback, closure);
 936                 StepVertical(board, flags, rf, ff, callback, closure);
 937                 break;
 938
 939             case SHOGI WhiteHCrown:
 940             case SHOGI BlackHCrown:
 941                 Bishop(board, flags, rf, ff, callback, closure);
 942                 SlideSideways(board, flags, rf, ff, callback, closure);
 943                 break;
 944
 945             case SHOGI WhiteCrown:
 946             case SHOGI BlackCrown:
 947                 Bishop(board, flags, rf, ff, callback, closure);
 948                 SlideVertical(board, flags, rf, ff, callback, closure);
 949                 break;
 950
 951             case SHOGI WhiteHorned:
 952                 Sting(board, flags, rf, ff, 1, 0, callback, closure);
 953                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 954                 if(killX >= 0) break;
 955                 Bishop(board, flags, rf, ff, callback, closure);
 956                 SlideSideways(board, flags, rf, ff, callback, closure);
 957                 SlideBackward(board, flags, rf, ff, callback, closure);
 958                 break;
 959
 960             case SHOGI BlackHorned:
 961                 Sting(board, flags, rf, ff, -1, 0, callback, closure);
 962                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 963                 if(killX >= 0) break;
 964                 Bishop(board, flags, rf, ff, callback, closure);
 965                 SlideSideways(board, flags, rf, ff, callback, closure);
 966                 SlideForward(board, flags, rf, ff, callback, closure);
 967                 break;
 968
 969             case SHOGI WhiteEagle:
 970                 Sting(board, flags, rf, ff, 1,  1, callback, closure);
 971                 Sting(board, flags, rf, ff, 1, -1, callback, closure);
 972                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 973                 if(killX >= 0) break;
 974                 Rook(board, flags, rf, ff, callback, closure);
 975                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
 976                 break;
 977
 978             case SHOGI BlackEagle:
 979                 Sting(board, flags, rf, ff, -1,  1, callback, closure);
 980                 Sting(board, flags, rf, ff, -1, -1, callback, closure);
 981                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 982                 if(killX >= 0) break;
 983                 Rook(board, flags, rf, ff, callback, closure);
 984                 SlideDiagForward(board, flags, rf, ff, callback, closure);
 985                 break;
 986
 987             case SHOGI WhiteDolphin:
 988             case SHOGI BlackHorse:
 989                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
 990                 SlideVertical(board, flags, rf, ff, callback, closure);
 991                 break;
 992
 993             case SHOGI BlackDolphin:
 994             case SHOGI WhiteHorse:
 995                 SlideDiagForward(board, flags, rf, ff, callback, closure);
 996                 SlideVertical(board, flags, rf, ff, callback, closure);
 997                 break;
 998
 999             case SHOGI WhiteLance:
1000                 SlideForward(board, flags, rf, ff, callback, closure);
1001                 break;
1002
1003             case SHOGI BlackLance:
1004                 SlideBackward(board, flags, rf, ff, callback, closure);
1005                 break;
1006
1007             case WhiteFalcon: // [HGM] wild: for wildcards, self-capture symbolizes move to anywhere
1008             case BlackFalcon:
1009             case WhiteCobra:
1010             case BlackCobra:
1011               callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1012               break;
1013
1014           }
1015       }
1016 }
1017
1018
1019 typedef struct {
1020     MoveCallback cb;
1021     VOIDSTAR cl;
1022 } GenLegalClosure;
1023
1024 int rFilter, fFilter; // [HGM] speed: sorry, but I get a bit tired of this closure madness
1025 Board xqCheckers, nullBoard;
1026
1027 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
1028                                 int rf, int ff, int rt, int ft,
1029                                 VOIDSTAR closure));
1030
1031 void
1032 GenLegalCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1033 {
1034     register GenLegalClosure *cl = (GenLegalClosure *) closure;
1035
1036     if(rFilter >= 0 && rFilter != rt || fFilter >= 0 && fFilter != ft) return; // [HGM] speed: ignore moves with wrong to-square
1037
1038     if (board[EP_STATUS] == EP_IRON_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)) return; //[HGM] lion
1039
1040     if (!(flags & F_IGNORE_CHECK) ) {
1041       int check, promo = (gameInfo.variant == VariantSpartan && kind == BlackPromotion);
1042       if(promo) {
1043             int r, f, kings=0;
1044             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT;       f++)
1045                 kings += (board[r][f] == BlackKing);
1046             if(kings >= 2)
1047               promo = 0;
1048             else
1049                 board[rf][ff] = BlackKing; // [HGM] spartan: promote to King before check-test
1050         }
1051         check = CheckTest(board, flags, rf, ff, rt, ft,
1052                   kind == WhiteCapturesEnPassant ||
1053                   kind == BlackCapturesEnPassant);
1054         if(promo) board[rf][ff] = BlackLance;
1055       if(check) return;
1056     }
1057     if (flags & F_ATOMIC_CAPTURE) {
1058       if (board[rt][ft] != EmptySquare ||
1059           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
1060         int r, f;
1061         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
1062         if (board[rf][ff] == king) return;
1063         for (r = rt-1; r <= rt+1; r++) {
1064           for (f = ft-1; f <= ft+1; f++) {
1065             if (r >= 0 && r < BOARD_HEIGHT && f >= BOARD_LEFT && f < BOARD_RGHT &&
1066                 board[r][f] == king) return;
1067           }
1068         }
1069       }
1070     }
1071     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
1072 }
1073
1074
1075 typedef struct {
1076     int rf, ff, rt, ft;
1077     ChessMove kind;
1078     int captures; // [HGM] losers
1079 } LegalityTestClosure;
1080
1081
1082 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
1083    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
1084    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
1085    moves that would destroy your own king.  The CASTLE_OK flags are
1086    true if castling is not yet ruled out by a move of the king or
1087    rook.  Return TRUE if the player on move is currently in check and
1088    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
1089 int
1090 GenLegal (Board board, int  flags, MoveCallback callback, VOIDSTAR closure, ChessSquare filter)
1091 {
1092     GenLegalClosure cl;
1093     int ff, ft, k, left, right, swap;
1094     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
1095     ChessSquare wKing = WhiteKing, bKing = BlackKing, *castlingRights = board[CASTLING];
1096     int inCheck = !ignoreCheck && CheckTest(board, flags, -1, -1, -1, -1, FALSE); // kludge alert: this would mark pre-existing checkers if status==1
1097
1098     cl.cb = callback;
1099     cl.cl = closure;
1100     xqCheckers[EP_STATUS] *= 2; // quasi: if previous CheckTest has been marking, we now set flag for suspending same checkers
1101     if(filter == EmptySquare) rFilter = fFilter = -1; // [HGM] speed: do not filter on square if we do not filter on piece
1102     GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl, filter);
1103
1104     if (inCheck) return TRUE;
1105
1106     /* Generate castling moves */
1107     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
1108         wKing = WhiteUnicorn; bKing = BlackUnicorn;
1109     }
1110
1111     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
1112         if ((flags & F_WHITE_ON_MOVE) &&
1113             (flags & F_WHITE_KCASTLE_OK) &&
1114             board[0][ff] == wKing &&
1115             board[0][ff + 1] == EmptySquare &&
1116             board[0][ff + 2] == EmptySquare &&
1117             board[0][BOARD_RGHT-3] == EmptySquare &&
1118             board[0][BOARD_RGHT-2] == EmptySquare &&
1119             board[0][BOARD_RGHT-1] == WhiteRook &&
1120             castlingRights[0] != NoRights && /* [HGM] check rights */
1121             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1122             (ignoreCheck ||
1123              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
1124               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
1125               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
1126               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
1127
1128             callback(board, flags,
1129                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
1130                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1131         }
1132         if ((flags & F_WHITE_ON_MOVE) &&
1133             (flags & F_WHITE_QCASTLE_OK) &&
1134             board[0][ff] == wKing &&
1135             board[0][ff - 1] == EmptySquare &&
1136             board[0][ff - 2] == EmptySquare &&
1137             board[0][BOARD_LEFT+2] == EmptySquare &&
1138             board[0][BOARD_LEFT+1] == EmptySquare &&
1139             board[0][BOARD_LEFT+0] == WhiteRook &&
1140             castlingRights[1] != NoRights && /* [HGM] check rights */
1141             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1142             (ignoreCheck ||
1143              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
1144               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
1145               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
1146
1147             callback(board, flags,
1148                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
1149                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
1150         }
1151         if (!(flags & F_WHITE_ON_MOVE) &&
1152             (flags & F_BLACK_KCASTLE_OK) &&
1153             board[BOARD_HEIGHT-1][ff] == bKing &&
1154             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
1155             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
1156             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
1157             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
1158             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
1159             castlingRights[3] != NoRights && /* [HGM] check rights */
1160             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1161             (ignoreCheck ||
1162              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
1163               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
1164               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
1165               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
1166
1167             callback(board, flags,
1168                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
1169                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1170         }
1171         if (!(flags & F_WHITE_ON_MOVE) &&
1172             (flags & F_BLACK_QCASTLE_OK) &&
1173             board[BOARD_HEIGHT-1][ff] == bKing &&
1174             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
1175             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
1176             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
1177             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
1178             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
1179             castlingRights[4] != NoRights && /* [HGM] check rights */
1180             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1181             (ignoreCheck ||
1182              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
1183               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
1184               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
1185
1186             callback(board, flags,
1187                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
1188                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
1189         }
1190     }
1191
1192   if((swap = gameInfo.variant == VariantSChess) || flags & F_FRC_TYPE_CASTLING) {
1193
1194     /* generate all potential FRC castling moves (KxR), ignoring flags */
1195     /* [HGM] test if the Rooks we find have castling rights */
1196     /* In S-Chess we generate RxK for allowed castlings, for gating at Rook square */
1197
1198
1199     if ((flags & F_WHITE_ON_MOVE) != 0) {
1200         ff = castlingRights[2]; /* King file if we have any rights */
1201         if(ff != NoRights && board[0][ff] == WhiteKing) {
1202     if (appData.debugMode) {
1203         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
1204                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
1205     }
1206             ft = castlingRights[0]; /* Rook file if we have H-side rights */
1207             left  = ff+1;
1208             right = BOARD_RGHT-2;
1209             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1210             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1211                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1212             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1213                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1214             if(ft != NoRights && board[0][ft] == WhiteRook)
1215                 callback(board, flags, WhiteHSideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
1216
1217             ft = castlingRights[1]; /* Rook file if we have A-side rights */
1218             left  = BOARD_LEFT+2;
1219             right = ff-1;
1220             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1221             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1222                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1223             if(ff > BOARD_LEFT+2)
1224             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1225                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1226             if(ft != NoRights && board[0][ft] == WhiteRook)
1227                 callback(board, flags, WhiteASideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
1228         }
1229     } else {
1230         ff = castlingRights[5]; /* King file if we have any rights */
1231         if(ff != NoRights && board[BOARD_HEIGHT-1][ff] == BlackKing) {
1232             ft = castlingRights[3]; /* Rook file if we have H-side rights */
1233             left  = ff+1;
1234             right = BOARD_RGHT-2;
1235             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1236             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1237                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1238             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1239                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1240             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
1241                 callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
1242
1243             ft = castlingRights[4]; /* Rook file if we have A-side rights */
1244             left  = BOARD_LEFT+2;
1245             right = ff-1;
1246             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1247             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1248                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1249             if(ff > BOARD_LEFT+2)
1250             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1251                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1252             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
1253                 callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
1254         }
1255     }
1256
1257   }
1258
1259     return FALSE;
1260 }
1261
1262
1263 typedef struct {
1264     int rking, fking;
1265     int check;
1266 } CheckTestClosure;
1267
1268
1269 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
1270                                  int rf, int ff, int rt, int ft,
1271                                  VOIDSTAR closure));
1272
1273
1274 void
1275 CheckTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1276 {
1277     register CheckTestClosure *cl = (CheckTestClosure *) closure;
1278
1279     if (rt == cl->rking && ft == cl->fking) {
1280         if(xqCheckers[EP_STATUS] >= 2 && xqCheckers[rf][ff]) return; // checker is piece with suspended checking power
1281         cl->check++;
1282         xqCheckers[rf][ff] = xqCheckers[EP_STATUS] & 1; // remember who is checking (if status == 1)
1283     }
1284     if( board[EP_STATUS] == EP_ROYAL_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)
1285         && (gameInfo.variant != VariantLion || board[rf][ff] != WhiteKing && board[rf][ff] != BlackKing) )
1286         cl->check++; // [HGM] lion: forbidden counterstrike against Lion equated to putting yourself in check
1287 }
1288
1289
1290 /* If the player on move were to move from (rf, ff) to (rt, ft), would
1291    he leave himself in check?  Or if rf == -1, is the player on move
1292    in check now?  enPassant must be TRUE if the indicated move is an
1293    e.p. capture.  The possibility of castling out of a check along the
1294    back rank is not accounted for (i.e., we still return nonzero), as
1295    this is illegal anyway.  Return value is the number of times the
1296    king is in check. */
1297 int
1298 CheckTest (Board board, int flags, int rf, int ff, int rt, int ft, int enPassant)
1299 {
1300     CheckTestClosure cl;
1301     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1302     ChessSquare captured = EmptySquare, ep;
1303     /*  Suppress warnings on uninitialized variables    */
1304
1305     if(gameInfo.variant == VariantXiangqi)
1306         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
1307     if(gameInfo.variant == VariantKnightmate)
1308         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
1309
1310     if (rt >= 0) {
1311         if (enPassant) {
1312             captured = board[rf][ft];
1313             board[rf][ft] = EmptySquare;
1314         } else {
1315             captured = board[rt][ft];
1316         }
1317         if(rf == DROP_RANK) board[rt][ft] = ff; else { // [HGM] drop
1318             board[rt][ft] = board[rf][ff];
1319             board[rf][ff] = EmptySquare;
1320         }
1321         ep = board[EP_STATUS];
1322         if( captured == WhiteLion || captured == BlackLion ) { // [HGM] lion: Chu Lion-capture rules
1323             ChessSquare victim = killX < 0 ? EmptySquare : board[killY][killX];
1324             if( (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion) &&           // capturer is Lion
1325                 (ff - ft > 1 || ft - ff > 1 || rf - rt > 1 || rt - rf > 1) &&           // captures from a distance
1326                 (victim == EmptySquare || victim == WhitePawn || victim == BlackPawn) ) // no or worthless 'bridge'
1327                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1328         }
1329     }
1330
1331     /* For compatibility with ICS wild 9, we scan the board in the
1332        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1333        and we test only whether that one is in check. */
1334     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1335         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1336           if (board[cl.rking][cl.fking] == king) {
1337               cl.check = 0;
1338               if(gameInfo.variant == VariantXiangqi) {
1339                   /* [HGM] In Xiangqi opposing Kings means check as well */
1340                   int i, dir;
1341                   dir = (king >= BlackPawn) ? -1 : 1;
1342                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1343                                 board[i][cl.fking] == EmptySquare; i+=dir );
1344                   if(i>=0 && i<BOARD_HEIGHT &&
1345                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1346                           cl.check++;
1347               }
1348               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1349               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1350                  goto undo_move;  /* 2-level break */
1351           }
1352       }
1353
1354   undo_move:
1355
1356     if (rt >= 0) {
1357         if(rf != DROP_RANK) // [HGM] drop
1358             board[rf][ff] = board[rt][ft];
1359         if (enPassant) {
1360             board[rf][ft] = captured;
1361             board[rt][ft] = EmptySquare;
1362         } else {
1363             board[rt][ft] = captured;
1364         }
1365         board[EP_STATUS] = ep;
1366     }
1367
1368     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1369 }
1370
1371 ChessMove
1372 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1373 {   // [HGM] put drop legality testing in separate routine for clarity
1374     int n;
1375 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1376     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1377     n = PieceToNumber(piece);
1378     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1379         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1380         return ImpossibleMove; // piece not available
1381     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1382         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1383            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1384             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1385             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1386         if(piece == WhitePawn || piece == BlackPawn) {
1387             int r;
1388             for(r=1; r<BOARD_HEIGHT-1; r++)
1389                 if(board[r][ft] == piece) return IllegalMove; // or there already is a Pawn in file
1390             // should still test if we mate with this Pawn
1391         }
1392     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1393         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1394     } else {
1395         if( (piece == WhitePawn || piece == BlackPawn) &&
1396             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1397             return IllegalMove; /* no pawn drops on 1st/8th */
1398     }
1399 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1400     if (!(flags & F_IGNORE_CHECK) &&
1401         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1402     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1403 }
1404
1405 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1406                                     int rf, int ff, int rt, int ft,
1407                                     VOIDSTAR closure));
1408
1409 void
1410 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1411 {
1412     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1413
1414     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1415         cl->captures++; // [HGM] losers: count legal captures
1416     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1417       cl->kind = kind;
1418 }
1419
1420 ChessMove
1421 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1422 {
1423     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1424
1425     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1426     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1427     piece = filterPiece = board[rf][ff];
1428     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1429
1430     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1431     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1432     if(piece == WhiteFalcon || piece == BlackFalcon ||
1433        piece == WhiteCobra  || piece == BlackCobra)
1434         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1435
1436     cl.rf = rf;
1437     cl.ff = ff;
1438     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1439     cl.ft = fFilter = ft;
1440     cl.kind = IllegalMove;
1441     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1442     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1443     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1444     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1445                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1446         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1447
1448     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1449     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1450         if(board[rf][ff] < BlackPawn) { // white
1451             if(rf != 0) return IllegalMove; // must be on back rank
1452             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1453             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1454         } else {
1455             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1456             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1457             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1458         }
1459     } else
1460     if(gameInfo.variant == VariantChu) {
1461         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1462         if(promoChar != '+')
1463             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1464         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') return ImpossibleMove;
1465         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1466     } else
1467     if(gameInfo.variant == VariantShogi) {
1468         /* [HGM] Shogi promotions. '=' means defer */
1469         if(rf != DROP_RANK && cl.kind == NormalMove) {
1470             ChessSquare piece = board[rf][ff];
1471
1472             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1473             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1474                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1475                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1476                   promoChar = '+'; // allowed ICS notations
1477 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1478             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1479                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1480             else if(flags & F_WHITE_ON_MOVE) {
1481                 if( (int) piece < (int) WhiteWazir &&
1482                      (rf >= BOARD_HEIGHT - BOARD_HEIGHT/3 || rt >= BOARD_HEIGHT - BOARD_HEIGHT/3) ) {
1483                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1484                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1485                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1486                     else /* promotion optional, default is defer */
1487                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1488                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1489             } else {
1490                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1491                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1492                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1493                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1494                     else /* promotion optional, default is defer */
1495                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1496                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1497             }
1498         }
1499     } else
1500     if (promoChar != NULLCHAR) {
1501         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1502         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1503             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1504             if(piece == EmptySquare)
1505                 cl.kind = ImpossibleMove; // non-existing piece
1506             if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1507                 if(promoChar != PieceToChar(BlackKing)) {
1508                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1509                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1510                 } else { // promotion to King allowed only if we do not haave two yet
1511                     int r, f, kings = 0;
1512                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1513                     if(kings == 2) cl.kind = IllegalMove;
1514                 }
1515             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1516                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1517             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1518              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1519             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1520              cl.kind = IllegalMove; // promotion to King usually not allowed
1521         } else {
1522             cl.kind = IllegalMove;
1523         }
1524     }
1525     return cl.kind;
1526 }
1527
1528 typedef struct {
1529     int count;
1530 } MateTestClosure;
1531
1532 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1533                                 int rf, int ff, int rt, int ft,
1534                                 VOIDSTAR closure));
1535
1536 void
1537 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1538 {
1539     register MateTestClosure *cl = (MateTestClosure *) closure;
1540
1541     cl->count++;
1542 }
1543
1544 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1545 int
1546 MateTest (Board board, int flags)
1547 {
1548     MateTestClosure cl;
1549     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1550     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1551
1552     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1553         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1554         nrKing += (board[r][f] == king);   // stm has king
1555         if( board[r][f] != EmptySquare ) {
1556             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1557                  myPieces++;
1558             else hisPieces++;
1559         }
1560     }
1561     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1562         case VariantShatranj:
1563                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1564         default:
1565                 break;
1566         case VariantAtomic:
1567                 if(nrKing == 0) return MT_NOKING;
1568                 break;
1569         case VariantLosers:
1570                 if(myPieces == 1) return MT_BARE;
1571     }
1572     cl.count = 0;
1573     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1574     // [HGM] 3check: yet to do!
1575     if (cl.count > 0) {
1576         return inCheck ? MT_CHECK : MT_NONE;
1577     } else {
1578         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1579                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1580             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1581             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1582                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1583                     if(board[n][holdings] != EmptySquare) {
1584                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1585                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1586                     }
1587         }
1588         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1589                 return myPieces == hisPieces ? MT_STALEMATE :
1590                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1591         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1592         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1593
1594         return inCheck ? MT_CHECKMATE
1595                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || gameInfo.variant == VariantShogi) ?
1596                           MT_STAINMATE : MT_STALEMATE;
1597     }
1598 }
1599
1600
1601 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1602                                     int rf, int ff, int rt, int ft,
1603                                     VOIDSTAR closure));
1604
1605 void
1606 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1607 {
1608     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1609     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1610
1611     // [HGM] wild: for wild-card pieces rt and rf are dummies
1612     if(piece == WhiteFalcon || piece == BlackFalcon ||
1613        piece == WhiteCobra  || piece == BlackCobra)
1614         wildCard = TRUE;
1615
1616     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1617          || PieceToChar(board[rf][ff]) == '~'
1618               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1619                                                                       ) &&
1620         (cl->rfIn == -1 || cl->rfIn == rf) &&
1621         (cl->ffIn == -1 || cl->ffIn == ff) &&
1622         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1623         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1624
1625         cl->count++;
1626         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1627           // [HGM] oneclick: if multiple moves, be sure we remember capture
1628           cl->piece = board[rf][ff];
1629           cl->rf = rf;
1630           cl->ff = ff;
1631           cl->rt = wildCard ? cl->rtIn : rt;
1632           cl->ft = wildCard ? cl->ftIn : ft;
1633           cl->kind = kind;
1634         }
1635         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1636     }
1637 }
1638
1639 void
1640 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
1641 {
1642     int illegal = 0; char c = closure->promoCharIn;
1643
1644     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1645     closure->count = closure->captures = 0;
1646     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1647     closure->kind = ImpossibleMove;
1648     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
1649     fFilter = closure->ftIn;
1650     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
1651         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1652         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
1653             closure->count = closure->captures = 0;
1654             closure->rf = closure->ff = closure->rt = closure->ft = 0;
1655             closure->kind = ImpossibleMove;
1656             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1657         }
1658     } else
1659     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1660     if (closure->count == 0) {
1661         /* See if it's an illegal move due to check */
1662         illegal = 1;
1663         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1664         if (closure->count == 0) {
1665             /* No, it's not even that */
1666           if(!appData.testLegality && closure->pieceIn != EmptySquare) {
1667             int f, r; // if there is only a single piece of the requested type on the board, use that
1668             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
1669             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1670                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
1671             if(closure->count > 1) illegal = 0; // ambiguous
1672           }
1673           if(closure->count == 0) {
1674             if (appData.debugMode) { int i, j;
1675                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
1676                     for(j=0; j<BOARD_WIDTH; j++)
1677                         fprintf(debugFP, "%3d", (int) board[i][j]);
1678                     fprintf(debugFP, "\n");
1679                 }
1680             }
1681             return;
1682           }
1683         }
1684     }
1685
1686     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1687     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
1688         if(closure->piece < BlackPawn) { // white
1689             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
1690             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
1691             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
1692         } else {
1693             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
1694             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
1695             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
1696         }
1697     } else
1698     if(gameInfo.variant == VariantChu) {
1699         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
1700     } else
1701     if(gameInfo.variant == VariantShogi) {
1702         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1703         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1704             ChessSquare piece = closure->piece;
1705             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1706                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1707                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1708                    c = '+'; // allowed ICS notations
1709             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1710             else if(flags & F_WHITE_ON_MOVE) {
1711                 if( (int) piece < (int) WhiteWazir &&
1712                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1713                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1714                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1715                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1716                     else /* promotion optional, default is defer */
1717                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1718                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1719             } else {
1720                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1721                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1722                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1723                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1724                     else /* promotion optional, default is defer */
1725                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1726                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1727             }
1728         }
1729         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1730         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1731     } else
1732     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1733         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1734             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
1735                gameInfo.variant == VariantMakruk || gameInfo.variant == VariantASEAN)
1736                 c = PieceToChar(BlackFerz);
1737             else if(gameInfo.variant == VariantGreat)
1738                 c = PieceToChar(BlackMan);
1739             else if(gameInfo.variant == VariantGrand)
1740                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
1741             else
1742                 c = PieceToChar(BlackQueen);
1743         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1744     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1745
1746     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1747     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1748         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1749     if (closure->count > 1) {
1750         closure->kind = AmbiguousMove;
1751     }
1752     if (illegal) {
1753         /* Note: If more than one illegal move matches, but no legal
1754            moves, we return IllegalMove, not AmbiguousMove.  Caller
1755            can look at closure->count to detect this.
1756         */
1757         closure->kind = IllegalMove;
1758     }
1759 }
1760
1761
1762 typedef struct {
1763     /* Input */
1764     ChessSquare piece;
1765     int rf, ff, rt, ft;
1766     /* Output */
1767     ChessMove kind;
1768     int rank;
1769     int file;
1770     int either;
1771 } CoordsToAlgebraicClosure;
1772
1773 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1774                                          ChessMove kind, int rf, int ff,
1775                                          int rt, int ft, VOIDSTAR closure));
1776
1777 void
1778 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1779 {
1780     register CoordsToAlgebraicClosure *cl =
1781       (CoordsToAlgebraicClosure *) closure;
1782
1783     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
1784         (board[rf][ff] == cl->piece
1785          || PieceToChar(board[rf][ff]) == '~' &&
1786             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1787                                      ) {
1788         if (rf == cl->rf) {
1789             if (ff == cl->ff) {
1790                 cl->kind = kind; /* this is the move we want */
1791             } else {
1792                 cl->file++; /* need file to rule out this move */
1793             }
1794         } else {
1795             if (ff == cl->ff) {
1796                 cl->rank++; /* need rank to rule out this move */
1797             } else {
1798                 cl->either++; /* rank or file will rule out this move */
1799             }
1800         }
1801     }
1802 }
1803
1804 /* Convert coordinates to normal algebraic notation.
1805    promoChar must be NULLCHAR or 'x' if not a promotion.
1806 */
1807 ChessMove
1808 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
1809 {
1810     ChessSquare piece;
1811     ChessMove kind;
1812     char *outp = out, c;
1813     CoordsToAlgebraicClosure cl;
1814
1815     if (rf == DROP_RANK) {
1816         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
1817         /* Bughouse piece drop */
1818         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1819         *outp++ = '@';
1820         *outp++ = ft + AAA;
1821         if(rt+ONE <= '9')
1822            *outp++ = rt + ONE;
1823         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1824         *outp = NULLCHAR;
1825         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1826     }
1827
1828     if (promoChar == 'x') promoChar = NULLCHAR;
1829     piece = board[rf][ff];
1830     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1831
1832     switch (piece) {
1833       case WhitePawn:
1834       case BlackPawn:
1835         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1836         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1837             /* Keep short notation if move is illegal only because it
1838                leaves the player in check, but still return IllegalMove */
1839             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1840             if (kind == IllegalMove) break;
1841             kind = IllegalMove;
1842         }
1843         /* Pawn move */
1844         *outp++ = ff + AAA;
1845         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1846             /* Non-capture; use style "e5" */
1847             if(rt+ONE <= '9')
1848                *outp++ = rt + ONE;
1849             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1850         } else {
1851             /* Capture; use style "exd5" */
1852             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1853             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1854             *outp++ = ft + AAA;
1855             if(rt+ONE <= '9')
1856                *outp++ = rt + ONE;
1857             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1858         }
1859         /* Use promotion suffix style "=Q" */
1860         *outp = NULLCHAR;
1861         if (promoChar != NULLCHAR) {
1862             if(IS_SHOGI(gameInfo.variant)) {
1863                 /* [HGM] ... but not in Shogi! */
1864                 *outp++ = promoChar == '=' ? '=' : '+';
1865             } else {
1866                 *outp++ = '=';
1867                 *outp++ = ToUpper(promoChar);
1868             }
1869             *outp = NULLCHAR;
1870         }
1871         return kind;
1872
1873
1874       case WhiteKing:
1875       case BlackKing:
1876         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1877         /* Code added by Tord:  FRC castling. */
1878         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1879            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1880           if(ft > ff)
1881             safeStrCpy(out, "O-O", MOVE_LEN);
1882           else
1883             safeStrCpy(out, "O-O-O", MOVE_LEN);
1884           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1885         }
1886         /* End of code added by Tord */
1887         /* Test for castling or ICS wild castling */
1888         /* Use style "O-O" (oh-oh) for PGN compatibility */
1889         else if (rf == rt &&
1890             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1891             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1892             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1893              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1894             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1895               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1896             else
1897               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1898
1899             /* This notation is always unambiguous, unless there are
1900                kings on both the d and e files, with "wild castling"
1901                possible for the king on the d file and normal castling
1902                possible for the other.  ICS rules for wild 9
1903                effectively make castling illegal for either king in
1904                this situation.  So I am not going to worry about it;
1905                I'll just generate an ambiguous O-O in this case.
1906             */
1907             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1908         }
1909
1910         /* else fall through */
1911       default:
1912         /* Piece move */
1913         cl.rf = rf;
1914         cl.ff = ff;
1915         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1916         cl.ft = fFilter = ft;
1917         cl.piece = piece;
1918         cl.kind = IllegalMove;
1919         cl.rank = cl.file = cl.either = 0;
1920         c = PieceToChar(piece) ;
1921         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
1922
1923         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1924             /* Generate pretty moves for moving into check, but
1925                still return IllegalMove.
1926             */
1927             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
1928             if (cl.kind == IllegalMove) break;
1929             cl.kind = IllegalMove;
1930         }
1931
1932         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1933            else "Ngf3" or "Ngxf7",
1934            else "N1f3" or "N5xf7",
1935            else "Ng1f3" or "Ng5xf7".
1936         */
1937         if( c == '~' || c == '+') {
1938            /* [HGM] print nonexistent piece as its demoted version */
1939            piece = (ChessSquare) (DEMOTED piece);
1940         }
1941         if(c=='+') *outp++ = c;
1942         *outp++ = ToUpper(PieceToChar(piece));
1943
1944         if (cl.file || (cl.either && !cl.rank)) {
1945             *outp++ = ff + AAA;
1946         }
1947         if (cl.rank) {
1948             if(rf+ONE <= '9')
1949                 *outp++ = rf + ONE;
1950             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1951         }
1952
1953         if(board[rt][ft] != EmptySquare)
1954           *outp++ = 'x';
1955
1956         *outp++ = ft + AAA;
1957         if(rt+ONE <= '9')
1958            *outp++ = rt + ONE;
1959         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1960         if (IS_SHOGI(gameInfo.variant)) {
1961             /* [HGM] in Shogi non-pawns can promote */
1962             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1963         }
1964         else if (gameInfo.variant != VariantSuper && promoChar &&
1965                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
1966             *outp++ = '=';
1967             *outp++ = ToUpper(promoChar);
1968         }
1969         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
1970             *outp++ = '/';
1971             *outp++ = ToUpper(promoChar);
1972         }
1973         *outp = NULLCHAR;
1974         return cl.kind;
1975
1976       case EmptySquare:
1977         /* Moving a nonexistent piece */
1978         break;
1979     }
1980
1981     /* Not a legal move, even ignoring check.
1982        If there was a piece on the from square,
1983        use style "Ng1g3" or "Ng1xe8";
1984        if there was a pawn or nothing (!),
1985        use style "g1g3" or "g1xe8".  Use "x"
1986        if a piece was on the to square, even
1987        a piece of the same color.
1988     */
1989     outp = out;
1990     c = 0;
1991     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1992         int r, f;
1993       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
1994                 c += (board[r][f] == piece); // count on-board pieces of given type
1995         *outp++ = ToUpper(PieceToChar(piece));
1996     }
1997   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
1998     *outp++ = ff + AAA;
1999     if(rf+ONE <= '9')
2000        *outp++ = rf + ONE;
2001     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2002   }
2003     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2004     *outp++ = ft + AAA;
2005     if(rt+ONE <= '9')
2006        *outp++ = rt + ONE;
2007     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2008     /* Use promotion suffix style "=Q" */
2009     if (promoChar != NULLCHAR && promoChar != 'x') {
2010         *outp++ = '=';
2011         *outp++ = ToUpper(promoChar);
2012     }
2013     *outp = NULLCHAR;
2014
2015     return IllegalMove;
2016 }
2017
2018 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2019
2020 typedef struct {
2021     /* Input */
2022     int rf, ff, rt, ft;
2023     /* Output */
2024     int recaptures;
2025 } ChaseClosure;
2026
2027 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2028
2029 int preyStackPointer, chaseStackPointer;
2030
2031 struct {
2032 unsigned char rf, ff, rt, ft;
2033 } chaseStack[100];
2034
2035 struct {
2036 unsigned char rank, file;
2037 } preyStack[100];
2038
2039
2040
2041
2042 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2043
2044 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2045                                 int rf, int ff, int rt, int ft,
2046                                 VOIDSTAR closure));
2047
2048 void
2049 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2050 {   // For adding captures that can lead to chase indictment to the chaseStack
2051     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2052     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2053     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2054     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2055     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2056     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2057     chaseStack[chaseStackPointer].rf = rf;
2058     chaseStack[chaseStackPointer].ff = ff;
2059     chaseStack[chaseStackPointer].rt = rt;
2060     chaseStack[chaseStackPointer].ft = ft;
2061     chaseStackPointer++;
2062 }
2063
2064 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2065                                 int rf, int ff, int rt, int ft,
2066                                 VOIDSTAR closure));
2067
2068 void
2069 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2070 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2071     int i;
2072     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2073
2074     if(board[rt][ft] == EmptySquare) return; // no capture
2075     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2076         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2077     }
2078     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2079     for(i=0; i<chaseStackPointer; i++) {
2080         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2081            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2082             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2083             chaseStack[i] = chaseStack[--chaseStackPointer];
2084             break;
2085         }
2086     }
2087 }
2088
2089 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2090                                 int rf, int ff, int rt, int ft,
2091                                 VOIDSTAR closure));
2092
2093 void
2094 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2095 {   // for determining if a piece (given through the closure) is protected
2096     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2097
2098     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2099     if(appData.debugMode && board[rt][ft] != EmptySquare)
2100         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2101 }
2102
2103 extern char moveList[MAX_MOVES][MOVE_LEN];
2104
2105 int
2106 PerpetualChase (int first, int last)
2107 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2108     int i, j, k, tail;
2109     ChaseClosure cl;
2110     ChessSquare captured;
2111
2112     preyStackPointer = 0;        // clear stack of chased pieces
2113     for(i=first; i<last; i+=2) { // for all positions with same side to move
2114         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2115         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2116         // determine all captures possible after the move, and put them on chaseStack
2117         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2118         if(appData.debugMode) { int n;
2119             for(n=0; n<chaseStackPointer; n++)
2120                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2121                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2122             fprintf(debugFP, ": all capts\n");
2123         }
2124         // determine all captures possible before the move, and delete them from chaseStack
2125         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2126         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2127         cl.rt = moveList[i][3]-ONE;
2128         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2129         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2130         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2131         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2132         if(appData.debugMode) { int n;
2133             for(n=0; n<chaseStackPointer; n++)
2134                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2135                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2136             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2137         }
2138         // chaseSack now contains all captures made possible by the move
2139         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2140             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2141             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2142
2143             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2144             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2145
2146             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2147                 continue; // C or H attack on R is always chase; leave on chaseStack
2148
2149             if(attacker == victim) {
2150                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2151                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2152                         // we can capture back with equal piece, so this is no chase but a sacrifice
2153                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2154                         j--; /* ! */ continue;
2155                 }
2156
2157             }
2158
2159             // the attack is on a lower piece, or on a pinned or blocked equal one
2160             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2161             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2162             // test if the victim is protected by a true protector. First make the capture.
2163             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2164             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2165             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2166             // Then test if the opponent can recapture
2167             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2168             cl.rt = chaseStack[j].rt;
2169             cl.ft = chaseStack[j].ft;
2170             if(appData.debugMode) {
2171                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2172             }
2173             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2174             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2175             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2176             // unmake the capture
2177             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2178             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2179             // if a recapture was found, piece is protected, and we are not chasing it.
2180             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2181                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2182                 j--; /* ! */
2183             }
2184         }
2185         // chaseStack now contains all moves that chased
2186         if(appData.debugMode) { int n;
2187             for(n=0; n<chaseStackPointer; n++)
2188                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2189                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2190             fprintf(debugFP, ": chases\n");
2191         }
2192         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2193             for(j=0; j<chaseStackPointer; j++) {
2194                 preyStack[j].rank = chaseStack[j].rt;
2195                 preyStack[j].file = chaseStack[j].ft;
2196             }
2197             preyStackPointer = chaseStackPointer;
2198         }
2199         tail = 0;
2200         for(j=0; j<chaseStackPointer; j++) {
2201             for(k=0; k<preyStackPointer; k++) {
2202                 // search the victim of each chase move on the preyStack (first occurrence)
2203                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2204                     if(k < tail) break; // piece was already identified as still being chased
2205                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2206                     preyStack[tail] = preyStack[k];                // by swapping
2207                     preyStack[k] = preyStack[preyStackPointer];
2208                     tail++;
2209                     break;
2210                 }
2211             }
2212         }
2213         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2214         if(appData.debugMode) { int n;
2215             for(n=0; n<preyStackPointer; n++)
2216                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2217             fprintf(debugFP, "always chased upto ply %d\n", i);
2218         }
2219         // now adjust the location of the chased pieces according to opponent move
2220         for(j=0; j<preyStackPointer; j++) {
2221             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2222                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2223                 preyStack[j].rank = moveList[i+1][3]-ONE;
2224                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2225                 break;
2226             }
2227         }
2228     }
2229     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2230                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2231 }