Size of Transposition Table Entry

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4451
Joined: Tue Feb 28, 2012 10:56 pm

Re: Size of Transposition Table Entry

Post by syzygy » Sat Sep 30, 2017 8:53 pm

Evert wrote:I switched to a dual-bound table a while back, but I haven't really noticed a difference in practice.
I wonder how dual bounds can ever be useful. It seems to me the older bound will almost never have sufficient depth to cause a cutoff. (It also seems doubtful to me that many nodes switch types from AND to OR and back.)

tomitank
Posts: 200
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Size of Transposition Table Entry

Post by tomitank » Sat Sep 30, 2017 9:04 pm

cdani wrote:
BeyondCritics wrote:Where does "secondmove" come from? Or is this a trade secret?
I save a second move to the hash sometimes. Was a little win.
The next Andscacs after 0.92 will be open source. The details will be clear then.
Very good news!

-Tamas

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Size of Transposition Table Entry

Post by cdani » Sat Sep 30, 2017 9:13 pm

Houdini wrote: Houdini 3 and 4 also used a second hash move, it gained a couple of Elo (less than 5 Elo).
Yes, less than 5 elo.
Houdini wrote: Surprisingly few entries actually contained a second move, did you ever verify the statistics on that?
I just verified it. Of 13147907 operations of saving hash, only 464 had a second move. Is much less than what I supposed!
Houdini wrote: In Houdini 5 and 6 I've dumped the second move in favor of some evaluation-related information, which proved to be a more profitable usage.
Nice! I bet that is king safety related :-) I thought about it many times, and is in the list of things to try seriously. Sure I will do it :-) And I think I will be able to maintain both informations.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Size of Transposition Table Entry

Post by Evert » Sat Sep 30, 2017 9:21 pm

syzygy wrote:
Evert wrote:I switched to a dual-bound table a while back, but I haven't really noticed a difference in practice.
I wonder how dual bounds can ever be useful. It seems to me the older bound will almost never have sufficient depth to cause a cutoff. (It also seems doubtful to me that many nodes switch types from AND to OR and back.)
Well, the idea was that they could be helpful for analysis in "worst case" positions. In practice it doesn't seem to help much (not that it hurts either).

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Size of Transposition Table Entry

Post by mcostalba » Sun Oct 01, 2017 8:20 am

Houdini wrote: In Houdini 5 and 6 I've dumped the second move in favor of some evaluation-related information, which proved to be a more profitable usage.
With evaluation-related information perhaps you mean you store the static eval in TT? C'mon don't be shy, you can say it....hey, now that I look better....we also do that:

Code: Select all

/// TTEntry struct is the 10 bytes transposition table entry, defined as below:
///
/// key        16 bit
/// move       16 bit
/// value      16 bit
/// eval value 16 bit
/// generation  6 bit
/// bound type  2 bit
/// depth       8 bit

What a nice surprise! We got the same idea :-)


We store entries in a single cluster aligned and within the cache size:

Code: Select all

  struct Cluster {
    TTEntry entry[ClusterSize];
    char padding[2]; // Align to a divisor of the cache line size
  };

  static_assert(CacheLineSize % sizeof(Cluster) == 0, "Cluster size incorrect");
So it is fetched in one go and storing the first bytes in the first word and other pseudo-smart tweaks don't have any advantage apart an obvious slowdown and useless increased complexity (as 99% of all so called optimizations are).

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Size of Transposition Table Entry

Post by lucasart » Sun Oct 01, 2017 8:42 am

mcostalba wrote:
Houdini wrote: In Houdini 5 and 6 I've dumped the second move in favor of some evaluation-related information, which proved to be a more profitable usage.
With evaluation-related information perhaps you mean you store the static eval in TT? C'mon don't be shy, you can say it....hey, now that I look better....we also do that:

Code: Select all

/// TTEntry struct is the 10 bytes transposition table entry, defined as below:
///
/// key        16 bit
/// move       16 bit
/// value      16 bit
/// eval value 16 bit
/// generation  6 bit
/// bound type  2 bit
/// depth       8 bit

What a nice surprise! We got the same idea :-)


We store entries in a single cluster aligned and within the cache size:

Code: Select all

  struct Cluster {
    TTEntry entry[ClusterSize];
    char padding[2]; // Align to a divisor of the cache line size
  };

  static_assert(CacheLineSize % sizeof(Cluster) == 0, "Cluster size incorrect");
So it is fetched in one go and storing the first bytes in the first word and other pseudo-smart tweaks don't have any advantage apart an obvious slowdown and useless increased complexity (as 99% of all so called optimizations are).
Storing the static eval in the TT is not a SF invention, if that's what you're trying to insinuate. It was there in Glaurung. It was there in Fruit long before, and I'm sure it was there in Crafty long before, and others too. It's one of the oldest tricks in the book. And so is cache line alignment.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Size of Transposition Table Entry

Post by cdani » Sun Oct 01, 2017 8:51 am

lucasart wrote: Storing the static eval in the TT is not a SF invention, if that's what you're trying to insinuate. It was there in Glaurung. It was there in Fruit long before, and I'm sure it was there in Crafty long before, and others too. It's one of the oldest tricks in the book. And so is cache line alignment.
Of course. Robert means something different.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Size of Transposition Table Entry

Post by mcostalba » Sun Oct 01, 2017 9:01 am

lucasart wrote:It was there in Glaurung.
Glaurung didn't need to do it becuase it was evaluating only at the leafs. But of course it is not a SF novelity.

User avatar
Houdini
Posts: 1471
Joined: Mon Mar 15, 2010 11:00 pm
Contact:

Re: Size of Transposition Table Entry

Post by Houdini » Sun Oct 01, 2017 10:56 am

mcostalba wrote:With evaluation-related information perhaps you mean you store the static eval in TT? C'mon don't be shy, you can say it....hey, now that I look better....we also do that:
Don't be such an ass, please. You can do better than that.

Houdini 5 and 6 store threat-related and king safety info in the hash table.

User avatar
Houdini
Posts: 1471
Joined: Mon Mar 15, 2010 11:00 pm
Contact:

Re: Size of Transposition Table Entry

Post by Houdini » Sun Oct 01, 2017 10:59 am

cdani wrote:I just verified it. Of 13147907 operations of saving hash, only 464 had a second move. Is much less than what I supposed!
Surprising, isn't it?
The most astonishing is that even this extremely low fill ratio produces some measurable Elo gain!

Post Reply