Initial checkin for typhoon chess engine.

1 files changed, 715 insertions, 0 deletions

diff --git a/src/fen.c b/src/fen.c
new file mode 100755
index 0000000..4d9b526
--- /dev/null
+++ b/src/fen.c
@@ -0,0 +1,715 @@
+/**
+
+Copyright (c) Scott Gasch
+
+Module Name:
+
+    fen.c
+
+Abstract:
+
+    Routines that translate from an internal POSITION structure into a
+    FEN string and vice versa.
+
+Author:
+
+    Scott Gasch ([email protected]) 8 Apr 2004
+
+Revision History:
+
+    $Id: fen.c 345 2007-12-02 22:56:42Z scott $
+
+**/
+
+#include "chess.h"
+
+char g_chPieceTypeToAbbrev[] = { '_', 'p', 'n', 'b', 'r', 'q', 'k' };
+char *g_szPieceAbbrevs = "pPnNbBrRqQkK";
+
+FLAG LooksLikeFen(char *p)
+/**
+
+Routine description:
+
+    Does some string look like a FEN?
+
+Parameters:
+
+    char *p : the string in question
+
+Return value:
+
+    FLAG : TRUE if yes, FALSE otherwise
+
+**/
+{
+    POSITION q;
+    return(FenToPosition(&q, p));
+}
+
+
+#define MAX_FEN_LEN_BYTES (128)
+
+char *
+PositionToFen(IN POSITION *pos)
+/**
+
+Routine description:
+
+    Translate a POSITION structure into a FEN string and return a pointer
+    to that string.  This function allocates memory that the caller must
+    free.  This code _is_ thread safe.
+    
+Parameters:
+
+    POSITION *p : the position to translate
+
+Return value:
+
+    char * : FEN representing POSITION *p.  NULL on error.
+
+**/
+{
+    ULONG uNumEmpty;                          // num emmpty squares in a row
+    COOR c;                                   // square
+    PIECE p;                                  // the piece there
+    char *pHeap = NULL;                       // ptr to a block of heap
+    char *pch;                                // used to build the string
+
+    //
+    // Alloc a buffer.  The caller must free this.  Note: I contend that 
+    // the longest possible FEN string capable of being generated by this 
+    // code is something like: 
+    //
+    // "k1q1r1r1/b1b1n1n1/p1p1p1p1/p1p1p1p1/K1Q1R1R1/B1B1N1N1/P1P1P1P1/P1P1P1P1 w KQkq d3 49"
+    //
+    // ...which is 85 characters long.  I allocate 128 here to be safe.
+    //
+    pHeap = SystemAllocateMemory(MAX_FEN_LEN_BYTES);
+    ASSERT(pHeap);
+    pch = pHeap;
+    memset(pHeap, 0, MAX_FEN_LEN_BYTES);
+
+    //
+    // The first field represents the placement of the pieces on the
+    // board.  The board contents are specified starting with the
+    // eighth rank and ending with the first rank.  For each rank, the
+    // squares are specified from file a to file h.  White pieces are
+    // identified by uppercase SAN piece letters ("PNBRQK") and black
+    // pieces are identified by lowercase SAN piece letters
+    // ("pnbrqk").  Empty squares are represented by the digits one
+    // through eight; the digit used represents the count of
+    // contiguous empty squares along a rank.  A solidus character "/"
+    // is used to separate data of adjacent ranks.
+    //
+    uNumEmpty = 0;
+    FOREACH_SQUARE(c)
+    {
+        if (!IS_ON_BOARD(c))
+        {
+            if (0 != uNumEmpty)
+            {
+                ASSERT(uNumEmpty < 9);
+                *pch++ = (char)(uNumEmpty + '0');
+                ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+                uNumEmpty = 0;
+            }
+            if ((c % 8) == 0) *pch++ = '/';
+            ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+            continue;
+        }
+        
+        p = pos->rgSquare[c].pPiece;
+        if (IS_EMPTY(p))
+        {
+            uNumEmpty++;
+        }
+        else
+        {
+            ASSERT(IS_VALID_PIECE(p));
+            if (0 != uNumEmpty)
+            {
+                ASSERT(uNumEmpty < 9);
+                *pch++ = (char)(uNumEmpty + '0');
+                ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+                uNumEmpty = 0;
+            }
+
+            *pch = g_chPieceTypeToAbbrev[PIECE_TYPE(p)];
+            ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+            if (IS_WHITE_PIECE(p))
+            {
+                *pch = (char)toupper(*pch);
+                ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+            }
+            pch++;
+        }
+    }
+    if (0 != uNumEmpty)
+    {
+        ASSERT(uNumEmpty < 9);
+        *pch++ = (char)(uNumEmpty + '0');
+        ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+        uNumEmpty = 0;
+    }
+
+    //
+    // The second field represents the active color.  A lower case "w"
+    // is used if White is to move; a lower case "b" is used if Black
+    // is the active player.
+    //
+    *pch++ = ' ';
+    ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+    ASSERT(IS_VALID_COLOR(pos->uToMove));
+    if (WHITE == pos->uToMove)
+    {
+        *pch++ = 'w';
+    }
+    else
+    {
+        *pch++ = 'b';
+    }
+    ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+
+    //
+    // The third field represents castling availability.  This
+    // indicates potential future castling that may of may not be
+    // possible at the moment due to blocking pieces or enemy attacks.
+    // If there is no castling availability for either side, the
+    // single character symbol "-" is used.  Otherwise, a combination
+    // of from one to four characters are present.  If White has
+    // kingside castling availability, the uppercase letter "K"
+    // appears.  If White has queenside castling availability, the
+    // uppercase letter "Q" appears.  If Black has kingside castling
+    // availability, the lowercase letter "k" appears.  If Black has
+    // queenside castling availability, then the lowercase letter "q"
+    // appears.  Those letters which appear will be ordered first
+    // uppercase before lowercase and second kingside before
+    // queenside.  There is no white space between the letters.
+    //
+    *pch++ = ' ';
+    *pch++ = '\0';
+    ASSERT(strlen(pHeap) < MAX_FEN_LEN_BYTES);
+    sprintf(pHeap,
+            "%s%s %s %u %u", 
+            pHeap, 
+            CastleInfoString(pos->bvCastleInfo),
+            CoorToString(pos->cEpSquare),
+            pos->uFifty, 
+            0);
+    return(pHeap);                            // Note: caller must free
+}
+
+
+static FLAG
+_FenToPosition_DoPiecePart(IN OUT POSITION *pos, 
+                           IN char *pPieces)
+/**
+
+Routine description:
+
+    The part of FenToPosition that parses the board/piece data in the
+    FEN string and sets the appropriate parts of POSITION *p.
+
+Parameters:
+
+    POSITION *pos,
+    char *pPieces
+
+Return value:
+
+    static FLAG : TRUE on success, FALSE otherwise
+
+**/
+{
+    char *pPieceIndex;
+    ULONG uPieceIndex;
+    ULONG uPieceCounters[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+    ULONG uNumNonPawns[2] = { 0, 0 };
+    ULONG uColor;
+    ULONG uFile = 0;
+    ULONG uIndex;
+    PIECE p;
+    COOR cSquare;
+
+    //
+    // Parse board position
+    //
+    cSquare = A8;
+    ASSERT(!isspace(*pPieces));
+    while(!isspace(*pPieces) && *pPieces)
+    {
+        if (cSquare > ARRAY_SIZE(pos->rgSquare))
+        {
+            Trace("FenToPosition: Ignoring extra piece/board information.\n");
+            break;
+        }
+
+        pPieceIndex = strchr(g_szPieceAbbrevs, *pPieces);
+        if (NULL == pPieceIndex)
+        {
+            switch(*pPieces)
+            {
+                case ('/'):
+                case ('\\'):
+                    uFile++;
+                    cSquare = 16 * uFile;
+                    break;
+
+                case ('-'):
+                    //
+                    // Incrementing the file here handles fens without
+                    // delimiting slashes too.
+                    //
+                    cSquare++;
+                    break;
+
+                case ('\n'):
+                    break;
+
+                default:
+                    if (isdigit(*pPieces))
+                    {
+                        cSquare += (*pPieces - '0');
+                    }
+                    else
+                    {
+                        Trace("FenToPosition: Ignoring bad piece '%c' in FEN "
+                              "information.\n");
+                    }
+            }
+        }
+        else
+        {
+            //
+            // The position of the piece code in the g_szPieceAbbrevs array
+            // cooresponds to the piece type.
+            //
+            uPieceIndex = (ULONG)((BYTE *)pPieceIndex - 
+                                  (BYTE *)g_szPieceAbbrevs);
+            uPieceIndex += 2;
+            p = (PIECE)uPieceIndex;
+            ASSERT(IS_VALID_PIECE(p));
+            uColor = PIECE_COLOR(p);
+            ASSERT(IS_VALID_COLOR(uColor));
+            
+            if (IS_PAWN(p))
+            {
+                //
+                // The pawn list is not ordered at all, add the new pawn's
+                // location to the list and point from the pawn to the list.
+                //
+                pos->cPawns[uColor][uPieceCounters[uPieceIndex]] = cSquare;
+                pos->rgSquare[cSquare].uIndex = uPieceCounters[uPieceIndex];
+                pos->rgSquare[cSquare].pPiece = p;
+                pos->uPawnMaterial[uColor] += VALUE_PAWN;
+            }
+            else
+            {
+                if (IS_KING(p))
+                {
+                    if (pos->cNonPawns[uColor][0] != ILLEGAL_COOR)
+                    {
+                        Trace("_FenToPosition: I can't handle positions with "
+                              "more than one king, sorry.\n");
+                        return(FALSE);
+                    }
+                    pos->cNonPawns[uColor][0] = cSquare;
+                    uIndex = 0;
+                }
+                else
+                {
+                    if (IS_BISHOP(p))
+                    {
+                        if (IS_WHITE_SQUARE_COOR(cSquare))
+                        {
+                            pos->uWhiteSqBishopCount[uColor]++;
+                        }
+                    }
+                    uIndex = uNumNonPawns[uColor] + 1;
+                    pos->cNonPawns[uColor][uIndex] = cSquare;
+                    uNumNonPawns[uColor]++;
+                }
+                pos->rgSquare[cSquare].pPiece = p;
+                pos->rgSquare[cSquare].uIndex = uIndex;
+                pos->uNonPawnMaterial[uColor] += PIECE_VALUE(p);
+            }
+            uPieceCounters[uPieceIndex]++;
+            cSquare++;
+        }
+        pPieces++;
+    }
+
+    //
+    // Set the piece counts based on uPieceCounter contents
+    //
+    if (IS_ON_BOARD(pos->cNonPawns[WHITE][0]))
+    {
+        uNumNonPawns[WHITE]++;
+    }
+    pos->uNonPawnCount[WHITE][0] = uNumNonPawns[WHITE];
+    if (IS_ON_BOARD(pos->cNonPawns[BLACK][0]))
+    {
+        uNumNonPawns[BLACK]++;
+    }
+    pos->uNonPawnCount[BLACK][0] = uNumNonPawns[BLACK];
+    FOREACH_COLOR(uColor)
+    {
+        pos->uPawnCount[uColor] = uPieceCounters[(PAWN << 1) | uColor];
+        for (p = KNIGHT; p <= KING; p++)
+        {
+            pos->uNonPawnCount[uColor][p] = 
+                uPieceCounters[(p << 1) | uColor];
+        }
+    }
+    ASSERT((pos->uPawnCount[WHITE] * VALUE_PAWN) == pos->uPawnMaterial[WHITE]);
+    ASSERT((pos->uPawnCount[BLACK] * VALUE_PAWN) == pos->uPawnMaterial[BLACK]);
+
+    if ((ILLEGAL_COOR == pos->cNonPawns[BLACK][0]) ||
+        (ILLEGAL_COOR == pos->cNonPawns[WHITE][0]))
+    {
+        Trace("FenToPosition: Warning, missing king location.\n");
+    }
+    return(TRUE);
+}    
+
+
+
+static FLAG
+_FenToPosition_DoSideToMove(IN OUT POSITION *p, 
+                            IN char *pFen)
+/**
+
+Routine description:
+
+    The part of FenToPosition that parses side to move part of the FEN 
+    string and sets POSITION *p appropriately.
+
+Parameters:
+
+    POSITION *p,
+    char *pFen
+
+Return value:
+
+    static FLAG : TRUE on success, FALSE otherwise
+
+**/
+{
+    p->uToMove = BAD_COLOR;
+    while(!isspace(*pFen) && *pFen)
+    {
+        if ((toupper(*pFen) == 'W') ||
+            (*pFen == '-'))
+        {
+            p->uToMove = WHITE;
+            break;
+        }
+        else if ((toupper(*pFen) == 'B'))
+        {
+            p->uToMove = BLACK;
+            break;
+        }
+        else
+        {
+            Trace("FenToPosition: Ignoring invalid side to move '%c'.\n",
+                  *pFen);
+        }
+        pFen++;
+    }
+    
+    if (BAD_COLOR == p->uToMove)
+    {
+        Trace("FenToPosition: Never figured out a side to move, defaulting to "
+              "WHITE to move.\n");
+        p->uToMove = WHITE;
+    }
+    return(TRUE);
+}
+
+
+static FLAG 
+_FenToPosition_DoCastlingPermissions(IN OUT POSITION *p, 
+                                     IN char *pCastle)
+/**
+
+Routine description:
+
+    Do the castling part of the FenToPosition function.  Sets the proper
+    castling bits in the POSITION pointed to by p based on the text in
+    *pCastle.
+
+Parameters:
+
+    POSITION *p : position to affect
+    char *pCastle : pointer to castle part of FEN string
+
+Return value:
+
+    static FLAG : TRUE on success, FALSE otherwise
+
+**/
+{
+    ASSERT(p->bvCastleInfo == 0);
+    while(!isspace(*pCastle) && *pCastle)
+    {
+        switch (*pCastle)
+        {
+            case ('K'):
+                if ((p->rgSquare[E1].pPiece == WHITE_KING) &&
+                    (p->rgSquare[H1].pPiece == WHITE_ROOK))
+                {
+                    p->bvCastleInfo |= CASTLE_WHITE_SHORT;
+                }
+                break;
+            case ('Q'):
+                if ((p->rgSquare[E1].pPiece == WHITE_KING) &&
+                    (p->rgSquare[A1].pPiece == WHITE_ROOK))
+                {
+                    p->bvCastleInfo |= CASTLE_WHITE_LONG;
+                }
+                break;
+            case ('k'):
+                if ((p->rgSquare[E8].pPiece == BLACK_KING) &&
+                    (p->rgSquare[H8].pPiece == BLACK_ROOK))
+                {
+                    p->bvCastleInfo |= CASTLE_BLACK_SHORT;
+                }
+                break;
+            case ('q'):
+                if ((p->rgSquare[E8].pPiece == BLACK_KING) &&
+                    (p->rgSquare[A8].pPiece == BLACK_ROOK))
+                {
+                    p->bvCastleInfo |= CASTLE_BLACK_LONG;
+                }
+                break;
+            case ('-'):
+            case ('\n'):
+                break;
+            default:
+                Trace("FenToPosition: Ignoring invalid castling option char"
+                      "acter '%c'.\n", *pCastle);
+        }
+        pCastle++;
+    }
+    return(TRUE);
+}
+
+
+
+static FLAG 
+_FenToPosition_DoEnPassant(IN OUT POSITION *p, 
+                           IN char *pEnPassant)
+/**
+
+Routine description:
+
+    The part of FenToPosition that handles translating an en-passant
+    square in the FEN string into the appropriate settings in the 
+    POSITION structure.
+
+Parameters:
+
+    POSITION *p : the position to populate
+    char *pEnPassant : the string that describes how to populate it
+
+Return value:
+
+    static FLAG : TRUE on success, FALSE otherwise
+
+**/
+{
+    COOR cEp = ILLEGAL_COOR;
+    ASSERT(!isspace(*pEnPassant));
+    
+    if (*pEnPassant != '-')
+    {
+        cEp = FILE_RANK_TO_COOR((tolower(pEnPassant[0]) - 'a'),
+                                (tolower(pEnPassant[1]) - '0'));
+        if ((!RANK3(cEp)) && (!RANK6(cEp)))
+        {
+            Trace("FenToPosition: Ignoring bogus enpassant coord '%c%c'\n",
+                  pEnPassant[0], pEnPassant[1]);
+        }
+        else
+        {
+            if (WHITE == p->uToMove)
+            {
+                if ((p->rgSquare[cEp + 15].pPiece != WHITE_PAWN) &&
+                    (p->rgSquare[cEp + 17].pPiece != WHITE_PAWN))
+                {
+                    Trace("FenToPosition: Ignoring bogus en-passant "
+                          "coordinate '%c%c'\n", pEnPassant[0], pEnPassant[1]);
+                    cEp = ILLEGAL_COOR;
+                }
+            }
+            else
+            {
+                ASSERT(p->uToMove == BLACK);
+                if ((p->rgSquare[cEp - 15].pPiece != BLACK_PAWN) &&
+                    (p->rgSquare[cEp - 17].pPiece != BLACK_PAWN))
+                {
+                    Trace("FenToPosition: Ignoring bogus en-passant "
+                          "coordinate '%c%c'\n", pEnPassant[0], pEnPassant[1]);
+                    cEp = ILLEGAL_COOR;
+                }
+            }
+        }
+    }
+    ASSERT(VALID_EP_SQUARE(cEp));
+    p->cEpSquare = cEp;
+    return(TRUE);
+}
+
+void 
+_FenToPosition_DoFiftyOrEpdOpcodes(POSITION *p, 
+                                   char *szFifty)
+/**
+
+Routine description:
+
+    Do the fifty-moves-without-progress part or handle the EPD
+    opcodes.
+
+Parameters:
+
+    POSITION *p,
+    char *szFifty
+
+Return value:
+
+    void
+
+**/
+{
+    ULONG u = 0;
+    int i;
+    CHAR *q, *op;
+    
+    p->uFifty = 0;
+    q = FindChunk(szFifty, u);
+    u++;
+    while(NULL != q)
+    {
+        //printf("%u: %s\n", u-1, q);
+ 
+        i = atoi(q);
+        if ((i > 0) && (i < 100))
+        {
+            p->uFifty = (ULONG)i;
+        }
+        else
+        {
+            if (!STRCMPI(q, "bm"))
+            {
+                op = FindChunk(szFifty, u);
+                u++;
+                if (NULL == op) break;
+            }
+            
+        }
+        q = FindChunk(szFifty, u);
+        u++;
+    }
+}
+        
+    
+
+FLAG 
+FenToPosition(IN OUT POSITION *p, 
+              IN char *szFen)
+/**
+
+Routine description:
+
+    Translates a FEN string into a POSITION structure.
+
+Parameters:
+
+    POSITION *p : the POSITION structure to populate
+    char *szFen : the FEN string that describes how to populate it
+
+Return value:
+
+    FLAG : TRUE on success, FALSE otherwise
+
+**/
+{
+    char *szCapturedFen = SystemAllocateMemory((ULONG)strlen(szFen) + 2);
+    char *szPieces, *szToMove, *szCastle, *szEnPassant, *szFifty;
+    ULONG u;
+
+    //
+    // Initialize the captured fen buffer with a trailing whitespace char
+    //
+    ASSERT(NULL != szCapturedFen);
+    strcpy(szCapturedFen, szFen);
+    strcat(szCapturedFen, " ");
+
+    //
+    // Parse it into chunks
+    //
+    szPieces = FindChunk(szCapturedFen, 1);
+    szToMove = FindChunk(szCapturedFen, 2);
+    szCastle = FindChunk(szCapturedFen, 3);
+    szEnPassant = FindChunk(szCapturedFen, 4);
+    szFifty = FindChunk(szCapturedFen, 5);
+    if ((NULL == szPieces) ||
+        (NULL == szToMove) ||
+        (NULL == szCastle) ||
+        (NULL == szEnPassant))
+    {
+        return(FALSE);
+    }
+         
+    //
+    // Clear the position struct
+    //
+    memset(p, 0, sizeof(POSITION));
+    for (u = 0; u < ARRAY_SIZE(p->cPawns[WHITE]); u++)
+    {
+        p->cPawns[WHITE][u] = p->cPawns[BLACK][u] = ILLEGAL_COOR;
+    }
+
+    for (u = 0; u < ARRAY_SIZE(p->cNonPawns[WHITE]); u++)
+    {
+        p->cNonPawns[WHITE][u] = p->cNonPawns[BLACK][u] = ILLEGAL_COOR;
+    }
+   
+    //
+    // Do the pieces / board
+    //
+    if (FALSE == _FenToPosition_DoPiecePart(p, szPieces))
+    {
+        return(FALSE);
+    }
+    
+    if (FALSE == _FenToPosition_DoSideToMove(p, szToMove))
+    {
+        return(FALSE);
+    }
+    
+    if (FALSE == _FenToPosition_DoCastlingPermissions(p, szCastle))
+    {
+        return(FALSE);
+    }
+
+    if (FALSE == _FenToPosition_DoEnPassant(p, szEnPassant))
+    {
+        return(FALSE);
+    }
+    _FenToPosition_DoFiftyOrEpdOpcodes(p, szFifty);
+
+    p->u64NonPawnSig = ComputeSig(p);
+    p->u64PawnSig = ComputePawnSig(p);
+    p->iMaterialBalance[WHITE] =
+        ((SCORE)(p->uNonPawnMaterial[WHITE] + p->uPawnMaterial[WHITE]) -
+         (SCORE)(p->uNonPawnMaterial[BLACK] + p->uPawnMaterial[BLACK]));
+    p->iMaterialBalance[BLACK] = p->iMaterialBalance[WHITE] * -1;
+
+#ifdef DEBUG
+    VerifyPositionConsistency(p, FALSE);
+#endif
+    SystemFreeMemory(szCapturedFen);
+    return(TRUE);
+}