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 || gameInfo.variant == VariantChuChess ? 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               if(gameInfo.variant == VariantChuChess) goto DragonHorse;
 676               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
 677                 for (s = -2; s <= 2; s += 4) {
 678                       rt = rf + s * d;
 679                       ft = ff + s * (1 - d);
 680                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 681                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
 682                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 683                   }
 684
 685             /* Shogi Dragon Horse has to continue with Wazir after Bishop */
 686             case SHOGI WhiteCardinal:
 687             case SHOGI BlackCardinal:
 688             case SHOGI WhitePCardinal:
 689             case SHOGI BlackPCardinal:
 690             DragonHorse:
 691                 Bishop(board, flags, rf, ff, callback, closure);
 692                 Wazir(board, flags, rf, ff, callback, closure);
 693                 break;
 694
 695             /* Capablanca Archbishop continues as Knight                  */
 696             case WhiteAngel:
 697             case BlackAngel:
 698                 Knight(board, flags, rf, ff, callback, closure);
 699
 700             /* Shogi Bishops are ordinary Bishops */
 701             case SHOGI WhiteBishop:
 702             case SHOGI BlackBishop:
 703             case SHOGI WhitePBishop:
 704             case SHOGI BlackPBishop:
 705             case WhiteBishop:
 706             case BlackBishop:
 707                 Bishop(board, flags, rf, ff, callback, closure);
 708                 break;
 709
 710             /* Shogi Lance is unlike anything, and asymmetric at that */
 711             case SHOGI WhiteQueen:
 712               if(gameInfo.variant == VariantChu) goto doQueen;
 713               for(i = 1;; i++) {
 714                       rt = rf + i;
 715                       ft = ff;
 716                       if (rt >= BOARD_HEIGHT) break;
 717                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 718                       callback(board, flags, NormalMove,
 719                                rf, ff, rt, ft, closure);
 720                       if (board[rt][ft] != EmptySquare) break;
 721               }
 722               break;
 723
 724             case SHOGI BlackQueen:
 725               if(gameInfo.variant == VariantChu) goto doQueen;
 726               for(i = 1;; i++) {
 727                       rt = rf - i;
 728                       ft = ff;
 729                       if (rt < 0) break;
 730                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 731                       callback(board, flags, NormalMove,
 732                                rf, ff, rt, ft, closure);
 733                       if (board[rt][ft] != EmptySquare) break;
 734               }
 735               break;
 736
 737             /* Make Dragon-King Dababba & Rook-like outside Shogi, for better disambiguation in variant Fairy */
 738             case WhiteDragon:
 739             case BlackDragon:
 740               if(gameInfo.variant == VariantChuChess) goto DragonKing;
 741               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
 742                 for (s = -2; s <= 2; s += 4) {
 743                       rt = rf + s * d;
 744                       ft = ff + s * (1 - d);
 745                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT || board[rf+rt>>1][ff+ft>>1] == EmptySquare) continue;
 746                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
 747                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
 748                   }
 749               if(gameInfo.variant == VariantSpartan) rookRange = 2; // in Spartan Chess restrict range to modern Dababba
 750               goto doRook;
 751
 752             /* Shogi Dragon King has to continue as Ferz after Rook moves */
 753             case SHOGI WhiteDragon:
 754             case SHOGI BlackDragon:
 755             case SHOGI WhitePDragon:
 756             case SHOGI BlackPDragon:
 757             DragonKing:
 758                 Rook(board, flags, rf, ff, callback, closure);
 759                 Ferz(board, flags, rf, ff, callback, closure);
 760                 break;
 761               m++;
 762
 763             /* Capablanca Chancellor sets flag to continue as Knight      */
 764             case WhiteMarshall:
 765             case BlackMarshall:
 766                 Rook(board, flags, rf, ff, callback, closure);
 767                 if(gameInfo.variant == VariantSpartan) // in Spartan Chess Chancellor is used for Dragon King.
 768                     Ferz(board, flags, rf, ff, callback, closure);
 769                 else
 770                     Knight(board, flags, rf, ff, callback, closure);
 771                 break;
 772
 773             /* Shogi Rooks are ordinary Rooks */
 774             case SHOGI WhiteRook:
 775             case SHOGI BlackRook:
 776             case SHOGI WhitePRook:
 777             case SHOGI BlackPRook:
 778             case WhiteRook:
 779             case BlackRook:
 780           doRook:
 781                 Rook(board, flags, rf, ff, callback, closure);
 782                 break;
 783
 784             case WhiteQueen:
 785             case BlackQueen:
 786             case SHOGI WhiteMother:
 787             case SHOGI BlackMother:
 788             doQueen:
 789                 Rook(board, flags, rf, ff, callback, closure);
 790                 Bishop(board, flags, rf, ff, callback, closure);
 791                 break;
 792
 793            case SHOGI WhitePawn:
 794                 StepForward(board, flags, rf, ff, callback, closure);
 795                 break;
 796
 797             case SHOGI BlackPawn:
 798                 StepBackward(board, flags, rf, ff, callback, closure);
 799                 break;
 800
 801             case WhiteMan:
 802                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
 803             case SHOGI WhiteFerz:
 804                 Ferz(board, flags, rf, ff, callback, closure);
 805                 StepForward(board, flags, rf, ff, callback, closure);
 806                 break;
 807
 808             case BlackMan:
 809                 if(gameInfo.variant != VariantMakruk && gameInfo.variant != VariantASEAN) goto commoner;
 810             case SHOGI BlackFerz:
 811                 StepBackward(board, flags, rf, ff, callback, closure);
 812
 813             case WhiteFerz:
 814             case BlackFerz:
 815                 /* [HGM] support Shatranj pieces */
 816                 Ferz(board, flags, rf, ff, callback, closure);
 817                 break;
 818
 819             case WhiteSilver:
 820             case BlackSilver:
 821                 Knight(board, flags, rf, ff, callback, closure); // [HGM] superchess: use for Centaur
 822
 823             commoner:
 824             case SHOGI WhiteMonarch:
 825             case SHOGI BlackMonarch:
 826             case SHOGI WhiteKing:
 827             case SHOGI BlackKing:
 828             case WhiteKing:
 829             case BlackKing:
 830                 Ferz(board, flags, rf, ff, callback, closure);
 831                 Wazir(board, flags, rf, ff, callback, closure);
 832                 break;
 833
 834             case WhiteNightrider:
 835             case BlackNightrider:
 836               for (i = -1; i <= 1; i += 2)
 837                 for (j = -1; j <= 1; j += 2)
 838                   for (s = 1; s <= 2; s++) {  int k;
 839                     for(k=1;; k++) {
 840                       rt = rf + k*i*s;
 841                       ft = ff + k*j*(3-s);
 842                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
 843                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 844                       callback(board, flags, NormalMove,
 845                                rf, ff, rt, ft, closure);
 846                       if (board[rt][ft] != EmptySquare) break;
 847                     }
 848                   }
 849               break;
 850
 851             Amazon:
 852                 Bishop(board, flags, rf, ff, callback, closure);
 853                 Rook(board, flags, rf, ff, callback, closure);
 854                 Knight(board, flags, rf, ff, callback, closure);
 855                 break;
 856
 857             // Use Lance as Berolina / Spartan Pawn.
 858             case WhiteLance:
 859               if(gameInfo.variant == VariantSuper) goto Amazon;
 860               if (rf < BOARD_HEIGHT-1 && BlackPiece(board[rf + 1][ff]))
 861                   callback(board, flags,
 862                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 863                            rf, ff, rf + 1, ff, closure);
 864               for (s = -1; s <= 1; s += 2) {
 865                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf + 1][ff + s] == EmptySquare)
 866                       callback(board, flags,
 867                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
 868                                rf, ff, rf + 1, ff + s, closure);
 869                   if (rf == 1 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[3][ff + 2*s] == EmptySquare )
 870                       callback(board, flags, NormalMove, rf, ff, 3, ff + 2*s, closure);
 871               }
 872               break;
 873
 874             case BlackLance:
 875               if(gameInfo.variant == VariantSuper) goto Amazon;
 876               if (rf > 0 && WhitePiece(board[rf - 1][ff]))
 877                   callback(board, flags,
 878                            rf <= promoRank ? BlackPromotion : NormalMove,
 879                            rf, ff, rf - 1, ff, closure);
 880               for (s = -1; s <= 1; s += 2) {
 881                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf - 1][ff + s] == EmptySquare)
 882                       callback(board, flags,
 883                                rf <= promoRank ? BlackPromotion : NormalMove,
 884                                rf, ff, rf - 1, ff + s, closure);
 885                   if (rf == BOARD_HEIGHT-2 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[rf-2][ff + 2*s] == EmptySquare )
 886                       callback(board, flags, NormalMove, rf, ff, rf-2, ff + 2*s, closure);
 887               }
 888             break;
 889
 890             case SHOGI WhiteNothing:
 891             case SHOGI BlackNothing:
 892             case SHOGI WhiteLion:
 893             case SHOGI BlackLion:
 894             case WhiteLion:
 895             case BlackLion:
 896               for(rt = rf - 2; rt <= rf + 2; rt++) for(ft = ff - 2; ft <= ff + 2; ft++) {
 897                 if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
 898                 if (!(ff == ft && rf == rt) && SameColor(board[rf][ff], board[rt][ft])) continue;
 899                 callback(board, flags, (rt-rf)*(rt-rf) + (ff-ft)*(ff-ft) < 3 && board[rt][ft] != EmptySquare ? FirstLeg : NormalMove,
 900                          rf, ff, rt, ft, closure);
 901               }
 902               break;
 903
 904             case SHOGI WhiteFalcon:
 905             case SHOGI BlackFalcon:
 906             case SHOGI WhitePDagger:
 907             case SHOGI BlackPDagger:
 908                 SlideSideways(board, flags, rf, ff, callback, closure);
 909                 StepVertical(board, flags, rf, ff, callback, closure);
 910                 break;
 911
 912             case SHOGI WhiteCobra:
 913             case SHOGI BlackCobra:
 914                 StepVertical(board, flags, rf, ff, callback, closure);
 915                 break;
 916
 917             case SHOGI (PROMOTED WhiteFerz):
 918                 if(gameInfo.variant == VariantShogi) goto WhiteGold;
 919             case SHOGI (PROMOTED BlackFerz):
 920                 if(gameInfo.variant == VariantShogi) goto BlackGold;
 921             case SHOGI WhitePSword:
 922             case SHOGI BlackPSword:
 923                 SlideVertical(board, flags, rf, ff, callback, closure);
 924                 StepSideways(board, flags, rf, ff, callback, closure);
 925                 break;
 926
 927             case SHOGI WhiteUnicorn:
 928             case SHOGI BlackUnicorn:
 929                 Ferz(board, flags, rf, ff, callback, closure);
 930                 StepVertical(board, flags, rf, ff, callback, closure);
 931                 break;
 932
 933             case SHOGI WhiteMan:
 934                 StepDiagForward(board, flags, rf, ff, callback, closure);
 935                 StepVertical(board, flags, rf, ff, callback, closure);
 936                 break;
 937
 938             case SHOGI BlackMan:
 939                 StepDiagBackward(board, flags, rf, ff, callback, closure);
 940                 StepVertical(board, flags, rf, ff, callback, closure);
 941                 break;
 942
 943             case SHOGI WhiteHCrown:
 944             case SHOGI BlackHCrown:
 945                 Bishop(board, flags, rf, ff, callback, closure);
 946                 SlideSideways(board, flags, rf, ff, callback, closure);
 947                 break;
 948
 949             case SHOGI WhiteCrown:
 950             case SHOGI BlackCrown:
 951                 Bishop(board, flags, rf, ff, callback, closure);
 952                 SlideVertical(board, flags, rf, ff, callback, closure);
 953                 break;
 954
 955             case SHOGI WhiteHorned:
 956                 Sting(board, flags, rf, ff, 1, 0, callback, closure);
 957                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 958                 if(killX >= 0) break;
 959                 Bishop(board, flags, rf, ff, callback, closure);
 960                 SlideSideways(board, flags, rf, ff, callback, closure);
 961                 SlideBackward(board, flags, rf, ff, callback, closure);
 962                 break;
 963
 964             case SHOGI BlackHorned:
 965                 Sting(board, flags, rf, ff, -1, 0, callback, closure);
 966                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 967                 if(killX >= 0) break;
 968                 Bishop(board, flags, rf, ff, callback, closure);
 969                 SlideSideways(board, flags, rf, ff, callback, closure);
 970                 SlideForward(board, flags, rf, ff, callback, closure);
 971                 break;
 972
 973             case SHOGI WhiteEagle:
 974                 Sting(board, flags, rf, ff, 1,  1, callback, closure);
 975                 Sting(board, flags, rf, ff, 1, -1, callback, closure);
 976                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 977                 if(killX >= 0) break;
 978                 Rook(board, flags, rf, ff, callback, closure);
 979                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
 980                 break;
 981
 982             case SHOGI BlackEagle:
 983                 Sting(board, flags, rf, ff, -1,  1, callback, closure);
 984                 Sting(board, flags, rf, ff, -1, -1, callback, closure);
 985                 callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
 986                 if(killX >= 0) break;
 987                 Rook(board, flags, rf, ff, callback, closure);
 988                 SlideDiagForward(board, flags, rf, ff, callback, closure);
 989                 break;
 990
 991             case SHOGI WhiteDolphin:
 992             case SHOGI BlackHorse:
 993                 SlideDiagBackward(board, flags, rf, ff, callback, closure);
 994                 SlideVertical(board, flags, rf, ff, callback, closure);
 995                 break;
 996
 997             case SHOGI BlackDolphin:
 998             case SHOGI WhiteHorse:
 999                 SlideDiagForward(board, flags, rf, ff, callback, closure);
1000                 SlideVertical(board, flags, rf, ff, callback, closure);
1001                 break;
1002
1003             case SHOGI WhiteLance:
1004                 SlideForward(board, flags, rf, ff, callback, closure);
1005                 break;
1006
1007             case SHOGI BlackLance:
1008                 SlideBackward(board, flags, rf, ff, callback, closure);
1009                 break;
1010
1011             case WhiteFalcon: // [HGM] wild: for wildcards, self-capture symbolizes move to anywhere
1012             case BlackFalcon:
1013             case WhiteCobra:
1014             case BlackCobra:
1015               callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
1016               break;
1017
1018           }
1019       }
1020 }
1021
1022
1023 typedef struct {
1024     MoveCallback cb;
1025     VOIDSTAR cl;
1026 } GenLegalClosure;
1027
1028 int rFilter, fFilter; // [HGM] speed: sorry, but I get a bit tired of this closure madness
1029 Board xqCheckers, nullBoard;
1030
1031 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
1032                                 int rf, int ff, int rt, int ft,
1033                                 VOIDSTAR closure));
1034
1035 void
1036 GenLegalCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1037 {
1038     register GenLegalClosure *cl = (GenLegalClosure *) closure;
1039
1040     if(rFilter >= 0 && rFilter != rt || fFilter >= 0 && fFilter != ft) return; // [HGM] speed: ignore moves with wrong to-square
1041
1042     if (board[EP_STATUS] == EP_IRON_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)) return; //[HGM] lion
1043
1044     if (!(flags & F_IGNORE_CHECK) ) {
1045       int check, promo = (gameInfo.variant == VariantSpartan && kind == BlackPromotion);
1046       if(promo) {
1047             int r, f, kings=0;
1048             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT;       f++)
1049                 kings += (board[r][f] == BlackKing);
1050             if(kings >= 2)
1051               promo = 0;
1052             else
1053                 board[rf][ff] = BlackKing; // [HGM] spartan: promote to King before check-test
1054         }
1055         check = CheckTest(board, flags, rf, ff, rt, ft,
1056                   kind == WhiteCapturesEnPassant ||
1057                   kind == BlackCapturesEnPassant);
1058         if(promo) board[rf][ff] = BlackLance;
1059       if(check) return;
1060     }
1061     if (flags & F_ATOMIC_CAPTURE) {
1062       if (board[rt][ft] != EmptySquare ||
1063           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
1064         int r, f;
1065         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
1066         if (board[rf][ff] == king) return;
1067         for (r = rt-1; r <= rt+1; r++) {
1068           for (f = ft-1; f <= ft+1; f++) {
1069             if (r >= 0 && r < BOARD_HEIGHT && f >= BOARD_LEFT && f < BOARD_RGHT &&
1070                 board[r][f] == king) return;
1071           }
1072         }
1073       }
1074     }
1075     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
1076 }
1077
1078
1079 typedef struct {
1080     int rf, ff, rt, ft;
1081     ChessMove kind;
1082     int captures; // [HGM] losers
1083 } LegalityTestClosure;
1084
1085
1086 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
1087    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
1088    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
1089    moves that would destroy your own king.  The CASTLE_OK flags are
1090    true if castling is not yet ruled out by a move of the king or
1091    rook.  Return TRUE if the player on move is currently in check and
1092    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
1093 int
1094 GenLegal (Board board, int  flags, MoveCallback callback, VOIDSTAR closure, ChessSquare filter)
1095 {
1096     GenLegalClosure cl;
1097     int ff, ft, k, left, right, swap;
1098     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
1099     ChessSquare wKing = WhiteKing, bKing = BlackKing, *castlingRights = board[CASTLING];
1100     int inCheck = !ignoreCheck && CheckTest(board, flags, -1, -1, -1, -1, FALSE); // kludge alert: this would mark pre-existing checkers if status==1
1101
1102     cl.cb = callback;
1103     cl.cl = closure;
1104     xqCheckers[EP_STATUS] *= 2; // quasi: if previous CheckTest has been marking, we now set flag for suspending same checkers
1105     if(filter == EmptySquare) rFilter = fFilter = -1; // [HGM] speed: do not filter on square if we do not filter on piece
1106     GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl, filter);
1107
1108     if (inCheck) return TRUE;
1109
1110     /* Generate castling moves */
1111     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
1112         wKing = WhiteUnicorn; bKing = BlackUnicorn;
1113     }
1114
1115     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
1116         if ((flags & F_WHITE_ON_MOVE) &&
1117             (flags & F_WHITE_KCASTLE_OK) &&
1118             board[0][ff] == wKing &&
1119             board[0][ff + 1] == EmptySquare &&
1120             board[0][ff + 2] == EmptySquare &&
1121             board[0][BOARD_RGHT-3] == EmptySquare &&
1122             board[0][BOARD_RGHT-2] == EmptySquare &&
1123             board[0][BOARD_RGHT-1] == WhiteRook &&
1124             castlingRights[0] != NoRights && /* [HGM] check rights */
1125             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1126             (ignoreCheck ||
1127              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
1128               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
1129               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
1130               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
1131
1132             callback(board, flags,
1133                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
1134                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1135         }
1136         if ((flags & F_WHITE_ON_MOVE) &&
1137             (flags & F_WHITE_QCASTLE_OK) &&
1138             board[0][ff] == wKing &&
1139             board[0][ff - 1] == EmptySquare &&
1140             board[0][ff - 2] == EmptySquare &&
1141             board[0][BOARD_LEFT+2] == EmptySquare &&
1142             board[0][BOARD_LEFT+1] == EmptySquare &&
1143             board[0][BOARD_LEFT+0] == WhiteRook &&
1144             castlingRights[1] != NoRights && /* [HGM] check rights */
1145             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
1146             (ignoreCheck ||
1147              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
1148               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
1149               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
1150
1151             callback(board, flags,
1152                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
1153                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
1154         }
1155         if (!(flags & F_WHITE_ON_MOVE) &&
1156             (flags & F_BLACK_KCASTLE_OK) &&
1157             board[BOARD_HEIGHT-1][ff] == bKing &&
1158             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
1159             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
1160             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
1161             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
1162             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
1163             castlingRights[3] != NoRights && /* [HGM] check rights */
1164             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1165             (ignoreCheck ||
1166              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
1167               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
1168               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
1169               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
1170
1171             callback(board, flags,
1172                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
1173                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
1174         }
1175         if (!(flags & F_WHITE_ON_MOVE) &&
1176             (flags & F_BLACK_QCASTLE_OK) &&
1177             board[BOARD_HEIGHT-1][ff] == bKing &&
1178             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
1179             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
1180             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
1181             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
1182             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
1183             castlingRights[4] != NoRights && /* [HGM] check rights */
1184             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
1185             (ignoreCheck ||
1186              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
1187               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
1188               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
1189
1190             callback(board, flags,
1191                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
1192                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
1193         }
1194     }
1195
1196   if((swap = gameInfo.variant == VariantSChess) || flags & F_FRC_TYPE_CASTLING) {
1197
1198     /* generate all potential FRC castling moves (KxR), ignoring flags */
1199     /* [HGM] test if the Rooks we find have castling rights */
1200     /* In S-Chess we generate RxK for allowed castlings, for gating at Rook square */
1201
1202
1203     if ((flags & F_WHITE_ON_MOVE) != 0) {
1204         ff = castlingRights[2]; /* King file if we have any rights */
1205         if(ff != NoRights && board[0][ff] == WhiteKing) {
1206     if (appData.debugMode) {
1207         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
1208                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
1209     }
1210             ft = castlingRights[0]; /* Rook file if we have H-side rights */
1211             left  = ff+1;
1212             right = BOARD_RGHT-2;
1213             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1214             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1215                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1216             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1217                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1218             if(ft != NoRights && board[0][ft] == WhiteRook)
1219                 callback(board, flags, WhiteHSideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
1220
1221             ft = castlingRights[1]; /* Rook file if we have A-side rights */
1222             left  = BOARD_LEFT+2;
1223             right = ff-1;
1224             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1225             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1226                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
1227             if(ff > BOARD_LEFT+2)
1228             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1229                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
1230             if(ft != NoRights && board[0][ft] == WhiteRook)
1231                 callback(board, flags, WhiteASideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
1232         }
1233     } else {
1234         ff = castlingRights[5]; /* King file if we have any rights */
1235         if(ff != NoRights && board[BOARD_HEIGHT-1][ff] == BlackKing) {
1236             ft = castlingRights[3]; /* Rook file if we have H-side rights */
1237             left  = ff+1;
1238             right = BOARD_RGHT-2;
1239             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
1240             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1241                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1242             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
1243                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1244             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
1245                 callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
1246
1247             ft = castlingRights[4]; /* Rook file if we have A-side rights */
1248             left  = BOARD_LEFT+2;
1249             right = ff-1;
1250             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
1251             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
1252                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
1253             if(ff > BOARD_LEFT+2)
1254             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
1255                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
1256             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
1257                 callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
1258         }
1259     }
1260
1261   }
1262
1263     return FALSE;
1264 }
1265
1266
1267 typedef struct {
1268     int rking, fking;
1269     int check;
1270 } CheckTestClosure;
1271
1272
1273 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
1274                                  int rf, int ff, int rt, int ft,
1275                                  VOIDSTAR closure));
1276
1277
1278 void
1279 CheckTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1280 {
1281     register CheckTestClosure *cl = (CheckTestClosure *) closure;
1282
1283     if (rt == cl->rking && ft == cl->fking) {
1284         if(xqCheckers[EP_STATUS] >= 2 && xqCheckers[rf][ff]) return; // checker is piece with suspended checking power
1285         cl->check++;
1286         xqCheckers[rf][ff] = xqCheckers[EP_STATUS] & 1; // remember who is checking (if status == 1)
1287     }
1288     if( board[EP_STATUS] == EP_ROYAL_LION && (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion)
1289         && (gameInfo.variant != VariantLion || board[rf][ff] != WhiteKing && board[rf][ff] != BlackKing) )
1290         cl->check++; // [HGM] lion: forbidden counterstrike against Lion equated to putting yourself in check
1291 }
1292
1293
1294 /* If the player on move were to move from (rf, ff) to (rt, ft), would
1295    he leave himself in check?  Or if rf == -1, is the player on move
1296    in check now?  enPassant must be TRUE if the indicated move is an
1297    e.p. capture.  The possibility of castling out of a check along the
1298    back rank is not accounted for (i.e., we still return nonzero), as
1299    this is illegal anyway.  Return value is the number of times the
1300    king is in check. */
1301 int
1302 CheckTest (Board board, int flags, int rf, int ff, int rt, int ft, int enPassant)
1303 {
1304     CheckTestClosure cl;
1305     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1306     ChessSquare captured = EmptySquare, ep, trampled;
1307     /*  Suppress warnings on uninitialized variables    */
1308
1309     if(gameInfo.variant == VariantXiangqi)
1310         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
1311     if(gameInfo.variant == VariantKnightmate)
1312         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
1313
1314     if (rt >= 0) {
1315         if (enPassant) {
1316             captured = board[rf][ft];
1317             board[rf][ft] = EmptySquare;
1318         } else {
1319             captured = board[rt][ft];
1320             if(killX >= 0) { trampled = board[killY][killX]; board[killY][killX] = EmptySquare; }
1321         }
1322         if(rf == DROP_RANK) board[rt][ft] = ff; else { // [HGM] drop
1323             board[rt][ft] = board[rf][ff];
1324             board[rf][ff] = EmptySquare;
1325         }
1326         ep = board[EP_STATUS];
1327         if( captured == WhiteLion || captured == BlackLion ) { // [HGM] lion: Chu Lion-capture rules
1328             ChessSquare victim = killX < 0 ? EmptySquare : trampled;
1329             if( (board[rt][ft] == WhiteLion || board[rt][ft] == BlackLion) &&           // capturer is Lion
1330                 (ff - ft > 1 || ft - ff > 1 || rf - rt > 1 || rt - rf > 1) &&           // captures from a distance
1331                 (victim == EmptySquare || victim == WhitePawn || victim == BlackPawn) ) // no or worthless 'bridge'
1332                      board[EP_STATUS] = EP_ROYAL_LION; // on distant Lion x Lion victim must not be pseudo-legally protected
1333         }
1334     }
1335
1336     /* For compatibility with ICS wild 9, we scan the board in the
1337        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1338        and we test only whether that one is in check. */
1339     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1340         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1341           if (board[cl.rking][cl.fking] == king) {
1342               cl.check = 0;
1343               if(gameInfo.variant == VariantXiangqi) {
1344                   /* [HGM] In Xiangqi opposing Kings means check as well */
1345                   int i, dir;
1346                   dir = (king >= BlackPawn) ? -1 : 1;
1347                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1348                                 board[i][cl.fking] == EmptySquare; i+=dir );
1349                   if(i>=0 && i<BOARD_HEIGHT &&
1350                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1351                           cl.check++;
1352               }
1353               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1354               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1355                  goto undo_move;  /* 2-level break */
1356           }
1357       }
1358
1359   undo_move:
1360
1361     if (rt >= 0) {
1362         if(rf != DROP_RANK) // [HGM] drop
1363             board[rf][ff] = board[rt][ft];
1364         if (enPassant) {
1365             board[rf][ft] = captured;
1366             board[rt][ft] = EmptySquare;
1367         } else {
1368             if(killX >= 0) board[killY][killX] = trampled;
1369             board[rt][ft] = captured;
1370         }
1371         board[EP_STATUS] = ep;
1372     }
1373
1374     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1375 }
1376
1377 int
1378 HasLion (Board board, int flags)
1379 {
1380     int lion = F_WHITE_ON_MOVE & flags ? WhiteLion : BlackLion;
1381     int r, f;
1382     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1383         if(board[r][f] == lion) return 1;
1384     return 0;
1385 }
1386
1387 ChessMove
1388 LegalDrop (Board board, int flags, ChessSquare piece, int rt, int ft)
1389 {   // [HGM] put drop legality testing in separate routine for clarity
1390     int n;
1391 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1392     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1393     n = PieceToNumber(piece);
1394     if((gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1395         && gameInfo.variant != VariantBughouse) // in bughouse we don't check for availability, because ICS doesn't always tell us
1396         return ImpossibleMove; // piece not available
1397     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1398         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1399            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1400             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1401             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1402         if(piece == WhitePawn || piece == BlackPawn) {
1403             int r;
1404             for(r=1; r<BOARD_HEIGHT-1; r++)
1405                 if(board[r][ft] == piece) return IllegalMove; // or there already is a Pawn in file
1406             // should still test if we mate with this Pawn
1407         }
1408     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1409         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1410     } else {
1411         if( (piece == WhitePawn || piece == BlackPawn) &&
1412             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1413             return IllegalMove; /* no pawn drops on 1st/8th */
1414     }
1415 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1416     if (!(flags & F_IGNORE_CHECK) &&
1417         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1418     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1419 }
1420
1421 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1422                                     int rf, int ff, int rt, int ft,
1423                                     VOIDSTAR closure));
1424
1425 void
1426 LegalityTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1427 {
1428     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1429
1430     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1431         cl->captures++; // [HGM] losers: count legal captures
1432     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1433       cl->kind = kind;
1434 }
1435
1436 ChessMove
1437 LegalityTest (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar)
1438 {
1439     LegalityTestClosure cl; ChessSquare piece, filterPiece;
1440
1441     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1442     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1443     piece = filterPiece = board[rf][ff];
1444     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece;
1445
1446     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1447     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1448     if(piece == WhiteFalcon || piece == BlackFalcon ||
1449        piece == WhiteCobra  || piece == BlackCobra)
1450         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1451
1452     cl.rf = rf;
1453     cl.ff = ff;
1454     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1455     cl.ft = fFilter = ft;
1456     cl.kind = IllegalMove;
1457     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1458     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1459     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1460     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1461                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1462         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1463
1464     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1465     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1466         if(board[rf][ff] < BlackPawn) { // white
1467             if(rf != 0) return IllegalMove; // must be on back rank
1468             if(!(board[VIRGIN][ff] & VIRGIN_W)) return IllegalMove; // non-virgin
1469             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1470         } else {
1471             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1472             if(!(board[VIRGIN][ff] & VIRGIN_B)) return IllegalMove; // non-virgin
1473             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1474         }
1475     } else
1476     if(gameInfo.variant == VariantChu) {
1477         if(cl.kind != NormalMove || promoChar == NULLCHAR || promoChar == '=') return cl.kind;
1478         if(promoChar != '+')
1479             return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1480         if(PieceToChar(CHUPROMOTED board[rf][ff]) != '+') return ImpossibleMove;
1481         return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1482     } else
1483     if(gameInfo.variant == VariantShogi) {
1484         /* [HGM] Shogi promotions. '=' means defer */
1485         if(rf != DROP_RANK && cl.kind == NormalMove) {
1486             ChessSquare piece = board[rf][ff];
1487
1488             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1489             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1490                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1491                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1492                   promoChar = '+'; // allowed ICS notations
1493 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1494             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1495                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1496             else if(flags & F_WHITE_ON_MOVE) {
1497                 if( (int) piece < (int) WhiteWazir &&
1498                      (rf >= BOARD_HEIGHT - BOARD_HEIGHT/3 || rt >= BOARD_HEIGHT - BOARD_HEIGHT/3) ) {
1499                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1500                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1501                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1502                     else /* promotion optional, default is defer */
1503                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1504                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1505             } else {
1506                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1507                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1508                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1509                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1510                     else /* promotion optional, default is defer */
1511                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1512                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1513             }
1514         }
1515     } else
1516     if (promoChar != NULLCHAR) {
1517         if(cl.kind == NormalMove && promoChar == '+') { // allow shogi-style promotion is pieceToChar specifies them
1518             ChessSquare piece = board[rf][ff];
1519             if(piece < BlackPawn ? piece > WhiteMan : piece > BlackMan) return ImpossibleMove; // already promoted
1520             // should test if in zone, really
1521             if(gameInfo.variant == VariantChuChess && (piece == WhiteKnight || piece == BlackKnight) && HasLion(board, flags))
1522                 return IllegalMove;
1523             if(PieceToChar(PROMOTED piece) == '+') return flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion;
1524         } else
1525         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1526         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1527             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1528             if(piece == EmptySquare)
1529                 cl.kind = ImpossibleMove; // non-existing piece
1530             if(gameInfo.variant == VariantChuChess && promoChar == 'l' && HasLion(board, flags)) {
1531                 cl.kind = IllegalMove; // no two Lions
1532             } else if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1533                 if(promoChar != PieceToChar(BlackKing)) {
1534                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1535                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1536                 } else { // promotion to King allowed only if we do not have two yet
1537                     int r, f, kings = 0;
1538                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1539                     if(kings == 2) cl.kind = IllegalMove;
1540                 }
1541             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1542                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1543             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1544              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1545             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1546              cl.kind = IllegalMove; // promotion to King usually not allowed
1547         } else {
1548             cl.kind = IllegalMove;
1549         }
1550     }
1551     return cl.kind;
1552 }
1553
1554 typedef struct {
1555     int count;
1556 } MateTestClosure;
1557
1558 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1559                                 int rf, int ff, int rt, int ft,
1560                                 VOIDSTAR closure));
1561
1562 void
1563 MateTestCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1564 {
1565     register MateTestClosure *cl = (MateTestClosure *) closure;
1566
1567     cl->count++;
1568 }
1569
1570 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1571 int
1572 MateTest (Board board, int flags)
1573 {
1574     MateTestClosure cl;
1575     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1576     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1577
1578     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1579         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1580         nrKing += (board[r][f] == king);   // stm has king
1581         if( board[r][f] != EmptySquare ) {
1582             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1583                  myPieces++;
1584             else hisPieces++;
1585         }
1586     }
1587     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1588         case VariantShatranj:
1589                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1590         default:
1591                 break;
1592         case VariantAtomic:
1593                 if(nrKing == 0) return MT_NOKING;
1594                 break;
1595         case VariantLosers:
1596                 if(myPieces == 1) return MT_BARE;
1597     }
1598     cl.count = 0;
1599     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1600     // [HGM] 3check: yet to do!
1601     if (cl.count > 0) {
1602         return inCheck ? MT_CHECK : MT_NONE;
1603     } else {
1604         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1605                                  && gameInfo.variant != VariantSChess && gameInfo.variant != VariantGrand) { // drop game
1606             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1607             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1608                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1609                     if(board[n][holdings] != EmptySquare) {
1610                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1611                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1612                     }
1613         }
1614         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1615                 return myPieces == hisPieces ? MT_STALEMATE :
1616                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1617         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1618         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1619
1620         return inCheck ? MT_CHECKMATE
1621                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj || gameInfo.variant == VariantShogi) ?
1622                           MT_STAINMATE : MT_STALEMATE;
1623     }
1624 }
1625
1626
1627 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1628                                     int rf, int ff, int rt, int ft,
1629                                     VOIDSTAR closure));
1630
1631 void
1632 DisambiguateCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1633 {
1634     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1635     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1636
1637     // [HGM] wild: for wild-card pieces rt and rf are dummies
1638     if(piece == WhiteFalcon || piece == BlackFalcon ||
1639        piece == WhiteCobra  || piece == BlackCobra)
1640         wildCard = TRUE;
1641
1642     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1643          || PieceToChar(board[rf][ff]) == '~'
1644               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1645                                                                       ) &&
1646         (cl->rfIn == -1 || cl->rfIn == rf) &&
1647         (cl->ffIn == -1 || cl->ffIn == ff) &&
1648         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1649         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1650
1651         cl->count++;
1652         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1653           // [HGM] oneclick: if multiple moves, be sure we remember capture
1654           cl->piece = board[rf][ff];
1655           cl->rf = rf;
1656           cl->ff = ff;
1657           cl->rt = wildCard ? cl->rtIn : rt;
1658           cl->ft = wildCard ? cl->ftIn : ft;
1659           cl->kind = kind;
1660         }
1661         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1662     }
1663 }
1664
1665 void
1666 Disambiguate (Board board, int flags, DisambiguateClosure *closure)
1667 {
1668     int illegal = 0; char c = closure->promoCharIn;
1669
1670     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1671     closure->count = closure->captures = 0;
1672     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1673     closure->kind = ImpossibleMove;
1674     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
1675     fFilter = closure->ftIn;
1676     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
1677         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1678         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
1679             closure->count = closure->captures = 0;
1680             closure->rf = closure->ff = closure->rt = closure->ft = 0;
1681             closure->kind = ImpossibleMove;
1682             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1683         }
1684     } else
1685     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1686     if (closure->count == 0) {
1687         /* See if it's an illegal move due to check */
1688         illegal = 1;
1689         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1690         if (closure->count == 0) {
1691             /* No, it's not even that */
1692           if(!appData.testLegality && closure->pieceIn != EmptySquare) {
1693             int f, r; // if there is only a single piece of the requested type on the board, use that
1694             closure->rt = closure->rtIn, closure->ft = closure->ftIn;
1695             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++)
1696                 if(board[r][f] == closure->pieceIn) closure->count++, closure->rf = r, closure->ff = f;
1697             if(closure->count > 1) illegal = 0; // ambiguous
1698           }
1699           if(closure->count == 0) {
1700             if (appData.debugMode) { int i, j;
1701                 for(i=BOARD_HEIGHT-1; i>=0; i--) {
1702                     for(j=0; j<BOARD_WIDTH; j++)
1703                         fprintf(debugFP, "%3d", (int) board[i][j]);
1704                     fprintf(debugFP, "\n");
1705                 }
1706             }
1707             return;
1708           }
1709         }
1710     }
1711
1712     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1713     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
1714         if(closure->piece < BlackPawn) { // white
1715             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
1716             if(!(board[VIRGIN][closure->ff] & VIRGIN_W)) closure->kind = IllegalMove; // non-virgin
1717             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
1718         } else {
1719             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
1720             if(!(board[VIRGIN][closure->ff] & VIRGIN_B)) closure->kind = IllegalMove; // non-virgin
1721             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
1722         }
1723     } else
1724     if(gameInfo.variant == VariantChu) {
1725         if(c == '+') closure->kind = (flags & F_WHITE_ON_MOVE ? WhitePromotion : BlackPromotion); // for now, accept any
1726     } else
1727     if(gameInfo.variant == VariantShogi) {
1728         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1729         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1730             ChessSquare piece = closure->piece;
1731             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1732                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1733                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1734                    c = '+'; // allowed ICS notations
1735             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1736             else if(flags & F_WHITE_ON_MOVE) {
1737                 if( (int) piece < (int) WhiteWazir &&
1738                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1739                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1740                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1741                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1742                     else /* promotion optional, default is defer */
1743                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion;
1744                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1745             } else {
1746                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1747                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1748                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1749                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1750                     else /* promotion optional, default is defer */
1751                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1752                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1753             }
1754         }
1755         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1756         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1757     } else
1758     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1759         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1760             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier ||
1761                gameInfo.variant == VariantMakruk || gameInfo.variant == VariantASEAN)
1762                 c = PieceToChar(BlackFerz);
1763             else if(gameInfo.variant == VariantGreat)
1764                 c = PieceToChar(BlackMan);
1765             else if(gameInfo.variant == VariantGrand)
1766                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
1767             else
1768                 c = PieceToChar(BlackQueen);
1769         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1770         else if(c == 'l' && gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
1771     } else if (c == '+') { // '+' outside shogi, check if pieceToCharTable enabled it
1772         ChessSquare p = closure->piece;
1773         if(p > WhiteMan && p < BlackPawn || p > BlackMan || PieceToChar(PROMOTED p) != '+')
1774             closure->kind = ImpossibleMove; // used on non-promotable piece
1775         else if(gameInfo.variant == VariantChuChess && HasLion(board, flags)) closure->kind = IllegalMove;
1776     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1777
1778     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1779     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1780         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1781     if (closure->count > 1) {
1782         closure->kind = AmbiguousMove;
1783     }
1784     if (illegal) {
1785         /* Note: If more than one illegal move matches, but no legal
1786            moves, we return IllegalMove, not AmbiguousMove.  Caller
1787            can look at closure->count to detect this.
1788         */
1789         closure->kind = IllegalMove;
1790     }
1791 }
1792
1793
1794 typedef struct {
1795     /* Input */
1796     ChessSquare piece;
1797     int rf, ff, rt, ft;
1798     /* Output */
1799     ChessMove kind;
1800     int rank;
1801     int file;
1802     int either;
1803 } CoordsToAlgebraicClosure;
1804
1805 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1806                                          ChessMove kind, int rf, int ff,
1807                                          int rt, int ft, VOIDSTAR closure));
1808
1809 void
1810 CoordsToAlgebraicCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
1811 {
1812     register CoordsToAlgebraicClosure *cl =
1813       (CoordsToAlgebraicClosure *) closure;
1814
1815     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
1816         (board[rf][ff] == cl->piece
1817          || PieceToChar(board[rf][ff]) == '~' &&
1818             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1819                                      ) {
1820         if (rf == cl->rf) {
1821             if (ff == cl->ff) {
1822                 cl->kind = kind; /* this is the move we want */
1823             } else {
1824                 cl->file++; /* need file to rule out this move */
1825             }
1826         } else {
1827             if (ff == cl->ff) {
1828                 cl->rank++; /* need rank to rule out this move */
1829             } else {
1830                 cl->either++; /* rank or file will rule out this move */
1831             }
1832         }
1833     }
1834 }
1835
1836 /* Convert coordinates to normal algebraic notation.
1837    promoChar must be NULLCHAR or 'x' if not a promotion.
1838 */
1839 ChessMove
1840 CoordsToAlgebraic (Board board, int flags, int rf, int ff, int rt, int ft, int promoChar, char out[MOVE_LEN])
1841 {
1842     ChessSquare piece;
1843     ChessMove kind;
1844     char *outp = out, c;
1845     CoordsToAlgebraicClosure cl;
1846
1847     if (rf == DROP_RANK) {
1848         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
1849         /* Bughouse piece drop */
1850         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1851         *outp++ = '@';
1852         *outp++ = ft + AAA;
1853         if(rt+ONE <= '9')
1854            *outp++ = rt + ONE;
1855         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1856         *outp = NULLCHAR;
1857         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1858     }
1859
1860     if (promoChar == 'x') promoChar = NULLCHAR;
1861     piece = board[rf][ff];
1862     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1863
1864     switch (piece) {
1865       case WhitePawn:
1866       case BlackPawn:
1867         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1868         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1869             /* Keep short notation if move is illegal only because it
1870                leaves the player in check, but still return IllegalMove */
1871             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1872             if (kind == IllegalMove) break;
1873             kind = IllegalMove;
1874         }
1875         /* Pawn move */
1876         *outp++ = ff + AAA;
1877         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1878             /* Non-capture; use style "e5" */
1879             if(rt+ONE <= '9')
1880                *outp++ = rt + ONE;
1881             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1882         } else {
1883             /* Capture; use style "exd5" */
1884             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1885             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1886             *outp++ = ft + AAA;
1887             if(rt+ONE <= '9')
1888                *outp++ = rt + ONE;
1889             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1890         }
1891         /* Use promotion suffix style "=Q" */
1892         *outp = NULLCHAR;
1893         if (promoChar != NULLCHAR) {
1894             if(IS_SHOGI(gameInfo.variant)) {
1895                 /* [HGM] ... but not in Shogi! */
1896                 *outp++ = promoChar == '=' ? '=' : '+';
1897             } else {
1898                 *outp++ = '=';
1899                 *outp++ = ToUpper(promoChar);
1900             }
1901             *outp = NULLCHAR;
1902         }
1903         return kind;
1904
1905
1906       case WhiteKing:
1907       case BlackKing:
1908         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1909         /* Code added by Tord:  FRC castling. */
1910         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1911            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1912           if(ft > ff)
1913             safeStrCpy(out, "O-O", MOVE_LEN);
1914           else
1915             safeStrCpy(out, "O-O-O", MOVE_LEN);
1916           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1917         }
1918         /* End of code added by Tord */
1919         /* Test for castling or ICS wild castling */
1920         /* Use style "O-O" (oh-oh) for PGN compatibility */
1921         else if (rf == rt &&
1922             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1923             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1924             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1925              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1926             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1927               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1928             else
1929               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1930
1931             /* This notation is always unambiguous, unless there are
1932                kings on both the d and e files, with "wild castling"
1933                possible for the king on the d file and normal castling
1934                possible for the other.  ICS rules for wild 9
1935                effectively make castling illegal for either king in
1936                this situation.  So I am not going to worry about it;
1937                I'll just generate an ambiguous O-O in this case.
1938             */
1939             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1940         }
1941
1942         /* else fall through */
1943       default:
1944         /* Piece move */
1945         cl.rf = rf;
1946         cl.ff = ff;
1947         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1948         cl.ft = fFilter = ft;
1949         cl.piece = piece;
1950         cl.kind = IllegalMove;
1951         cl.rank = cl.file = cl.either = 0;
1952         c = PieceToChar(piece) ;
1953         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
1954
1955         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1956             /* Generate pretty moves for moving into check, but
1957                still return IllegalMove.
1958             */
1959             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
1960             if (cl.kind == IllegalMove) break;
1961             cl.kind = IllegalMove;
1962         }
1963
1964         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1965            else "Ngf3" or "Ngxf7",
1966            else "N1f3" or "N5xf7",
1967            else "Ng1f3" or "Ng5xf7".
1968         */
1969         if( c == '~' || c == '+') {
1970            /* [HGM] print nonexistent piece as its demoted version */
1971            piece = (ChessSquare) (DEMOTED piece - 11*(gameInfo.variant == VariantChu));
1972         }
1973         if(c=='+') *outp++ = c;
1974         *outp++ = ToUpper(PieceToChar(piece));
1975
1976         if (cl.file || (cl.either && !cl.rank)) {
1977             *outp++ = ff + AAA;
1978         }
1979         if (cl.rank) {
1980             if(rf+ONE <= '9')
1981                 *outp++ = rf + ONE;
1982             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1983         }
1984
1985         if(board[rt][ft] != EmptySquare)
1986           *outp++ = 'x';
1987
1988         *outp++ = ft + AAA;
1989         if(rt+ONE <= '9')
1990            *outp++ = rt + ONE;
1991         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1992         if (IS_SHOGI(gameInfo.variant)) {
1993             /* [HGM] in Shogi non-pawns can promote */
1994             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1995         }
1996         else if (gameInfo.variant == VariantChuChess && promoChar ||
1997                  gameInfo.variant != VariantSuper && promoChar &&
1998                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
1999             *outp++ = '=';
2000             *outp++ = ToUpper(promoChar);
2001         }
2002         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
2003             *outp++ = '/';
2004             *outp++ = ToUpper(promoChar);
2005         }
2006         *outp = NULLCHAR;
2007         return cl.kind;
2008
2009       case EmptySquare:
2010         /* Moving a nonexistent piece */
2011         break;
2012     }
2013
2014     /* Not a legal move, even ignoring check.
2015        If there was a piece on the from square,
2016        use style "Ng1g3" or "Ng1xe8";
2017        if there was a pawn or nothing (!),
2018        use style "g1g3" or "g1xe8".  Use "x"
2019        if a piece was on the to square, even
2020        a piece of the same color.
2021     */
2022     outp = out;
2023     c = 0;
2024     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
2025         int r, f;
2026       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
2027                 c += (board[r][f] == piece); // count on-board pieces of given type
2028         *outp++ = ToUpper(PieceToChar(piece));
2029     }
2030   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
2031     *outp++ = ff + AAA;
2032     if(rf+ONE <= '9')
2033        *outp++ = rf + ONE;
2034     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
2035   }
2036     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
2037     *outp++ = ft + AAA;
2038     if(rt+ONE <= '9')
2039        *outp++ = rt + ONE;
2040     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
2041     /* Use promotion suffix style "=Q" */
2042     if (promoChar != NULLCHAR && promoChar != 'x') {
2043         *outp++ = '=';
2044         *outp++ = ToUpper(promoChar);
2045     }
2046     *outp = NULLCHAR;
2047
2048     return IllegalMove;
2049 }
2050
2051 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
2052
2053 typedef struct {
2054     /* Input */
2055     int rf, ff, rt, ft;
2056     /* Output */
2057     int recaptures;
2058 } ChaseClosure;
2059
2060 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
2061
2062 int preyStackPointer, chaseStackPointer;
2063
2064 struct {
2065 unsigned char rf, ff, rt, ft;
2066 } chaseStack[100];
2067
2068 struct {
2069 unsigned char rank, file;
2070 } preyStack[100];
2071
2072
2073
2074
2075 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
2076
2077 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
2078                                 int rf, int ff, int rt, int ft,
2079                                 VOIDSTAR closure));
2080
2081 void
2082 AttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2083 {   // For adding captures that can lead to chase indictment to the chaseStack
2084     if(board[rt][ft] == EmptySquare) return;                               // non-capture
2085     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2086     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
2087     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
2088     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
2089     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
2090     chaseStack[chaseStackPointer].rf = rf;
2091     chaseStack[chaseStackPointer].ff = ff;
2092     chaseStack[chaseStackPointer].rt = rt;
2093     chaseStack[chaseStackPointer].ft = ft;
2094     chaseStackPointer++;
2095 }
2096
2097 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
2098                                 int rf, int ff, int rt, int ft,
2099                                 VOIDSTAR closure));
2100
2101 void
2102 ExistingAttacksCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2103 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
2104     int i;
2105     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
2106
2107     if(board[rt][ft] == EmptySquare) return; // no capture
2108     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
2109         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
2110     }
2111     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
2112     for(i=0; i<chaseStackPointer; i++) {
2113         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
2114            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
2115             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
2116             chaseStack[i] = chaseStack[--chaseStackPointer];
2117             break;
2118         }
2119     }
2120 }
2121
2122 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
2123                                 int rf, int ff, int rt, int ft,
2124                                 VOIDSTAR closure));
2125
2126 void
2127 ProtectedCallback (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)
2128 {   // for determining if a piece (given through the closure) is protected
2129     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
2130
2131     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
2132     if(appData.debugMode && board[rt][ft] != EmptySquare)
2133         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
2134 }
2135
2136 extern char moveList[MAX_MOVES][MOVE_LEN];
2137
2138 int
2139 PerpetualChase (int first, int last)
2140 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
2141     int i, j, k, tail;
2142     ChaseClosure cl;
2143     ChessSquare captured;
2144
2145     preyStackPointer = 0;        // clear stack of chased pieces
2146     for(i=first; i<last; i+=2) { // for all positions with same side to move
2147         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
2148         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
2149         // determine all captures possible after the move, and put them on chaseStack
2150         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
2151         if(appData.debugMode) { int n;
2152             for(n=0; n<chaseStackPointer; n++)
2153                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2154                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2155             fprintf(debugFP, ": all capts\n");
2156         }
2157         // determine all captures possible before the move, and delete them from chaseStack
2158         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
2159         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
2160         cl.rt = moveList[i][3]-ONE;
2161         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
2162         CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1; // giant kludge to make GenLegal ignore pre-existing checks
2163         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
2164         xqCheckers[EP_STATUS] = 0; // disable the generation of quasi-legal moves again
2165         if(appData.debugMode) { int n;
2166             for(n=0; n<chaseStackPointer; n++)
2167                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2168                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2169             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
2170         }
2171         // chaseSack now contains all captures made possible by the move
2172         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
2173             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2174             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2175
2176             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
2177             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
2178
2179             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
2180                 continue; // C or H attack on R is always chase; leave on chaseStack
2181
2182             if(attacker == victim) {
2183                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
2184                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
2185                         // we can capture back with equal piece, so this is no chase but a sacrifice
2186                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
2187                         j--; /* ! */ continue;
2188                 }
2189
2190             }
2191
2192             // the attack is on a lower piece, or on a pinned or blocked equal one
2193             CopyBoard(xqCheckers, nullBoard); xqCheckers[EP_STATUS] = 1;
2194             CheckTest(boards[i+1], PosFlags(i+1), -1, -1, -1, -1, FALSE); // if we deliver check with our move, the checkers get marked
2195             // test if the victim is protected by a true protector. First make the capture.
2196             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2197             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
2198             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
2199             // Then test if the opponent can recapture
2200             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
2201             cl.rt = chaseStack[j].rt;
2202             cl.ft = chaseStack[j].ft;
2203             if(appData.debugMode) {
2204                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
2205             }
2206             xqCheckers[EP_STATUS] = 2; // causes GenLegal to ignore the checks we delivered with the move, in real life evaded before we captured
2207             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
2208             xqCheckers[EP_STATUS] = 0; // disable quasi-legal moves again
2209             // unmake the capture
2210             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
2211             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
2212             // if a recapture was found, piece is protected, and we are not chasing it.
2213             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
2214                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
2215                 j--; /* ! */
2216             }
2217         }
2218         // chaseStack now contains all moves that chased
2219         if(appData.debugMode) { int n;
2220             for(n=0; n<chaseStackPointer; n++)
2221                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
2222                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
2223             fprintf(debugFP, ": chases\n");
2224         }
2225         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
2226             for(j=0; j<chaseStackPointer; j++) {
2227                 preyStack[j].rank = chaseStack[j].rt;
2228                 preyStack[j].file = chaseStack[j].ft;
2229             }
2230             preyStackPointer = chaseStackPointer;
2231         }
2232         tail = 0;
2233         for(j=0; j<chaseStackPointer; j++) {
2234             for(k=0; k<preyStackPointer; k++) {
2235                 // search the victim of each chase move on the preyStack (first occurrence)
2236                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
2237                     if(k < tail) break; // piece was already identified as still being chased
2238                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
2239                     preyStack[tail] = preyStack[k];                // by swapping
2240                     preyStack[k] = preyStack[preyStackPointer];
2241                     tail++;
2242                     break;
2243                 }
2244             }
2245         }
2246         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
2247         if(appData.debugMode) { int n;
2248             for(n=0; n<preyStackPointer; n++)
2249                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
2250             fprintf(debugFP, "always chased upto ply %d\n", i);
2251         }
2252         // now adjust the location of the chased pieces according to opponent move
2253         for(j=0; j<preyStackPointer; j++) {
2254             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
2255                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
2256                 preyStack[j].rank = moveList[i+1][3]-ONE;
2257                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
2258                 break;
2259             }
2260         }
2261     }
2262     return preyStackPointer ? 256*(preyStack[preyStackPointer].file - BOARD_LEFT + AAA) + (preyStack[preyStackPointer].rank + ONE)
2263                                 : 0; // if any piece was left on preyStack, it has been perpetually chased,and we return the
2264 }