Weaker play with TT

[maksimKorzh]

Hi guys, I'm facing a very strange issue:
My engine wit TT plays much worse instead of no TT version.
My TT is 32bit (jsvascript) it gives a couple of plies deeper search and doesn't make some weird blunders -
just seems to be playing well, but the results are so weird.

I'm using the simplest TT implementation possible with always replace schema.
Any clue on where to search for possible bugs are highly appreciated.

P.S. Code: https://github.com/maksimKorzh/wukongJS ... /wukong.js
TT functions, lines: 1299 - 1386
AlphaBeta, lines 1565 - 1335

[mar]

I don't understand your masking around hashEntries:

Code: Select all

var hashEntry = hashTable[hashKey & (hashEntries - 4)];

why -4, plus hashEntries seems nowehere close to a power of two (default is some weird value like 16M/80, so I'm puzzled
if hashEntries was 2**n, then masking with (hashEntries-1) I would understand
so this way I think you utilize only a fraction of the TT due to masking problems

why not simply hashKey % hashEntries?

or, if you prefer to use masking, then you should round hashEntries to a power of two, then mask with hashEntries-1

EDIT: -4 would make sense if you used buckets of 4 entries, which you don't use (because you don't know how big an entry is in JS if you use objects)

[maksimKorzh]

I don't understand your masking around hashEntries:

Code: Select all

var hashEntry = hashTable[hashKey & (hashEntries - 4)];

why -4, plus hashEntries seems nowehere close to a power of two (default is some weird value like 16M/80, so I'm puzzled
if hashEntries was 2**n, then masking with (hashEntries-1) I would understand
so this way I think you utilize only a fraction of the TT due to masking problems

why not simply hashKey % hashEntries?

or, if you prefer to use masking, then you should round hashEntries to a power of two, then mask with hashEntries-1

EDIT: -4 would make sense if you used buckets of 4 entries, which you don't use (because you don't know how big an entry is in JS if you use objects)

Hi Martin

First I've used hashKey % hashEntries but this resulted with almost no hits in TT. I thought it was due to the negative hash keys. I tried abs(hashKey) % hashEntries but also too few tt hits. I was confused with negative values so decided to use masking and -4 is to make sure I don't exceed tt bounds.

So how can I deal with negative hash keys?

[mar]

I see. have you tried to mask it to 32 bits (or 31) first, like hashKey &= 0xffffffff? then use %?
still - if you round number of entries to nearest power of two and then mask with num_entries-1, it should work as is

[hgm]

I suppose you use separate 32-bit keys for the signature and the index, since JavaScript doesn't have a 64-bit type. For the signature you don't care what the sign is, it is only used for a comparison of numbers. You want the index to be within the range of the TT, though, which also means non-negative.

Note that the fact that the index key can be negative is self-inflicted. In Zobrist hashing the key is an XOR of all the Zobrist keys. If you had defined all Zobrist keys with the sign bit zero (i.e. positive), their XOR would also be positive. In fact there is no need to do any masking during TT access; you could have done the masking on the Zobrist keys, so that the bits you want to mask away would always be zero to start with.

[maksimKorzh]

I see. have you tried to mask it to 32 bits (or 31) first, like hashKey &= 0xffffffff? then use %?
still - if you round number of entries to nearest power of two and then mask with num_entries-1, it should work as is

index = (hashkey & 0x7FFFFFFF) % hashEntries
worked for me.

I didn't do hashKey &= since I don't want to change the hash key when calculating index.
Also I used 0x7FFFFFFF mask instead of 0xFFFFFFFF so that 32th bit (negative as far as I'm aware) is not actually getting involved,
so eventually I use 31 bits from my hash key while 32th bit is just getting stripped, eventually I'm always getting positive numbers to % with hashEntries.

If the the above index calculation is fine then thank you very much pointing out such an elegant solution.

P.S. Martin, comewhere in the Cheng thread you've mentioned something like: "because I've made no progress since 4.40dev and because CEGT is already testing Guenther's compiles" - I just wanted to ask what you do when feel that kind of reaching the limits - when you feel like you can't make an engine stronger or can't make any progress - What do you do in that case? I mean Stockfish kind of never stucks and getting improved forever but many
other engines reaching some Elo level and then just stuck there forever.

What is the secret of "keep going" the progress?
Thanks in advance?

[mar]

P.S. Martin, comewhere in the Cheng thread you've mentioned something like: "because I've made no progress since 4.40dev and because CEGT is already testing Guenther's compiles" - I just wanted to ask what you do when feel that kind of reaching the limits - when you feel like you can't make an engine stronger or can't make any progress - What do you do in that case? I mean Stockfish kind of never stucks and getting improved forever but many
other engines reaching some Elo level and then just stuck there forever.

What is the secret of "keep going" the progress?
Thanks in advance?

ah yes, that statement was not entirely correct as my actual version was ~10-15 elo stronger than dev,
but since CEGT already started to test Guenther's compile, I decided to make it an official release,
I didn't want a dev version to pollute the rating lists. Also had I released something that's only 10 elo stronger in selfplay,
due to error bars it might as well be listed below 4.40 dev, so I was sort of forced to release.
lesson learned: never push to master until the release is ready

the secret is simply motivation and patience, easier said than done of course.
when I can't make progress I switch to something else than chess (=take a break) and perhaps at some time in the future
the motivation will return for a while

[maksimKorzh]

I suppose you use separate 32-bit keys for the signature and the index, since JavaScript doesn't have a 64-bit type. For the signature you don't care what the sign is, it is only used for a comparison of numbers. You want the index to be within the range of the TT, though, which also means non-negative.

Note that the fact that the index key can be negative is self-inflicted. In Zobrist hashing the key is an XOR of all the Zobrist keys. If you had defined all Zobrist keys with the sign bit zero (i.e. positive), their XOR would also be positive. In fact there is no need to do any masking during TT access; you could have done the masking on the Zobrist keys, so that the bits you want to mask away would always be zero to start with.

re: I suppose you use separate 32-bit keys for the signature and the index, since JavaScript doesn't have a 64-bit type. For the signature you don't care what the sign is, it is only used for a comparison of numbers. You want the index to be within the range of the TT, though, which also means non-negative.

Didn't exactly get what you mean.
I have my own simple XOR shift based pseudo random number generator to have same hash keys in any environment.
My hash keys are 32bit signed (I tried to make them unsigned via new Uint32Array(hashKey)[0] but after XORing it drops back to being negative)
I assume by "signature" you mean unique position identifier to detect repetitions, if so - yes.
And yes, I want the index to be within the range of TT, Martins solution "(hashKey & 0x7FFFFFFF) % hashEntries" seems to be working fine.
Masking Zobrist key itself is very interesting idea but I like to keep them as they are for simplicity -
I mean when masking is done for tt index calculation it's clear that negative bit is being stripped to fit tt length while
masking Zobrist key might a bit tricky to understand WHY to do that, say someone would like to take my engine
as a bases then long time before implementing tt he would have no use of stripped negative bit in Zobrist key
while it might be an unclear part in the code - I try to avoid code forcing to guess what the author meant.
Only buggy code makes wondering)

I have a couple more questions:
1. How to measure the efficiency of TT (I understand how to count tt hits, but how to count efficiency percentage?)
2. What are the "buckets" for tt and how to use them, I remember you've been explaining this before but can't find related threads.

Thanks in advance.

[pedrox]

I have no knowledge of javascript.

My question is whether bestmove is returned correctly by the function that checks the hash table. In C language I use pointers when I want to return more than one parameter to the calling function, so I call the Read_Hash() function, pass it the &bestmove parameter and then return it with *bestmove. However JavaScript doesn't have pointers so I think it has to be passed the parameter as an object.

In the negamax function you have defined bestmove:
var bestMove = { value: 0 };

You check the hash tables with:
readHashEntry(alpha, beta, bestMove, depth)

And you update the value of bestmove in the function:
function readHashEntry(alpha, beta, bestMove, depth) {
...
// store best move
bestMove.value = hashEntry.bestMove;
...
}

My question is: shouldn't the bestmove variable that you have defined within the negamax() function be global so that it can be updated in the readHashEntry() function ?

[hgm]

I assume by "signature" you mean unique position identifier to detect repetitions, if so - yes.

The 'signature' is what you store in the hash entry to recognize whether that entry contains information on the position you seek, or for some other position that accidentally mapped to the same entry. Normally one uses a 64-bit key, and then uses (say) the lower 32 bits to store in the entry, and the upper 32 bits (masked down to as many as you need to span the entire table) to calculate the index. Some people store all 64 bits as signature, but that is a waste of space, since the bits that are used to derive the index from are guaranteed to match, or you would not be looking in that entry.