Bitboard CHESS ENGINE in C: implementing HASH TABLE aka transposition table (read/write hash entry)

Hey what's up guys, Code Monkey King's here. In this video we gonna be writing functions to read/write data from/to hash table entries. That's pretty it)

Bruce Moreland's page on TT:

SOURCE CODE:

[gurudasbhandarkar]

While explaining why we should consider the checking of stored hash key with current hash key, at around 12:38 to 12:40, it is because of collisions. For example let us assume our current hash key is 123 and table size is 10, thus the index of the array would be 3 (123 % 10). However since we plan to store keys using the modulo approach, assume another key say 333 would be saved in the same location in the transposition table. Since the information present for key 123 is not same as key 333, we need to explicitly check for keys.

[morsmortis]

Additional explanation:

The modulo operator (%) can be viewed as follows:

If we want to calculate a % b we basically do division with rest. It can be seen as repeatedly subtracting b from a until a < b. This can be sped up a number of ways. Euclid's algorithm is worth a google search.

What it guarantees is that the result of a % b will be less than b which is why it is useful for indexing because it does not walk out of the bounds when b is the size of an array.

[haraldluessen]

Returning beta: that is ok because in a fail hard environment you do not need anything bigger than beta.
Each score >= beta achieves the same, a beta cutoff or fail high.
In a fail soft environment that may be different but it is also more unstable (but not wrong).
For now just stay with return beta.

The same is true on the other side of the alpha-beta window with alpha.
And the check with hash_entry->score >= alpha (current alpha parameter) is also ok.
All we know about a stored flag_alpha score is that the position had that score or lower the last time.
If a stored hash_entry->score is > alpha now then it may still be way below the current alpha.
Therefore we cannot use it now.

hash_entry->depth >= depth:
If the stored depth from a former search is lower that the needed depth in the current search position than we cannot use the score. We could use a stored move as a good guess to start with but
you can implement that later.
If the stored depth is equal to the current depth then we can use the score and the whole hash_entry.
If the stored depth is higher than the current depth then we can also use the score. It is even searched with more effort or precision and it is even more reliable. Unfortunately the search may become a little mit more unstable somehow because now the search depends on the order of moves and everything is highly interconnected.
That is the darkside of using a hash table.

There is another problem with the stored depth and mate scores.
(By the way do you tell the UCI GUI the right mate scores that it understands or just some heigh or low values?)
Back to mate scores. These should be adjusted before you store them in the TT and when you read them from TT.
When you are at ply 5 and store a mate score of mate_in_ply_8 then score it as depth 3. (3 plies from stored position)
When you are at ply 5 and find a mate value of depth 3 in the TT then return it as mate_in_ply_8.
Otherwise you will have strange behaviour approaching mates and in the endgame.

[adolfjamesurian]

Im using js and how do I define tt * entry = &..??

[adolfjamesurian]

and also what s the value of hash_key? isn't in the constructor?