moves.c

   1 /*
   2  * moves.c - Move generation and checking
   3  * $Id: moves.c,v 2.1 2003/10/27 19:21:00 mann Exp $
   4  *
   5  * Copyright 1991 by Digital Equipment Corporation, Maynard, Massachusetts.
   6  * Enhancements Copyright 1992-95 Free Software Foundation, Inc.
   7  *
   8  * The following terms apply to Digital Equipment Corporation's copyright
   9  * interest in XBoard:
  10  * ------------------------------------------------------------------------
  11  * All Rights Reserved
  12  *
  13  * Permission to use, copy, modify, and distribute this software and its
  14  * documentation for any purpose and without fee is hereby granted,
  15  * provided that the above copyright notice appear in all copies and that
  16  * both that copyright notice and this permission notice appear in
  17  * supporting documentation, and that the name of Digital not be
  18  * used in advertising or publicity pertaining to distribution of the
  19  * software without specific, written prior permission.
  20  *
  21  * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  22  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  23  * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  24  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  25  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  26  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  27  * SOFTWARE.
  28  * ------------------------------------------------------------------------
  29  *
  30  * The following terms apply to the enhanced version of XBoard distributed
  31  * by the Free Software Foundation:
  32  * ------------------------------------------------------------------------
  33  * This program is free software; you can redistribute it and/or modify
  34  * it under the terms of the GNU General Public License as published by
  35  * the Free Software Foundation; either version 2 of the License, or
  36  * (at your option) any later version.
  37  *
  38  * This program is distributed in the hope that it will be useful,
  39  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  40  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  41  * GNU General Public License for more details.
  42  *
  43  * You should have received a copy of the GNU General Public License
  44  * along with this program; if not, write to the Free Software
  45  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  46  * ------------------------------------------------------------------------
  47  */
  48
  49 #include "config.h"
  50
  51 #include <stdio.h>
  52 #if HAVE_STRING_H
  53 # include <string.h>
  54 #else /* not HAVE_STRING_H */
  55 # include <strings.h>
  56 #endif /* not HAVE_STRING_H */
  57 #include "common.h"
  58 #include "backend.h"
  59 #include "moves.h"
  60 #include "parser.h"
  61
  62 int WhitePiece P((ChessSquare));
  63 int BlackPiece P((ChessSquare));
  64 int SameColor P((ChessSquare, ChessSquare));
  65
  66
  67 int WhitePiece(piece)
  68      ChessSquare piece;
  69 {
  70     return (int) piece >= (int) WhitePawn && (int) piece <= (int) WhiteKing;
  71 }
  72
  73 int BlackPiece(piece)
  74      ChessSquare piece;
  75 {
  76     return (int) piece >= (int) BlackPawn && (int) piece <= (int) BlackKing;
  77 }
  78
  79 int SameColor(piece1, piece2)
  80      ChessSquare piece1, piece2;
  81 {
  82     return ((int) piece1 >= (int) WhitePawn &&
  83             (int) piece1 <= (int) WhiteKing &&
  84             (int) piece2 >= (int) WhitePawn &&
  85             (int) piece2 <= (int) WhiteKing)
  86       ||   ((int) piece1 >= (int) BlackPawn &&
  87             (int) piece1 <= (int) BlackKing &&
  88             (int) piece2 >= (int) BlackPawn &&
  89             (int) piece2 <= (int) BlackKing);
  90 }
  91
  92 ChessSquare PromoPiece(moveType)
  93      ChessMove moveType;
  94 {
  95     switch (moveType) {
  96       default:
  97         return EmptySquare;
  98       case WhitePromotionQueen:
  99         return WhiteQueen;
 100       case BlackPromotionQueen:
 101         return BlackQueen;
 102       case WhitePromotionRook:
 103         return WhiteRook;
 104       case BlackPromotionRook:
 105         return BlackRook;
 106       case WhitePromotionBishop:
 107         return WhiteBishop;
 108       case BlackPromotionBishop:
 109         return BlackBishop;
 110       case WhitePromotionKnight:
 111         return WhiteKnight;
 112       case BlackPromotionKnight:
 113         return BlackKnight;
 114       case WhitePromotionKing:
 115         return WhiteKing;
 116       case BlackPromotionKing:
 117         return BlackKing;
 118     }
 119 }
 120
 121 ChessMove PromoCharToMoveType(whiteOnMove, promoChar)
 122      int whiteOnMove;
 123      int promoChar;
 124 {
 125     if (whiteOnMove) {
 126         switch (promoChar) {
 127           case 'n':
 128           case 'N':
 129             return WhitePromotionKnight;
 130           case 'b':
 131           case 'B':
 132             return WhitePromotionBishop;
 133           case 'r':
 134           case 'R':
 135             return WhitePromotionRook;
 136           case 'q':
 137           case 'Q':
 138             return WhitePromotionQueen;
 139           case 'k':
 140           case 'K':
 141             return WhitePromotionKing;
 142           case NULLCHAR:
 143           default:
 144             return NormalMove;
 145         }
 146     } else {
 147         switch (promoChar) {
 148           case 'n':
 149           case 'N':
 150             return BlackPromotionKnight;
 151           case 'b':
 152           case 'B':
 153             return BlackPromotionBishop;
 154           case 'r':
 155           case 'R':
 156             return BlackPromotionRook;
 157           case 'q':
 158           case 'Q':
 159             return BlackPromotionQueen;
 160           case 'k':
 161           case 'K':
 162             return BlackPromotionKing;
 163           case NULLCHAR:
 164           default:
 165             return NormalMove;
 166         }
 167     }
 168 }
 169
 170 char pieceToChar[] = {
 171     'P', 'N', 'B', 'R', 'Q', 'K',
 172     'p', 'n', 'b', 'r', 'q', 'k', 'x'
 173   };
 174
 175 char PieceToChar(p)
 176      ChessSquare p;
 177 {
 178     return pieceToChar[(int) p];
 179 }
 180
 181 ChessSquare CharToPiece(c)
 182      int c;
 183 {
 184     switch (c) {
 185       default:
 186       case 'x': return EmptySquare;
 187       case 'P': return WhitePawn;
 188       case 'R': return WhiteRook;
 189       case 'N': return WhiteKnight;
 190       case 'B': return WhiteBishop;
 191       case 'Q': return WhiteQueen;
 192       case 'K': return WhiteKing;
 193       case 'p': return BlackPawn;
 194       case 'r': return BlackRook;
 195       case 'n': return BlackKnight;
 196       case 'b': return BlackBishop;
 197       case 'q': return BlackQueen;
 198       case 'k': return BlackKing;
 199     }
 200 }
 201
 202 void CopyBoard(to, from)
 203      Board to, from;
 204 {
 205     int i, j;
 206
 207     for (i = 0; i < BOARD_SIZE; i++)
 208       for (j = 0; j < BOARD_SIZE; j++)
 209         to[i][j] = from[i][j];
 210 }
 211
 212 int CompareBoards(board1, board2)
 213      Board board1, board2;
 214 {
 215     int i, j;
 216
 217     for (i = 0; i < BOARD_SIZE; i++)
 218       for (j = 0; j < BOARD_SIZE; j++) {
 219           if (board1[i][j] != board2[i][j])
 220             return FALSE;
 221     }
 222     return TRUE;
 223 }
 224
 225
 226 /* Call callback once for each pseudo-legal move in the given
 227    position, except castling moves. A move is pseudo-legal if it is
 228    legal, or if it would be legal except that it leaves the king in
 229    check.  In the arguments, epfile is EP_NONE if the previous move
 230    was not a double pawn push, or the file 0..7 if it was, or
 231    EP_UNKNOWN if we don't know and want to allow all e.p. captures.
 232    Promotion moves generated are to Queen only.
 233 */
 234 void GenPseudoLegal(board, flags, epfile, callback, closure)
 235      Board board;
 236      int flags;
 237      int epfile;
 238      MoveCallback callback;
 239      VOIDSTAR closure;
 240 {
 241     int rf, ff;
 242     int i, j, d, s, fs, rs, rt, ft;
 243
 244     for (rf = 0; rf <= 7; rf++)
 245       for (ff = 0; ff <= 7; ff++) {
 246           if (flags & F_WHITE_ON_MOVE) {
 247               if (!WhitePiece(board[rf][ff])) continue;
 248           } else {
 249               if (!BlackPiece(board[rf][ff])) continue;
 250           }
 251           switch (board[rf][ff]) {
 252             case EmptySquare:
 253             default:
 254               /* can't happen */
 255               break;
 256
 257             case WhitePawn:
 258               if (rf < 7 && board[rf + 1][ff] == EmptySquare) {
 259                   callback(board, flags,
 260                            rf == 6 ? WhitePromotionQueen : NormalMove,
 261                            rf, ff, rf + 1, ff, closure);
 262               }
 263               if (rf == 1 && board[2][ff] == EmptySquare &&
 264                   board[3][ff] == EmptySquare) {
 265                   callback(board, flags, NormalMove,
 266                            rf, ff, 3, ff, closure);
 267               }
 268               for (s = -1; s <= 1; s += 2) {
 269                   if (rf < 7 && ff + s >= 0 && ff + s <= 7 &&
 270                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 271                        BlackPiece(board[rf + 1][ff + s]))) {
 272                       callback(board, flags,
 273                                rf == 6 ? WhitePromotionQueen : NormalMove,
 274                                rf, ff, rf + 1, ff + s, closure);
 275                   }
 276                   if (rf == 4) {
 277                       if (ff + s >= 0 && ff + s <= 7 &&
 278                           (epfile == ff + s || epfile == EP_UNKNOWN) &&
 279                           board[4][ff + s] == BlackPawn &&
 280                           board[5][ff + s] == EmptySquare) {
 281                           callback(board, flags, WhiteCapturesEnPassant,
 282                                    rf, ff, 5, ff + s, closure);
 283                       }
 284                   }
 285               }
 286               break;
 287
 288             case BlackPawn:
 289               if (rf > 0 && board[rf - 1][ff] == EmptySquare) {
 290                   callback(board, flags,
 291                            rf == 1 ? BlackPromotionQueen : NormalMove,
 292                            rf, ff, rf - 1, ff, closure);
 293               }
 294               if (rf == 6 && board[5][ff] == EmptySquare &&
 295                   board[4][ff] == EmptySquare) {
 296                   callback(board, flags, NormalMove,
 297                            rf, ff, 4, ff, closure);
 298               }
 299               for (s = -1; s <= 1; s += 2) {
 300                   if (rf > 0 && ff + s >= 0 && ff + s <= 7 &&
 301                       ((flags & F_KRIEGSPIEL_CAPTURE) ||
 302                        WhitePiece(board[rf - 1][ff + s]))) {
 303                       callback(board, flags,
 304                                rf == 1 ? BlackPromotionQueen : NormalMove,
 305                                rf, ff, rf - 1, ff + s, closure);
 306                   }
 307                   if (rf == 3) {
 308                       if (ff + s >= 0 && ff + s <= 7 &&
 309                           (epfile == ff + s || epfile == EP_UNKNOWN) &&
 310                           board[3][ff + s] == WhitePawn &&
 311                           board[2][ff + s] == EmptySquare) {
 312                           callback(board, flags, BlackCapturesEnPassant,
 313                                    rf, ff, 2, ff + s, closure);
 314                       }
 315                   }
 316               }
 317               break;
 318
 319             case WhiteKnight:
 320             case BlackKnight:
 321               for (i = -1; i <= 1; i += 2)
 322                 for (j = -1; j <= 1; j += 2)
 323                   for (s = 1; s <= 2; s++) {
 324                       rt = rf + i*s;
 325                       ft = ff + j*(3-s);
 326                       if (rt < 0 || rt > 7 || ft < 0 || ft > 7) continue;
 327                       if (SameColor(board[rf][ff], board[rt][ft])) continue;
 328                       callback(board, flags, NormalMove,
 329                                rf, ff, rt, ft, closure);
 330                   }
 331               break;
 332
 333             case WhiteBishop:
 334             case BlackBishop:
 335               for (rs = -1; rs <= 1; rs += 2)
 336                 for (fs = -1; fs <= 1; fs += 2)
 337                   for (i = 1;; i++) {
 338                       rt = rf + (i * rs);
 339                       ft = ff + (i * fs);
 340                       if (rt < 0 || rt > 7 || ft < 0 || ft > 7) break;
 341                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 342                       callback(board, flags, NormalMove,
 343                                rf, ff, rt, ft, closure);
 344                       if (board[rt][ft] != EmptySquare) break;
 345                   }
 346               break;
 347
 348             case WhiteRook:
 349             case BlackRook:
 350               for (d = 0; d <= 1; d++)
 351                 for (s = -1; s <= 1; s += 2)
 352                   for (i = 1;; i++) {
 353                       rt = rf + (i * s) * d;
 354                       ft = ff + (i * s) * (1 - d);
 355                       if (rt < 0 || rt > 7 || ft < 0 || ft > 7) break;
 356                       if (SameColor(board[rf][ff], board[rt][ft])) break;
 357                       callback(board, flags, NormalMove,
 358                                rf, ff, rt, ft, closure);
 359                       if (board[rt][ft] != EmptySquare) break;
 360                   }
 361               break;
 362
 363             case WhiteQueen:
 364             case BlackQueen:
 365               for (rs = -1; rs <= 1; rs++)
 366                 for (fs = -1; fs <= 1; fs++) {
 367                     if (rs == 0 && fs == 0) continue;
 368                     for (i = 1;; i++) {
 369                         rt = rf + (i * rs);
 370                         ft = ff + (i * fs);
 371                         if (rt < 0 || rt > 7 || ft < 0 || ft > 7) break;
 372                         if (SameColor(board[rf][ff], board[rt][ft])) break;
 373                         callback(board, flags, NormalMove,
 374                                  rf, ff, rt, ft, closure);
 375                         if (board[rt][ft] != EmptySquare) break;
 376                     }
 377                 }
 378               break;
 379
 380             case WhiteKing:
 381             case BlackKing:
 382               for (i = -1; i <= 1; i++)
 383                 for (j = -1; j <= 1; j++) {
 384                     if (i == 0 && j == 0) continue;
 385                     rt = rf + i;
 386                     ft = ff + j;
 387                     if (rt < 0 || rt > 7 || ft < 0 || ft > 7) continue;
 388                     if (SameColor(board[rf][ff], board[rt][ft])) continue;
 389                     callback(board, flags, NormalMove,
 390                              rf, ff, rt, ft, closure);
 391                 }
 392               break;
 393           }
 394       }
 395 }
 396
 397
 398 typedef struct {
 399     MoveCallback cb;
 400     VOIDSTAR cl;
 401 } GenLegalClosure;
 402
 403 extern void GenLegalCallback P((Board board, int flags, ChessMove kind,
 404                                 int rf, int ff, int rt, int ft,
 405                                 VOIDSTAR closure));
 406
 407 void GenLegalCallback(board, flags, kind, rf, ff, rt, ft, closure)
 408      Board board;
 409      int flags;
 410      ChessMove kind;
 411      int rf, ff, rt, ft;
 412      VOIDSTAR closure;
 413 {
 414     register GenLegalClosure *cl = (GenLegalClosure *) closure;
 415
 416     if (!(flags & F_IGNORE_CHECK) &&
 417         CheckTest(board, flags, rf, ff, rt, ft,
 418                   kind == WhiteCapturesEnPassant ||
 419                   kind == BlackCapturesEnPassant)) return;
 420     if (flags & F_ATOMIC_CAPTURE) {
 421       if (board[rt][ft] != EmptySquare ||
 422           kind == WhiteCapturesEnPassant || kind == BlackCapturesEnPassant) {
 423         int r, f;
 424         ChessSquare king = (flags & F_WHITE_ON_MOVE) ? WhiteKing : BlackKing;
 425         if (board[rf][ff] == king) return;
 426         for (r = rt-1; r <= rt+1; r++) {
 427           for (f = ft-1; f <= ft+1; f++) {
 428             if (r >= 0 && r <= 7 && f >= 0 && f <= 7 &&
 429                 board[r][f] == king) return;
 430           }
 431         }
 432       }
 433     }
 434     cl->cb(board, flags, kind, rf, ff, rt, ft, cl->cl);
 435 }
 436
 437
 438 typedef struct {
 439     int rf, ff, rt, ft;
 440     ChessMove kind;
 441 } LegalityTestClosure;
 442
 443
 444 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
 445    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
 446    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
 447    moves that would destroy your own king.  The CASTLE_OK flags are
 448    true if castling is not yet ruled out by a move of the king or
 449    rook.  Return TRUE if the player on move is currently in check and
 450    F_IGNORE_CHECK is not set.  */
 451 int GenLegal(board, flags, epfile, callback, closure)
 452      Board board;
 453      int flags;
 454      int epfile;
 455      MoveCallback callback;
 456      VOIDSTAR closure;
 457 {
 458     GenLegalClosure cl;
 459     int ff, ft;
 460     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
 461
 462     cl.cb = callback;
 463     cl.cl = closure;
 464     GenPseudoLegal(board, flags, epfile, GenLegalCallback, (VOIDSTAR) &cl);
 465
 466     if (!ignoreCheck &&
 467         CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE;
 468
 469     /* Generate castling moves */
 470     for (ff = 4; ff >= 3; ff-- /*ics wild 1*/) {
 471         if ((flags & F_WHITE_ON_MOVE) &&
 472             (flags & F_WHITE_KCASTLE_OK) &&
 473             board[0][ff] == WhiteKing &&
 474             board[0][ff + 1] == EmptySquare &&
 475             board[0][ff + 2] == EmptySquare &&
 476             board[0][6] == EmptySquare &&
 477             board[0][7] == WhiteRook &&
 478             (ignoreCheck ||
 479              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
 480               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
 481
 482             callback(board, flags,
 483                      ff==4 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
 484                      0, ff, 0, ff + 2, closure);
 485         }
 486         if ((flags & F_WHITE_ON_MOVE) &&
 487             (flags & F_WHITE_QCASTLE_OK) &&
 488             board[0][ff] == WhiteKing &&
 489             board[0][ff - 1] == EmptySquare &&
 490             board[0][ff - 2] == EmptySquare &&
 491             board[0][1] == EmptySquare &&
 492             board[0][0] == WhiteRook &&
 493             (ignoreCheck ||
 494              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
 495               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
 496
 497             callback(board, flags,
 498                      ff==4 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
 499                      0, ff, 0, ff - 2, closure);
 500         }
 501         if (!(flags & F_WHITE_ON_MOVE) &&
 502             (flags & F_BLACK_KCASTLE_OK) &&
 503             board[7][ff] == BlackKing &&
 504             board[7][ff + 1] == EmptySquare &&
 505             board[7][ff + 2] == EmptySquare &&
 506             board[7][6] == EmptySquare &&
 507             board[7][7] == BlackRook &&
 508             (ignoreCheck ||
 509              (!CheckTest(board, flags, 7, ff, 7, ff + 1, FALSE) &&
 510               !CheckTest(board, flags, 7, ff, 7, ff + 2, FALSE)))) {
 511
 512             callback(board, flags,
 513                      ff==4 ? BlackKingSideCastle : BlackKingSideCastleWild,
 514                      7, ff, 7, ff + 2, closure);
 515         }
 516         if (!(flags & F_WHITE_ON_MOVE) &&
 517             (flags & F_BLACK_QCASTLE_OK) &&
 518             board[7][ff] == BlackKing &&
 519             board[7][ff - 1] == EmptySquare &&
 520             board[7][ff - 2] == EmptySquare &&
 521             board[7][1] == EmptySquare &&
 522             board[7][0] == BlackRook &&
 523             (ignoreCheck ||
 524              (!CheckTest(board, flags, 7, ff, 7, ff - 1, FALSE) &&
 525               !CheckTest(board, flags, 7, ff, 7, ff - 1, FALSE)))) {
 526
 527             callback(board, flags,
 528                      ff==4 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
 529                      7, ff, 7, ff - 2, closure);
 530         }
 531     }
 532
 533     /* PUSH Fabien */
 534
 535     /* generate all potential FRC castling moves (KxR), ignoring flags */
 536
 537     if ((flags & F_WHITE_ON_MOVE) != 0) {
 538
 539        for (ff = 1; ff < 7; ff++) {
 540           if (board[0][ff] == WhiteKing) {
 541              for (ft = 0; ft < 8; ft++) {
 542                 if (board[0][ft] == WhiteRook) {
 543                    callback(board, flags,
 544                             (ft > ff) ? WhiteHSideCastleFR : WhiteASideCastleFR,
 545                             0, ff, 0, ft, closure);
 546                 }
 547              }
 548           }
 549        }
 550
 551     } else {
 552
 553        for (ff = 1; ff < 7; ff++) {
 554           if (board[7][ff] == BlackKing) {
 555              for (ft = 0; ft < 8; ft++) {
 556                 if (board[7][ft] == BlackRook) {
 557                    callback(board, flags,
 558                             (ft > ff) ? BlackHSideCastleFR : BlackASideCastleFR,
 559                             7, ff, 7, ft, closure);
 560                 }
 561              }
 562           }
 563        }
 564     }
 565
 566     /* POP Fabien */
 567
 568     return FALSE;
 569 }
 570
 571
 572 typedef struct {
 573     int rking, fking;
 574     int check;
 575 } CheckTestClosure;
 576
 577
 578 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
 579                                  int rf, int ff, int rt, int ft,
 580                                  VOIDSTAR closure));
 581
 582
 583 void CheckTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 584      Board board;
 585      int flags;
 586      ChessMove kind;
 587      int rf, ff, rt, ft;
 588      VOIDSTAR closure;
 589 {
 590     register CheckTestClosure *cl = (CheckTestClosure *) closure;
 591
 592     if (rt == cl->rking && ft == cl->fking) cl->check++;
 593 }
 594
 595
 596 /* If the player on move were to move from (rf, ff) to (rt, ft), would
 597    he leave himself in check?  Or if rf == -1, is the player on move
 598    in check now?  enPassant must be TRUE if the indicated move is an
 599    e.p. capture.  The possibility of castling out of a check along the
 600    back rank is not accounted for (i.e., we still return nonzero), as
 601    this is illegal anyway.  Return value is the number of times the
 602    king is in check. */
 603 int CheckTest(board, flags, rf, ff, rt, ft, enPassant)
 604      Board board;
 605      int flags;
 606      int rf, ff, rt, ft, enPassant;
 607 {
 608     CheckTestClosure cl;
 609     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
 610     ChessSquare captured = EmptySquare;
 611     /*  Suppress warnings on uninitialized variables    */
 612
 613     if (rf >= 0) {
 614         if (enPassant) {
 615             captured = board[rf][ft];
 616             board[rf][ft] = EmptySquare;
 617         } else {
 618             captured = board[rt][ft];
 619         }
 620         board[rt][ft] = board[rf][ff];
 621         board[rf][ff] = EmptySquare;
 622     }
 623
 624     /* For compatibility with ICS wild 9, we scan the board in the
 625        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
 626        and we test only whether that one is in check. */
 627     cl.check = 0;
 628     for (cl.fking = 0; cl.fking <= 7; cl.fking++)
 629         for (cl.rking = 0; cl.rking <= 7; cl.rking++) {
 630           if (board[cl.rking][cl.fking] == king) {
 631               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, -1,
 632                              CheckTestCallback, (VOIDSTAR) &cl);
 633               goto undo_move;  /* 2-level break */
 634           }
 635       }
 636
 637   undo_move:
 638
 639     if (rf >= 0) {
 640         board[rf][ff] = board[rt][ft];
 641         if (enPassant) {
 642             board[rf][ft] = captured;
 643             board[rt][ft] = EmptySquare;
 644         } else {
 645             board[rt][ft] = captured;
 646         }
 647     }
 648
 649     return cl.check;
 650 }
 651
 652
 653 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
 654                                     int rf, int ff, int rt, int ft,
 655                                     VOIDSTAR closure));
 656
 657 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 658      Board board;
 659      int flags;
 660      ChessMove kind;
 661      int rf, ff, rt, ft;
 662      VOIDSTAR closure;
 663 {
 664     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
 665
 666     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
 667       cl->kind = kind;
 668 }
 669
 670 ChessMove LegalityTest(board, flags, epfile, rf, ff, rt, ft, promoChar)
 671      Board board;
 672      int flags, epfile;
 673      int rf, ff, rt, ft, promoChar;
 674 {
 675     LegalityTestClosure cl;
 676
 677     cl.rf = rf;
 678     cl.ff = ff;
 679     cl.rt = rt;
 680     cl.ft = ft;
 681     cl.kind = IllegalMove;
 682     GenLegal(board, flags, epfile, LegalityTestCallback, (VOIDSTAR) &cl);
 683     if (promoChar != NULLCHAR && promoChar != 'x') {
 684         if (cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
 685             cl.kind =
 686               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0, promoChar);
 687         } else {
 688             cl.kind = IllegalMove;
 689         }
 690     }
 691     return cl.kind;
 692 }
 693
 694 typedef struct {
 695     int count;
 696 } MateTestClosure;
 697
 698 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
 699                                 int rf, int ff, int rt, int ft,
 700                                 VOIDSTAR closure));
 701
 702 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 703      Board board;
 704      int flags;
 705      ChessMove kind;
 706      int rf, ff, rt, ft;
 707      VOIDSTAR closure;
 708 {
 709     register MateTestClosure *cl = (MateTestClosure *) closure;
 710
 711     cl->count++;
 712 }
 713
 714 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
 715 int MateTest(board, flags, epfile)
 716      Board board;
 717      int flags, epfile;
 718 {
 719     MateTestClosure cl;
 720     int inCheck;
 721
 722     cl.count = 0;
 723     inCheck = GenLegal(board, flags, epfile, MateTestCallback, (VOIDSTAR) &cl);
 724     if (cl.count > 0) {
 725         return inCheck ? MT_CHECK : MT_NONE;
 726     } else {
 727         return inCheck ? MT_CHECKMATE : MT_STALEMATE;
 728     }
 729 }
 730
 731
 732 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
 733                                     int rf, int ff, int rt, int ft,
 734                                     VOIDSTAR closure));
 735
 736 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
 737      Board board;
 738      int flags;
 739      ChessMove kind;
 740      int rf, ff, rt, ft;
 741      VOIDSTAR closure;
 742 {
 743     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
 744
 745     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]) &&
 746         (cl->rfIn == -1 || cl->rfIn == rf) &&
 747         (cl->ffIn == -1 || cl->ffIn == ff) &&
 748         (cl->rtIn == -1 || cl->rtIn == rt) &&
 749         (cl->ftIn == -1 || cl->ftIn == ft)) {
 750
 751         cl->count++;
 752         cl->piece = board[rf][ff];
 753         cl->rf = rf;
 754         cl->ff = ff;
 755         cl->rt = rt;
 756         cl->ft = ft;
 757         cl->kind = kind;
 758     }
 759 }
 760
 761 void Disambiguate(board, flags, epfile, closure)
 762      Board board;
 763      int flags, epfile;
 764      DisambiguateClosure *closure;
 765 {
 766     int illegal = 0;
 767     closure->count = 0;
 768     closure->rf = closure->ff = closure->rt = closure->ft = 0;
 769     closure->kind = ImpossibleMove;
 770     GenLegal(board, flags, epfile, DisambiguateCallback, (VOIDSTAR) closure);
 771     if (closure->count == 0) {
 772         /* See if it's an illegal move due to check */
 773         illegal = 1;
 774         GenLegal(board, flags|F_IGNORE_CHECK, epfile, DisambiguateCallback,
 775                  (VOIDSTAR) closure);
 776         if (closure->count == 0) {
 777             /* No, it's not even that */
 778             return;
 779         }
 780     }
 781     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
 782         if (closure->kind == WhitePromotionQueen
 783             || closure->kind == BlackPromotionQueen) {
 784             closure->kind =
 785               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
 786                                   closure->promoCharIn);
 787         } else {
 788             closure->kind = IllegalMove;
 789         }
 790     }
 791     closure->promoChar = ToLower(PieceToChar(PromoPiece(closure->kind)));
 792     if (closure->promoChar == 'x') closure->promoChar = NULLCHAR;
 793     if (closure->count > 1) {
 794         closure->kind = AmbiguousMove;
 795     }
 796     if (illegal) {
 797         /* Note: If more than one illegal move matches, but no legal
 798            moves, we return IllegalMove, not AmbiguousMove.  Caller
 799            can look at closure->count to detect this.
 800         */
 801         closure->kind = IllegalMove;
 802     }
 803 }
 804
 805
 806 typedef struct {
 807     /* Input */
 808     ChessSquare piece;
 809     int rf, ff, rt, ft;
 810     /* Output */
 811     ChessMove kind;
 812     int rank;
 813     int file;
 814     int either;
 815 } CoordsToAlgebraicClosure;
 816
 817 extern void CoordsToAlgebraicCallback P((Board board, int flags,
 818                                          ChessMove kind, int rf, int ff,
 819                                          int rt, int ft, VOIDSTAR closure));
 820
 821 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
 822      Board board;
 823      int flags;
 824      ChessMove kind;
 825      int rf, ff, rt, ft;
 826      VOIDSTAR closure;
 827 {
 828     register CoordsToAlgebraicClosure *cl =
 829       (CoordsToAlgebraicClosure *) closure;
 830
 831     if (rt == cl->rt && ft == cl->ft &&
 832         board[rf][ff] == cl->piece) {
 833         if (rf == cl->rf) {
 834             if (ff == cl->ff) {
 835                 cl->kind = kind; /* this is the move we want */
 836             } else {
 837                 cl->file++; /* need file to rule out this move */
 838             }
 839         } else {
 840             if (ff == cl->ff) {
 841                 cl->rank++; /* need rank to rule out this move */
 842             } else {
 843                 cl->either++; /* rank or file will rule out this move */
 844             }
 845         }
 846     }
 847 }
 848
 849 /* Convert coordinates to normal algebraic notation.
 850    promoChar must be NULLCHAR or 'x' if not a promotion.
 851 */
 852 ChessMove CoordsToAlgebraic(board, flags, epfile,
 853                             rf, ff, rt, ft, promoChar, out)
 854      Board board;
 855      int flags, epfile;
 856      int rf, ff, rt, ft;
 857      int promoChar;
 858      char out[MOVE_LEN];
 859 {
 860     ChessSquare piece;
 861     ChessMove kind;
 862     char *outp = out;
 863     CoordsToAlgebraicClosure cl;
 864
 865     if (rf == DROP_RANK) {
 866         /* Bughouse piece drop */
 867         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
 868         *outp++ = '@';
 869         *outp++ = ft + 'a';
 870         *outp++ = rt + '1';
 871         *outp = NULLCHAR;
 872         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
 873     }
 874
 875     if (promoChar == 'x') promoChar = NULLCHAR;
 876     piece = board[rf][ff];
 877     switch (piece) {
 878       case WhitePawn:
 879       case BlackPawn:
 880         kind = LegalityTest(board, flags, epfile, rf, ff, rt, ft, promoChar);
 881         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
 882             /* Keep short notation if move is illegal only because it
 883                leaves the player in check, but still return IllegalMove */
 884             kind = LegalityTest(board, flags|F_IGNORE_CHECK, epfile,
 885                                rf, ff, rt, ft, promoChar);
 886             if (kind == IllegalMove) break;
 887             kind = IllegalMove;
 888         }
 889         /* Pawn move */
 890         *outp++ = ff + 'a';
 891         if (ff == ft) {
 892             /* Non-capture; use style "e5" */
 893             *outp++ = rt + '1';
 894         } else {
 895             /* Capture; use style "exd5" */
 896             *outp++ = 'x';
 897             *outp++ = ft + 'a';
 898             *outp++ = rt + '1';
 899         }
 900         /* Use promotion suffix style "=Q" */
 901         if (promoChar != NULLCHAR && promoChar != 'x') {
 902             *outp++ = '=';
 903             *outp++ = ToUpper(promoChar);
 904         }
 905         *outp = NULLCHAR;
 906         return kind;
 907
 908
 909       case WhiteKing:
 910       case BlackKing:
 911         /* Fabien moved code: FRC castling first (if KxR), wild castling second */
 912         /* Code added by Tord:  FRC castling. */
 913         if((piece == WhiteKing && board[rt][ft] == WhiteRook) ||
 914            (piece == BlackKing && board[rt][ft] == BlackRook)) {
 915           if(ft > ff) strcpy(out, "O-O"); else strcpy(out, "O-O-O");
 916             return LegalityTest(board, flags, epfile,
 917                                 rf, ff, rt, ft, promoChar);
 918         }
 919         /* End of code added by Tord */
 920         /* Test for castling or ICS wild castling */
 921         /* Use style "O-O" (oh-oh) for PGN compatibility */
 922         else if (rf == rt &&
 923             rf == ((piece == WhiteKing) ? 0 : 7) &&
 924             ((ff == 4 && (ft == 2 || ft == 6)) ||
 925              (ff == 3 && (ft == 1 || ft == 5)))) {
 926             switch (ft) {
 927               case 1:
 928               case 6:
 929                 strcpy(out, "O-O");
 930                 break;
 931               case 2:
 932               case 5:
 933                 strcpy(out, "O-O-O");
 934                 break;
 935             }
 936             /* This notation is always unambiguous, unless there are
 937                kings on both the d and e files, with "wild castling"
 938                possible for the king on the d file and normal castling
 939                possible for the other.  ICS rules for wild 9
 940                effectively make castling illegal for either king in
 941                this situation.  So I am not going to worry about it;
 942                I'll just generate an ambiguous O-O in this case.
 943             */
 944             return LegalityTest(board, flags, epfile,
 945                                 rf, ff, rt, ft, promoChar);
 946         }
 947
 948         /* else fall through */
 949
 950       default:
 951         /* Piece move */
 952         cl.rf = rf;
 953         cl.ff = ff;
 954         cl.rt = rt;
 955         cl.ft = ft;
 956         cl.piece = piece;
 957         cl.kind = IllegalMove;
 958         cl.rank = cl.file = cl.either = 0;
 959         GenLegal(board, flags, epfile,
 960                  CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
 961
 962         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
 963             /* Generate pretty moves for moving into check, but
 964                still return IllegalMove.
 965             */
 966             GenLegal(board, flags|F_IGNORE_CHECK, epfile,
 967                      CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
 968             if (cl.kind == IllegalMove) break;
 969             cl.kind = IllegalMove;
 970         }
 971
 972         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
 973            else "Ngf3" or "Ngxf7",
 974            else "N1f3" or "N5xf7",
 975            else "Ng1f3" or "Ng5xf7".
 976         */
 977         *outp++ = ToUpper(PieceToChar(piece));
 978
 979         if (cl.file || (cl.either && !cl.rank)) {
 980             *outp++ = ff + 'a';
 981         }
 982         if (cl.rank) {
 983             *outp++ = rf + '1';
 984         }
 985
 986         if(board[rt][ft] != EmptySquare)
 987           *outp++ = 'x';
 988
 989         *outp++ = ft + 'a';
 990         *outp++ = rt + '1';
 991         *outp = NULLCHAR;
 992         return cl.kind;
 993
 994       case EmptySquare:
 995         /* Moving a nonexistent piece */
 996         break;
 997     }
 998
 999     /* Not a legal move, even ignoring check.
1000        If there was a piece on the from square,
1001        use style "Ng1g3" or "Ng1xe8";
1002        if there was a pawn or nothing (!),
1003        use style "g1g3" or "g1xe8".  Use "x"
1004        if a piece was on the to square, even
1005        a piece of the same color.
1006     */
1007     outp = out;
1008     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
1009         *outp++ = ToUpper(PieceToChar(piece));
1010     }
1011     *outp++ = ff + 'a';
1012     *outp++ = rf + '1';
1013     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
1014     *outp++ = ft + 'a';
1015     *outp++ = rt + '1';
1016     /* Use promotion suffix style "=Q" */
1017     if (promoChar != NULLCHAR && promoChar != 'x') {
1018         *outp++ = '=';
1019         *outp++ = ToUpper(promoChar);
1020     }
1021     *outp = NULLCHAR;
1022
1023     return IllegalMove;
1024 }