Everyone probes for interior nodes, the main point of the TT is to get the cut-move from the previous iteration. Leaf nodes would not have been searched in the previous iteration, and getting their score from a transposition will hardly save any work, as you already are in a leaf, so that there is no tree to search to get the score.Pio wrote: ↑Mon Jul 13, 2020 10:12 pmMy engine does also not use Zobrist but uses instead a series of multiplications, shifts and XOR-ing but of course my engine is really bad. I think Zobrist-hashing is extremely smart and much better than what I currently do.
I have one idea for a maybe new type of replacement strategy. What about using a scheme that keeps the read entries and kicks out the seldom accessed ones. My idea is as follow (let’s take a four entry bucket as an example):
1) when saving an entry always save it as the last entry and kick out the existing entry at its place, i.e. save the new position as entry 4 by overwriting what is there (should not be done if the positions are the same and the depth is less for the new one, then you just keep the old information since it is more precious)
2) when reading the TT and getting a hit you bump up the read entry and bump down the entry that is replaced. For example if you access/read entry 3 you bump it up to entry 2 and bump the previous entry 3 down to entry 2. If you read the first entry you don’t do anything.
I guess my replacement strategy will work better for those engines that also probe interior nodes since otherwise my replacement strategy might kick out deeper entries too much.
Some nice properties of the strategy is that:
1) it is very simple
2) unreachable positions will quickly be kicked out since they won’t be accessed
3) You will not need an age field and can thus make the entries a little bit smaller and simplify the logic
4) If the TT is probed for interior nodes the TT will keep more of the deeper entries
What do you think?
/Pio
Your method is not simpler than what is usually done: you would have to swap entries, and entries usually consist of more than a single machine word. Normally one leaves the entries in place, and just overwrites one of those.
The way the deepest entries are preserved in your scheme is rather indirect and unreliable. Reading the depth directly is simple and reliable.
Note that the way we walk the tree is such that transpositions occur with decreasing frequencies. If a position can be reached by 4 independent moves of player A (assuming player B always played the same moves) A-B-C-D, there are 4! = 24 transpositions. The first one you encounter is A-B-D-C, which needs a different move 3 ply before the leaf, which happens fast). Then you will encounter A-C-D-B, which required a move change 5 ply before the leaf, which takes much longer. (You will skip A-C-B-D, which already gave a hash cut at A-C-B.) So accesses occur in bursts. This can easily make a shallow entry temporarily pass a deep entry in your scheme, leading to overwriting of the deep entry.