a8f55b6c1c928a795a4aafc94367b07f4f609455
[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 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 #if HAVE_STRING_H
58 # include <string.h>
59 #else /* not HAVE_STRING_H */
60 # include <strings.h>
61 #endif /* not HAVE_STRING_H */
62 #include "common.h"
63 #include "backend.h"
64 #include "moves.h"
65 #include "parser.h"
66
67 int WhitePiece P((ChessSquare));
68 int BlackPiece P((ChessSquare));
69 int SameColor P((ChessSquare, ChessSquare));
70 int PosFlags(int index);
71
72 extern signed char initialRights[BOARD_FILES]; /* [HGM] all rights enabled, set in InitPosition */
73 int quickFlag;
74
75 int WhitePiece(piece)
76      ChessSquare piece;
77 {
78     return (int) piece >= (int) WhitePawn && (int) piece < (int) BlackPawn;
79 }
80
81 int BlackPiece(piece)
82      ChessSquare piece;
83 {
84     return (int) piece >= (int) BlackPawn && (int) piece < (int) EmptySquare;
85 }
86
87 #if 0
88 int SameColor(piece1, piece2)
89      ChessSquare piece1, piece2;
90 {
91     return ((int) piece1 >= (int) WhitePawn &&   /* [HGM] can be > King ! */
92             (int) piece1 <  (int) BlackPawn &&
93             (int) piece2 >= (int) WhitePawn &&
94             (int) piece2 <  (int) BlackPawn)
95       ||   ((int) piece1 >= (int) BlackPawn &&
96             (int) piece1 <  (int) EmptySquare &&
97             (int) piece2 >= (int) BlackPawn &&
98             (int) piece2 <  (int) EmptySquare);
99 }
100 #else
101 #define SameColor(piece1, piece2) (piece1 < EmptySquare && piece2 < EmptySquare && (piece1 < BlackPawn) == (piece2 < BlackPawn))
102 #endif
103
104 char pieceToChar[] = {
105                         'P', 'N', 'B', 'R', 'Q', 'F', 'E', 'A', 'C', 'W', 'M',
106                         'O', 'H', 'I', 'J', 'G', 'D', 'V', 'L', 'S', 'U', 'K',
107                         'p', 'n', 'b', 'r', 'q', 'f', 'e', 'a', 'c', 'w', 'm',
108                         'o', 'h', 'i', 'j', 'g', 'd', 'v', 'l', 's', 'u', 'k',
109                         'x' };
110 char pieceNickName[EmptySquare];
111
112 char PieceToChar(p)
113      ChessSquare p;
114 {
115     if((int)p < 0 || (int)p >= (int)EmptySquare) return('x'); /* [HGM] for safety */
116     return pieceToChar[(int) p];
117 }
118
119 int PieceToNumber(p)  /* [HGM] holdings: count piece type, ignoring non-participating piece types */
120      ChessSquare p;
121 {
122     int i=0;
123     ChessSquare start = (int)p >= (int)BlackPawn ? BlackPawn : WhitePawn;
124
125     while(start++ != p) if(pieceToChar[(int)start-1] != '.') i++;
126     return i;
127 }
128
129 ChessSquare CharToPiece(c)
130      int c;
131 {
132      int i;
133      if(c == '.') return EmptySquare;
134      for(i=0; i< (int) EmptySquare; i++)
135           if(pieceNickName[i] == c) return (ChessSquare) i;
136      for(i=0; i< (int) EmptySquare; i++)
137           if(pieceToChar[i] == c) return (ChessSquare) i;
138      return EmptySquare;
139 }
140
141 void CopyBoard(to, from)
142      Board to, from;
143 {
144     int i, j;
145
146     for (i = 0; i < BOARD_HEIGHT; i++)
147       for (j = 0; j < BOARD_WIDTH; j++)
148         to[i][j] = from[i][j];
149     for (j = 0; j < BOARD_FILES-1; j++) // [HGM] gamestate: copy castling rights and ep status
150         to[CASTLING][j] = from[CASTLING][j];
151     to[HOLDINGS_SET] = 0; // flag used in ICS play
152 }
153
154 int CompareBoards(board1, board2)
155      Board board1, board2;
156 {
157     int i, j;
158
159     for (i = 0; i < BOARD_HEIGHT; i++)
160       for (j = 0; j < BOARD_WIDTH; j++) {
161           if (board1[i][j] != board2[i][j])
162             return FALSE;
163     }
164     return TRUE;
165 }
166
167
168 /* Call callback once for each pseudo-legal move in the given
169    position, except castling moves. A move is pseudo-legal if it is
170    legal, or if it would be legal except that it leaves the king in
171    check.  In the arguments, epfile is EP_NONE if the previous move
172    was not a double pawn push, or the file 0..7 if it was, or
173    EP_UNKNOWN if we don't know and want to allow all e.p. captures.
174    Promotion moves generated are to Queen only.
175 */
176 void GenPseudoLegal(board, flags, callback, closure, filter)
177      Board board;
178      int flags;
179      MoveCallback callback;
180      VOIDSTAR closure;
181      ChessSquare filter; // [HGM] speed: only do moves with this piece type
182 {
183     int rf, ff;
184     int i, j, d, s, fs, rs, rt, ft, m;
185     int epfile = (signed char)board[EP_STATUS]; // [HGM] gamestate: extract ep status from board
186     int promoRank = gameInfo.variant == VariantMakruk || gameInfo.variant == VariantGrand ? 3 : 1;
187
188     for (rf = 0; rf < BOARD_HEIGHT; rf++)
189       for (ff = BOARD_LEFT; ff < BOARD_RGHT; ff++) {
190           ChessSquare piece;
191           int rookRange;
192
193           if(board[rf][ff] == EmptySquare) continue;
194           if ((flags & F_WHITE_ON_MOVE) != (board[rf][ff] < BlackPawn)) continue; // [HGM] speed: wrong color
195           rookRange = 1000;
196           m = 0; piece = board[rf][ff];
197           if(PieceToChar(piece) == '~')
198                  piece = (ChessSquare) ( DEMOTED piece );
199           if(filter != EmptySquare && piece != filter) continue;
200           if(gameInfo.variant == VariantShogi)
201                  piece = (ChessSquare) ( SHOGI piece );
202
203           switch ((int)piece) {
204             /* case EmptySquare: [HGM] this is nonsense, and conflicts with Shogi cases */
205             default:
206               /* can't happen ([HGM] except for faries...) */
207               break;
208
209              case WhitePawn:
210               if(gameInfo.variant == VariantXiangqi) {
211                   /* [HGM] capture and move straight ahead in Xiangqi */
212                   if (rf < BOARD_HEIGHT-1 &&
213                            !SameColor(board[rf][ff], board[rf + 1][ff]) ) {
214                            callback(board, flags, NormalMove,
215                                     rf, ff, rf + 1, ff, closure);
216                   }
217                   /* and move sideways when across the river */
218                   for (s = -1; s <= 1; s += 2) {
219                       if (rf >= BOARD_HEIGHT>>1 &&
220                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
221                           !WhitePiece(board[rf][ff+s]) ) {
222                            callback(board, flags, NormalMove,
223                                     rf, ff, rf, ff+s, closure);
224                       }
225                   }
226                   break;
227               }
228               if (rf < BOARD_HEIGHT-1 && board[rf + 1][ff] == EmptySquare) {
229                   callback(board, flags,
230                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
231                            rf, ff, rf + 1, ff, closure);
232               }
233               if (rf <= (BOARD_HEIGHT>>1)-3 && board[rf+1][ff] == EmptySquare && // [HGM] grand: also on 3rd rank on 10-board
234                   gameInfo.variant != VariantShatranj && /* [HGM] */
235                   gameInfo.variant != VariantCourier  && /* [HGM] */
236                   board[rf+2][ff] == EmptySquare ) {
237                       callback(board, flags, NormalMove,
238                                rf, ff, rf+2, ff, closure);
239               }
240               for (s = -1; s <= 1; s += 2) {
241                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
242                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
243                        BlackPiece(board[rf + 1][ff + s]))) {
244                       callback(board, flags,
245                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
246                                rf, ff, rf + 1, ff + s, closure);
247                   }
248                   if (rf >= BOARD_HEIGHT+1>>1) {// [HGM] grand: 4th & 5th rank on 10-board
249                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
250                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf < BOARD_HEIGHT-3 &&
251                           board[rf][ff + s] == BlackPawn &&
252                           board[rf+1][ff + s] == EmptySquare) {
253                           callback(board, flags, WhiteCapturesEnPassant,
254                                    rf, ff, rf+1, ff + s, closure);
255                       }
256                   }
257               }
258               break;
259
260             case BlackPawn:
261               if(gameInfo.variant == VariantXiangqi) {
262                   /* [HGM] capture straight ahead in Xiangqi */
263                   if (rf > 0 && !SameColor(board[rf][ff], board[rf - 1][ff]) ) {
264                            callback(board, flags, NormalMove,
265                                     rf, ff, rf - 1, ff, closure);
266                   }
267                   /* and move sideways when across the river */
268                   for (s = -1; s <= 1; s += 2) {
269                       if (rf < BOARD_HEIGHT>>1 &&
270                           ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
271                           !BlackPiece(board[rf][ff+s]) ) {
272                            callback(board, flags, NormalMove,
273                                     rf, ff, rf, ff+s, closure);
274                       }
275                   }
276                   break;
277               }
278               if (rf > 0 && board[rf - 1][ff] == EmptySquare) {
279                   callback(board, flags,
280                            rf <= promoRank ? BlackPromotion : NormalMove,
281                            rf, ff, rf - 1, ff, closure);
282               }
283               if (rf >= (BOARD_HEIGHT+1>>1)+2 && board[rf-1][ff] == EmptySquare && // [HGM] grand
284                   gameInfo.variant != VariantShatranj && /* [HGM] */
285                   gameInfo.variant != VariantCourier  && /* [HGM] */
286                   board[rf-2][ff] == EmptySquare) {
287                   callback(board, flags, NormalMove,
288                            rf, ff, rf-2, ff, closure);
289               }
290               for (s = -1; s <= 1; s += 2) {
291                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
292                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
293                        WhitePiece(board[rf - 1][ff + s]))) {
294                       callback(board, flags,
295                                rf <= promoRank ? BlackPromotion : NormalMove,
296                                rf, ff, rf - 1, ff + s, closure);
297                   }
298                   if (rf < BOARD_HEIGHT>>1) {
299                       if (ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
300                           (epfile == ff + s || epfile == EP_UNKNOWN) && rf > 2 &&
301                           board[rf][ff + s] == WhitePawn &&
302                           board[rf-1][ff + s] == EmptySquare) {
303                           callback(board, flags, BlackCapturesEnPassant,
304                                    rf, ff, rf-1, ff + s, closure);
305                       }
306                   }
307               }
308               break;
309
310             case WhiteUnicorn:
311             case BlackUnicorn:
312             case WhiteKnight:
313             case BlackKnight:
314             mounted:
315               for (i = -1; i <= 1; i += 2)
316                 for (j = -1; j <= 1; j += 2)
317                   for (s = 1; s <= 2; s++) {
318                       rt = rf + i*s;
319                       ft = ff + j*(3-s);
320                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
321                           && ( gameInfo.variant != VariantXiangqi || board[rf+i*(s-1)][ff+j*(2-s)] == EmptySquare)
322                           && !SameColor(board[rf][ff], board[rt][ft]))
323                       callback(board, flags, NormalMove,
324                                rf, ff, rt, ft, closure);
325                   }
326               break;
327
328             case SHOGI WhiteKnight:
329               for (s = -1; s <= 1; s += 2) {
330                   if (rf < BOARD_HEIGHT-2 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
331                       !SameColor(board[rf][ff], board[rf + 2][ff + s])) {
332                       callback(board, flags, NormalMove,
333                                rf, ff, rf + 2, ff + s, closure);
334                   }
335               }
336               break;
337
338             case SHOGI BlackKnight:
339               for (s = -1; s <= 1; s += 2) {
340                   if (rf > 1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
341                       !SameColor(board[rf][ff], board[rf - 2][ff + s])) {
342                       callback(board, flags, NormalMove,
343                                rf, ff, rf - 2, ff + s, closure);
344                   }
345               }
346               break;
347
348             case WhiteCannon:
349             case BlackCannon:
350               for (d = 0; d <= 1; d++)
351                 for (s = -1; s <= 1; s += 2) {
352                   m = 0;
353                   for (i = 1;; i++) {
354                       rt = rf + (i * s) * d;
355                       ft = ff + (i * s) * (1 - d);
356                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
357                       if (m == 0 && board[rt][ft] == EmptySquare)
358                                  callback(board, flags, NormalMove,
359                                           rf, ff, rt, ft, closure);
360                       if (m == 1 && board[rt][ft] != EmptySquare &&
361                           !SameColor(board[rf][ff], board[rt][ft]) )
362                                  callback(board, flags, NormalMove,
363                                           rf, ff, rt, ft, closure);
364                       if (board[rt][ft] != EmptySquare && m++) break;
365                   }
366                 }
367               break;
368
369             /* Gold General (and all its promoted versions) . First do the */
370             /* diagonal forward steps, then proceed as normal Wazir        */
371             case SHOGI WhiteWazir:
372             case SHOGI (PROMOTED WhitePawn):
373             case SHOGI (PROMOTED WhiteKnight):
374             case SHOGI (PROMOTED WhiteQueen):
375             case SHOGI (PROMOTED WhiteFerz):
376               for (s = -1; s <= 1; s += 2) {
377                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
378                       !SameColor(board[rf][ff], board[rf + 1][ff + s])) {
379                       callback(board, flags, NormalMove,
380                                rf, ff, rf + 1, ff + s, closure);
381                   }
382               }
383               goto finishGold;
384
385             case SHOGI BlackWazir:
386             case SHOGI (PROMOTED BlackPawn):
387             case SHOGI (PROMOTED BlackKnight):
388             case SHOGI (PROMOTED BlackQueen):
389             case SHOGI (PROMOTED BlackFerz):
390               for (s = -1; s <= 1; s += 2) {
391                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT &&
392                       !SameColor(board[rf][ff], board[rf - 1][ff + s])) {
393                       callback(board, flags, NormalMove,
394                                rf, ff, rf - 1, ff + s, closure);
395                   }
396               }
397
398             case WhiteWazir:
399             case BlackWazir:
400             finishGold:
401               for (d = 0; d <= 1; d++)
402                 for (s = -1; s <= 1; s += 2) {
403                       rt = rf + s * d;
404                       ft = ff + s * (1 - d);
405                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
406                           && !SameColor(board[rf][ff], board[rt][ft]) &&
407                           (gameInfo.variant != VariantXiangqi || InPalace(rt, ft) ) )
408                                callback(board, flags, NormalMove,
409                                         rf, ff, rt, ft, closure);
410                       }
411               break;
412
413             case WhiteAlfil:
414             case BlackAlfil:
415                 /* [HGM] support Shatranj pieces */
416                 for (rs = -1; rs <= 1; rs += 2)
417                   for (fs = -1; fs <= 1; fs += 2) {
418                       rt = rf + 2 * rs;
419                       ft = ff + 2 * fs;
420                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
421                           && ( gameInfo.variant != VariantXiangqi ||
422                                board[rf+rs][ff+fs] == EmptySquare && (2*rf < BOARD_HEIGHT) == (2*rt < BOARD_HEIGHT) )
423
424                           && !SameColor(board[rf][ff], board[rt][ft]))
425                                callback(board, flags, NormalMove,
426                                         rf, ff, rt, ft, closure);
427                       if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier
428                                                              || gameInfo.variant == VariantXiangqi) continue; // classical Alfil
429                       rt = rf + rs; // in unknown variant we assume Modern Elephant, which can also do one step
430                       ft = ff + fs;
431                       if (!(rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT)
432                           && !SameColor(board[rf][ff], board[rt][ft]))
433                                callback(board, flags, NormalMove,
434                                         rf, ff, rt, ft, closure);
435                   }
436                 if(gameInfo.variant == VariantSpartan)
437                    for(fs = -1; fs <= 1; fs += 2) {
438                       ft = ff + fs;
439                       if (!(ft < BOARD_LEFT || ft >= BOARD_RGHT) && board[rf][ft] == EmptySquare)
440                                callback(board, flags, NormalMove, rf, ff, rf, ft, closure);
441                    }
442                 break;
443
444             /* Make Dragon-Horse also do Dababba moves outside Shogi, for better disambiguation in variant Fairy */
445             case WhiteCardinal:
446             case BlackCardinal:
447               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
448                 for (s = -2; s <= 2; s += 4) {
449                       rt = rf + s * d;
450                       ft = ff + s * (1 - d);
451                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
452                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
453                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
454                   }
455
456             /* Shogi Dragon Horse has to continue with Wazir after Bishop */
457             case SHOGI WhiteCardinal:
458             case SHOGI BlackCardinal:
459               m++;
460
461             /* Capablanca Archbishop continues as Knight                  */
462             case WhiteAngel:
463             case BlackAngel:
464               m++;
465
466             /* Shogi Bishops are ordinary Bishops */
467             case SHOGI WhiteBishop:
468             case SHOGI BlackBishop:
469             case WhiteBishop:
470             case BlackBishop:
471               for (rs = -1; rs <= 1; rs += 2)
472                 for (fs = -1; fs <= 1; fs += 2)
473                   for (i = 1;; i++) {
474                       rt = rf + (i * rs);
475                       ft = ff + (i * fs);
476                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
477                       if (SameColor(board[rf][ff], board[rt][ft])) break;
478                       callback(board, flags, NormalMove,
479                                rf, ff, rt, ft, closure);
480                       if (board[rt][ft] != EmptySquare) break;
481                   }
482                 if(m==1) goto mounted;
483                 if(m==2) goto finishGold;
484                 /* Bishop falls through */
485               break;
486
487             /* Shogi Lance is unlike anything, and asymmetric at that */
488             case SHOGI WhiteQueen:
489               for(i = 1;; i++) {
490                       rt = rf + i;
491                       ft = ff;
492                       if (rt >= BOARD_HEIGHT) break;
493                       if (SameColor(board[rf][ff], board[rt][ft])) break;
494                       callback(board, flags, NormalMove,
495                                rf, ff, rt, ft, closure);
496                       if (board[rt][ft] != EmptySquare) break;
497               }
498               break;
499
500             case SHOGI BlackQueen:
501               for(i = 1;; i++) {
502                       rt = rf - i;
503                       ft = ff;
504                       if (rt < 0) break;
505                       if (SameColor(board[rf][ff], board[rt][ft])) break;
506                       callback(board, flags, NormalMove,
507                                rf, ff, rt, ft, closure);
508                       if (board[rt][ft] != EmptySquare) break;
509               }
510               break;
511
512             /* Make Dragon-King Dababba & Rook-like outside Shogi, for better disambiguation in variant Fairy */
513             case WhiteDragon:
514             case BlackDragon:
515               for (d = 0; d <= 1; d++) // Dababba moves that Rook cannot do
516                 for (s = -2; s <= 2; s += 4) {
517                       rt = rf + s * d;
518                       ft = ff + s * (1 - d);
519                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT || board[rf+rt>>1][ff+ft>>1] == EmptySquare) continue;
520                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
521                       callback(board, flags, NormalMove, rf, ff, rt, ft, closure);
522                   }
523               if(gameInfo.variant == VariantSpartan) rookRange = 2; // in Spartan Chess restrict range to modern Dababba
524               goto doRook;
525               
526             /* Shogi Dragon King has to continue as Ferz after Rook moves */
527             case SHOGI WhiteDragon:
528             case SHOGI BlackDragon:
529               m++;
530
531             /* Capablanca Chancellor sets flag to continue as Knight      */
532             case WhiteMarshall:
533             case BlackMarshall:
534               m++;
535               m += (gameInfo.variant == VariantSpartan); // in Spartan Chess Chancellor is used for Dragon King.
536
537             /* Shogi Rooks are ordinary Rooks */
538             case SHOGI WhiteRook:
539             case SHOGI BlackRook:
540             case WhiteRook:
541             case BlackRook:
542           doRook:
543               for (d = 0; d <= 1; d++)
544                 for (s = -1; s <= 1; s += 2)
545                   for (i = 1;; i++) {
546                       rt = rf + (i * s) * d;
547                       ft = ff + (i * s) * (1 - d);
548                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
549                       if (SameColor(board[rf][ff], board[rt][ft])) break;
550                       callback(board, flags, NormalMove,
551                                rf, ff, rt, ft, closure);
552                       if (board[rt][ft] != EmptySquare || i == rookRange) break;
553                   }
554                 if(m==1) goto mounted;
555                 if(m==2) goto finishSilver;
556               break;
557
558             case WhiteQueen:
559             case BlackQueen:
560               for (rs = -1; rs <= 1; rs++)
561                 for (fs = -1; fs <= 1; fs++) {
562                     if (rs == 0 && fs == 0) continue;
563                     for (i = 1;; i++) {
564                         rt = rf + (i * rs);
565                         ft = ff + (i * fs);
566                         if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
567                         if (SameColor(board[rf][ff], board[rt][ft])) break;
568                         callback(board, flags, NormalMove,
569                                  rf, ff, rt, ft, closure);
570                         if (board[rt][ft] != EmptySquare) break;
571                     }
572                 }
573               break;
574
575             /* Shogi Pawn and Silver General: first the Pawn move,    */
576             /* then the General continues like a Ferz                 */
577             case WhiteMan:
578                 if(gameInfo.variant != VariantMakruk) goto commoner;
579             case SHOGI WhitePawn:
580             case SHOGI WhiteFerz:
581                   if (rf < BOARD_HEIGHT-1 &&
582                            !SameColor(board[rf][ff], board[rf + 1][ff]) )
583                            callback(board, flags, NormalMove,
584                                     rf, ff, rf + 1, ff, closure);
585               if(piece != SHOGI WhitePawn) goto finishSilver;
586               break;
587
588             case BlackMan:
589                 if(gameInfo.variant != VariantMakruk) goto commoner;
590             case SHOGI BlackPawn:
591             case SHOGI BlackFerz:
592                   if (rf > 0 &&
593                            !SameColor(board[rf][ff], board[rf - 1][ff]) )
594                            callback(board, flags, NormalMove,
595                                     rf, ff, rf - 1, ff, closure);
596               if(piece == SHOGI BlackPawn) break;
597
598             case WhiteFerz:
599             case BlackFerz:
600             finishSilver:
601                 /* [HGM] support Shatranj pieces */
602                 for (rs = -1; rs <= 1; rs += 2)
603                   for (fs = -1; fs <= 1; fs += 2) {
604                       rt = rf + rs;
605                       ft = ff + fs;
606                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
607                       if (!SameColor(board[rf][ff], board[rt][ft]) &&
608                           (gameInfo.variant != VariantXiangqi || InPalace(rt, ft) ) )
609                                callback(board, flags, NormalMove,
610                                         rf, ff, rt, ft, closure);
611                   }
612                 break;
613
614             case WhiteSilver:
615             case BlackSilver:
616                 m++; // [HGM] superchess: use for Centaur
617             commoner:
618             case SHOGI WhiteKing:
619             case SHOGI BlackKing:
620             case WhiteKing:
621             case BlackKing:
622 //            walking:
623               for (i = -1; i <= 1; i++)
624                 for (j = -1; j <= 1; j++) {
625                     if (i == 0 && j == 0) continue;
626                     rt = rf + i;
627                     ft = ff + j;
628                     if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) continue;
629                     if (SameColor(board[rf][ff], board[rt][ft])) continue;
630                     callback(board, flags, NormalMove,
631                              rf, ff, rt, ft, closure);
632                 }
633                 if(m==1) goto mounted;
634               break;
635
636             case WhiteNightrider:
637             case BlackNightrider:
638               for (i = -1; i <= 1; i += 2)
639                 for (j = -1; j <= 1; j += 2)
640                   for (s = 1; s <= 2; s++) {  int k;
641                     for(k=1;; k++) {
642                       rt = rf + k*i*s;
643                       ft = ff + k*j*(3-s);
644                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
645                       if (SameColor(board[rf][ff], board[rt][ft])) break;
646                       callback(board, flags, NormalMove,
647                                rf, ff, rt, ft, closure);
648                       if (board[rt][ft] != EmptySquare) break;
649                     }
650                   }
651               break;
652
653             Amazon:
654               /* First do Bishop,then continue like Chancellor */
655               for (rs = -1; rs <= 1; rs += 2)
656                 for (fs = -1; fs <= 1; fs += 2)
657                   for (i = 1;; i++) {
658                       rt = rf + (i * rs);
659                       ft = ff + (i * fs);
660                       if (rt < 0 || rt >= BOARD_HEIGHT || ft < BOARD_LEFT || ft >= BOARD_RGHT) break;
661                       if (SameColor(board[rf][ff], board[rt][ft])) break;
662                       callback(board, flags, NormalMove,
663                                rf, ff, rt, ft, closure);
664                       if (board[rt][ft] != EmptySquare) break;
665                   }
666               m++;
667               goto doRook;
668
669             // Use Lance as Berolina / Spartan Pawn.
670             case WhiteLance:
671               if(gameInfo.variant == VariantSuper) goto Amazon;
672               if (rf < BOARD_HEIGHT-1 && BlackPiece(board[rf + 1][ff]))
673                   callback(board, flags,
674                            rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
675                            rf, ff, rf + 1, ff, closure);
676               for (s = -1; s <= 1; s += 2) {
677                   if (rf < BOARD_HEIGHT-1 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf + 1][ff + s] == EmptySquare)
678                       callback(board, flags, 
679                                rf >= BOARD_HEIGHT-1-promoRank ? WhitePromotion : NormalMove,
680                                rf, ff, rf + 1, ff + s, closure);
681                   if (rf == 1 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[3][ff + 2*s] == EmptySquare )
682                       callback(board, flags, NormalMove, rf, ff, 3, ff + 2*s, closure);
683               }
684               break;
685                 
686             case BlackLance:
687               if(gameInfo.variant == VariantSuper) goto Amazon;
688               if (rf > 0 && WhitePiece(board[rf - 1][ff]))
689                   callback(board, flags,
690                            rf <= promoRank ? BlackPromotion : NormalMove,
691                            rf, ff, rf - 1, ff, closure);
692               for (s = -1; s <= 1; s += 2) {
693                   if (rf > 0 && ff + s >= BOARD_LEFT && ff + s < BOARD_RGHT && board[rf - 1][ff + s] == EmptySquare)
694                       callback(board, flags, 
695                                rf <= promoRank ? BlackPromotion : NormalMove,
696                                rf, ff, rf - 1, ff + s, closure);
697                   if (rf == BOARD_HEIGHT-2 && ff + 2*s >= BOARD_LEFT && ff + 2*s < BOARD_RGHT && board[rf-2][ff + 2*s] == EmptySquare )
698                       callback(board, flags, NormalMove, rf, ff, rf-2, ff + 2*s, closure);
699               }
700             break;
701
702             case WhiteFalcon: // [HGM] wild: for wildcards, self-capture symbolizes move to anywhere
703             case BlackFalcon:
704             case WhiteCobra:
705             case BlackCobra:
706               callback(board, flags, NormalMove, rf, ff, rf, ff, closure);
707               break;
708
709           }
710       }
711 }
712
713
714 typedef struct {
715     MoveCallback cb;
716     VOIDSTAR cl;
717 } GenLegalClosure;
718
719 int rFilter, fFilter; // [HGM] speed: sorry, but I get a bit tired of this closure madness
720
721 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
722                                 int rf, int ff, int rt, int ft,
723                                 VOIDSTAR closure));
724
725 void GenLegalCallback(board, flags, kind, rf, ff, rt, ft, closure)
726      Board board;
727      int flags;
728      ChessMove kind;
729      int rf, ff, rt, ft;
730      VOIDSTAR closure;
731 {
732     register GenLegalClosure *cl = (GenLegalClosure *) closure;
733
734     if(rFilter >= 0 && rFilter != rt || fFilter >= 0 && fFilter != ft) return; // [HGM] speed: ignore moves with wrong to-square
735
736     if (!(flags & F_IGNORE_CHECK) ) {
737       int check, promo = (gameInfo.variant == VariantSpartan && kind == BlackPromotion);
738       if(promo) board[rf][ff] = BlackKing; // [HGM] spartan: promote to King before check-test
739         check = CheckTest(board, flags, rf, ff, rt, ft,
740                   kind == WhiteCapturesEnPassant ||
741                   kind == BlackCapturesEnPassant);
742         if(promo) board[rf][ff] = BlackLance;
743       if(check) return;
744     }
745     if (flags & F_ATOMIC_CAPTURE) {
746       if (board[rt][ft] != EmptySquare ||
747           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
748         int r, f;
749         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
750         if (board[rf][ff] == king) return;
751         for (r = rt-1; r <= rt+1; r++) {
752           for (f = ft-1; f <= ft+1; f++) {
753             if (r >= 0 && r < BOARD_HEIGHT && f >= BOARD_LEFT && f < BOARD_RGHT &&
754                 board[r][f] == king) return;
755           }
756         }
757       }
758     }
759     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
760 }
761
762
763 typedef struct {
764     int rf, ff, rt, ft;
765     ChessMove kind;
766     int captures; // [HGM] losers
767 } LegalityTestClosure;
768
769
770 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
771    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
772    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
773    moves that would destroy your own king.  The CASTLE_OK flags are
774    true if castling is not yet ruled out by a move of the king or
775    rook.  Return TRUE if the player on move is currently in check and
776    F_IGNORE_CHECK is not set.  [HGM] add castlingRights parameter */
777 int GenLegal(board, flags, callback, closure, filter)
778      Board board;
779      int flags;
780      MoveCallback callback;
781      VOIDSTAR closure;
782      ChessSquare filter;
783 {
784     GenLegalClosure cl;
785     int ff, ft, k, left, right, swap;
786     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
787     ChessSquare wKing = WhiteKing, bKing = BlackKing, *castlingRights = board[CASTLING];
788
789     cl.cb = callback;
790     cl.cl = closure;
791     if(filter == EmptySquare) rFilter = fFilter = -1; // [HGM] speed: do not filter on square if we do not filter on piece
792     GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl, filter);
793
794     if (!ignoreCheck &&
795         CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE;
796
797     /* Generate castling moves */
798     if(gameInfo.variant == VariantKnightmate) { /* [HGM] Knightmate */
799         wKing = WhiteUnicorn; bKing = BlackUnicorn;
800     }
801
802     for (ff = BOARD_WIDTH>>1; ff >= (BOARD_WIDTH-1)>>1; ff-- /*ics wild 1*/) {
803         if ((flags & F_WHITE_ON_MOVE) &&
804             (flags & F_WHITE_KCASTLE_OK) &&
805             board[0][ff] == wKing &&
806             board[0][ff + 1] == EmptySquare &&
807             board[0][ff + 2] == EmptySquare &&
808             board[0][BOARD_RGHT-3] == EmptySquare &&
809             board[0][BOARD_RGHT-2] == EmptySquare &&
810             board[0][BOARD_RGHT-1] == WhiteRook &&
811             castlingRights[0] != NoRights && /* [HGM] check rights */
812             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
813             (ignoreCheck ||
814              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
815               !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-3, FALSE) &&
816               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, 0, ff, 0, BOARD_RGHT-2, FALSE)) &&
817               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
818
819             callback(board, flags,
820                      ff==BOARD_WIDTH>>1 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
821                      0, ff, 0, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
822         }
823         if ((flags & F_WHITE_ON_MOVE) &&
824             (flags & F_WHITE_QCASTLE_OK) &&
825             board[0][ff] == wKing &&
826             board[0][ff - 1] == EmptySquare &&
827             board[0][ff - 2] == EmptySquare &&
828             board[0][BOARD_LEFT+2] == EmptySquare &&
829             board[0][BOARD_LEFT+1] == EmptySquare &&
830             board[0][BOARD_LEFT+0] == WhiteRook &&
831             castlingRights[1] != NoRights && /* [HGM] check rights */
832             ( castlingRights[2] == ff || castlingRights[6] == ff ) &&
833             (ignoreCheck ||
834              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
835               !CheckTest(board, flags, 0, ff, 0, BOARD_LEFT+3, FALSE) &&
836               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
837
838             callback(board, flags,
839                      ff==BOARD_WIDTH>>1 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
840                      0, ff, 0, ff - ((gameInfo.boardWidth+2)>>2), closure);
841         }
842         if (!(flags & F_WHITE_ON_MOVE) &&
843             (flags & F_BLACK_KCASTLE_OK) &&
844             board[BOARD_HEIGHT-1][ff] == bKing &&
845             board[BOARD_HEIGHT-1][ff + 1] == EmptySquare &&
846             board[BOARD_HEIGHT-1][ff + 2] == EmptySquare &&
847             board[BOARD_HEIGHT-1][BOARD_RGHT-3] == EmptySquare &&
848             board[BOARD_HEIGHT-1][BOARD_RGHT-2] == EmptySquare &&
849             board[BOARD_HEIGHT-1][BOARD_RGHT-1] == BlackRook &&
850             castlingRights[3] != NoRights && /* [HGM] check rights */
851             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
852             (ignoreCheck ||
853              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 1, FALSE) &&
854               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-3, FALSE) &&
855               (gameInfo.variant != VariantJanus || !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_RGHT-2, FALSE)) &&
856               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + 2, FALSE)))) {
857
858             callback(board, flags,
859                      ff==BOARD_WIDTH>>1 ? BlackKingSideCastle : BlackKingSideCastleWild,
860                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff + ((gameInfo.boardWidth+2)>>2) + (gameInfo.variant == VariantJanus), closure);
861         }
862         if (!(flags & F_WHITE_ON_MOVE) &&
863             (flags & F_BLACK_QCASTLE_OK) &&
864             board[BOARD_HEIGHT-1][ff] == bKing &&
865             board[BOARD_HEIGHT-1][ff - 1] == EmptySquare &&
866             board[BOARD_HEIGHT-1][ff - 2] == EmptySquare &&
867             board[BOARD_HEIGHT-1][BOARD_LEFT+2] == EmptySquare &&
868             board[BOARD_HEIGHT-1][BOARD_LEFT+1] == EmptySquare &&
869             board[BOARD_HEIGHT-1][BOARD_LEFT+0] == BlackRook &&
870             castlingRights[4] != NoRights && /* [HGM] check rights */
871             ( castlingRights[5] == ff || castlingRights[7] == ff ) &&
872             (ignoreCheck ||
873              (!CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 1, FALSE) &&
874               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, BOARD_LEFT+3, FALSE) &&
875               !CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - 2, FALSE)))) {
876
877             callback(board, flags,
878                      ff==BOARD_WIDTH>>1 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
879                      BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, ff - ((gameInfo.boardWidth+2)>>2), closure);
880         }
881     }
882
883   if((swap = gameInfo.variant == VariantSChess) || flags & F_FRC_TYPE_CASTLING) {
884
885     /* generate all potential FRC castling moves (KxR), ignoring flags */
886     /* [HGM] test if the Rooks we find have castling rights */
887     /* In S-Chess we generate RxK for allowed castlings, for gating at Rook square */
888
889
890     if ((flags & F_WHITE_ON_MOVE) != 0) {
891         ff = castlingRights[2]; /* King file if we have any rights */
892         if(ff != NoRights && board[0][ff] == WhiteKing) {
893     if (appData.debugMode) {
894         fprintf(debugFP, "FRC castling, %d %d %d %d %d %d\n",
895                 castlingRights[0],castlingRights[1],ff,castlingRights[3],castlingRights[4],castlingRights[5]);
896     }
897             ft = castlingRights[0]; /* Rook file if we have H-side rights */
898             left  = ff+1;
899             right = BOARD_RGHT-2;
900             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
901             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
902                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
903             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
904                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
905             if(ft != NoRights && board[0][ft] == WhiteRook)
906                 callback(board, flags, WhiteHSideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
907
908             ft = castlingRights[1]; /* Rook file if we have A-side rights */
909             left  = BOARD_LEFT+2;
910             right = ff-1;
911             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
912             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
913                 if(k != ft && board[0][k] != EmptySquare) ft = NoRights;
914             if(ff > BOARD_LEFT+2)
915             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
916                 if(!ignoreCheck && CheckTest(board, flags, 0, ff, 0, k, FALSE)) ft = NoRights;
917             if(ft != NoRights && board[0][ft] == WhiteRook)
918                 callback(board, flags, WhiteASideCastleFR, 0, swap ? ft : ff, 0, swap ? ff : ft, closure);
919         }
920     } else {
921         ff = castlingRights[5]; /* King file if we have any rights */
922         if(ff != NoRights && board[BOARD_HEIGHT-1][ff] == BlackKing) {
923             ft = castlingRights[3]; /* Rook file if we have H-side rights */
924             left  = ff+1;
925             right = BOARD_RGHT-2;
926             if(ff == BOARD_RGHT-2) left = right = ff-1;    /* special case */
927             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
928                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
929             for(k=left; k<right && ft != NoRights; k++) /* then if not checked */
930                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
931             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
932                 callback(board, flags, BlackHSideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
933
934             ft = castlingRights[4]; /* Rook file if we have A-side rights */
935             left  = BOARD_LEFT+2;
936             right = ff-1;
937             if(ff <= BOARD_LEFT+2) { left = ff+1; right = BOARD_LEFT+3; }
938             for(k=left; k<=right && ft != NoRights; k++) /* first test if blocked */
939                 if(k != ft && board[BOARD_HEIGHT-1][k] != EmptySquare) ft = NoRights;
940             if(ff > BOARD_LEFT+2)
941             for(k=left+1; k<=right && ft != NoRights; k++) /* then if not checked */
942                 if(!ignoreCheck && CheckTest(board, flags, BOARD_HEIGHT-1, ff, BOARD_HEIGHT-1, k, FALSE)) ft = NoRights;
943             if(ft != NoRights && board[BOARD_HEIGHT-1][ft] == BlackRook)
944                 callback(board, flags, BlackASideCastleFR, BOARD_HEIGHT-1, swap ? ft : ff, BOARD_HEIGHT-1, swap ? ff : ft, closure);
945         }
946     }
947
948   }
949
950     return FALSE;
951 }
952
953
954 typedef struct {
955     int rking, fking;
956     int check;
957 } CheckTestClosure;
958
959
960 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
961                                  int rf, int ff, int rt, int ft,
962                                  VOIDSTAR closure));
963
964
965 void CheckTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
966      Board board;
967      int flags;
968      ChessMove kind;
969      int rf, ff, rt, ft;
970      VOIDSTAR closure;
971 {
972     register CheckTestClosure *cl = (CheckTestClosure *) closure;
973
974     if (rt == cl->rking && ft == cl->fking) cl->check++;
975 }
976
977
978 /* If the player on move were to move from (rf, ff) to (rt, ft), would
979    he leave himself in check?  Or if rf == -1, is the player on move
980    in check now?  enPassant must be TRUE if the indicated move is an
981    e.p. capture.  The possibility of castling out of a check along the
982    back rank is not accounted for (i.e., we still return nonzero), as
983    this is illegal anyway.  Return value is the number of times the
984    king is in check. */
985 int CheckTest(board, flags, rf, ff, rt, ft, enPassant)
986      Board board;
987      int flags;
988      int rf, ff, rt, ft, enPassant;
989 {
990     CheckTestClosure cl;
991     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
992     ChessSquare captured = EmptySquare;
993     /*  Suppress warnings on uninitialized variables    */
994
995     if(gameInfo.variant == VariantXiangqi)
996         king = flags & F_WHITE_ON_MOVE ? WhiteWazir : BlackWazir;
997     if(gameInfo.variant == VariantKnightmate)
998         king = flags & F_WHITE_ON_MOVE ? WhiteUnicorn : BlackUnicorn;
999
1000     if (rf >= 0) {
1001         if (enPassant) {
1002             captured = board[rf][ft];
1003             board[rf][ft] = EmptySquare;
1004         } else {
1005             captured = board[rt][ft];
1006         }
1007         board[rt][ft] = board[rf][ff];
1008         board[rf][ff] = EmptySquare;
1009     } else board[rt][ft] = ff; // [HGM] drop
1010
1011     /* For compatibility with ICS wild 9, we scan the board in the
1012        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
1013        and we test only whether that one is in check. */
1014     for (cl.fking = BOARD_LEFT+0; cl.fking < BOARD_RGHT; cl.fking++)
1015         for (cl.rking = 0; cl.rking < BOARD_HEIGHT; cl.rking++) {
1016           if (board[cl.rking][cl.fking] == king) {
1017               cl.check = 0;
1018               if(gameInfo.variant == VariantXiangqi) {
1019                   /* [HGM] In Xiangqi opposing Kings means check as well */
1020                   int i, dir;
1021                   dir = (king >= BlackPawn) ? -1 : 1;
1022                   for( i=cl.rking+dir; i>=0 && i<BOARD_HEIGHT &&
1023                                 board[i][cl.fking] == EmptySquare; i+=dir );
1024                   if(i>=0 && i<BOARD_HEIGHT &&
1025                       board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) )
1026                           cl.check++;
1027               }
1028               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare);
1029               if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too
1030                  goto undo_move;  /* 2-level break */
1031           }
1032       }
1033
1034   undo_move:
1035
1036     if (rf >= 0) {
1037         board[rf][ff] = board[rt][ft];
1038         if (enPassant) {
1039             board[rf][ft] = captured;
1040             board[rt][ft] = EmptySquare;
1041         } else {
1042             board[rt][ft] = captured;
1043         }
1044     } else board[rt][ft] = EmptySquare; // [HGM] drop
1045
1046     return cl.fking < BOARD_RGHT ? cl.check : 1000; // [HGM] atomic: return 1000 if we have no king
1047 }
1048
1049 ChessMove LegalDrop(board, flags, piece, rt, ft)
1050      Board board;
1051      int flags;
1052      ChessSquare piece;
1053      int rt, ft;
1054 {   // [HGM] put drop legality testing in separate routine for clarity
1055     int n;
1056 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1057     if(board[rt][ft] != EmptySquare) return ImpossibleMove; // must drop to empty square
1058     n = PieceToNumber(piece);
1059     if(gameInfo.holdingsWidth == 0 || (flags & F_WHITE_ON_MOVE ? board[n][BOARD_WIDTH-1] : board[BOARD_HEIGHT-1-n][0]) != piece)
1060         return ImpossibleMove; // piece not available
1061     if(gameInfo.variant == VariantShogi) { // in Shogi lots of drops are forbidden!
1062         if((piece == WhitePawn || piece == WhiteQueen) && rt == BOARD_HEIGHT-1 ||
1063            (piece == BlackPawn || piece == BlackQueen) && rt == 0 ||
1064             piece == WhiteKnight && rt > BOARD_HEIGHT-3 ||
1065             piece == BlackKnight && rt < 2 ) return IllegalMove; // e.g. where dropped piece has no moves
1066         if(piece == WhitePawn || piece == BlackPawn) {
1067             int r;
1068             for(r=1; r<BOARD_HEIGHT-1; r++)
1069                 if(board[r][ft] == piece) return IllegalMove; // or there already is a Pawn in file
1070             // should still test if we mate with this Pawn
1071         }
1072     } else if(gameInfo.variant == VariantSChess) { // only back-rank drops
1073         if (rt != (piece < BlackPawn ? 0 : BOARD_HEIGHT-1)) return IllegalMove;
1074     } else {
1075         if( (piece == WhitePawn || piece == BlackPawn) &&
1076             (rt == 0 || rt == BOARD_HEIGHT -1 ) )
1077             return IllegalMove; /* no pawn drops on 1st/8th */
1078     }
1079 if(appData.debugMode) fprintf(debugFP, "LegalDrop: %d @ %d,%d)\n", piece, ft, rt);
1080     if (!(flags & F_IGNORE_CHECK) &&
1081         CheckTest(board, flags, DROP_RANK, piece, rt, ft, FALSE) ) return IllegalMove;
1082     return flags & F_WHITE_ON_MOVE ? WhiteDrop : BlackDrop;
1083 }
1084
1085 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
1086                                     int rf, int ff, int rt, int ft,
1087                                     VOIDSTAR closure));
1088
1089 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1090      Board board;
1091      int flags;
1092      ChessMove kind;
1093      int rf, ff, rt, ft;
1094      VOIDSTAR closure;
1095 {
1096     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
1097
1098 //    if (appData.debugMode) {
1099 //        fprintf(debugFP, "Legality test: %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1100 //    }
1101     if(board[rt][ft] != EmptySquare || kind==WhiteCapturesEnPassant || kind==BlackCapturesEnPassant)
1102         cl->captures++; // [HGM] losers: count legal captures
1103     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
1104       cl->kind = kind;
1105 }
1106
1107 ChessMove LegalityTest(board, flags, rf, ff, rt, ft, promoChar)
1108      Board board;
1109      int flags;
1110      int rf, ff, rt, ft, promoChar;
1111 {
1112     LegalityTestClosure cl; ChessSquare piece, filterPiece, *castlingRights = board[CASTLING];
1113
1114     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1115     if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft);
1116     piece = filterPiece = board[rf][ff];
1117     if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece; 
1118
1119     if (appData.debugMode) {
1120         int i;
1121         for(i=0; i<6; i++) fprintf(debugFP, "%d ", castlingRights[i]);
1122         fprintf(debugFP, "Legality test? %c%c%c%c\n", ff+AAA, rf+ONE, ft+AAA, rt+ONE);
1123     }
1124     /* [HGM] Cobra and Falcon are wildcard pieces; consider all their moves legal */
1125     /* (perhaps we should disallow moves that obviously leave us in check?)              */
1126     if(piece == WhiteFalcon || piece == BlackFalcon ||
1127        piece == WhiteCobra  || piece == BlackCobra)
1128         return CheckTest(board, flags, rf, ff, rt, ft, FALSE) ? IllegalMove : NormalMove;
1129
1130     cl.rf = rf;
1131     cl.ff = ff;
1132     cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1133     cl.ft = fFilter = ft;
1134     cl.kind = IllegalMove;
1135     cl.captures = 0; // [HGM] losers: prepare to count legal captures.
1136     if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures
1137     GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece);
1138     if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare
1139                 && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant)
1140         return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal
1141
1142     if(promoChar == 'x') promoChar = NULLCHAR; // [HGM] is this ever the case?
1143     if(gameInfo.variant == VariantSChess && promoChar && promoChar != '=' && board[rf][ff] != WhitePawn && board[rf][ff] != BlackPawn) {
1144         if(board[rf][ff] < BlackPawn) { // white
1145             if(rf != 0) return IllegalMove; // must be on back rank
1146             if(board[PieceToNumber(CharToPiece(ToUpper(promoChar)))][BOARD_WIDTH-2] == 0) return ImpossibleMove;// must be in stock
1147         } else {
1148             if(rf != BOARD_HEIGHT-1) return IllegalMove;
1149             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(promoChar)))][1] == 0) return ImpossibleMove;
1150         }
1151     } else
1152     if(gameInfo.variant == VariantShogi) {
1153         /* [HGM] Shogi promotions. '=' means defer */
1154         if(rf != DROP_RANK && cl.kind == NormalMove) {
1155             ChessSquare piece = board[rf][ff];
1156
1157             if(promoChar == PieceToChar(BlackQueen)) promoChar = NULLCHAR; /* [HGM] Kludge */
1158             if(promoChar == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1159                promoChar == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1160                promoChar == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1161                   promoChar = '+'; // allowed ICS notations
1162 if(appData.debugMode)fprintf(debugFP,"SHOGI promoChar = %c\n", promoChar ? promoChar : '-');
1163             if(promoChar != NULLCHAR && promoChar != '+' && promoChar != '=')
1164                 return CharToPiece(promoChar) == EmptySquare ? ImpossibleMove : IllegalMove;
1165             else if(flags & F_WHITE_ON_MOVE) {
1166                 if( (int) piece < (int) WhiteWazir &&
1167                      (rf >= BOARD_HEIGHT*2/3 || rt >= BOARD_HEIGHT*2/3) ) {
1168                     if( (piece == WhitePawn || piece == WhiteQueen) && rt > BOARD_HEIGHT-2 ||
1169                          piece == WhiteKnight && rt > BOARD_HEIGHT-3) /* promotion mandatory */
1170                        cl.kind = promoChar == '=' ? IllegalMove : WhitePromotion;
1171                     else /* promotion optional, default is defer */
1172                        cl.kind = promoChar == '+' ? WhitePromotion : WhiteNonPromotion;
1173                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1174             } else {
1175                 if( (int) piece < (int) BlackWazir && (rf < BOARD_HEIGHT/3 || rt < BOARD_HEIGHT/3) ) {
1176                     if( (piece == BlackPawn || piece == BlackQueen) && rt < 1 ||
1177                          piece == BlackKnight && rt < 2 ) /* promotion obligatory */
1178                        cl.kind = promoChar == '=' ? IllegalMove : BlackPromotion;
1179                     else /* promotion optional, default is defer */
1180                        cl.kind = promoChar == '+' ? BlackPromotion : BlackNonPromotion;
1181                 } else cl.kind = promoChar == '+' ? IllegalMove : NormalMove;
1182             }
1183         }
1184     } else
1185     if (promoChar != NULLCHAR) {
1186         if(promoChar == '=') cl.kind = IllegalMove; else // [HGM] shogi: no deferred promotion outside Shogi
1187         if (cl.kind == WhitePromotion || cl.kind == BlackPromotion) {
1188             ChessSquare piece = CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(promoChar) : ToLower(promoChar));
1189             if(piece == EmptySquare)
1190                 cl.kind = ImpossibleMove; // non-existing piece
1191             if(gameInfo.variant == VariantSpartan && cl.kind == BlackPromotion ) {
1192                 if(promoChar != PieceToChar(BlackKing)) {
1193                     if(CheckTest(board, flags, rf, ff, rt, ft, FALSE)) cl.kind = IllegalMove; // [HGM] spartan: only promotion to King was possible
1194                     if(piece == BlackLance) cl.kind = ImpossibleMove;
1195                 } else { // promotion to King allowed only if we do not haave two yet
1196                     int r, f, kings = 0;
1197                     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) kings += (board[r][f] == BlackKing);
1198                     if(kings == 2) cl.kind = IllegalMove;
1199                 }
1200             } else if(piece == WhitePawn && rt == BOARD_HEIGHT-1 ||
1201                           piece == BlackPawn && rt == 0) cl.kind = IllegalMove; // cannot stay Pawn on last rank in any variant
1202             else if((piece == WhiteUnicorn || piece == BlackUnicorn) && gameInfo.variant == VariantKnightmate)
1203              cl.kind = IllegalMove; // promotion to Royal Knight not allowed
1204             else if((piece == WhiteKing || piece == BlackKing) && gameInfo.variant != VariantSuicide && gameInfo.variant != VariantGiveaway)
1205              cl.kind = IllegalMove; // promotion to King usually not allowed
1206         } else {
1207             cl.kind = IllegalMove;
1208         }
1209     }
1210     return cl.kind;
1211 }
1212
1213 typedef struct {
1214     int count;
1215 } MateTestClosure;
1216
1217 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
1218                                 int rf, int ff, int rt, int ft,
1219                                 VOIDSTAR closure));
1220
1221 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
1222      Board board;
1223      int flags;
1224      ChessMove kind;
1225      int rf, ff, rt, ft;
1226      VOIDSTAR closure;
1227 {
1228     register MateTestClosure *cl = (MateTestClosure *) closure;
1229
1230     cl->count++;
1231 }
1232
1233 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
1234 int MateTest(board, flags)
1235      Board board;
1236      int flags;
1237 {
1238     MateTestClosure cl;
1239     int inCheck, r, f, myPieces=0, hisPieces=0, nrKing=0;
1240     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
1241
1242     for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
1243         // [HGM] losers: Count pieces and kings, to detect other unorthodox winning conditions
1244         nrKing += (board[r][f] == king);   // stm has king
1245         if( board[r][f] != EmptySquare ) {
1246             if((int)board[r][f] <= (int)king && (int)board[r][f] >= (int)king - (int)WhiteKing + (int)WhitePawn)
1247                  myPieces++;
1248             else hisPieces++;
1249         }
1250     }
1251     if(appData.debugMode) fprintf(debugFP, "MateTest: K=%d, my=%d, his=%d\n", nrKing, myPieces, hisPieces);
1252     switch(gameInfo.variant) { // [HGM] losers: extinction wins
1253         case VariantShatranj:
1254                 if(hisPieces == 1) return myPieces > 1 ? MT_BARE : MT_DRAW;
1255         default:
1256                 break;
1257         case VariantAtomic:
1258                 if(nrKing == 0) return MT_NOKING;
1259                 break;
1260         case VariantLosers:
1261                 if(myPieces == 1) return MT_BARE;
1262     }
1263     cl.count = 0;
1264     inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare);
1265     // [HGM] 3check: yet to do!
1266     if (cl.count > 0) {
1267         return inCheck ? MT_CHECK : MT_NONE;
1268     } else {
1269         if(gameInfo.holdingsWidth && gameInfo.variant != VariantSuper && gameInfo.variant != VariantGreat
1270                                                                       && gameInfo.variant != VariantGrand) { // drop game
1271             int r, f, n, holdings = flags & F_WHITE_ON_MOVE ? BOARD_WIDTH-1 : 0;
1272             for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) if(board[r][f] == EmptySquare) // all empty squares
1273                 for(n=0; n<BOARD_HEIGHT; n++) // all pieces in hand
1274                     if(board[n][holdings] != EmptySquare) {
1275                         int moveType = LegalDrop(board, flags, board[n][holdings], r, f);
1276                         if(moveType == WhiteDrop || moveType == BlackDrop) return (inCheck ? MT_CHECK : MT_NONE); // we have legal drop
1277                     }
1278         }
1279         if(gameInfo.variant == VariantSuicide) // [HGM] losers: always stalemate, since no check, but result varies
1280                 return myPieces == hisPieces ? MT_STALEMATE :
1281                                         myPieces > hisPieces ? MT_STAINMATE : MT_STEALMATE;
1282         else if(gameInfo.variant == VariantLosers) return inCheck ? MT_TRICKMATE : MT_STEALMATE;
1283         else if(gameInfo.variant == VariantGiveaway) return MT_STEALMATE; // no check exists, stalemated = win
1284
1285         return inCheck ? MT_CHECKMATE
1286                        : (gameInfo.variant == VariantXiangqi || gameInfo.variant == VariantShatranj) ?
1287                           MT_STAINMATE : MT_STALEMATE;
1288     }
1289 }
1290
1291
1292 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
1293                                     int rf, int ff, int rt, int ft,
1294                                     VOIDSTAR closure));
1295
1296 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
1297      Board board;
1298      int flags;
1299      ChessMove kind;
1300      int rf, ff, rt, ft;
1301      VOIDSTAR closure;
1302 {
1303     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
1304     int wildCard = FALSE; ChessSquare piece = board[rf][ff];
1305
1306     // [HGM] wild: for wild-card pieces rt and rf are dummies
1307     if(piece == WhiteFalcon || piece == BlackFalcon ||
1308        piece == WhiteCobra  || piece == BlackCobra)
1309         wildCard = TRUE;
1310
1311     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]
1312          || PieceToChar(board[rf][ff]) == '~'
1313               && cl->pieceIn == (ChessSquare)(DEMOTED board[rf][ff])
1314                                                                       ) &&
1315         (cl->rfIn == -1 || cl->rfIn == rf) &&
1316         (cl->ffIn == -1 || cl->ffIn == ff) &&
1317         (cl->rtIn == -1 || cl->rtIn == rt || wildCard) &&
1318         (cl->ftIn == -1 || cl->ftIn == ft || wildCard)) {
1319
1320         cl->count++;
1321         if(cl->count == 1 || board[rt][ft] != EmptySquare) {
1322           // [HGM] oneclick: if multiple moves, be sure we remember capture
1323           cl->piece = board[rf][ff];
1324           cl->rf = rf;
1325           cl->ff = ff;
1326           cl->rt = wildCard ? cl->rtIn : rt;
1327           cl->ft = wildCard ? cl->ftIn : ft;
1328           cl->kind = kind;
1329         }
1330         cl->captures += (board[rt][ft] != EmptySquare); // [HGM] oneclick: count captures
1331     }
1332 }
1333
1334 void Disambiguate(board, flags, closure)
1335      Board board;
1336      int flags;
1337      DisambiguateClosure *closure;
1338 {
1339     int illegal = 0; char c = closure->promoCharIn;
1340
1341     if(quickFlag) flags = flags & ~1 | quickFlag & 1; // [HGM] speed: in quick mode quickFlag specifies side-to-move.
1342     closure->count = closure->captures = 0;
1343     closure->rf = closure->ff = closure->rt = closure->ft = 0;
1344     closure->kind = ImpossibleMove;
1345     if (appData.debugMode) {
1346         fprintf(debugFP, "Disambiguate in:  %d(%d,%d)-(%d,%d) = %d (%c)\n",
1347                              closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn,
1348                              closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-');
1349     }
1350     rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square
1351     fFilter = closure->ftIn;
1352     if(quickFlag) { // [HGM] speed: try without check test first, because if that is not ambiguous, we are happy
1353         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1354         if(closure->count > 1) { // gamble did not pay off. retry with check test to resolve ambiguity
1355             closure->count = closure->captures = 0;
1356             closure->rf = closure->ff = closure->rt = closure->ft = 0;
1357             closure->kind = ImpossibleMove;
1358             GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1359         }
1360     } else
1361     GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type
1362     if (closure->count == 0) {
1363         /* See if it's an illegal move due to check */
1364         illegal = 1;
1365         GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn);
1366         if (closure->count == 0) {
1367             /* No, it's not even that */
1368     if (appData.debugMode) { int i, j;
1369         for(i=BOARD_HEIGHT-1; i>=0; i--) {
1370                 for(j=0; j<BOARD_WIDTH; j++)
1371                         fprintf(debugFP, "%3d", (int) board[i][j]);
1372                 fprintf(debugFP, "\n");
1373         }
1374     }
1375             return;
1376         }
1377     }
1378
1379     if (c == 'x') c = NULLCHAR; // get rid of any 'x' (which should never happen?)
1380     if(gameInfo.variant == VariantSChess && c && c != '=' && closure->piece != WhitePawn && closure->piece != BlackPawn) {
1381         if(closure->piece < BlackPawn) { // white
1382             if(closure->rf != 0) closure->kind = IllegalMove; // must be on back rank
1383             if(board[PieceToNumber(CharToPiece(ToUpper(c)))][BOARD_WIDTH-2] == 0) closure->kind = ImpossibleMove;// must be in stock
1384         } else {
1385             if(closure->rf != BOARD_HEIGHT-1) closure->kind = IllegalMove;
1386             if(board[BOARD_HEIGHT-1-PieceToNumber(CharToPiece(ToLower(c)))][1] == 0) closure->kind = ImpossibleMove;
1387         }
1388     } else
1389     if(gameInfo.variant == VariantShogi) {
1390         /* [HGM] Shogi promotions. On input, '=' means defer, '+' promote. Afterwards, c is set to '+' for promotions, NULL other */
1391         if(closure->rfIn != DROP_RANK && closure->kind == NormalMove) {
1392             ChessSquare piece = closure->piece;
1393             if (c == 'd' && (piece == WhiteRook   || piece == BlackRook)   ||
1394                 c == 'h' && (piece == WhiteBishop || piece == BlackBishop) ||
1395                 c == 'g' && (piece <= WhiteFerz || piece <= BlackFerz && piece >= BlackPawn) )
1396                    c = '+'; // allowed ICS notations
1397             if(c != NULLCHAR && c != '+' && c != '=') closure->kind = IllegalMove; // otherwise specifying a piece is illegal
1398             else if(flags & F_WHITE_ON_MOVE) {
1399                 if( (int) piece < (int) WhiteWazir &&
1400                      (closure->rf >= BOARD_HEIGHT-(BOARD_HEIGHT/3) || closure->rt >= BOARD_HEIGHT-(BOARD_HEIGHT/3)) ) {
1401                     if( (piece == WhitePawn || piece == WhiteQueen) && closure->rt > BOARD_HEIGHT-2 ||
1402                          piece == WhiteKnight && closure->rt > BOARD_HEIGHT-3) /* promotion mandatory */
1403                        closure->kind = c == '=' ? IllegalMove : WhitePromotion;
1404                     else /* promotion optional, default is defer */
1405                        closure->kind = c == '+' ? WhitePromotion : WhiteNonPromotion; 
1406                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1407             } else {
1408                 if( (int) piece < (int) BlackWazir && (closure->rf < BOARD_HEIGHT/3 || closure->rt < BOARD_HEIGHT/3) ) {
1409                     if( (piece == BlackPawn || piece == BlackQueen) && closure->rt < 1 ||
1410                          piece == BlackKnight && closure->rt < 2 ) /* promotion obligatory */
1411                        closure->kind = c == '=' ? IllegalMove : BlackPromotion;
1412                     else /* promotion optional, default is defer */
1413                        closure->kind = c == '+' ? BlackPromotion : BlackNonPromotion;
1414                 } else closure->kind = c == '+' ? IllegalMove : NormalMove;
1415             }
1416         }
1417         if(closure->kind == WhitePromotion || closure->kind == BlackPromotion) c = '+'; else
1418         if(closure->kind == WhiteNonPromotion || closure->kind == BlackNonPromotion) c = '=';
1419     } else
1420     if (closure->kind == WhitePromotion || closure->kind == BlackPromotion) {
1421         if(c == NULLCHAR) { // missing promoChar on mandatory promotion; use default for variant
1422             if(gameInfo.variant == VariantShatranj || gameInfo.variant == VariantCourier || gameInfo.variant == VariantMakruk)
1423                 c = PieceToChar(BlackFerz);
1424             else if(gameInfo.variant == VariantGreat)
1425                 c = PieceToChar(BlackMan);
1426             else if(gameInfo.variant == VariantGrand)
1427                     closure->kind = closure->rt != 0 && closure->rt != BOARD_HEIGHT-1 ? NormalMove : AmbiguousMove; // no default in Grand Chess
1428             else
1429                 c = PieceToChar(BlackQueen);
1430         } else if(c == '=') closure->kind = IllegalMove; // no deferral outside Shogi
1431     } else if (c != NULLCHAR) closure->kind = IllegalMove;
1432
1433     closure->promoChar = ToLower(c); // this can be NULLCHAR! Note we keep original promoChar even if illegal.
1434     if(c != '+' && c != '=' && c != NULLCHAR && CharToPiece(flags & F_WHITE_ON_MOVE ? ToUpper(c) : ToLower(c)) == EmptySquare)
1435         closure->kind = ImpossibleMove; // but we cannot handle non-existing piece types!
1436     if (closure->count > 1) {
1437         closure->kind = AmbiguousMove;
1438     }
1439     if (illegal) {
1440         /* Note: If more than one illegal move matches, but no legal
1441            moves, we return IllegalMove, not AmbiguousMove.  Caller
1442            can look at closure->count to detect this.
1443         */
1444         closure->kind = IllegalMove;
1445     }
1446     if (appData.debugMode) {
1447         fprintf(debugFP, "Disambiguate out: %d(%d,%d)-(%d,%d) = %d (%c)\n",
1448         closure->piece,closure->ff,closure->rf,closure->ft,closure->rt,closure->promoChar,
1449         closure->promoChar >= ' ' ? closure->promoChar:'-');
1450     }
1451 }
1452
1453
1454 typedef struct {
1455     /* Input */
1456     ChessSquare piece;
1457     int rf, ff, rt, ft;
1458     /* Output */
1459     ChessMove kind;
1460     int rank;
1461     int file;
1462     int either;
1463 } CoordsToAlgebraicClosure;
1464
1465 extern void CoordsToAlgebraicCallback P((Board board, int flags,
1466                                          ChessMove kind, int rf, int ff,
1467                                          int rt, int ft, VOIDSTAR closure));
1468
1469 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
1470      Board board;
1471      int flags;
1472      ChessMove kind;
1473      int rf, ff, rt, ft;
1474      VOIDSTAR closure;
1475 {
1476     register CoordsToAlgebraicClosure *cl =
1477       (CoordsToAlgebraicClosure *) closure;
1478
1479     if ((rt == cl->rt && ft == cl->ft || rt == rf && ft == ff) && // [HGM] null move matches any toSquare
1480         (board[rf][ff] == cl->piece
1481          || PieceToChar(board[rf][ff]) == '~' &&
1482             (ChessSquare) (DEMOTED board[rf][ff]) == cl->piece)
1483                                      ) {
1484         if (rf == cl->rf) {
1485             if (ff == cl->ff) {
1486                 cl->kind = kind; /* this is the move we want */
1487             } else {
1488                 cl->file++; /* need file to rule out this move */
1489             }
1490         } else {
1491             if (ff == cl->ff) {
1492                 cl->rank++; /* need rank to rule out this move */
1493             } else {
1494                 cl->either++; /* rank or file will rule out this move */
1495             }
1496         }
1497     }
1498 }
1499
1500 /* Convert coordinates to normal algebraic notation.
1501    promoChar must be NULLCHAR or 'x' if not a promotion.
1502 */
1503 ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out)
1504      Board board;
1505      int flags;
1506      int rf, ff, rt, ft;
1507      int promoChar;
1508      char out[MOVE_LEN];
1509 {
1510     ChessSquare piece;
1511     ChessMove kind;
1512     char *outp = out, c;
1513     CoordsToAlgebraicClosure cl;
1514
1515     if (rf == DROP_RANK) {
1516         if(ff == EmptySquare) { strncpy(outp, "--",3); return NormalMove; } // [HGM] pass
1517         /* Bughouse piece drop */
1518         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
1519         *outp++ = '@';
1520         *outp++ = ft + AAA;
1521         if(rt+ONE <= '9')
1522            *outp++ = rt + ONE;
1523         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1524         *outp = NULLCHAR;
1525         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
1526     }
1527
1528     if (promoChar == 'x') promoChar = NULLCHAR;
1529     piece = board[rf][ff];
1530     if(PieceToChar(piece)=='~') piece = (ChessSquare)(DEMOTED piece);
1531
1532   if (appData.debugMode)
1533           fprintf(debugFP, "CoordsToAlgebraic, piece=%d (%d,%d)-(%d,%d) %c\n", (int)piece,ff,rf,ft,rt,promoChar >= ' ' ? promoChar : '-');
1534     switch (piece) {
1535       case WhitePawn:
1536       case BlackPawn:
1537         kind = LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1538         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1539             /* Keep short notation if move is illegal only because it
1540                leaves the player in check, but still return IllegalMove */
1541             kind = LegalityTest(board, flags|F_IGNORE_CHECK, rf, ff, rt, ft, promoChar);
1542             if (kind == IllegalMove) break;
1543             kind = IllegalMove;
1544         }
1545         /* Pawn move */
1546         *outp++ = ff + AAA;
1547         if (ff == ft && board[rt][ft] == EmptySquare) { /* [HGM] Xiangqi has straight noncapts! */
1548             /* Non-capture; use style "e5" */
1549             if(rt+ONE <= '9')
1550                *outp++ = rt + ONE;
1551             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1552         } else {
1553             /* Capture; use style "exd5" */
1554             if(gameInfo.variant != VariantXiangqi || board[rt][ft] != EmptySquare )
1555             *outp++ = 'x';  /* [HGM] Xiangqi has sideway noncaptures across river! */
1556             *outp++ = ft + AAA;
1557             if(rt+ONE <= '9')
1558                *outp++ = rt + ONE;
1559             else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1560         }
1561         /* Use promotion suffix style "=Q" */
1562         *outp = NULLCHAR;
1563   if (appData.debugMode)
1564           fprintf(debugFP, "movetype=%d, promochar=%d=%c\n", (int)kind, promoChar, promoChar >= ' ' ? promoChar : '-');
1565         if (promoChar != NULLCHAR) {
1566             if(gameInfo.variant == VariantShogi) {
1567                 /* [HGM] ... but not in Shogi! */
1568                 *outp++ = promoChar == '=' ? '=' : '+';
1569             } else {
1570                 *outp++ = '=';
1571                 *outp++ = ToUpper(promoChar);
1572             }
1573             *outp = NULLCHAR;
1574         }
1575         return kind;
1576
1577
1578       case WhiteKing:
1579       case BlackKing:
1580         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
1581         /* Code added by Tord:  FRC castling. */
1582         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
1583            (piece == BlackKing && board[rt][ft] == BlackRook)) {
1584           if(ft > ff)
1585             safeStrCpy(out, "O-O", MOVE_LEN);
1586           else
1587             safeStrCpy(out, "O-O-O", MOVE_LEN);
1588           return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1589         }
1590         /* End of code added by Tord */
1591         /* Test for castling or ICS wild castling */
1592         /* Use style "O-O" (oh-oh) for PGN compatibility */
1593         else if (rf == rt &&
1594             rf == ((piece == WhiteKing) ? 0 : BOARD_HEIGHT-1) &&
1595             (ft - ff > 1 || ff - ft > 1) &&  // No castling if legal King move (on narrow boards!)
1596             ((ff == BOARD_WIDTH>>1 && (ft == BOARD_LEFT+2 || ft == BOARD_RGHT-2)) ||
1597              (ff == (BOARD_WIDTH-1)>>1 && (ft == BOARD_LEFT+1 || ft == BOARD_RGHT-3)))) {
1598             if(ft==BOARD_LEFT+1 || ft==BOARD_RGHT-2)
1599               snprintf(out, MOVE_LEN, "O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1600             else
1601               snprintf(out, MOVE_LEN, "O-O-O%c%c", promoChar ? '/' : 0, ToUpper(promoChar));
1602
1603             /* This notation is always unambiguous, unless there are
1604                kings on both the d and e files, with "wild castling"
1605                possible for the king on the d file and normal castling
1606                possible for the other.  ICS rules for wild 9
1607                effectively make castling illegal for either king in
1608                this situation.  So I am not going to worry about it;
1609                I'll just generate an ambiguous O-O in this case.
1610             */
1611             return LegalityTest(board, flags, rf, ff, rt, ft, promoChar);
1612         }
1613
1614         /* else fall through */
1615       default:
1616         /* Piece move */
1617         cl.rf = rf;
1618         cl.ff = ff;
1619         cl.rt = rFilter = rt; // [HGM] speed: filter on to-square
1620         cl.ft = fFilter = ft;
1621         cl.piece = piece;
1622         cl.kind = IllegalMove;
1623         cl.rank = cl.file = cl.either = 0;
1624         c = PieceToChar(piece) ;
1625         GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed
1626
1627         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
1628             /* Generate pretty moves for moving into check, but
1629                still return IllegalMove.
1630             */
1631             GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece));
1632             if (cl.kind == IllegalMove) break;
1633             cl.kind = IllegalMove;
1634         }
1635
1636         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
1637            else "Ngf3" or "Ngxf7",
1638            else "N1f3" or "N5xf7",
1639            else "Ng1f3" or "Ng5xf7".
1640         */
1641         if( c == '~' || c == '+') {
1642            /* [HGM] print nonexistent piece as its demoted version */
1643            piece = (ChessSquare) (DEMOTED piece);
1644         }
1645         if(c=='+') *outp++ = c;
1646         *outp++ = ToUpper(PieceToChar(piece));
1647
1648         if (cl.file || (cl.either && !cl.rank)) {
1649             *outp++ = ff + AAA;
1650         }
1651         if (cl.rank) {
1652             if(rf+ONE <= '9')
1653                 *outp++ = rf + ONE;
1654             else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1655         }
1656
1657         if(board[rt][ft] != EmptySquare)
1658           *outp++ = 'x';
1659
1660         *outp++ = ft + AAA;
1661         if(rt+ONE <= '9')
1662            *outp++ = rt + ONE;
1663         else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1664         if (gameInfo.variant == VariantShogi) {
1665             /* [HGM] in Shogi non-pawns can promote */
1666             *outp++ = promoChar; // Don't bother to correct move type, return value is never used!
1667         }
1668         else if (gameInfo.variant != VariantSuper && promoChar && 
1669                  (piece == WhiteLance || piece == BlackLance) ) { // Lance sometimes represents Pawn
1670             *outp++ = '=';
1671             *outp++ = ToUpper(promoChar);
1672         }
1673         else if (gameInfo.variant == VariantSChess && promoChar) { // and in S-Chess we have gating
1674             *outp++ = '/';
1675             *outp++ = ToUpper(promoChar);
1676         }
1677         *outp = NULLCHAR;
1678         return cl.kind;
1679         
1680       case EmptySquare:
1681         /* Moving a nonexistent piece */
1682         break;
1683     }
1684
1685     /* Not a legal move, even ignoring check.
1686        If there was a piece on the from square,
1687        use style "Ng1g3" or "Ng1xe8";
1688        if there was a pawn or nothing (!),
1689        use style "g1g3" or "g1xe8".  Use "x"
1690        if a piece was on the to square, even
1691        a piece of the same color.
1692     */
1693     outp = out;
1694     c = 0;
1695     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1696         int r, f;
1697       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<=BOARD_RGHT; f++)
1698                 c += (board[r][f] == piece); // count on-board pieces of given type
1699         *outp++ = ToUpper(PieceToChar(piece));
1700     }
1701   if(c != 1) { // [HGM] but if there is only one piece of the mentioned type, no from-square, thank you!
1702     *outp++ = ff + AAA;
1703     if(rf+ONE <= '9')
1704        *outp++ = rf + ONE;
1705     else { *outp++ = (rf+ONE-'0')/10 + '0';*outp++ = (rf+ONE-'0')%10 + '0'; }
1706   }
1707     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1708     *outp++ = ft + AAA;
1709     if(rt+ONE <= '9')
1710        *outp++ = rt + ONE;
1711     else { *outp++ = (rt+ONE-'0')/10 + '0';*outp++ = (rt+ONE-'0')%10 + '0'; }
1712     /* Use promotion suffix style "=Q" */
1713     if (promoChar != NULLCHAR && promoChar != 'x') {
1714         *outp++ = '=';
1715         *outp++ = ToUpper(promoChar);
1716     }
1717     *outp = NULLCHAR;
1718
1719     return IllegalMove;
1720 }
1721
1722 // [HGM] XQ: the following code serves to detect perpetual chasing (Asian rules)
1723
1724 typedef struct {
1725     /* Input */
1726     int rf, ff, rt, ft;
1727     /* Output */
1728     int recaptures;
1729 } ChaseClosure;
1730
1731 // I guess the following variables logically belong in the closure too, but I was too lazy and used globals
1732
1733 int preyStackPointer, chaseStackPointer;
1734
1735 struct {
1736 unsigned char rf, ff, rt, ft;
1737 } chaseStack[100];
1738
1739 struct {
1740 unsigned char rank, file;
1741 } preyStack[100];
1742
1743
1744
1745
1746 // there are three new callbacks for use with GenLegal: for adding captures, deleting them, and finding a recapture
1747
1748 extern void AtacksCallback P((Board board, int flags, ChessMove kind,
1749                                 int rf, int ff, int rt, int ft,
1750                                 VOIDSTAR closure));
1751
1752 void AttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1753      Board board;
1754      int flags;
1755      ChessMove kind;
1756      int rf, ff, rt, ft;
1757      VOIDSTAR closure;
1758 {   // For adding captures that can lead to chase indictment to the chaseStack
1759     if(board[rt][ft] == EmptySquare) return;                               // non-capture
1760     if(board[rt][ft] == WhitePawn && rt <  BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1761     if(board[rt][ft] == BlackPawn && rt >= BOARD_HEIGHT/2) return;         // Pawn before river can be chased
1762     if(board[rf][ff] == WhitePawn  || board[rf][ff] == BlackPawn)  return; // Pawns are allowed to chase
1763     if(board[rf][ff] == WhiteWazir || board[rf][ff] == BlackWazir) return; // King is allowed to chase
1764     // move cannot be excluded from being a chase trivially (based on attacker and victim); save it on chaseStack
1765     chaseStack[chaseStackPointer].rf = rf;
1766     chaseStack[chaseStackPointer].ff = ff;
1767     chaseStack[chaseStackPointer].rt = rt;
1768     chaseStack[chaseStackPointer].ft = ft;
1769     chaseStackPointer++;
1770 }
1771
1772 extern void ExistingAtacksCallback P((Board board, int flags, ChessMove kind,
1773                                 int rf, int ff, int rt, int ft,
1774                                 VOIDSTAR closure));
1775
1776 void ExistingAttacksCallback(board, flags, kind, rf, ff, rt, ft, closure)
1777      Board board;
1778      int flags;
1779      ChessMove kind;
1780      int rf, ff, rt, ft;
1781      VOIDSTAR closure;
1782 {   // for removing pre-exsting captures from the chaseStack, to be left with newly created ones
1783     int i;
1784     register ChaseClosure *cl = (ChaseClosure *) closure; //closure tells us the move played in the repeat loop
1785
1786     if(board[rt][ft] == EmptySquare) return; // no capture
1787     if(rf == cl->rf && ff == cl->ff) { // attacks with same piece from new position are not considered new
1788         rf = cl->rt; ff = cl->ft;      // doctor their fromSquare so they will be recognized in chaseStack
1789     }
1790     // search move in chaseStack, and delete it if it occurred there (as we know now it is not a new capture)
1791     for(i=0; i<chaseStackPointer; i++) {
1792         if(chaseStack[i].rf == rf && chaseStack[i].ff == ff &&
1793            chaseStack[i].rt == rt && chaseStack[i].ft == ft   ) {
1794             // move found on chaseStack, delete it by overwriting with move popped from top of chaseStack
1795             chaseStack[i] = chaseStack[--chaseStackPointer];
1796             break;
1797         }
1798     }
1799 }
1800
1801 extern void ProtectedCallback P((Board board, int flags, ChessMove kind,
1802                                 int rf, int ff, int rt, int ft,
1803                                 VOIDSTAR closure));
1804
1805 void ProtectedCallback(board, flags, kind, rf, ff, rt, ft, closure)
1806      Board board;
1807      int flags;
1808      ChessMove kind;
1809      int rf, ff, rt, ft;
1810      VOIDSTAR closure;
1811 {   // for determining if a piece (given through the closure) is protected
1812     register ChaseClosure *cl = (ChaseClosure *) closure; // closure tells us where to recapture
1813
1814     if(rt == cl->rt && ft == cl->ft) cl->recaptures++;    // count legal recaptures to this square
1815     if(appData.debugMode && board[rt][ft] != EmptySquare)
1816         fprintf(debugFP, "try %c%c%c%c=%d\n", ff+AAA, rf+ONE,ft+AAA, rt+ONE, cl->recaptures);
1817 }
1818
1819 extern char moveList[MAX_MOVES][MOVE_LEN];
1820
1821 int PerpetualChase(int first, int last)
1822 {   // this routine detects if the side to move in the 'first' position is perpetually chasing (when not checking)
1823     int i, j, k, tail;
1824     ChaseClosure cl;
1825     ChessSquare captured;
1826
1827     preyStackPointer = 0;        // clear stack of chased pieces
1828     for(i=first; i<last; i+=2) { // for all positions with same side to move
1829         if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i);
1830         chaseStackPointer = 0;   // clear stack that is going to hold possible chases
1831         // determine all captures possible after the move, and put them on chaseStack
1832         GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare);
1833         if(appData.debugMode) { int n;
1834             for(n=0; n<chaseStackPointer; n++)
1835                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1836                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1837             fprintf(debugFP, ": all capts\n");
1838         }
1839         // determine all captures possible before the move, and delete them from chaseStack
1840         cl.rf = moveList[i][1]-ONE; // prepare closure to pass move that led from i to i+1
1841         cl.ff = moveList[i][0]-AAA+BOARD_LEFT;
1842         cl.rt = moveList[i][3]-ONE;
1843         cl.ft = moveList[i][2]-AAA+BOARD_LEFT;
1844         GenLegal(boards[i],   PosFlags(i), ExistingAttacksCallback, &cl, EmptySquare);
1845         if(appData.debugMode) { int n;
1846             for(n=0; n<chaseStackPointer; n++)
1847                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1848                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1849             fprintf(debugFP, ": new capts after %c%c%c%c\n", cl.ff+AAA, cl.rf+ONE, cl.ft+AAA, cl.rt+ONE);
1850         }
1851         // chaseSack now contains all captures made possible by the move
1852         for(j=0; j<chaseStackPointer; j++) { // run through chaseStack to identify true chases
1853             int attacker = (int)boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1854             int victim   = (int)boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1855
1856             if(attacker >= (int) BlackPawn) attacker = BLACK_TO_WHITE attacker; // convert to white, as piecee type
1857             if(victim   >= (int) BlackPawn) victim   = BLACK_TO_WHITE victim;
1858
1859             if((attacker == WhiteKnight || attacker == WhiteCannon) && victim == WhiteRook)
1860                 continue; // C or H attack on R is always chase; leave on chaseStack
1861
1862             if(attacker == victim) {
1863                 if(LegalityTest(boards[i+1], PosFlags(i+1), chaseStack[j].rt,
1864                    chaseStack[j].ft, chaseStack[j].rf, chaseStack[j].ff, NULLCHAR) == NormalMove) {
1865                         // we can capture back with equal piece, so this is no chase but a sacrifice
1866                         chaseStack[j] = chaseStack[--chaseStackPointer]; // delete the capture from the chaseStack
1867                         j--; /* ! */ continue;
1868                 }
1869
1870             }
1871
1872             // the attack is on a lower piece, or on a pinned or blocked equal one
1873             // test if the victim is protected by a true protector. First make the capture.
1874             captured = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1875             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = boards[i+1][chaseStack[j].rf][chaseStack[j].ff];
1876             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = EmptySquare;
1877             // Then test if the opponent can recapture
1878             cl.recaptures = 0;         // prepare closure to pass recapture square and count moves to it
1879             cl.rt = chaseStack[j].rt;
1880             cl.ft = chaseStack[j].ft;
1881             if(appData.debugMode) {
1882                 fprintf(debugFP, "test if we can recapture %c%c\n", cl.ft+AAA, cl.rt+ONE);
1883             }
1884             GenLegal(boards[i+1], PosFlags(i+1), ProtectedCallback, &cl, EmptySquare); // try all moves
1885             // unmake the capture
1886             boards[i+1][chaseStack[j].rf][chaseStack[j].ff] = boards[i+1][chaseStack[j].rt][chaseStack[j].ft];
1887             boards[i+1][chaseStack[j].rt][chaseStack[j].ft] = captured;
1888             // if a recapture was found, piece is protected, and we are not chasing it.
1889             if(cl.recaptures) { // attacked piece was defended by true protector, no chase
1890                 chaseStack[j] = chaseStack[--chaseStackPointer]; // so delete from chaseStack
1891                 j--; /* ! */
1892             }
1893         }
1894         // chaseStack now contains all moves that chased
1895         if(appData.debugMode) { int n;
1896             for(n=0; n<chaseStackPointer; n++)
1897                 fprintf(debugFP, "%c%c%c%c ", chaseStack[n].ff+AAA, chaseStack[n].rf+ONE,
1898                                               chaseStack[n].ft+AAA, chaseStack[n].rt+ONE);
1899             fprintf(debugFP, ": chases\n");
1900         }
1901         if(i == first) { // copy all people chased by first move of repeat cycle to preyStack
1902             for(j=0; j<chaseStackPointer; j++) {
1903                 preyStack[j].rank = chaseStack[j].rt;
1904                 preyStack[j].file = chaseStack[j].ft;
1905             }
1906             preyStackPointer = chaseStackPointer;
1907         }
1908         tail = 0;
1909         for(j=0; j<chaseStackPointer; j++) {
1910             for(k=0; k<preyStackPointer; k++) {
1911                 // search the victim of each chase move on the preyStack (first occurrence)
1912                 if(chaseStack[j].ft == preyStack[k].file && chaseStack[j].rt == preyStack[k].rank ) {
1913                     if(k < tail) break; // piece was already identified as still being chased
1914                     preyStack[preyStackPointer] = preyStack[tail]; // move chased piece to bottom part of preyStack
1915                     preyStack[tail] = preyStack[k];                // by swapping
1916                     preyStack[k] = preyStack[preyStackPointer];
1917                     tail++;
1918                     break;
1919                 }
1920             }
1921         }
1922         preyStackPointer = tail; // keep bottom part of preyStack, popping pieces unchased on move i.
1923         if(appData.debugMode) { int n;
1924             for(n=0; n<preyStackPointer; n++)
1925                 fprintf(debugFP, "%c%c ", preyStack[n].file+AAA, preyStack[n].rank+ONE);
1926             fprintf(debugFP, "always chased upto ply %d\n", i);
1927         }
1928         // now adjust the location of the chased pieces according to opponent move
1929         for(j=0; j<preyStackPointer; j++) {
1930             if(preyStack[j].rank == moveList[i+1][1]-ONE &&
1931                preyStack[j].file == moveList[i+1][0]-AAA+BOARD_LEFT) {
1932                 preyStack[j].rank = moveList[i+1][3]-ONE;
1933                 preyStack[j].file = moveList[i+1][2]-AAA+BOARD_LEFT;
1934                 break;
1935             }
1936         }
1937     }
1938     return preyStackPointer; // if any piece was left on preyStack, it has been perpetually chased
1939 }