Size of Transposition Table Entry

[syzygy]

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]

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

[cdani]

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.

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!

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.

[Evert]

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]

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).

[lucasart]

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.

[cdani]

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]

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.

[Houdini]

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.

[Houdini]

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!