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