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