src/fen.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     fen.c
   8
   9 Abstract:
  10
  11     Routines that translate from an internal POSITION structure into a
  12     FEN string and vice versa.
  13
  14 Author:
  15
  16     Scott Gasch ([email protected]) 8 Apr 2004
  17
  18 Revision History:
  19
  20     $Id: fen.c 345 2007-12-02 22:56:42Z scott $
  21
  22 **/
  23
  24 #include "chess.h"
  25
  26 char g_chPieceTypeToAbbrev[] = { '_', 'p', 'n', 'b', 'r', 'q', 'k' };
  27 char *g_szPieceAbbrevs = "pPnNbBrRqQkK";
  28
  29 FLAG LooksLikeFen(char *p)
  30 /**
  31
  32 Routine description:
  33
  34     Does some string look like a FEN?
  35
  36 Parameters:
  37
  38     char *p : the string in question
  39
  40 Return value:
  41
  42     FLAG : TRUE if yes, FALSE otherwise
  43
  44 **/
  45 {
  46     POSITION q;
  47     return(FenToPosition(&q, p));
  48 }
  49
  50
  51 #define MAX_FEN_LEN_BYTES (128)
  52
  53 char *
  54 PositionToFen(IN POSITION *pos)
  55 /**
  56
  57 Routine description:
  58
  59     Translate a POSITION structure into a FEN string and return a pointer
  60     to that string.  This function allocates memory that the caller must
  61     free.  This code _is_ thread safe.
  62
  63 Parameters:
  64
  65     POSITION *p : the position to translate
  66
  67 Return value:
  68
  69     char * : FEN representing POSITION *p.  NULL on error.
  70
  71 **/
  72 {
  73     ULONG uNumEmpty;                          // num emmpty squares in a row
  74     COOR c;                                   // square
  75     PIECE p;                                  // the piece there
  76     char *pHeap = NULL;                       // ptr to a block of heap
  77     char *pch;                                // used to build the string
  78
  79     //
  80     // Alloc a buffer.  The caller must free this.  Note: I contend that
  81     // the longest possible FEN string capable of being generated by this
  82     // code is something like:
  83     //
  84     // "k1q1r1r1/b1b1n1n1/p1p1p1p1/p1p1p1p1/K1Q1R1R1/B1B1N1N1/P1P1P1P1/P1P1P1P1 w KQkq d3 49"
  85     //
  86     // ...which is 85 characters long.  I allocate 128 here to be safe.
  87     //
  88     pHeap = SystemAllocateMemory(MAX_FEN_LEN_BYTES);
  89     ASSERT(pHeap);
  90     pch = pHeap;
  91     memset(pHeap, 0, MAX_FEN_LEN_BYTES);
  92
  93     //
  94     // The first field represents the placement of the pieces on the
  95     // board.  The board contents are specified starting with the
  96     // eighth rank and ending with the first rank.  For each rank, the
  97     // squares are specified from file a to file h.  White pieces are
  98     // identified by uppercase SAN piece letters ("PNBRQK") and black
  99     // pieces are identified by lowercase SAN piece letters
 100     // ("pnbrqk").  Empty squares are represented by the digits one
 101     // through eight; the digit used represents the count of
 102     // contiguous empty squares along a rank.  A solidus character "/"
 103     // is used to separate data of adjacent ranks.
 104     //
 105     uNumEmpty = 0;
 106     FOREACH_SQUARE(c)
 107     {
 108         if (!IS_ON_BOARD(c))
 109         {
 110             if (0 != uNumEmpty)
 111             {
 112                 ASSERT(uNumEmpty < 9);
 113                 *pch++ = (char)(uNumEmpty + '0');
 114                 ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 115                 uNumEmpty = 0;
 116             }
 117             if ((c % 8) == 0) *pch++ = '/';
 118             ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 119             continue;
 120         }
 121
 122         p = pos->rgSquare[c].pPiece;
 123         if (IS_EMPTY(p))
 124         {
 125             uNumEmpty++;
 126         }
 127         else
 128         {
 129             ASSERT(IS_VALID_PIECE(p));
 130             if (0 != uNumEmpty)
 131             {
 132                 ASSERT(uNumEmpty < 9);
 133                 *pch++ = (char)(uNumEmpty + '0');
 134                 ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 135                 uNumEmpty = 0;
 136             }
 137
 138             *pch = g_chPieceTypeToAbbrev[PIECE_TYPE(p)];
 139             ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 140             if (IS_WHITE_PIECE(p))
 141             {
 142                 *pch = (char)toupper(*pch);
 143                 ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 144             }
 145             pch++;
 146         }
 147     }
 148     if (0 != uNumEmpty)
 149     {
 150         ASSERT(uNumEmpty < 9);
 151         *pch++ = (char)(uNumEmpty + '0');
 152         ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 153         uNumEmpty = 0;
 154     }
 155
 156     //
 157     // The second field represents the active color.  A lower case "w"
 158     // is used if White is to move; a lower case "b" is used if Black
 159     // is the active player.
 160     //
 161     *pch++ = ' ';
 162     ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 163     ASSERT(IS_VALID_COLOR(pos->uToMove));
 164     if (WHITE == pos->uToMove)
 165     {
 166         *pch++ = 'w';
 167     }
 168     else
 169     {
 170         *pch++ = 'b';
 171     }
 172     ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 173
 174     //
 175     // The third field represents castling availability.  This
 176     // indicates potential future castling that may of may not be
 177     // possible at the moment due to blocking pieces or enemy attacks.
 178     // If there is no castling availability for either side, the
 179     // single character symbol "-" is used.  Otherwise, a combination
 180     // of from one to four characters are present.  If White has
 181     // kingside castling availability, the uppercase letter "K"
 182     // appears.  If White has queenside castling availability, the
 183     // uppercase letter "Q" appears.  If Black has kingside castling
 184     // availability, the lowercase letter "k" appears.  If Black has
 185     // queenside castling availability, then the lowercase letter "q"
 186     // appears.  Those letters which appear will be ordered first
 187     // uppercase before lowercase and second kingside before
 188     // queenside.  There is no white space between the letters.
 189     //
 190     *pch++ = ' ';
 191     *pch++ = '\0';
 192     ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
 193     sprintf(pHeap,
 194             "%s%s %s %u %u",
 195             pHeap,
 196             CastleInfoString(pos->bvCastleInfo),
 197             CoorToString(pos->cEpSquare),
 198             pos->uFifty,
 199             0);
 200     return(pHeap);                            // Note: caller must free
 201 }
 202
 203
 204 static FLAG
 205 _FenToPosition_DoPiecePart(IN OUT POSITION *pos,
 206                            IN char *pPieces)
 207 /**
 208
 209 Routine description:
 210
 211     The part of FenToPosition that parses the board/piece data in the
 212     FEN string and sets the appropriate parts of POSITION *p.
 213
 214 Parameters:
 215
 216     POSITION *pos,
 217     char *pPieces
 218
 219 Return value:
 220
 221     static FLAG : TRUE on success, FALSE otherwise
 222
 223 **/
 224 {
 225     char *pPieceIndex;
 226     ULONG uPieceIndex;
 227     ULONG uPieceCounters[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
 228     ULONG uNumNonPawns[2] = { 0, 0 };
 229     ULONG uColor;
 230     ULONG uFile = 0;
 231     ULONG uIndex;
 232     PIECE p;
 233     COOR cSquare;
 234
 235     //
 236     // Parse board position
 237     //
 238     cSquare = A8;
 239     ASSERT(!isspace(*pPieces));
 240     while(!isspace(*pPieces) && *pPieces)
 241     {
 242         if (cSquare > ARRAY_SIZE(pos->rgSquare))
 243         {
 244             Trace("FenToPosition: Ignoring extra piece/board information.\n");
 245             break;
 246         }
 247
 248         pPieceIndex = strchr(g_szPieceAbbrevs, *pPieces);
 249         if (NULL == pPieceIndex)
 250         {
 251             switch(*pPieces)
 252             {
 253                 case ('/'):
 254                 case ('\\'):
 255                     uFile++;
 256                     cSquare = 16 * uFile;
 257                     break;
 258
 259                 case ('-'):
 260                     //
 261                     // Incrementing the file here handles fens without
 262                     // delimiting slashes too.
 263                     //
 264                     cSquare++;
 265                     break;
 266
 267                 case ('\n'):
 268                     break;
 269
 270                 default:
 271                     if (isdigit(*pPieces))
 272                     {
 273                         cSquare += (*pPieces - '0');
 274                     }
 275                     else
 276                     {
 277                         Trace("FenToPosition: Ignoring bad piece '%c' in FEN "
 278                               "information.\n");
 279                     }
 280             }
 281         }
 282         else
 283         {
 284             //
 285             // The position of the piece code in the g_szPieceAbbrevs array
 286             // cooresponds to the piece type.
 287             //
 288             uPieceIndex = (ULONG)((BYTE *)pPieceIndex -
 289                                   (BYTE *)g_szPieceAbbrevs);
 290             uPieceIndex += 2;
 291             p = (PIECE)uPieceIndex;
 292             ASSERT(IS_VALID_PIECE(p));
 293             uColor = PIECE_COLOR(p);
 294             ASSERT(IS_VALID_COLOR(uColor));
 295
 296             if (IS_PAWN(p))
 297             {
 298                 //
 299                 // The pawn list is not ordered at all, add the new pawn's
 300                 // location to the list and point from the pawn to the list.
 301                 //
 302                 pos->cPawns[uColor][uPieceCounters[uPieceIndex]] = cSquare;
 303                 pos->rgSquare[cSquare].uIndex = uPieceCounters[uPieceIndex];
 304                 pos->rgSquare[cSquare].pPiece = p;
 305                 pos->uPawnMaterial[uColor] += VALUE_PAWN;
 306             }
 307             else
 308             {
 309                 if (IS_KING(p))
 310                 {
 311                     if (pos->cNonPawns[uColor][0] != ILLEGAL_COOR)
 312                     {
 313                         Trace("_FenToPosition: I can't handle positions with "
 314                               "more than one king, sorry.\n");
 315                         return(FALSE);
 316                     }
 317                     pos->cNonPawns[uColor][0] = cSquare;
 318                     uIndex = 0;
 319                 }
 320                 else
 321                 {
 322                     if (IS_BISHOP(p))
 323                     {
 324                         if (IS_WHITE_SQUARE_COOR(cSquare))
 325                         {
 326                             pos->uWhiteSqBishopCount[uColor]++;
 327                         }
 328                     }
 329                     uIndex = uNumNonPawns[uColor] + 1;
 330                     pos->cNonPawns[uColor][uIndex] = cSquare;
 331                     uNumNonPawns[uColor]++;
 332                 }
 333                 pos->rgSquare[cSquare].pPiece = p;
 334                 pos->rgSquare[cSquare].uIndex = uIndex;
 335                 pos->uNonPawnMaterial[uColor] += PIECE_VALUE(p);
 336             }
 337             uPieceCounters[uPieceIndex]++;
 338             cSquare++;
 339         }
 340         pPieces++;
 341     }
 342
 343     //
 344     // Set the piece counts based on uPieceCounter contents
 345     //
 346     if (IS_ON_BOARD(pos->cNonPawns[WHITE][0]))
 347     {
 348         uNumNonPawns[WHITE]++;
 349     }
 350     pos->uNonPawnCount[WHITE][0] = uNumNonPawns[WHITE];
 351     if (IS_ON_BOARD(pos->cNonPawns[BLACK][0]))
 352     {
 353         uNumNonPawns[BLACK]++;
 354     }
 355     pos->uNonPawnCount[BLACK][0] = uNumNonPawns[BLACK];
 356     FOREACH_COLOR(uColor)
 357     {
 358         pos->uPawnCount[uColor] = uPieceCounters[(PAWN << 1) | uColor];
 359         for (p = KNIGHT; p <= KING; p++)
 360         {
 361             pos->uNonPawnCount[uColor][p] =
 362                 uPieceCounters[(p << 1) | uColor];
 363         }
 364     }
 365     ASSERT((pos->uPawnCount[WHITE] * VALUE_PAWN) == pos->uPawnMaterial[WHITE]);
 366     ASSERT((pos->uPawnCount[BLACK] * VALUE_PAWN) == pos->uPawnMaterial[BLACK]);
 367
 368     if ((ILLEGAL_COOR == pos->cNonPawns[BLACK][0]) ||
 369         (ILLEGAL_COOR == pos->cNonPawns[WHITE][0]))
 370     {
 371         Trace("FenToPosition: Warning, missing king location.\n");
 372     }
 373     return(TRUE);
 374 }
 375
 376
 377
 378 static FLAG
 379 _FenToPosition_DoSideToMove(IN OUT POSITION *p,
 380                             IN char *pFen)
 381 /**
 382
 383 Routine description:
 384
 385     The part of FenToPosition that parses side to move part of the FEN
 386     string and sets POSITION *p appropriately.
 387
 388 Parameters:
 389
 390     POSITION *p,
 391     char *pFen
 392
 393 Return value:
 394
 395     static FLAG : TRUE on success, FALSE otherwise
 396
 397 **/
 398 {
 399     p->uToMove = BAD_COLOR;
 400     while(!isspace(*pFen) && *pFen)
 401     {
 402         if ((toupper(*pFen) == 'W') ||
 403             (*pFen == '-'))
 404         {
 405             p->uToMove = WHITE;
 406             break;
 407         }
 408         else if ((toupper(*pFen) == 'B'))
 409         {
 410             p->uToMove = BLACK;
 411             break;
 412         }
 413         else
 414         {
 415             Trace("FenToPosition: Ignoring invalid side to move '%c'.\n",
 416                   *pFen);
 417         }
 418         pFen++;
 419     }
 420
 421     if (BAD_COLOR == p->uToMove)
 422     {
 423         Trace("FenToPosition: Never figured out a side to move, defaulting to "
 424               "WHITE to move.\n");
 425         p->uToMove = WHITE;
 426     }
 427     return(TRUE);
 428 }
 429
 430
 431 static FLAG
 432 _FenToPosition_DoCastlingPermissions(IN OUT POSITION *p,
 433                                      IN char *pCastle)
 434 /**
 435
 436 Routine description:
 437
 438     Do the castling part of the FenToPosition function.  Sets the proper
 439     castling bits in the POSITION pointed to by p based on the text in
 440     *pCastle.
 441
 442 Parameters:
 443
 444     POSITION *p : position to affect
 445     char *pCastle : pointer to castle part of FEN string
 446
 447 Return value:
 448
 449     static FLAG : TRUE on success, FALSE otherwise
 450
 451 **/
 452 {
 453     ASSERT(p->bvCastleInfo == 0);
 454     while(!isspace(*pCastle) && *pCastle)
 455     {
 456         switch (*pCastle)
 457         {
 458             case ('K'):
 459                 if ((p->rgSquare[E1].pPiece == WHITE_KING) &&
 460                     (p->rgSquare[H1].pPiece == WHITE_ROOK))
 461                 {
 462                     p->bvCastleInfo |= CASTLE_WHITE_SHORT;
 463                 }
 464                 break;
 465             case ('Q'):
 466                 if ((p->rgSquare[E1].pPiece == WHITE_KING) &&
 467                     (p->rgSquare[A1].pPiece == WHITE_ROOK))
 468                 {
 469                     p->bvCastleInfo |= CASTLE_WHITE_LONG;
 470                 }
 471                 break;
 472             case ('k'):
 473                 if ((p->rgSquare[E8].pPiece == BLACK_KING) &&
 474                     (p->rgSquare[H8].pPiece == BLACK_ROOK))
 475                 {
 476                     p->bvCastleInfo |= CASTLE_BLACK_SHORT;
 477                 }
 478                 break;
 479             case ('q'):
 480                 if ((p->rgSquare[E8].pPiece == BLACK_KING) &&
 481                     (p->rgSquare[A8].pPiece == BLACK_ROOK))
 482                 {
 483                     p->bvCastleInfo |= CASTLE_BLACK_LONG;
 484                 }
 485                 break;
 486             case ('-'):
 487             case ('\n'):
 488                 break;
 489             default:
 490                 Trace("FenToPosition: Ignoring invalid castling option char"
 491                       "acter '%c'.\n", *pCastle);
 492         }
 493         pCastle++;
 494     }
 495     return(TRUE);
 496 }
 497
 498
 499
 500 static FLAG
 501 _FenToPosition_DoEnPassant(IN OUT POSITION *p,
 502                            IN char *pEnPassant)
 503 /**
 504
 505 Routine description:
 506
 507     The part of FenToPosition that handles translating an en-passant
 508     square in the FEN string into the appropriate settings in the
 509     POSITION structure.
 510
 511 Parameters:
 512
 513     POSITION *p : the position to populate
 514     char *pEnPassant : the string that describes how to populate it
 515
 516 Return value:
 517
 518     static FLAG : TRUE on success, FALSE otherwise
 519
 520 **/
 521 {
 522     COOR cEp = ILLEGAL_COOR;
 523     ASSERT(!isspace(*pEnPassant));
 524
 525     if (*pEnPassant != '-')
 526     {
 527         cEp = FILE_RANK_TO_COOR((tolower(pEnPassant[0]) - 'a'),
 528                                 (tolower(pEnPassant[1]) - '0'));
 529         if ((!RANK3(cEp)) && (!RANK6(cEp)))
 530         {
 531             Trace("FenToPosition: Ignoring bogus enpassant coord '%c%c'\n",
 532                   pEnPassant[0], pEnPassant[1]);
 533         }
 534         else
 535         {
 536             if (WHITE == p->uToMove)
 537             {
 538                 if ((p->rgSquare[cEp + 15].pPiece != WHITE_PAWN) &&
 539                     (p->rgSquare[cEp + 17].pPiece != WHITE_PAWN))
 540                 {
 541                     Trace("FenToPosition: Ignoring bogus en-passant "
 542                           "coordinate '%c%c'\n", pEnPassant[0], pEnPassant[1]);
 543                     cEp = ILLEGAL_COOR;
 544                 }
 545             }
 546             else
 547             {
 548                 ASSERT(p->uToMove == BLACK);
 549                 if ((p->rgSquare[cEp - 15].pPiece != BLACK_PAWN) &&
 550                     (p->rgSquare[cEp - 17].pPiece != BLACK_PAWN))
 551                 {
 552                     Trace("FenToPosition: Ignoring bogus en-passant "
 553                           "coordinate '%c%c'\n", pEnPassant[0], pEnPassant[1]);
 554                     cEp = ILLEGAL_COOR;
 555                 }
 556             }
 557         }
 558     }
 559     ASSERT(VALID_EP_SQUARE(cEp));
 560     p->cEpSquare = cEp;
 561     return(TRUE);
 562 }
 563
 564 void
 565 _FenToPosition_DoFiftyOrEpdOpcodes(POSITION *p,
 566                                    char *szFifty)
 567 /**
 568
 569 Routine description:
 570
 571     Do the fifty-moves-without-progress part or handle the EPD
 572     opcodes.
 573
 574 Parameters:
 575
 576     POSITION *p,
 577     char *szFifty
 578
 579 Return value:
 580
 581     void
 582
 583 **/
 584 {
 585     ULONG u = 0;
 586     int i;
 587     CHAR *q, *op;
 588
 589     p->uFifty = 0;
 590     q = FindChunk(szFifty, u);
 591     u++;
 592     while(NULL != q)
 593     {
 594         //printf("%u: %s\n", u-1, q);
 595
 596         i = atoi(q);
 597         if ((i > 0) && (i < 100))
 598         {
 599             p->uFifty = (ULONG)i;
 600         }
 601         else
 602         {
 603             if (!STRCMPI(q, "bm"))
 604             {
 605                 op = FindChunk(szFifty, u);
 606                 u++;
 607                 if (NULL == op) break;
 608             }
 609
 610         }
 611         q = FindChunk(szFifty, u);
 612         u++;
 613     }
 614 }
 615
 616
 617
 618 FLAG
 619 FenToPosition(IN OUT POSITION *p,
 620               IN char *szFen)
 621 /**
 622
 623 Routine description:
 624
 625     Translates a FEN string into a POSITION structure.
 626
 627 Parameters:
 628
 629     POSITION *p : the POSITION structure to populate
 630     char *szFen : the FEN string that describes how to populate it
 631
 632 Return value:
 633
 634     FLAG : TRUE on success, FALSE otherwise
 635
 636 **/
 637 {
 638     char *szCapturedFen = SystemAllocateMemory((ULONG)strlen(szFen) + 2);
 639     char *szPieces, *szToMove, *szCastle, *szEnPassant, *szFifty;
 640     ULONG u;
 641
 642     //
 643     // Initialize the captured fen buffer with a trailing whitespace char
 644     //
 645     ASSERT(NULL != szCapturedFen);
 646     strcpy(szCapturedFen, szFen);
 647     strcat(szCapturedFen, " ");
 648
 649     //
 650     // Parse it into chunks
 651     //
 652     szPieces = FindChunk(szCapturedFen, 1);
 653     szToMove = FindChunk(szCapturedFen, 2);
 654     szCastle = FindChunk(szCapturedFen, 3);
 655     szEnPassant = FindChunk(szCapturedFen, 4);
 656     szFifty = FindChunk(szCapturedFen, 5);
 657     if ((NULL == szPieces) ||
 658         (NULL == szToMove) ||
 659         (NULL == szCastle) ||
 660         (NULL == szEnPassant))
 661     {
 662         return(FALSE);
 663     }
 664
 665     //
 666     // Clear the position struct
 667     //
 668     memset(p, 0, sizeof(POSITION));
 669     for (u = 0; u < ARRAY_SIZE(p->cPawns[WHITE]); u++)
 670     {
 671         p->cPawns[WHITE][u] = p->cPawns[BLACK][u] = ILLEGAL_COOR;
 672     }
 673
 674     for (u = 0; u < ARRAY_SIZE(p->cNonPawns[WHITE]); u++)
 675     {
 676         p->cNonPawns[WHITE][u] = p->cNonPawns[BLACK][u] = ILLEGAL_COOR;
 677     }
 678
 679     //
 680     // Do the pieces / board
 681     //
 682     if (FALSE == _FenToPosition_DoPiecePart(p, szPieces))
 683     {
 684         return(FALSE);
 685     }
 686
 687     if (FALSE == _FenToPosition_DoSideToMove(p, szToMove))
 688     {
 689         return(FALSE);
 690     }
 691
 692     if (FALSE == _FenToPosition_DoCastlingPermissions(p, szCastle))
 693     {
 694         return(FALSE);
 695     }
 696
 697     if (FALSE == _FenToPosition_DoEnPassant(p, szEnPassant))
 698     {
 699         return(FALSE);
 700     }
 701     _FenToPosition_DoFiftyOrEpdOpcodes(p, szFifty);
 702
 703     p->u64NonPawnSig = ComputeSig(p);
 704     p->u64PawnSig = ComputePawnSig(p);
 705     p->iMaterialBalance[WHITE] =
 706         ((SCORE)(p->uNonPawnMaterial[WHITE] + p->uPawnMaterial[WHITE]) -
 707          (SCORE)(p->uNonPawnMaterial[BLACK] + p->uPawnMaterial[BLACK]));
 708     p->iMaterialBalance[BLACK] = p->iMaterialBalance[WHITE] * -1;
 709
 710 #ifdef DEBUG
 711     VerifyPositionConsistency(p, FALSE);
 712 #endif
 713     SystemFreeMemory(szCapturedFen);
 714     return(TRUE);
 715 }