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 <stdio.h>
  22. #include <stdlib.h>
  23. #include <assert.h>
  24. #include <math.h>
  25. #include "hash.h"
  26. #include "protector.h"
  27. #include "io.h"
  28. #include "keytable.h"
  29.  
  30. #define NODE_TABLE_SIZE (MAX_THREADS * MAX_DEPTH * 32)
  31.  
  32. const unsigned int NUM_DATES = 16;
  33. const unsigned int CLUSTER_SIZE = 4;
  34. const UINT8 DEPTH_NONE = 0;
  35. Nodeentry nodeUsageTable[NODE_TABLE_SIZE];
  36. long numNodeTableEntries;
  37.  
  38. INT16 getHashentryValue(const Hashentry * entry)
  39. {
  40.    return (INT16) (entry->data & 0xFFFF);
  41. }
  42.  
  43. INT16 getHashentryStaticValue(const Hashentry * entry)
  44. {
  45.    return (INT16) ((entry->data >> 16) & 0xFFFF);
  46. }
  47.  
  48. UINT8 getHashentryImportance(const Hashentry * entry)
  49. {
  50.    return (UINT8) ((entry->data >> 32) & 0xFF);
  51. }
  52.  
  53. UINT16 getHashentryMove(const Hashentry * entry)
  54. {
  55.    return (UINT16) ((entry->data >> 40) & 0xFFFF);
  56. }
  57.  
  58. UINT8 getHashentryDate(const Hashentry * entry)
  59. {
  60.    return (UINT8) ((entry->data >> 56) & 0x0F);
  61. }
  62.  
  63. UINT8 getHashentryFlag(const Hashentry * entry)
  64. {
  65.    return (UINT8) ((entry->data >> 60) & 0x03);
  66. }
  67.  
  68. UINT64 getHashentryKey(const Hashentry * entry)
  69. {
  70.    return entry->key ^ entry->data;
  71. }
  72.  
  73. static int getAge(const Hashtable * hashtable, const UINT8 date)
  74. {
  75.    assert(date < NUM_DATES);
  76.    assert(hashtable->date < NUM_DATES);
  77.  
  78.    return (hashtable->date + NUM_DATES - date) & (NUM_DATES - 1);
  79. }
  80.  
  81. void incrementDate(Hashtable * hashtable)
  82. {
  83.    assert(hashtable->date < NUM_DATES);
  84.  
  85.    hashtable->date = (UINT8) ((hashtable->date + 1) % NUM_DATES);
  86.  
  87.    assert(hashtable->date < NUM_DATES);
  88. }
  89.  
  90. static void deleteTables(Hashtable * hashtable)
  91. {
  92.    if (hashtable->table != 0)
  93.    {
  94.       free(hashtable->table);
  95.       hashtable->table = 0;
  96.    }
  97. }
  98.  
  99. static UINT64 _getHashData(INT16 value, INT16 staticValue, UINT8 importance,
  100.                            UINT16 bestMove, UINT8 date, UINT8 flag)
  101. {
  102.    return ((UINT64) (value & 0xFFFF)) |
  103.       ((UINT64) (staticValue & 0xFFFF)) << 16 |
  104.       ((UINT64) importance) << 32 |
  105.       ((UINT64) bestMove) << 40 |
  106.       ((UINT64) date) << 56 | ((UINT64) flag) << 60;
  107. }
  108.  
  109. Hashentry constructHashEntry(UINT64 key, INT16 value, INT16 staticValue,
  110.                              UINT8 importance, UINT16 bestMove, UINT8 date,
  111.                              UINT8 flag)
  112. {
  113.    Hashentry entry;
  114.  
  115.    entry.key = key;
  116.    entry.data = _getHashData(value, staticValue, importance,
  117.                              bestMove, date, flag);
  118.  
  119.    return entry;
  120. }
  121.  
  122. void resetHashtable(Hashtable * hashtable)
  123. {
  124.    UINT64 l;
  125.    Hashentry emptyEntry;
  126.  
  127.    emptyEntry.key = ULONG_ZERO;
  128.    emptyEntry.data = _getHashData(-VALUE_MATED, 0, DEPTH_NONE,
  129.                                   (UINT16) NO_MOVE, 0, HASHVALUE_UPPER_LIMIT);
  130.  
  131.    for (l = 0; l < hashtable->tableSize + CLUSTER_SIZE; l++)
  132.    {
  133.       hashtable->table[l] = emptyEntry;
  134.    }
  135.  
  136.    hashtable->date = 0;
  137.    hashtable->entriesUsed = 0;
  138.  
  139.    /* logDebug("hashtable reset done.\n"); */
  140. }
  141.  
  142. void resetNodetable()
  143. {
  144.    int i;
  145.  
  146.    for (i = 0; i < NODE_TABLE_SIZE; i++)
  147.    {
  148.       nodeUsageTable[i].key = ULONG_ZERO;
  149.    }
  150. }
  151.  
  152. void initializeHashtable(Hashtable * hashtable)
  153. {
  154.    hashtable->table = 0;
  155.    hashtable->tableSize = 0;
  156.    hashtable->entriesUsed = 0;
  157. }
  158.  
  159. bool isPrimeNumber(UINT64 n)
  160. {
  161.    UINT64 limit, d;
  162.  
  163.    if (n == 2)
  164.    {
  165.       return TRUE;
  166.    }
  167.  
  168.    if (n < 2 || n % 2 == 0)
  169.    {
  170.       return FALSE;
  171.    }
  172.  
  173.    limit = (UINT64) (sqrt((double) n) + 1.0);
  174.  
  175.    for (d = 3; d <= limit; d += 2)
  176.    {
  177.       if (n % d == 0)
  178.       {
  179.          return FALSE;
  180.       }
  181.    }
  182.  
  183.    return TRUE;
  184. }
  185.  
  186. UINT64 getNextPrime(UINT64 n)
  187. {
  188.    while (isPrimeNumber(n) == FALSE)
  189.    {
  190.       n++;
  191.    }
  192.  
  193.    return n;
  194. }
  195.  
  196. UINT64 getPreviousPrime(UINT64 n)
  197. {
  198.    n--;
  199.  
  200.    while (isPrimeNumber(n) == FALSE)
  201.    {
  202.       n--;
  203.    }
  204.  
  205.    return n;
  206. }
  207.  
  208. void setHashtableSize(Hashtable * hashtable, UINT64 size)
  209. {
  210.    const UINT64 ENTRY_SIZE = sizeof(Hashentry);
  211.  
  212.    deleteTables(hashtable);
  213.    hashtable->tableSize = getNextPrime(size / ENTRY_SIZE);
  214.    hashtable->table =
  215.       malloc((size_t)((hashtable->tableSize + CLUSTER_SIZE) * ENTRY_SIZE)); // Pierre-Marie Baty -- added type cast
  216.  
  217.    /* logDebug("Hashtable size: %ld entries\n",
  218.       hashtable->tableSize); */
  219. }
  220.  
  221. UINT64 getHashIndex(Hashtable * hashtable, UINT64 key)
  222. {
  223.    return key % ((hashtable)->tableSize);
  224. }
  225.  
  226. void setHashentry(Hashtable * hashtable, UINT64 key, INT16 value,
  227.                   UINT8 importance, UINT16 bestMove, UINT8 flag,
  228.                   INT16 staticValue)
  229. {
  230.    const UINT64 index = getHashIndex(hashtable, key);
  231.    UINT64 data, i, bestEntry = 0;
  232.    int bestEntryScore = -1024;
  233.    Hashentry *entryToBeReplaced;
  234.  
  235.    for (i = 0; i < CLUSTER_SIZE; i++)
  236.    {
  237.       Hashentry copy = hashtable->table[index + i];
  238.       const UINT8 copyDate = getHashentryDate(&copy);
  239.       const int copyFlag = getHashentryFlag(&copy);
  240.  
  241.       if (getHashentryKey(&copy) == key || copy.key == ULONG_ZERO)
  242.       {
  243.          if (copyDate != hashtable->date || copy.key == ULONG_ZERO)
  244.          {
  245.             hashtable->entriesUsed++;
  246.          }
  247.  
  248.          if (bestMove == (UINT16) NO_MOVE)
  249.          {
  250.             bestMove = getHashentryMove(&copy);
  251.          }
  252.  
  253.          data = _getHashData(value, staticValue, importance, bestMove,
  254.                              hashtable->date, flag);
  255.          hashtable->table[index + i].key = key ^ data;
  256.          hashtable->table[index + i].data = data;
  257.  
  258.          return;
  259.       }
  260.       else
  261.       {
  262.          const int score =
  263.             getAge(hashtable, copyDate) * 8 -
  264.             getHashentryImportance(&copy) -
  265.             (copyFlag == HASHVALUE_EXACT ? 24 : 0);
  266.  
  267.          if (score > bestEntryScore)
  268.          {
  269.             bestEntry = i;
  270.             bestEntryScore = score;
  271.          }
  272.       }
  273.    }
  274.  
  275.    if (getHashentryDate(&hashtable->table[index + bestEntry]) !=
  276.        hashtable->date)
  277.    {
  278.       hashtable->entriesUsed++;
  279.    }
  280.  
  281.    entryToBeReplaced = &hashtable->table[index + bestEntry];
  282.    data = _getHashData(value, staticValue, importance, bestMove,
  283.                        hashtable->date, flag);
  284.    entryToBeReplaced->key = key ^ data;
  285.    entryToBeReplaced->data = data;
  286. }
  287.  
  288. Hashentry *getHashentry(Hashtable * hashtable, UINT64 key)
  289. {
  290.    const UINT64 index = getHashIndex(hashtable, key);
  291.    UINT64 i;
  292.  
  293.    for (i = 0; i < CLUSTER_SIZE; i++)
  294.    {
  295.       Hashentry *tableEntry = &hashtable->table[index + i];
  296.  
  297.       if (getHashentryKey(tableEntry) == key)
  298.       {
  299.          if (getHashentryDate(tableEntry) != hashtable->date)
  300.          {
  301. #ifndef NDEBUG
  302.             const Hashentry originalEntry = *tableEntry;
  303. #endif
  304.             const UINT64 mask = (((UINT64) 0x0F) << 56);
  305.             const UINT64 newData = (tableEntry->data & ~mask) |
  306.                (((UINT64) hashtable->date) << 56);
  307.  
  308.             tableEntry->key = key ^ newData;
  309.             tableEntry->data = newData;
  310.             hashtable->entriesUsed++;
  311.  
  312.             assert(getHashentryValue(&originalEntry) ==
  313.                    getHashentryValue(tableEntry));
  314.             assert(getHashentryStaticValue(&originalEntry) ==
  315.                    getHashentryStaticValue(tableEntry));
  316.             assert(getHashentryImportance(&originalEntry) ==
  317.                    getHashentryImportance(tableEntry));
  318.             assert(getHashentryMove(&originalEntry) ==
  319.                    getHashentryMove(tableEntry));
  320.             assert(getHashentryFlag(&originalEntry) ==
  321.                    getHashentryFlag(tableEntry));
  322.             assert(hashtable->date == getHashentryDate(tableEntry));
  323.          }
  324.  
  325.          return tableEntry;
  326.       }
  327.    }
  328.  
  329.    return 0;
  330. }
  331.  
  332. UINT64 getNodeIndex(UINT64 key)
  333. {
  334.    return key % numNodeTableEntries;
  335. }
  336.  
  337. bool nodeIsInUse(UINT64 key, UINT8 depth)
  338. {
  339.    UINT64 nodeIndex = getNodeIndex(key);
  340.  
  341.    return nodeUsageTable[nodeIndex].key == key &&
  342.       nodeUsageTable[nodeIndex].depth >= depth && key != ULONG_ZERO;
  343. }
  344.  
  345. bool setNodeUsage(UINT64 key, UINT8 depth)
  346. {
  347.    UINT64 nodeIndex = getNodeIndex(key);
  348.  
  349.    if (nodeUsageTable[nodeIndex].key == ULONG_ZERO)
  350.    {
  351.       nodeUsageTable[nodeIndex].key = key;
  352.       nodeUsageTable[nodeIndex].depth = depth;
  353.  
  354.       return TRUE;
  355.    }
  356.    else
  357.    {
  358.       return FALSE;
  359.    }
  360. }
  361.  
  362. void resetNodeUsage(UINT64 key, UINT8 depth)
  363. {
  364.    UINT64 nodeIndex = getNodeIndex(key);
  365.  
  366.    nodeUsageTable[nodeIndex].key = ULONG_ZERO;
  367. }
  368.  
  369. int initializeModuleHash()
  370. {
  371.    resetNodetable();
  372.    numNodeTableEntries = (long)getPreviousPrime(NODE_TABLE_SIZE); // Pierre-Marie Baty -- added type cast
  373.  
  374.    return 0;
  375. }
  376.  
  377. static int testAgeCalculation()
  378. {
  379.    Hashtable hashtable;
  380.  
  381.    hashtable.date = 0;
  382.    assert(getAge(&hashtable, (UINT8) (NUM_DATES - 1)) == 1);
  383.    assert(getAge(&hashtable, 0) == 0);
  384.    assert(getAge(&hashtable, 1) == (int) (NUM_DATES - 1));
  385.  
  386.    hashtable.date = 2;
  387.    assert(getAge(&hashtable, 1) == 1);
  388.    assert(getAge(&hashtable, 2) == 0);
  389.    assert(getAge(&hashtable, 3) == (int) (NUM_DATES - 1));
  390.  
  391.    hashtable.date = (UINT8) (NUM_DATES - 1);
  392.    assert(getAge(&hashtable, (UINT8) (NUM_DATES - 2)) == 1);
  393.    assert(getAge(&hashtable, (UINT8) (NUM_DATES - 1)) == 0);
  394.    assert(getAge(&hashtable, 0) == (int) (NUM_DATES - 1));
  395.  
  396.    return (hashtable.date == (UINT8) (NUM_DATES - 1) ? 0 : 1);
  397. }
  398.  
  399. int testModuleHash()
  400. {
  401.    int result = 0;
  402.  
  403.    if ((result = testAgeCalculation()) != 0)
  404.    {
  405.       return result;
  406.    }
  407.  
  408.    return 0;
  409. }
  410.