Implement Transposition Table

[mateusz2173]

Read https://www.chessprogramming.org/Transposition_Table Transposition Table is a cache table for search. Implement transposition table which can store 3 types of scores:

1. EXACT - exact value found during search. We should store it every time we found exact value, that is when alpha < score < beta
2. BETA - should be stored when search fails high, that is when alpha < beta <= score
3. ALPHA - should be stored when search fails low, that is when neither 1 or 2 happened. (score <= alpha)

Along with scores we should also store:

• depth (on which we write entry to transposition table)
• move associated with found score

If entry already exists for the position, replace it only if current_depth > old_entry_depth

Add reading transposition table to the beginning of the search (before we jump into searching moves): In case we've found cache entry for the position and depth_entry >= current_depth then we can return cached score.

Let's make cache size = 16MB for now Index the table using zobryist hashes (they are implemented in our base - chess.hpp) entry = table[position.hash % table_size]

[mateusz2173]

Should be done after this: #10

[DomiKoPL]

I will start working on this today.

[mateusz2173]

One more thing:

Operations on TT (write, read entry) should be safe to use with multiple threads.

We'll rely on it later.

One can do it with atomics or lockless tricks (like here https://www.chessprogramming.org/Shared_Hash_Table#Lockless) or whatever you consider good enough

[DomiKoPL]

Ohhhh, that changes things a bit. Sure I will change it.

[mateusz2173]

Thx and sorry for the confusion

[DomiKoPL]

I should come up with some solution by the EOW.

[DomiKoPL]

@mateusz2173 Should TT also include age?

[mateusz2173]

If it doesnt require a lot of effort, let's include it.