Emanuel's Proximity Table -- The Shift of a Paradigm

[klx]

Introduction
For 50 years, the transposition table has been the back bone of chess engines. I am here to tell you, that you are all doing it wrong.

Background
The premise of the transposition table ("TT") is constant time access. You create your hash (Zobrish), and look it up, in instant time right? Well, on a recent 150 km bike ride, my mind started wandering. What is actually "constant time"? How has hardware changed since 1970? It suddenly struck me: The transposition table is an outdated concept. Today's technology calls for new development. This moment was the birth of... Emanuel's Proximity Table!

As I returned home, I sat down to code. 45 minutes later, I had my first proof of concept. The results were beyond what I could have hoped for. For large TTs, order of magnitude improvement is possible!

So, at this point, you must wonder: How can Emanuel's Proximity Table achieve these speedups?

Emanuel's Proximity Table
The key realization is: CACHE AWARENESS

A constant time lookup is not a constant time lookup.

There is L1 cache, L2 cache, L3 cache, etc. The speed of a single lookup in RAM can vary from just 1 ns to ~100 ns depending on cache availability.

Let us now look at how a TT works: Every lookup will basically be at a "random" (Zobrish) position, incurring a very costly cache miss on every single access. The key idea behind Emanuel's Proximity Table is the opposite: to put subsequent lookups next to each other in memory, minimizing the amount of cache misses. In essence, it eliminates the "random access" part of "Random Access Memory".

Of course, the TT access time is not the only costly thing in a chess engine. But with 2 accesses for every position (one read one write), and no other expensive memory lookups (note that things like Piece Square Table and History Heuristic Table are small enough to remain cached), it will be a major contributor of total search time.

[hgm]

The problem is that at the time you write the position in the TT you have no idea when it will be probed. This will not occur in the same order. If the place in memory where you store a position depends on what you happened to store just before it, there is no way to find it back in another context. You need an absolute mapping of positions to memory locations, not one that depends on what you last did before (which will be different every time).

So your idea doesn't seem to work at all.

[xr_a_y]

For sure, "cache aware hashing" is not a new subject

https://www.itu.dk/people/pagh/papers/cohash.pdf
https://www.cs.cmu.edu/~damon2006/pdf/z ... ashing.pdf
http://ce-publications.et.tudelft.nl/pu ... orithm.pdf
https://people.csail.mit.edu/sanchez/pa ... .micro.pdf
...

but probably, for now, it is not a big success for chess engine where the hash is/must be incrementally updated. What is your proposition ?

[Mergi]

How has hardware changed since 1970?

What also changed since the 1970, besides cache, is that now you have many cores running simultaneously even on the cheapest hardware. Is your tt "sorting" technique SMP friendly?

put subsequent lookups next to each other in memory

Can you give some more detail on how this is achieved?

[Sopel]

The results were beyond what I could have hoped for. For large TTs, order of magnitude improvement is possible!

What did you benchmark? How realistic was it?

Judging from the fact that your post has no actual code I assume it was a very simple test to measure the RAM and L1 access latency. Modern engines have a lot of stuff to do before the TT probe is needed and after the TT key is known, so they prefetch the TT entry, hiding the latency - did you take this into account?

[AndrewGrant]

The results were beyond what I could have hoped for. For large TTs, order of magnitude improvement is possible!

What did you benchmark? How realistic was it?

Judging from the fact that your post has no actual code I assume it was a very simple test to measure the RAM and L1 access latency. Modern engines have a lot of stuff to do before the TT probe is needed and after the TT key is known, so they prefetch the TT entry, hiding the latency - did you take this into account?

http://talkchess.com/forum3/viewtopic.php?f=7&t=77549
Read that Sopel, and you probably won't read the rest of this thread as it develops.

[klx]

Modern engines have a lot of stuff to do before the TT probe is needed and after the TT key is known, so they prefetch the TT entry, hiding the latency

Ooh, that's... a very smart approach, thanks for sharing.

[klx]

New idea!

Emanuel's Prefetching Proximity Table

[smatovic]

Looking forward for the Emanuel Tree Pruning

Seriously, there is IMO nothing wrong in reinventing the wheel or come up with some ideas, but consider that on this forum there are chess programmers present who are since 40+ years active on this topic, or alike.

--
Srdja

[klx]

Looking forward for the Emanuel Tree Pruning

Ask, and you shall receive. I just discovered Alpha-Emanuel-Beta search; monumental improvement over regular Alpha-Beta:

http://talkchess.com/forum3/viewtopic.php?f=7&t=78079