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