Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.     Protector -- a UCI chess engine
  3.  
  4.     Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)
  5.  
  6.     This program is free software: you can redistribute it and/or modify
  7.     it under the terms of the GNU General Public License as published by
  8.     the Free Software Foundation, either version 3 of the License, or
  9.     (at your option) any later version.
  10.  
  11.     This program is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18.  
  19. */
  20.  
  21. #include "book.h"
  22. #include "io.h"
  23. #include "pgn.h"
  24. #include <string.h>
  25. #include <assert.h>
  26. #include <stdlib.h>
  27. #include <time.h>
  28.  
  29. static const UINT32 ILLEGAL_OFFSET = 0xFFFFFFFF;
  30. Book globalBook;
  31.  
  32. int openBook(Book * book, const char *name)
  33. {
  34.    char indexfileName[256], movefileName[256];
  35.  
  36.    strcpy(indexfileName, name);
  37.    strcat(indexfileName, ".bki");
  38.    strcpy(movefileName, name);
  39.    strcat(movefileName, ".bkm");
  40.  
  41.    book->readonly = FALSE;
  42.    book->indexFile = fopen(indexfileName, "r+");
  43.    book->moveFile = fopen(movefileName, "r+");
  44.  
  45.    if (book->indexFile == NULL)
  46.    {
  47.       book->indexFile = fopen(indexfileName, "w+");
  48.    }
  49.  
  50.    if (book->moveFile == NULL)
  51.    {
  52.       book->moveFile = fopen(movefileName, "w+");
  53.    }
  54.  
  55.    if (book->indexFile == NULL)
  56.    {
  57.       book->indexFile = fopen(indexfileName, "r");
  58.       book->readonly = TRUE;
  59.    }
  60.  
  61.    if (book->moveFile == NULL)
  62.    {
  63.       book->moveFile = fopen(movefileName, "r");
  64.       book->readonly = TRUE;
  65.    }
  66.  
  67.    if (book->indexFile != NULL)
  68.    {
  69.       fseek(book->indexFile, 0, SEEK_END);
  70.       book->numberOfPositions =
  71.          (ftell(book->indexFile) + 1) / sizeof(BookPosition);
  72.    }
  73.  
  74.    if (book->moveFile != NULL)
  75.    {
  76.       fseek(book->moveFile, 0, SEEK_END);
  77.       book->numberOfMoves = (ftell(book->moveFile) + 1) / sizeof(BookMove);
  78.    }
  79.  
  80.    if (book->indexFile != NULL && book->moveFile != NULL)
  81.    {
  82.       return 0;
  83.    }
  84.    else
  85.    {
  86.       if (book->indexFile != NULL)
  87.       {
  88.          fclose(book->indexFile);
  89.          book->indexFile = NULL;
  90.       }
  91.  
  92.       if (book->moveFile != NULL)
  93.       {
  94.          fclose(book->moveFile);
  95.          book->moveFile = NULL;
  96.       }
  97.  
  98.       return -1;
  99.    }
  100. }
  101.  
  102. void closeBook(Book * book)
  103. {
  104.    if (book->indexFile != NULL)
  105.    {
  106.       fclose(book->indexFile);
  107.    }
  108.  
  109.    if (book->moveFile != NULL)
  110.    {
  111.       fclose(book->moveFile);
  112.    }
  113. }
  114.  
  115. static BookPosition loadBookposition(const Book * book, const UINT32 offset)
  116. {
  117.    BookPosition position;
  118.  
  119.    fseek(book->indexFile, offset, SEEK_SET);
  120.    fread(&position, sizeof(BookPosition), 1, book->indexFile);
  121.  
  122.    return position;
  123. }
  124.  
  125. static void storeBookposition(Book * book, const BookPosition * position,
  126.                               const UINT32 offset)
  127. {
  128.    fseek(book->indexFile, offset, SEEK_SET);
  129.    fwrite(position, sizeof(BookPosition), 1, book->indexFile);
  130. }
  131.  
  132. static BookMove loadBookmove(const Book * book, const UINT32 offset)
  133. {
  134.    BookMove move;
  135.  
  136.    fseek(book->moveFile, offset, SEEK_SET);
  137.    fread(&move, sizeof(BookMove), 1, book->moveFile);
  138.  
  139.    return move;
  140. }
  141.  
  142. static void storeBookmove(Book * book, const BookMove * move,
  143.                           const UINT32 offset)
  144. {
  145.    fseek(book->moveFile, offset, SEEK_SET);
  146.    fwrite(move, sizeof(BookMove), 1, book->moveFile);
  147. }
  148.  
  149. void createEmptyBook(Book * book)
  150. {
  151.    BookPosition position;
  152.    int i;
  153.  
  154.    position.hashKey = 0;
  155.    position.nextPosition = ILLEGAL_OFFSET;
  156.    position.firstMove = ILLEGAL_OFFSET;
  157.  
  158.    for (i = 0; i < BOOKINDEX_SIZE; i++)
  159.    {
  160.       storeBookposition(book, &position, i * sizeof(BookPosition));
  161.    }
  162.  
  163.    book->numberOfPositions = BOOKINDEX_SIZE;
  164.    book->numberOfMoves = 0;
  165. }
  166.  
  167. static UINT32 getBookpositionOffset(const Book * book, const UINT64 hashKey)
  168. {
  169.    UINT32 offset = (UINT32) getBookpositionIndexOffset(hashKey);
  170.    BookPosition position = loadBookposition(book, offset);
  171.  
  172.    while (position.hashKey != hashKey &&
  173.           position.nextPosition != ILLEGAL_OFFSET)
  174.    {
  175.       offset = position.nextPosition;
  176.       position = loadBookposition(book, offset);
  177.    }
  178.  
  179.    return (position.hashKey == hashKey &&
  180.            position.firstMove != ILLEGAL_OFFSET ? offset : ILLEGAL_OFFSET);
  181. }
  182.  
  183. static void addBookposition(Book * book, const BookPosition * position)
  184. {
  185.    UINT32 offset = (UINT32) getBookpositionIndexOffset(position->hashKey);
  186.    BookPosition currentPosition = loadBookposition(book, offset);
  187.  
  188.    if (currentPosition.firstMove == ILLEGAL_OFFSET)
  189.    {
  190.       storeBookposition(book, position, offset);
  191.    }
  192.    else
  193.    {
  194.       UINT32 newOffset = book->numberOfPositions++ * sizeof(BookPosition);
  195.  
  196.       storeBookposition(book, position, newOffset);
  197.  
  198.       while (currentPosition.nextPosition != ILLEGAL_OFFSET)
  199.       {
  200.          offset = currentPosition.nextPosition;
  201.          currentPosition = loadBookposition(book, offset);
  202.       }
  203.  
  204.       currentPosition.nextPosition = newOffset;
  205.       storeBookposition(book, &currentPosition, offset);
  206.    }
  207. }
  208.  
  209. static UINT32 getBookmoveOffset(const Book * book, const UINT64 hashKey,
  210.                                 const UINT16 move)
  211. {
  212.    UINT32 offset = getBookpositionOffset(book, hashKey);
  213.    BookMove currentMove;
  214.  
  215.    if (offset == ILLEGAL_OFFSET)
  216.    {
  217.       return ILLEGAL_OFFSET;
  218.    }
  219.    else
  220.    {
  221.       BookPosition position = loadBookposition(book, offset);
  222.  
  223.       if (position.firstMove == ILLEGAL_OFFSET)
  224.       {
  225.          return ILLEGAL_OFFSET;
  226.       }
  227.       else
  228.       {
  229.          offset = position.firstMove;
  230.          currentMove = loadBookmove(book, offset);
  231.       }
  232.    }
  233.  
  234.    while (currentMove.move != move &&
  235.           currentMove.nextAlternative != ILLEGAL_OFFSET)
  236.    {
  237.       offset = currentMove.nextAlternative;
  238.       currentMove = loadBookmove(book, offset);
  239.    }
  240.  
  241.    return (currentMove.move == move ? offset : ILLEGAL_OFFSET);
  242. }
  243.  
  244. static void appendBookmove(Book * book, const UINT64 hashKey,
  245.                            const BookMove * move)
  246. {
  247.    UINT32 moveOffset = book->numberOfMoves++ * sizeof(BookMove);
  248.    UINT32 positionOffset = getBookpositionOffset(book, hashKey);
  249.    BookPosition position;
  250.  
  251.    storeBookmove(book, move, moveOffset);
  252.  
  253.    if (positionOffset == ILLEGAL_OFFSET)
  254.    {
  255.       position.hashKey = hashKey;
  256.       position.firstMove = moveOffset;
  257.       position.nextPosition = ILLEGAL_OFFSET;
  258.       addBookposition(book, &position);
  259.    }
  260.    else
  261.    {
  262.       position = loadBookposition(book, positionOffset);
  263.  
  264.       if (position.firstMove == ILLEGAL_OFFSET)
  265.       {
  266.          position.firstMove = moveOffset;
  267.          storeBookposition(book, &position, positionOffset);
  268.       }
  269.       else
  270.       {
  271.          UINT32 currentMoveOffset = position.firstMove;
  272.          BookMove currentMove = loadBookmove(book, currentMoveOffset);
  273.  
  274.          while (currentMove.nextAlternative != ILLEGAL_OFFSET)
  275.          {
  276.             currentMoveOffset = currentMove.nextAlternative;
  277.             currentMove = loadBookmove(book, currentMoveOffset);
  278.          }
  279.  
  280.          currentMove.nextAlternative = moveOffset;
  281.          storeBookmove(book, &currentMove, currentMoveOffset);
  282.       }
  283.    }
  284. }
  285.  
  286. static void updateBookmove(BookMove * move, const Color activeColor,
  287.                            const GameResult result, const bool personalResult)
  288. {
  289.    if (personalResult != FALSE)
  290.    {
  291.       move->numberOfPersonalGames++;
  292.  
  293.       if (result == RESULT_WHITE_WINS)
  294.       {
  295.          move->personalScore += (activeColor == WHITE ? 1 : -1);
  296.       }
  297.       else if (result == RESULT_BLACK_WINS)
  298.       {
  299.          move->personalScore += (activeColor == BLACK ? 1 : -1);
  300.       }
  301.    }
  302.    else
  303.    {
  304.       move->numberOfGames++;
  305.  
  306.       if (result == RESULT_WHITE_WINS)
  307.       {
  308.          move->score += (activeColor == WHITE ? 1 : -1);
  309.       }
  310.       else if (result == RESULT_BLACK_WINS)
  311.       {
  312.          move->score += (activeColor == BLACK ? 1 : -1);
  313.       }
  314.    }
  315. }
  316.  
  317. void addBookmove(Book * book, const Position * position,
  318.                  const Move move, const GameResult result,
  319.                  const bool personalResult)
  320. {
  321.    BookMove bookMove;
  322.    UINT32 bookmoveOffset;
  323.  
  324.    bookMove.move = packedMove(move);
  325.    bookmoveOffset = getBookmoveOffset(book, position->hashKey, bookMove.move);
  326.  
  327.    if (bookmoveOffset == ILLEGAL_OFFSET)
  328.    {
  329.       bookMove.numberOfGames = 0;
  330.       bookMove.score = 0;
  331.       bookMove.numberOfPersonalGames = 0;
  332.       bookMove.personalScore = 0;
  333.       bookMove.nextAlternative = ILLEGAL_OFFSET;
  334.  
  335.       updateBookmove(&bookMove, position->activeColor, result,
  336.                      personalResult);
  337.       appendBookmove(book, position->hashKey, &bookMove);
  338.    }
  339.    else
  340.    {
  341.       bookMove = loadBookmove(book, bookmoveOffset);
  342.  
  343.       updateBookmove(&bookMove, position->activeColor, result,
  344.                      personalResult);
  345.       storeBookmove(book, &bookMove, bookmoveOffset);
  346.    }
  347. }
  348.  
  349. static void appendBookGame(Book * book, const PGNGame * game,
  350.                            const int maximumNumberOfPlies)
  351. {
  352.    Gamemove *currentMove = game->firstMove;
  353.    int plycount = 0;
  354.    GameResult result = RESULT_UNKNOWN;
  355.  
  356.    if (strcmp(game->result, GAMERESULT_WHITE_WINS) == 0)
  357.    {
  358.       result = RESULT_WHITE_WINS;
  359.    }
  360.  
  361.    if (strcmp(game->result, GAMERESULT_DRAW) == 0)
  362.    {
  363.       result = RESULT_DRAW;
  364.    }
  365.  
  366.    if (strcmp(game->result, GAMERESULT_BLACK_WINS) == 0)
  367.    {
  368.       result = RESULT_BLACK_WINS;
  369.    }
  370.  
  371.    if (result == RESULT_UNKNOWN || strcmp(game->setup, "1") == 0)
  372.    {
  373.       logDebug("Skipping book game %s-%s.\n", game->white, game->black);
  374.  
  375.       return;
  376.    }
  377.  
  378.    while (plycount++ < maximumNumberOfPlies && currentMove != 0)
  379.    {
  380.       addBookmove(book, &currentMove->position,
  381.                   gameMove2Move(currentMove), result, FALSE);
  382.       currentMove = currentMove->nextMove;
  383.    }
  384. }
  385.  
  386. void appendBookDatabase(Book * book, const char *filename,
  387.                         int maximumNumberOfPlies)
  388. {
  389.    PGNFile pgnfile;
  390.    PGNGame *game;
  391.    long i;
  392.  
  393.    if (openPGNFile(&pgnfile, filename) != 0)
  394.    {
  395.       return;
  396.    }
  397.  
  398.    logReport("\nProcessing book file '%s' [%ld game(s)]\n", filename,
  399.              pgnfile.numGames);
  400.  
  401.    for (i = 1; i <= pgnfile.numGames; i++)
  402.    {
  403.       game = getGame(&pgnfile, i);
  404.       logReport("Processing book game #%ld.\n", i);
  405.       appendBookGame(book, game, maximumNumberOfPlies);
  406.       freePgnGame(game);
  407.    }
  408.  
  409.    closePGNFile(&pgnfile);
  410. }
  411.  
  412. static int getSuccessProbability(UINT16 numGames, INT16 score)
  413. {
  414.    int result;
  415.  
  416.    if (numGames == 0)
  417.    {
  418.       return 0;
  419.    }
  420.  
  421.    result = (50 * (long) (numGames + score)) / (long) numGames;
  422.  
  423.    assert(result >= 0 && result <= 100);
  424.  
  425.    return result;
  426. }
  427.  
  428. static int getBookmoveValue(const BookMove * move, const UINT32 numberOfGames)
  429. {
  430.    const int weightGames = 10, weightPersonalGames = 1;
  431.    int successProbability, personalSuccessProbability, moveProbability;
  432.  
  433.    successProbability =
  434.       getSuccessProbability(move->numberOfGames, move->score);
  435.    personalSuccessProbability =
  436.       getSuccessProbability(move->numberOfPersonalGames, move->personalScore);
  437.    moveProbability = (move->numberOfGames * 100) / numberOfGames;
  438.  
  439.    successProbability = (successProbability * weightGames +
  440.                          personalSuccessProbability * weightPersonalGames) /
  441.       (weightGames + weightPersonalGames);
  442.  
  443.    return successProbability * moveProbability;
  444. }
  445.  
  446. void getBookmoves(const Book * book, const UINT64 hashKey,
  447.                   const Movelist * legalMoves, Movelist * bookMoves)
  448. {
  449.    UINT32 positionOffset = getBookpositionOffset(book, hashKey), moveOffset;
  450.    BookPosition position;
  451.    BookMove bookMove, bookMoveStore[MAX_MOVES_PER_POSITION];
  452.    UINT32 numberOfGames = 0;
  453.    int i;
  454.  
  455.    bookMoves->numberOfMoves = 0;
  456.  
  457.    if (positionOffset == ILLEGAL_OFFSET)
  458.    {
  459.       return;
  460.    }
  461.  
  462.    position = loadBookposition(book, positionOffset);
  463.    moveOffset = position.firstMove;
  464.  
  465.    while (moveOffset != ILLEGAL_OFFSET)
  466.    {
  467.       Move move;
  468.  
  469.       bookMove = loadBookmove(book, moveOffset);
  470.       move = (Move) bookMove.move;
  471.  
  472.       if (listContainsMove(legalMoves, move))
  473.       {
  474.          numberOfGames += bookMove.numberOfGames;
  475.          bookMoveStore[bookMoves->numberOfMoves] = bookMove;
  476.          bookMoves->moves[bookMoves->numberOfMoves++] = move;
  477.       }
  478.  
  479.       moveOffset = bookMove.nextAlternative;
  480.    }
  481.  
  482.    for (i = 0; i < bookMoves->numberOfMoves; i++)
  483.    {
  484.       const int value =
  485.          max(1, getBookmoveValue(&bookMoveStore[i], numberOfGames));
  486.  
  487.       setMoveValue(&bookMoves->moves[i], value);
  488.    }
  489. }
  490.  
  491. static Move chooseBookmove(const Movelist * bookMoves)
  492. {
  493.    int i;
  494.    UINT32 randomNumber, sum = 0;
  495.  
  496.    for (i = 0; i < bookMoves->numberOfMoves; i++)
  497.    {
  498.       sum += getMoveValue(bookMoves->moves[i]);
  499.    }
  500.  
  501.    srand((unsigned int) (getTimestamp() + time(0)));
  502.    randomNumber = ((UINT32) rand() * (UINT32) rand() + (UINT32) rand()) % sum;
  503.  
  504.    logDebug("dumping bookmove list...\n");
  505.    dumpMovelist(bookMoves);
  506.    logDebug("sum: %lu random: %lu\n", sum, randomNumber);
  507.  
  508.    sum = 0;
  509.  
  510.    for (i = 0; i < bookMoves->numberOfMoves; i++)
  511.    {
  512.       sum += getMoveValue(bookMoves->moves[i]);
  513.  
  514.       if (sum > randomNumber)
  515.       {
  516.          return bookMoves->moves[i];
  517.       }
  518.    }
  519.  
  520.    return bookMoves->moves[bookMoves->numberOfMoves - 1];
  521. }
  522.  
  523. Move getBookmove(const Book * book, const UINT64 hashKey,
  524.                  const Movelist * legalMoves)
  525. {
  526.    Movelist bookMoves;
  527.    Move move = NO_MOVE;
  528.  
  529.    if (book->indexFile != 0 && book->moveFile != 0 &&
  530.        book->numberOfPositions > 0 && book->numberOfMoves > 0)
  531.    {
  532.       initMovelist(&bookMoves, 0);
  533.       getBookmoves(book, hashKey, legalMoves, &bookMoves);
  534.  
  535.       if (bookMoves.numberOfMoves > 0)
  536.       {
  537.          logDebug("%d bookmoves available. choosing bookmove...\n",
  538.                   bookMoves.numberOfMoves);
  539.  
  540.          move = chooseBookmove(&bookMoves);
  541.  
  542.          logDebug("chose bookmove %d-%d\n", getFromSquare(move),
  543.                   getToSquare(move));
  544.       }
  545.    }
  546.  
  547.    return move;
  548. }
  549.  
  550. int initializeModuleBook()
  551. {
  552.    if (openBook(&globalBook, "book") < 0)
  553.    {
  554.       logDebug("No opening book available.\n");
  555.    }
  556.    else
  557.    {
  558.       logDebug("Opening book found. %ld positions, %ld moves\n",
  559.                globalBook.numberOfPositions, globalBook.numberOfMoves);
  560.    }
  561.  
  562.    return 0;
  563. }
  564.  
  565. static int testPositionOperations()
  566. {
  567.    Book book;
  568.    UINT64 hashKey = BOOKINDEX_SIZE + 100;
  569.    BookPosition position;
  570.  
  571.    position.hashKey = hashKey;
  572.    position.nextPosition = ILLEGAL_OFFSET;
  573.    position.firstMove = 0;
  574.  
  575.    openBook(&book, "moduletest");
  576.    createEmptyBook(&book);
  577.  
  578.    assert(getBookpositionOffset(&book, hashKey) == ILLEGAL_OFFSET);
  579.    addBookposition(&book, &position);
  580.    assert(getBookpositionOffset(&book, hashKey) ==
  581.           getBookpositionIndexOffset(hashKey));
  582.    position.hashKey += BOOKINDEX_SIZE;
  583.    addBookposition(&book, &position);
  584.    assert(getBookpositionOffset(&book, position.hashKey) ==
  585.           BOOKINDEX_SIZE * sizeof(BookPosition));
  586.  
  587.    closeBook(&book);
  588.    assert(remove("moduletest.bki") == 0);
  589.    assert(remove("moduletest.bkm") == 0);
  590.  
  591.    return 0;
  592. }
  593.  
  594. static int testMoveOperations()
  595. {
  596.    Book book;
  597.    UINT64 hashKey = 4711;
  598.    BookMove move;
  599.  
  600.    openBook(&book, "moduletest");
  601.    createEmptyBook(&book);
  602.  
  603.    move.move = 7;
  604.    assert(getBookmoveOffset(&book, hashKey, move.move) == ILLEGAL_OFFSET);
  605.    move.move = 17;
  606.    move.nextAlternative = ILLEGAL_OFFSET;
  607.    appendBookmove(&book, hashKey, &move);
  608.    assert(getBookmoveOffset(&book, hashKey, move.move) ==
  609.           0 * sizeof(BookMove));
  610.    move.move = 19;
  611.    appendBookmove(&book, hashKey, &move);
  612.    assert(getBookmoveOffset(&book, hashKey, move.move) ==
  613.           1 * sizeof(BookMove));
  614.  
  615.    hashKey += 160939;
  616.    assert(getBookmoveOffset(&book, hashKey, move.move) == ILLEGAL_OFFSET);
  617.    appendBookmove(&book, hashKey, &move);
  618.    assert(getBookmoveOffset(&book, hashKey, move.move) ==
  619.           2 * sizeof(BookMove));
  620.  
  621.    closeBook(&book);
  622.    assert(remove("moduletest.bki") == 0);
  623.    assert(remove("moduletest.bkm") == 0);
  624.  
  625.    return 0;
  626. }
  627.  
  628. int testModuleBook()
  629. {
  630.    int result;
  631.  
  632.    if ((result = testPositionOperations()) != 0)
  633.    {
  634.       return result;
  635.    }
  636.  
  637.    if ((result = testMoveOperations()) != 0)
  638.    {
  639.       return result;
  640.    }
  641.  
  642.    return 0;
  643. }
  644.