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