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