Problems with TT, sometimes makes blunder moves

[kbhearn]

When data is packed to reduce the entry size below 16 bytes, to squeeze more than 4 in a cache line, the following scheme is very competitive:

Code: Select all

typedef struct { // 8 bytes
  unsigned int lock;
  short int score;
  short int moveAndBoundType;
} HashData;

typedef struct { // 32 bytes
  unsigned char lockExt[3];
  char filler1;
  HashData data[3];
  unsigned int depth[3];
  char filler2;
} HashBucket;

Should really express such things with the stdint types instead - the above is reliant on sizes that vary between platforms... plus i think you chose the wrong size for your depth to add up to 32 bytes even if you are counting int as always 32 bit.

Code: Select all

typedef struct { // 8 bytes
  uint32_t lock;
  int16_t score;
  int16_t moveAndBoundType;
} HashData;

typedef struct { // 32 bytes
  uint8_t lockExt[3];
  int8_t filler1;
  HashData data[3];
  uint8_t depth[3];
  int8_t filler2;
} HashBucket;

[hgm]

Oops, you are right. I intended the depth to be (unsigned char). For now it seems we will have difficulty searching deeper than 256 ply...

Btw, I like this way of packing move and flags; it doesn't seem to cause any overhead. The & operations to test the flags don't care whether the move is also in the word. They only have to be stripped off with an extra & to get the hashMove. But the moveAndBoundType word appears in a register anyway for the bound-type testing, and when the move had been stored in a separate word, it would have to explicitly loaded there. Likewise, in the hash store you replace a separate store operation by an | .

[tttony]

So you might consider to change your algorithm to determine the hash table size in a way that also works for an entry size of, say, 24 bytes.

Here is an example code including test code:

Code: Select all

#include <cstdio>
#include <cstdint>
#include <cassert>

uint64_t get_ttsize_from_size_MB(int size_MB, int entry_size)
{
    uint64_t ttsize = 1;
    uint64_t requested_size = uint64_t(size_MB) << 20;
    while (2 * ttsize * entry_size <= requested_size) {
        ttsize *= 2;
    }
    assert(ttsize * entry_size <= requested_size);
    assert((ttsize % 2) == 0);
    return ttsize;
}

void test_ttsize()
{
    for (int entry_size = 8; entry_size <= 40; entry_size += 8) {
        for (int size_MB = 1; size_MB <= 1024; size_MB++) {
            uint64_t ttsize = get_ttsize_from_size_MB(size_MB, entry_size);
            printf("entry_size=%2d size_MB=%4d ttsize=%llu\n", entry_size, size_MB, ttsize);
        }
    }
}

int main()
{
    test_ttsize();
    return 0;
}

Cool! Useful for test the struct size with tt size

The test vs old version finished and gave ~59 ELO gain

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Skiull 0.2 x64                 : 0000   00  00  0000    00.2 %   1341   50.9 %
  2 Skiull 0.1 x64                 : 0000   00  00  0000    00.8 %   1459   50.9 %

Code: Select all

1 Skiull 0.2 x64            : 1459  1000 (+408,=509,- 83), 66.2 %

Skiull 0.1 x64                : 1000 (+408,=509,- 83), 66.2 %

2 Skiull 0.1 x64            : 1341  1000 (+ 83,=509,-408), 33.8 %

Skiull 0.2 x64                : 1000 (+ 83,=509,-408), 33.8 %

Later I will implement repetition detection, now I'm refactoring MakeMove, it has redundant code it's a mess