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