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, trampled;
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             if(killX >= 0) { trampled = board[killY][killX]; board[killY][killX] = EmptySquare; }
1317         }
1318         if(rf == DROP_RANK) board[rt][ft] = ff; else { // [HGM] drop
1319             board[rt][ft] = board[rf][ff];
1320             board[rf][ff] = EmptySquare;
1321         }
1322         ep = board[EP_STATUS];
1323         if( captured == WhiteLion || captured == BlackLion ) { // [HGM] lion: Chu Lion-capture rules
1324             ChessSquare victim = killX < 0 ? EmptySquare : trampled;
1325             if( (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion) &&           // capturer is Lion
1326                 (ff - ft > 1 || ft - ff > 1 || rf - rt > 1 || rt - rf > 1) &&           // captures from a distance
1327                 (victim == EmptySquare || victim == WhitePawn || victim == BlackPawn) ) // no or worthless 'bridge'
1328                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1329         }
1330     }
1331
1332     /* For compatibility with ICS wild 9, we scan the board in the
1333        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1334        and we test only whether that one is in check. */
1335     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1336         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1337           if (board[cl.rking][cl.fking] == king) {
1338               cl.check = 0;
1339               if(gameInfo.variant == VariantXiangqi) {
1340                   /* [HGM] In Xiangqi opposing Kings means check as well */
1341                   int i, dir;
1342                   dir = (king >= BlackPawn) ? -1 : 1;
1343                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1344                                 board[i][cl.fking] == EmptySquare; i+=dir );
1345                   if(i>=0 && i<BOARD_HEIGHT &&
1346                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1347                           cl.check++;
1348               }
1349               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1350               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1351                  goto undo_move;  /* 2-level break */
1352           }
1353       }
1354
1355   undo_move:
1356
1357     if (rt >= 0) {
1358         if(rf != DROP_RANK) // [HGM] drop
1359             board[rf][ff] = board[rt][ft];
1360         if (enPassant) {
1361             board[rf][ft] = captured;
1362             board[rt][ft] = EmptySquare;
1363         } else {
1364             if(killX >= 0) board[killY][killX] = trampled;
1365             board[rt][ft] = captured;
1366         }
1367         board[EP_STATUS] = ep;
1368     }
1369
1370     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1371 }
1372
1373 ChessMove
1374 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1375 {   // [HGM] put drop legality testing in separate routine for clarity
1376     int n;
1377 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1378     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1379     n = PieceToNumber(piece);
1380     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1381         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1382         return ImpossibleMove; // piece not available
1383     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1384         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1385            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1386             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1387             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1388         if(piece == WhitePawn || piece == BlackPawn) {
1389             int r;
1390             for(r=1; r<BOARD_HEIGHT-1; r++)
1391                 if(board[r][ft] == piece) return IllegalMove; // or there already is a Pawn in file
1392             // should still test if we mate with this Pawn
1393         }
1394     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1395         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1396     } else {
1397         if( (piece == WhitePawn || piece == BlackPawn) &&
1398             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1399             return IllegalMove; /* no pawn drops on 1st/8th */
1400     }
1401 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1402     if (!(flags & F_IGNORE_CHECK) &&
1403         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1404     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1405 }
1406
1407 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1408                                     int rf, int ff, int rt, int ft,
1409                                     VOIDSTAR closure));
1410
1411 void
1412 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1413 {
1414     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1415
1416     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1417         cl->captures++; // [HGM] losers: count legal captures
1418     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1419       cl->kind = kind;
1420 }
1421
1422 ChessMove
1423 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1424 {
1425     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1426
1427     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1428     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1429     piece = filterPiece = board[rf][ff];
1430     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1431
1432     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1433     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1434     if(piece == WhiteFalcon || piece == BlackFalcon ||
1435        piece == WhiteCobra  || piece == BlackCobra)
1436         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1437
1438     cl.rf = rf;
1439     cl.ff = ff;
1440     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1441     cl.ft = fFilter = ft;
1442     cl.kind = IllegalMove;
1443     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1444     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1445     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1446     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1447                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1448         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1449
1450     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1451     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1452         if(board[rf][ff] < BlackPawn) { // white
1453             if(rf != 0) return IllegalMove; // must be on back rank
1454             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1455             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1456         } else {
1457             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1458             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1459             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1460         }
1461     } else
1462     if(gameInfo.variant == VariantChu) {
1463         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1464         if(promoChar != '+')
1465             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1466         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') return ImpossibleMove;
1467         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1468     } else
1469     if(gameInfo.variant == VariantShogi) {
1470         /* [HGM] Shogi promotions. '=' means defer */
1471         if(rf != DROP_RANK && cl.kind == NormalMove) {
1472             ChessSquare piece = board[rf][ff];
1473
1474             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1475             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1476                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1477                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1478                   promoChar = '+'; // allowed ICS notations
1479 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1480             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1481                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1482             else if(flags & F_WHITE_ON_MOVE) {
1483                 if( (int) piece < (int) WhiteWazir &&
1484                      (rf >= BOARD_HEIGHT - BOARD_HEIGHT/3 || rt >= BOARD_HEIGHT - BOARD_HEIGHT/3) ) {
1485                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1486                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1487                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1488                     else /* promotion optional, default is defer */
1489                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1490                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1491             } else {
1492                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1493                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1494                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1495                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1496                     else /* promotion optional, default is defer */
1497                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1498                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1499             }
1500         }
1501     } else
1502     if (promoChar != NULLCHAR) {
1503         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1504         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1505             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1506             if(piece == EmptySquare)
1507                 cl.kind = ImpossibleMove; // non-existing piece
1508             if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1509                 if(promoChar != PieceToChar(BlackKing)) {
1510                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1511                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1512                 } else { // promotion to King allowed only if we do not haave two yet
1513                     int r, f, kings = 0;
1514                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1515                     if(kings == 2) cl.kind = IllegalMove;
1516                 }
1517             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1518                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1519             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1520              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1521             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1522              cl.kind = IllegalMove; // promotion to King usually not allowed
1523         } else {
1524             cl.kind = IllegalMove;
1525         }
1526     }
1527     return cl.kind;
1528 }
1529
1530 typedef struct {
1531     int count;
1532 } MateTestClosure;
1533
1534 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1535                                 int rf, int ff, int rt, int ft,
1536                                 VOIDSTAR closure));
1537
1538 void
1539 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1540 {
1541     register MateTestClosure *cl = (MateTestClosure *) closure;
1542
1543     cl->count++;
1544 }
1545
1546 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1547 int
1548 MateTest (Board board, int flags)
1549 {
1550     MateTestClosure cl;
1551     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1552     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1553
1554     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1555         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1556         nrKing += (board[r][f] == king);   // stm has king
1557         if( board[r][f] != EmptySquare ) {
1558             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1559                  myPieces++;
1560             else hisPieces++;
1561         }
1562     }
1563     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1564         case VariantShatranj:
1565                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1566         default:
1567                 break;
1568         case VariantAtomic:
1569                 if(nrKing == 0) return MT_NOKING;
1570                 break;
1571         case VariantLosers:
1572                 if(myPieces == 1) return MT_BARE;
1573     }
1574     cl.count = 0;
1575     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1576     // [HGM] 3check: yet to do!
1577     if (cl.count > 0) {
1578         return inCheck ? MT_CHECK : MT_NONE;
1579     } else {
1580         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1581                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1582             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1583             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1584                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1585                     if(board[n][holdings] != EmptySquare) {
1586                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1587                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1588                     }
1589         }
1590         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1591                 return myPieces == hisPieces ? MT_STALEMATE :
1592                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1593         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1594         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1595
1596         return inCheck ? MT_CHECKMATE
1597                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || gameInfo.variant == VariantShogi) ?
1598                           MT_STAINMATE : MT_STALEMATE;
1599     }
1600 }
1601
1602
1603 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1604                                     int rf, int ff, int rt, int ft,
1605                                     VOIDSTAR closure));
1606
1607 void
1608 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1609 {
1610     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1611     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1612
1613     // [HGM] wild: for wild-card pieces rt and rf are dummies
1614     if(piece == WhiteFalcon || piece == BlackFalcon ||
1615        piece == WhiteCobra  || piece == BlackCobra)
1616         wildCard = TRUE;
1617
1618     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1619          || PieceToChar(board[rf][ff]) == '~'
1620               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1621                                                                       ) &&
1622         (cl->rfIn == -1 || cl->rfIn == rf) &&
1623         (cl->ffIn == -1 || cl->ffIn == ff) &&
1624         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1625         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1626
1627         cl->count++;
1628         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1629           // [HGM] oneclick: if multiple moves, be sure we remember capture
1630           cl->piece = board[rf][ff];
1631           cl->rf = rf;
1632           cl->ff = ff;
1633           cl->rt = wildCard ? cl->rtIn : rt;
1634           cl->ft = wildCard ? cl->ftIn : ft;
1635           cl->kind = kind;
1636         }
1637         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1638     }
1639 }
1640
1641 void
1642 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
1643 {
1644     int illegal = 0; char c = closure->promoCharIn;
1645
1646     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1647     closure->count = closure->captures = 0;
1648     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1649     closure->kind = ImpossibleMove;
1650     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
1651     fFilter = closure->ftIn;
1652     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
1653         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1654         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
1655             closure->count = closure->captures = 0;
1656             closure->rf = closure->ff = closure->rt = closure->ft = 0;
1657             closure->kind = ImpossibleMove;
1658             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1659         }
1660     } else
1661     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1662     if (closure->count == 0) {
1663         /* See if it's an illegal move due to check */
1664         illegal = 1;
1665         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1666         if (closure->count == 0) {
1667             /* No, it's not even that */
1668           if(!appData.testLegality && closure->pieceIn != EmptySquare) {
1669             int f, r; // if there is only a single piece of the requested type on the board, use that
1670             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
1671             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1672                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
1673             if(closure->count > 1) illegal = 0; // ambiguous
1674           }
1675           if(closure->count == 0) {
1676             if (appData.debugMode) { int i, j;
1677                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
1678                     for(j=0; j<BOARD_WIDTH; j++)
1679                         fprintf(debugFP, "%3d", (int) board[i][j]);
1680                     fprintf(debugFP, "\n");
1681                 }
1682             }
1683             return;
1684           }
1685         }
1686     }
1687
1688     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1689     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
1690         if(closure->piece < BlackPawn) { // white
1691             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
1692             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
1693             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
1694         } else {
1695             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
1696             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
1697             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
1698         }
1699     } else
1700     if(gameInfo.variant == VariantChu) {
1701         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
1702     } else
1703     if(gameInfo.variant == VariantShogi) {
1704         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1705         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1706             ChessSquare piece = closure->piece;
1707             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1708                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1709                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1710                    c = '+'; // allowed ICS notations
1711             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1712             else if(flags & F_WHITE_ON_MOVE) {
1713                 if( (int) piece < (int) WhiteWazir &&
1714                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1715                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1716                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1717                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1718                     else /* promotion optional, default is defer */
1719                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1720                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1721             } else {
1722                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1723                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1724                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1725                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1726                     else /* promotion optional, default is defer */
1727                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1728                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1729             }
1730         }
1731         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1732         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1733     } else
1734     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1735         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1736             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
1737                gameInfo.variant == VariantMakruk || gameInfo.variant == VariantASEAN)
1738                 c = PieceToChar(BlackFerz);
1739             else if(gameInfo.variant == VariantGreat)
1740                 c = PieceToChar(BlackMan);
1741             else if(gameInfo.variant == VariantGrand)
1742                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
1743             else
1744                 c = PieceToChar(BlackQueen);
1745         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1746     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1747
1748     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1749     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1750         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1751     if (closure->count > 1) {
1752         closure->kind = AmbiguousMove;
1753     }
1754     if (illegal) {
1755         /* Note: If more than one illegal move matches, but no legal
1756            moves, we return IllegalMove, not AmbiguousMove.  Caller
1757            can look at closure->count to detect this.
1758         */
1759         closure->kind = IllegalMove;
1760     }
1761 }
1762
1763
1764 typedef struct {
1765     /* Input */
1766     ChessSquare piece;
1767     int rf, ff, rt, ft;
1768     /* Output */
1769     ChessMove kind;
1770     int rank;
1771     int file;
1772     int either;
1773 } CoordsToAlgebraicClosure;
1774
1775 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1776                                          ChessMove kind, int rf, int ff,
1777                                          int rt, int ft, VOIDSTAR closure));
1778
1779 void
1780 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1781 {
1782     register CoordsToAlgebraicClosure *cl =
1783       (CoordsToAlgebraicClosure *) closure;
1784
1785     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
1786         (board[rf][ff] == cl->piece
1787          || PieceToChar(board[rf][ff]) == '~' &&
1788             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1789                                      ) {
1790         if (rf == cl->rf) {
1791             if (ff == cl->ff) {
1792                 cl->kind = kind; /* this is the move we want */
1793             } else {
1794                 cl->file++; /* need file to rule out this move */
1795             }
1796         } else {
1797             if (ff == cl->ff) {
1798                 cl->rank++; /* need rank to rule out this move */
1799             } else {
1800                 cl->either++; /* rank or file will rule out this move */
1801             }
1802         }
1803     }
1804 }
1805
1806 /* Convert coordinates to normal algebraic notation.
1807    promoChar must be NULLCHAR or 'x' if not a promotion.
1808 */
1809 ChessMove
1810 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
1811 {
1812     ChessSquare piece;
1813     ChessMove kind;
1814     char *outp = out, c;
1815     CoordsToAlgebraicClosure cl;
1816
1817     if (rf == DROP_RANK) {
1818         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
1819         /* Bughouse piece drop */
1820         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1821         *outp++ = '@';
1822         *outp++ = ft + AAA;
1823         if(rt+ONE <= '9')
1824            *outp++ = rt + ONE;
1825         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1826         *outp = NULLCHAR;
1827         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1828     }
1829
1830     if (promoChar == 'x') promoChar = NULLCHAR;
1831     piece = board[rf][ff];
1832     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1833
1834     switch (piece) {
1835       case WhitePawn:
1836       case BlackPawn:
1837         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1838         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1839             /* Keep short notation if move is illegal only because it
1840                leaves the player in check, but still return IllegalMove */
1841             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1842             if (kind == IllegalMove) break;
1843             kind = IllegalMove;
1844         }
1845         /* Pawn move */
1846         *outp++ = ff + AAA;
1847         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1848             /* Non-capture; use style "e5" */
1849             if(rt+ONE <= '9')
1850                *outp++ = rt + ONE;
1851             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1852         } else {
1853             /* Capture; use style "exd5" */
1854             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1855             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1856             *outp++ = ft + AAA;
1857             if(rt+ONE <= '9')
1858                *outp++ = rt + ONE;
1859             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1860         }
1861         /* Use promotion suffix style "=Q" */
1862         *outp = NULLCHAR;
1863         if (promoChar != NULLCHAR) {
1864             if(IS_SHOGI(gameInfo.variant)) {
1865                 /* [HGM] ... but not in Shogi! */
1866                 *outp++ = promoChar == '=' ? '=' : '+';
1867             } else {
1868                 *outp++ = '=';
1869                 *outp++ = ToUpper(promoChar);
1870             }
1871             *outp = NULLCHAR;
1872         }
1873         return kind;
1874
1875
1876       case WhiteKing:
1877       case BlackKing:
1878         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1879         /* Code added by Tord:  FRC castling. */
1880         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1881            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1882           if(ft > ff)
1883             safeStrCpy(out, "O-O", MOVE_LEN);
1884           else
1885             safeStrCpy(out, "O-O-O", MOVE_LEN);
1886           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1887         }
1888         /* End of code added by Tord */
1889         /* Test for castling or ICS wild castling */
1890         /* Use style "O-O" (oh-oh) for PGN compatibility */
1891         else if (rf == rt &&
1892             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1893             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1894             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1895              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1896             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1897               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1898             else
1899               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1900
1901             /* This notation is always unambiguous, unless there are
1902                kings on both the d and e files, with "wild castling"
1903                possible for the king on the d file and normal castling
1904                possible for the other.  ICS rules for wild 9
1905                effectively make castling illegal for either king in
1906                this situation.  So I am not going to worry about it;
1907                I'll just generate an ambiguous O-O in this case.
1908             */
1909             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1910         }
1911
1912         /* else fall through */
1913       default:
1914         /* Piece move */
1915         cl.rf = rf;
1916         cl.ff = ff;
1917         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1918         cl.ft = fFilter = ft;
1919         cl.piece = piece;
1920         cl.kind = IllegalMove;
1921         cl.rank = cl.file = cl.either = 0;
1922         c = PieceToChar(piece) ;
1923         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
1924
1925         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1926             /* Generate pretty moves for moving into check, but
1927                still return IllegalMove.
1928             */
1929             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
1930             if (cl.kind == IllegalMove) break;
1931             cl.kind = IllegalMove;
1932         }
1933
1934         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1935            else "Ngf3" or "Ngxf7",
1936            else "N1f3" or "N5xf7",
1937            else "Ng1f3" or "Ng5xf7".
1938         */
1939         if( c == '~' || c == '+') {
1940            /* [HGM] print nonexistent piece as its demoted version */
1941            piece = (ChessSquare) (DEMOTED piece - 11*(gameInfo.variant == VariantChu));
1942         }
1943         if(c=='+') *outp++ = c;
1944         *outp++ = ToUpper(PieceToChar(piece));
1945
1946         if (cl.file || (cl.either && !cl.rank)) {
1947             *outp++ = ff + AAA;
1948         }
1949         if (cl.rank) {
1950             if(rf+ONE <= '9')
1951                 *outp++ = rf + ONE;
1952             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1953         }
1954
1955         if(board[rt][ft] != EmptySquare)
1956           *outp++ = 'x';
1957
1958         *outp++ = ft + AAA;
1959         if(rt+ONE <= '9')
1960            *outp++ = rt + ONE;
1961         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1962         if (IS_SHOGI(gameInfo.variant)) {
1963             /* [HGM] in Shogi non-pawns can promote */
1964             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1965         }
1966         else if (gameInfo.variant != VariantSuper && promoChar &&
1967                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
1968             *outp++ = '=';
1969             *outp++ = ToUpper(promoChar);
1970         }
1971         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
1972             *outp++ = '/';
1973             *outp++ = ToUpper(promoChar);
1974         }
1975         *outp = NULLCHAR;
1976         return cl.kind;
1977
1978       case EmptySquare:
1979         /* Moving a nonexistent piece */
1980         break;
1981     }
1982
1983     /* Not a legal move, even ignoring check.
1984        If there was a piece on the from square,
1985        use style "Ng1g3" or "Ng1xe8";
1986        if there was a pawn or nothing (!),
1987        use style "g1g3" or "g1xe8".  Use "x"
1988        if a piece was on the to square, even
1989        a piece of the same color.
1990     */
1991     outp = out;
1992     c = 0;
1993     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1994         int r, f;
1995       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
1996                 c += (board[r][f] == piece); // count on-board pieces of given type
1997         *outp++ = ToUpper(PieceToChar(piece));
1998     }
1999   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2000     *outp++ = ff + AAA;
2001     if(rf+ONE <= '9')
2002        *outp++ = rf + ONE;
2003     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2004   }
2005     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2006     *outp++ = ft + AAA;
2007     if(rt+ONE <= '9')
2008        *outp++ = rt + ONE;
2009     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2010     /* Use promotion suffix style "=Q" */
2011     if (promoChar != NULLCHAR && promoChar != 'x') {
2012         *outp++ = '=';
2013         *outp++ = ToUpper(promoChar);
2014     }
2015     *outp = NULLCHAR;
2016
2017     return IllegalMove;
2018 }
2019
2020 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2021
2022 typedef struct {
2023     /* Input */
2024     int rf, ff, rt, ft;
2025     /* Output */
2026     int recaptures;
2027 } ChaseClosure;
2028
2029 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2030
2031 int preyStackPointer, chaseStackPointer;
2032
2033 struct {
2034 unsigned char rf, ff, rt, ft;
2035 } chaseStack[100];
2036
2037 struct {
2038 unsigned char rank, file;
2039 } preyStack[100];
2040
2041
2042
2043
2044 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2045
2046 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2047                                 int rf, int ff, int rt, int ft,
2048                                 VOIDSTAR closure));
2049
2050 void
2051 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2052 {   // For adding captures that can lead to chase indictment to the chaseStack
2053     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2054     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2055     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2056     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2057     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2058     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2059     chaseStack[chaseStackPointer].rf = rf;
2060     chaseStack[chaseStackPointer].ff = ff;
2061     chaseStack[chaseStackPointer].rt = rt;
2062     chaseStack[chaseStackPointer].ft = ft;
2063     chaseStackPointer++;
2064 }
2065
2066 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2067                                 int rf, int ff, int rt, int ft,
2068                                 VOIDSTAR closure));
2069
2070 void
2071 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2072 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2073     int i;
2074     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2075
2076     if(board[rt][ft] == EmptySquare) return; // no capture
2077     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2078         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2079     }
2080     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2081     for(i=0; i<chaseStackPointer; i++) {
2082         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2083            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2084             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2085             chaseStack[i] = chaseStack[--chaseStackPointer];
2086             break;
2087         }
2088     }
2089 }
2090
2091 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2092                                 int rf, int ff, int rt, int ft,
2093                                 VOIDSTAR closure));
2094
2095 void
2096 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2097 {   // for determining if a piece (given through the closure) is protected
2098     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2099
2100     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2101     if(appData.debugMode && board[rt][ft] != EmptySquare)
2102         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2103 }
2104
2105 extern char moveList[MAX_MOVES][MOVE_LEN];
2106
2107 int
2108 PerpetualChase (int first, int last)
2109 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2110     int i, j, k, tail;
2111     ChaseClosure cl;
2112     ChessSquare captured;
2113
2114     preyStackPointer = 0;        // clear stack of chased pieces
2115     for(i=first; i<last; i+=2) { // for all positions with same side to move
2116         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2117         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2118         // determine all captures possible after the move, and put them on chaseStack
2119         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2120         if(appData.debugMode) { int n;
2121             for(n=0; n<chaseStackPointer; n++)
2122                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2123                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2124             fprintf(debugFP, ": all capts\n");
2125         }
2126         // determine all captures possible before the move, and delete them from chaseStack
2127         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2128         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2129         cl.rt = moveList[i][3]-ONE;
2130         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2131         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2132         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2133         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2134         if(appData.debugMode) { int n;
2135             for(n=0; n<chaseStackPointer; n++)
2136                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2137                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2138             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2139         }
2140         // chaseSack now contains all captures made possible by the move
2141         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2142             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2143             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2144
2145             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2146             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2147
2148             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2149                 continue; // C or H attack on R is always chase; leave on chaseStack
2150
2151             if(attacker == victim) {
2152                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2153                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2154                         // we can capture back with equal piece, so this is no chase but a sacrifice
2155                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2156                         j--; /* ! */ continue;
2157                 }
2158
2159             }
2160
2161             // the attack is on a lower piece, or on a pinned or blocked equal one
2162             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2163             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2164             // test if the victim is protected by a true protector. First make the capture.
2165             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2166             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2167             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2168             // Then test if the opponent can recapture
2169             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2170             cl.rt = chaseStack[j].rt;
2171             cl.ft = chaseStack[j].ft;
2172             if(appData.debugMode) {
2173                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2174             }
2175             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2176             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2177             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2178             // unmake the capture
2179             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2180             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2181             // if a recapture was found, piece is protected, and we are not chasing it.
2182             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2183                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2184                 j--; /* ! */
2185             }
2186         }
2187         // chaseStack now contains all moves that chased
2188         if(appData.debugMode) { int n;
2189             for(n=0; n<chaseStackPointer; n++)
2190                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2191                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2192             fprintf(debugFP, ": chases\n");
2193         }
2194         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2195             for(j=0; j<chaseStackPointer; j++) {
2196                 preyStack[j].rank = chaseStack[j].rt;
2197                 preyStack[j].file = chaseStack[j].ft;
2198             }
2199             preyStackPointer = chaseStackPointer;
2200         }
2201         tail = 0;
2202         for(j=0; j<chaseStackPointer; j++) {
2203             for(k=0; k<preyStackPointer; k++) {
2204                 // search the victim of each chase move on the preyStack (first occurrence)
2205                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2206                     if(k < tail) break; // piece was already identified as still being chased
2207                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2208                     preyStack[tail] = preyStack[k];                // by swapping
2209                     preyStack[k] = preyStack[preyStackPointer];
2210                     tail++;
2211                     break;
2212                 }
2213             }
2214         }
2215         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2216         if(appData.debugMode) { int n;
2217             for(n=0; n<preyStackPointer; n++)
2218                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2219             fprintf(debugFP, "always chased upto ply %d\n", i);
2220         }
2221         // now adjust the location of the chased pieces according to opponent move
2222         for(j=0; j<preyStackPointer; j++) {
2223             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2224                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2225                 preyStack[j].rank = moveList[i+1][3]-ONE;
2226                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2227                 break;
2228             }
2229         }
2230     }
2231     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2232                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2233 }