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