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