moves.c

   1 /*
   2  * moves.c - Move generation and checking
   3  * $Id$
   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 /* Like GenPseudoLegal, but (1) include castling moves, (2) unless
 439    F_IGNORE_CHECK is set in the flags, omit moves that would leave the
 440    king in check, and (3) if F_ATOMIC_CAPTURE is set in the flags, omit
 441    moves that would destroy your own king.  The CASTLE_OK flags are
 442    true if castling is not yet ruled out by a move of the king or
 443    rook.  Return TRUE if the player on move is currently in check and
 444    F_IGNORE_CHECK is not set.  */
 445 int GenLegal(board, flags, epfile, callback, closure)
 446      Board board;
 447      int flags;
 448      int epfile;
 449      MoveCallback callback;
 450      VOIDSTAR closure;
 451 {
 452     GenLegalClosure cl;
 453     int ff;
 454     int ignoreCheck = (flags & F_IGNORE_CHECK) != 0;
 455
 456     cl.cb = callback;
 457     cl.cl = closure;
 458     GenPseudoLegal(board, flags, epfile, GenLegalCallback, (VOIDSTAR) &cl);
 459
 460     if (!ignoreCheck &&
 461         CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE;
 462
 463     /* Generate castling moves */
 464     for (ff = 4; ff >= 3; ff-- /*ics wild 1*/) {
 465         if ((flags & F_WHITE_ON_MOVE) &&
 466             (flags & F_WHITE_KCASTLE_OK) &&
 467             board[0][ff] == WhiteKing &&
 468             board[0][ff + 1] == EmptySquare &&
 469             board[0][ff + 2] == EmptySquare &&
 470             board[0][6] == EmptySquare &&
 471             board[0][7] == WhiteRook &&
 472             (ignoreCheck ||
 473              (!CheckTest(board, flags, 0, ff, 0, ff + 1, FALSE) &&
 474               !CheckTest(board, flags, 0, ff, 0, ff + 2, FALSE)))) {
 475
 476             callback(board, flags,
 477                      ff==4 ? WhiteKingSideCastle : WhiteKingSideCastleWild,
 478                      0, ff, 0, ff + 2, closure);
 479         }
 480         if ((flags & F_WHITE_ON_MOVE) &&
 481             (flags & F_WHITE_QCASTLE_OK) &&
 482             board[0][ff] == WhiteKing &&
 483             board[0][ff - 1] == EmptySquare &&
 484             board[0][ff - 2] == EmptySquare &&
 485             board[0][1] == EmptySquare &&
 486             board[0][0] == WhiteRook &&
 487             (ignoreCheck ||
 488              (!CheckTest(board, flags, 0, ff, 0, ff - 1, FALSE) &&
 489               !CheckTest(board, flags, 0, ff, 0, ff - 2, FALSE)))) {
 490
 491             callback(board, flags,
 492                      ff==4 ? WhiteQueenSideCastle : WhiteQueenSideCastleWild,
 493                      0, ff, 0, ff - 2, closure);
 494         }
 495         if (!(flags & F_WHITE_ON_MOVE) &&
 496             (flags & F_BLACK_KCASTLE_OK) &&
 497             board[7][ff] == BlackKing &&
 498             board[7][ff + 1] == EmptySquare &&
 499             board[7][ff + 2] == EmptySquare &&
 500             board[7][6] == EmptySquare &&
 501             board[7][7] == BlackRook &&
 502             (ignoreCheck ||
 503              (!CheckTest(board, flags, 7, ff, 7, ff + 1, FALSE) &&
 504               !CheckTest(board, flags, 7, ff, 7, ff + 2, FALSE)))) {
 505
 506             callback(board, flags,
 507                      ff==4 ? BlackKingSideCastle : BlackKingSideCastleWild,
 508                      7, ff, 7, ff + 2, closure);
 509         }
 510         if (!(flags & F_WHITE_ON_MOVE) &&
 511             (flags & F_BLACK_QCASTLE_OK) &&
 512             board[7][ff] == BlackKing &&
 513             board[7][ff - 1] == EmptySquare &&
 514             board[7][ff - 2] == EmptySquare &&
 515             board[7][1] == EmptySquare &&
 516             board[7][0] == BlackRook &&
 517             (ignoreCheck ||
 518              (!CheckTest(board, flags, 7, ff, 7, ff - 1, FALSE) &&
 519               !CheckTest(board, flags, 7, ff, 7, ff - 1, FALSE)))) {
 520
 521             callback(board, flags,
 522                      ff==4 ? BlackQueenSideCastle : BlackQueenSideCastleWild,
 523                      7, ff, 7, ff - 2, closure);
 524         }
 525     }
 526
 527     return FALSE;
 528 }
 529
 530
 531 typedef struct {
 532     int rking, fking;
 533     int check;
 534 } CheckTestClosure;
 535
 536
 537 extern void CheckTestCallback P((Board board, int flags, ChessMove kind,
 538                                  int rf, int ff, int rt, int ft,
 539                                  VOIDSTAR closure));
 540
 541
 542 void CheckTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 543      Board board;
 544      int flags;
 545      ChessMove kind;
 546      int rf, ff, rt, ft;
 547      VOIDSTAR closure;
 548 {
 549     register CheckTestClosure *cl = (CheckTestClosure *) closure;
 550
 551     if (rt == cl->rking && ft == cl->fking) cl->check++;
 552 }
 553
 554
 555 /* If the player on move were to move from (rf, ff) to (rt, ft), would
 556    he leave himself in check?  Or if rf == -1, is the player on move
 557    in check now?  enPassant must be TRUE if the indicated move is an
 558    e.p. capture.  The possibility of castling out of a check along the
 559    back rank is not accounted for (i.e., we still return nonzero), as
 560    this is illegal anyway.  Return value is the number of times the
 561    king is in check. */
 562 int CheckTest(board, flags, rf, ff, rt, ft, enPassant)
 563      Board board;
 564      int flags;
 565      int rf, ff, rt, ft, enPassant;
 566 {
 567     CheckTestClosure cl;
 568     ChessSquare king = flags & F_WHITE_ON_MOVE ? WhiteKing : BlackKing;
 569     ChessSquare captured = EmptySquare;
 570     /*  Suppress warnings on uninitialized variables    */
 571
 572     if (rf >= 0) {
 573         if (enPassant) {
 574             captured = board[rf][ft];
 575             board[rf][ft] = EmptySquare;
 576         } else {
 577             captured = board[rt][ft];
 578         }
 579         board[rt][ft] = board[rf][ff];
 580         board[rf][ff] = EmptySquare;
 581     }
 582
 583     /* For compatibility with ICS wild 9, we scan the board in the
 584        order a1, a2, a3, ... b1, b2, ..., h8 to find the first king,
 585        and we test only whether that one is in check. */
 586     cl.check = 0;
 587     for (cl.fking = 0; cl.fking <= 7; cl.fking++)
 588         for (cl.rking = 0; cl.rking <= 7; cl.rking++) {
 589           if (board[cl.rking][cl.fking] == king) {
 590               GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, -1,
 591                              CheckTestCallback, (VOIDSTAR) &cl);
 592               goto undo_move;  /* 2-level break */
 593           }
 594       }
 595
 596   undo_move:
 597
 598     if (rf >= 0) {
 599         board[rf][ff] = board[rt][ft];
 600         if (enPassant) {
 601             board[rf][ft] = captured;
 602             board[rt][ft] = EmptySquare;
 603         } else {
 604             board[rt][ft] = captured;
 605         }
 606     }
 607
 608     return cl.check;
 609 }
 610
 611
 612 typedef struct {
 613     int rf, ff, rt, ft;
 614     ChessMove kind;
 615 } LegalityTestClosure;
 616
 617 extern void LegalityTestCallback P((Board board, int flags, ChessMove kind,
 618                                     int rf, int ff, int rt, int ft,
 619                                     VOIDSTAR closure));
 620
 621 void LegalityTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 622      Board board;
 623      int flags;
 624      ChessMove kind;
 625      int rf, ff, rt, ft;
 626      VOIDSTAR closure;
 627 {
 628     register LegalityTestClosure *cl = (LegalityTestClosure *) closure;
 629
 630     if (rf == cl->rf && ff == cl->ff && rt == cl->rt && ft == cl->ft)
 631       cl->kind = kind;
 632 }
 633
 634 ChessMove LegalityTest(board, flags, epfile, rf, ff, rt, ft, promoChar)
 635      Board board;
 636      int flags, epfile;
 637      int rf, ff, rt, ft, promoChar;
 638 {
 639     LegalityTestClosure cl;
 640
 641     cl.rf = rf;
 642     cl.ff = ff;
 643     cl.rt = rt;
 644     cl.ft = ft;
 645     cl.kind = IllegalMove;
 646     GenLegal(board, flags, epfile, LegalityTestCallback, (VOIDSTAR) &cl);
 647     if (promoChar != NULLCHAR && promoChar != 'x') {
 648         if (cl.kind == WhitePromotionQueen || cl.kind == BlackPromotionQueen) {
 649             cl.kind =
 650               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0, promoChar);
 651         } else {
 652             cl.kind = IllegalMove;
 653         }
 654     }
 655     return cl.kind;
 656 }
 657
 658 typedef struct {
 659     int count;
 660 } MateTestClosure;
 661
 662 extern void MateTestCallback P((Board board, int flags, ChessMove kind,
 663                                 int rf, int ff, int rt, int ft,
 664                                 VOIDSTAR closure));
 665
 666 void MateTestCallback(board, flags, kind, rf, ff, rt, ft, closure)
 667      Board board;
 668      int flags;
 669      ChessMove kind;
 670      int rf, ff, rt, ft;
 671      VOIDSTAR closure;
 672 {
 673     register MateTestClosure *cl = (MateTestClosure *) closure;
 674
 675     cl->count++;
 676 }
 677
 678 /* Return MT_NONE, MT_CHECK, MT_CHECKMATE, or MT_STALEMATE */
 679 int MateTest(board, flags, epfile)
 680      Board board;
 681      int flags, epfile;
 682 {
 683     MateTestClosure cl;
 684     int inCheck;
 685
 686     cl.count = 0;
 687     inCheck = GenLegal(board, flags, epfile, MateTestCallback, (VOIDSTAR) &cl);
 688     if (cl.count > 0) {
 689         return inCheck ? MT_CHECK : MT_NONE;
 690     } else {
 691         return inCheck ? MT_CHECKMATE : MT_STALEMATE;
 692     }
 693 }
 694
 695
 696 extern void DisambiguateCallback P((Board board, int flags, ChessMove kind,
 697                                     int rf, int ff, int rt, int ft,
 698                                     VOIDSTAR closure));
 699
 700 void DisambiguateCallback(board, flags, kind, rf, ff, rt, ft, closure)
 701      Board board;
 702      int flags;
 703      ChessMove kind;
 704      int rf, ff, rt, ft;
 705      VOIDSTAR closure;
 706 {
 707     register DisambiguateClosure *cl = (DisambiguateClosure *) closure;
 708
 709     if ((cl->pieceIn == EmptySquare || cl->pieceIn == board[rf][ff]) &&
 710         (cl->rfIn == -1 || cl->rfIn == rf) &&
 711         (cl->ffIn == -1 || cl->ffIn == ff) &&
 712         (cl->rtIn == -1 || cl->rtIn == rt) &&
 713         (cl->ftIn == -1 || cl->ftIn == ft)) {
 714
 715         cl->count++;
 716         cl->piece = board[rf][ff];
 717         cl->rf = rf;
 718         cl->ff = ff;
 719         cl->rt = rt;
 720         cl->ft = ft;
 721         cl->kind = kind;
 722     }
 723 }
 724
 725 void Disambiguate(board, flags, epfile, closure)
 726      Board board;
 727      int flags, epfile;
 728      DisambiguateClosure *closure;
 729 {
 730     int illegal = 0;
 731     closure->count = 0;
 732     closure->rf = closure->ff = closure->rt = closure->ft = 0;
 733     closure->kind = ImpossibleMove;
 734     GenLegal(board, flags, epfile, DisambiguateCallback, (VOIDSTAR) closure);
 735     if (closure->count == 0) {
 736         /* See if it's an illegal move due to check */
 737         illegal = 1;
 738         GenLegal(board, flags|F_IGNORE_CHECK, epfile, DisambiguateCallback,
 739                  (VOIDSTAR) closure);
 740         if (closure->count == 0) {
 741             /* No, it's not even that */
 742             return;
 743         }
 744     }
 745     if (closure->promoCharIn != NULLCHAR && closure->promoCharIn != 'x') {
 746         if (closure->kind == WhitePromotionQueen
 747             || closure->kind == BlackPromotionQueen) {
 748             closure->kind =
 749               PromoCharToMoveType((flags & F_WHITE_ON_MOVE) != 0,
 750                                   closure->promoCharIn);
 751         } else {
 752             closure->kind = IllegalMove;
 753         }
 754     }
 755     closure->promoChar = ToLower(PieceToChar(PromoPiece(closure->kind)));
 756     if (closure->promoChar == 'x') closure->promoChar = NULLCHAR;
 757     if (closure->count > 1) {
 758         closure->kind = AmbiguousMove;
 759     }
 760     if (illegal) {
 761         /* Note: If more than one illegal move matches, but no legal
 762            moves, we return IllegalMove, not AmbiguousMove.  Caller
 763            can look at closure->count to detect this.
 764         */
 765         closure->kind = IllegalMove;
 766     }
 767 }
 768
 769
 770 typedef struct {
 771     /* Input */
 772     ChessSquare piece;
 773     int rf, ff, rt, ft;
 774     /* Output */
 775     ChessMove kind;
 776     int rank;
 777     int file;
 778     int either;
 779 } CoordsToAlgebraicClosure;
 780
 781 extern void CoordsToAlgebraicCallback P((Board board, int flags,
 782                                          ChessMove kind, int rf, int ff,
 783                                          int rt, int ft, VOIDSTAR closure));
 784
 785 void CoordsToAlgebraicCallback(board, flags, kind, rf, ff, rt, ft, closure)
 786      Board board;
 787      int flags;
 788      ChessMove kind;
 789      int rf, ff, rt, ft;
 790      VOIDSTAR closure;
 791 {
 792     register CoordsToAlgebraicClosure *cl =
 793       (CoordsToAlgebraicClosure *) closure;
 794
 795     if (rt == cl->rt && ft == cl->ft &&
 796         board[rf][ff] == cl->piece) {
 797         if (rf == cl->rf) {
 798             if (ff == cl->ff) {
 799                 cl->kind = kind; /* this is the move we want */
 800             } else {
 801                 cl->file++; /* need file to rule out this move */
 802             }
 803         } else {
 804             if (ff == cl->ff) {
 805                 cl->rank++; /* need rank to rule out this move */
 806             } else {
 807                 cl->either++; /* rank or file will rule out this move */
 808             }
 809         }
 810     }
 811 }
 812
 813 /* Convert coordinates to normal algebraic notation.
 814    promoChar must be NULLCHAR or 'x' if not a promotion.
 815 */
 816 ChessMove CoordsToAlgebraic(board, flags, epfile,
 817                             rf, ff, rt, ft, promoChar, out)
 818      Board board;
 819      int flags, epfile;
 820      int rf, ff, rt, ft;
 821      int promoChar;
 822      char out[MOVE_LEN];
 823 {
 824     ChessSquare piece;
 825     ChessMove kind;
 826     char *outp = out;
 827     CoordsToAlgebraicClosure cl;
 828
 829     if (rf == DROP_RANK) {
 830         /* Bughouse piece drop */
 831         *outp++ = ToUpper(PieceToChar((ChessSquare) ff));
 832         *outp++ = '@';
 833         *outp++ = ft + 'a';
 834         *outp++ = rt + '1';
 835         *outp = NULLCHAR;
 836         return (flags & F_WHITE_ON_MOVE) ? WhiteDrop : BlackDrop;
 837     }
 838
 839     if (promoChar == 'x') promoChar = NULLCHAR;
 840     piece = board[rf][ff];
 841     switch (piece) {
 842       case WhitePawn:
 843       case BlackPawn:
 844         kind = LegalityTest(board, flags, epfile, rf, ff, rt, ft, promoChar);
 845         if (kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
 846             /* Keep short notation if move is illegal only because it
 847                leaves the player in check, but still return IllegalMove */
 848             kind = LegalityTest(board, flags|F_IGNORE_CHECK, epfile,
 849                                rf, ff, rt, ft, promoChar);
 850             if (kind == IllegalMove) break;
 851             kind = IllegalMove;
 852         }
 853         /* Pawn move */
 854         *outp++ = ff + 'a';
 855         if (ff == ft) {
 856             /* Non-capture; use style "e5" */
 857             *outp++ = rt + '1';
 858         } else {
 859             /* Capture; use style "exd5" */
 860             *outp++ = 'x';
 861             *outp++ = ft + 'a';
 862             *outp++ = rt + '1';
 863         }
 864         /* Use promotion suffix style "=Q" */
 865         if (promoChar != NULLCHAR && promoChar != 'x') {
 866             *outp++ = '=';
 867             *outp++ = ToUpper(promoChar);
 868         }
 869         *outp = NULLCHAR;
 870         return kind;
 871
 872
 873       case WhiteKing:
 874       case BlackKing:
 875         /* Test for castling or ICS wild castling */
 876         /* Use style "O-O" (oh-oh) for PGN compatibility */
 877         if (rf == rt &&
 878             rf == ((piece == WhiteKing) ? 0 : 7) &&
 879             ((ff == 4 && (ft == 2 || ft == 6)) ||
 880              (ff == 3 && (ft == 1 || ft == 5)))) {
 881             switch (ft) {
 882               case 1:
 883               case 6:
 884                 strcpy(out, "O-O");
 885                 break;
 886               case 2:
 887               case 5:
 888                 strcpy(out, "O-O-O");
 889                 break;
 890             }
 891             /* This notation is always unambiguous, unless there are
 892                kings on both the d and e files, with "wild castling"
 893                possible for the king on the d file and normal castling
 894                possible for the other.  ICS rules for wild 9
 895                effectively make castling illegal for either king in
 896                this situation.  So I am not going to worry about it;
 897                I'll just generate an ambiguous O-O in this case.
 898             */
 899             return LegalityTest(board, flags, epfile,
 900                                 rf, ff, rt, ft, promoChar);
 901         }
 902         /* else fall through */
 903
 904       default:
 905         /* Piece move */
 906         cl.rf = rf;
 907         cl.ff = ff;
 908         cl.rt = rt;
 909         cl.ft = ft;
 910         cl.piece = piece;
 911         cl.kind = IllegalMove;
 912         cl.rank = cl.file = cl.either = 0;
 913         GenLegal(board, flags, epfile,
 914                  CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
 915
 916         if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) {
 917             /* Generate pretty moves for moving into check, but
 918                still return IllegalMove.
 919             */
 920             GenLegal(board, flags|F_IGNORE_CHECK, epfile,
 921                      CoordsToAlgebraicCallback, (VOIDSTAR) &cl);
 922             if (cl.kind == IllegalMove) break;
 923             cl.kind = IllegalMove;
 924         }
 925
 926         /* Style is "Nf3" or "Nxf7" if this is unambiguous,
 927            else "Ngf3" or "Ngxf7",
 928            else "N1f3" or "N5xf7",
 929            else "Ng1f3" or "Ng5xf7".
 930         */
 931         *outp++ = ToUpper(PieceToChar(piece));
 932
 933         if (cl.file || (cl.either && !cl.rank)) {
 934             *outp++ = ff + 'a';
 935         }
 936         if (cl.rank) {
 937             *outp++ = rf + '1';
 938         }
 939
 940         if(board[rt][ft] != EmptySquare)
 941           *outp++ = 'x';
 942
 943         *outp++ = ft + 'a';
 944         *outp++ = rt + '1';
 945         *outp = NULLCHAR;
 946         return cl.kind;
 947
 948       case EmptySquare:
 949         /* Moving a nonexistent piece */
 950         break;
 951     }
 952
 953     /* Not a legal move, even ignoring check.
 954        If there was a piece on the from square,
 955        use style "Ng1g3" or "Ng1xe8";
 956        if there was a pawn or nothing (!),
 957        use style "g1g3" or "g1xe8".  Use "x"
 958        if a piece was on the to square, even
 959        a piece of the same color.
 960     */
 961     outp = out;
 962     if (piece != EmptySquare && piece != WhitePawn && piece != BlackPawn) {
 963         *outp++ = ToUpper(PieceToChar(piece));
 964     }
 965     *outp++ = ff + 'a';
 966     *outp++ = rf + '1';
 967     if (board[rt][ft] != EmptySquare) *outp++ = 'x';
 968     *outp++ = ft + 'a';
 969     *outp++ = rt + '1';
 970     /* Use promotion suffix style "=Q" */
 971     if (promoChar != NULLCHAR && promoChar != 'x') {
 972         *outp++ = '=';
 973         *outp++ = ToUpper(promoChar);
 974     }
 975     *outp = NULLCHAR;
 976
 977     return IllegalMove;
 978 }