Using the TranspositionTable for long searches

1598 views
Skip to first unread message

Theodr Elwurtz

unread,
Sep 22, 2014, 3:32:08 PM9/22/14
to fishc...@googlegroups.com

I have two questions about how the Transposition Table works: (1) Are bits ignored in the key (and if so is this safe)? and (2) can I use the TT for very long searches?


Question 1: the Key Size

---------------------------------


I understand a TranspositionTable (TT) consists of a clusterCount clusters, where each cluster holds 3 TT entries. Each cluster has size 32 bytes. The whole TT holds clusterCount*3 TTEntry's, each of which represents one position.


When a Key is probed using probe(), the lower bits are used as an index into the clusters. Once the right cluster is chosen, the high 16 bits of the Key are used to find the matching TTEntry within that cluster.


For example, in a 1MB hash table, the clusterCount would be 2 to the 15 (which is 2 to the (20-5)). Therefore, when a Key is probed, the lower 14 bits of the Key would be used index into the clusters, and the upper 16 bits of the Key would be used to select the one of the three TTEntry's in that cluster.


This means that only 30 bits of the key are actually used; the other 34 bits of the Key of a position are ignored.


Am I understanding that right? Only 30 bits of the key would be used in a 1MB hash table (and likewise only only 35 bits in a 32M hash table)?


If so, wouldn’t using only 30 bits of key lead to a substantial risk of key clashes, in which probe() returns the TTEntry corresponding to a position that is different from the one searched for? I understand that there are some old papers suggesting that smaller key sizes don’t affect the performance much, but I don’t think those dealt with only 30-bit effective keys and, even if they did, searches nowadays routinely search a lot more nodes than when those papers were written.


Question 2: long searches

------------------------------------

Suppose I wanted to search a position very deeply, over several days. I might easily search 100s of billions of nodes in that one search. I have two concerns here:


  1. If the premises of question 1 is right, then say a 2 GB TT (for a 41-bit effective key) is probably not going to be usable for this due to key clashes, right?


  1. Since the generation of each TTE will be the same, will there be some kind of “churn” or other problems with the TT in this case? Are there other concerns with dealing with this use case vis-a-vis the TT? That is, the number of nodes in a single search is much larger than the TT itself: is this a problem?

Marco Costalba

unread,
Sep 24, 2014, 2:48:48 AM9/24/14
to Theodr Elwurtz, fishc...@googlegroups.com
Question 1: the Key Size

You understand it right. Change was tested under different conditions and passed the tests: so change is good.

Here we only use real games tests to validate a change, we don't use papers, argumentation, assumptions, impressions, doubts, deductions, etc: here we only use real games test, if test passes then change is good.

Question 2: long searches

You can search for months: there are no problems, the entries are anyhow overwritten by new ones as search goes on, so an entry alias does not live forever and you end up with a stable average number of aliases in TT that depends on the TT size, not on the time you search on it.


m_ste...@yahoo.com

unread,
Sep 24, 2014, 4:10:40 AM9/24/14
to fishc...@googlegroups.com, theodr....@gmail.com
I understand the search is somehow robust to deal even with cases of hard collisions correctly. Could someone point out the specific code that makes that happen?

Thanks Fisherman

Ronald de Man

unread,
Sep 30, 2014, 3:09:09 PM9/30/14
to fishc...@googlegroups.com
On Wednesday, September 24, 2014 10:10:40 AM UTC+2, m_ste...@yahoo.com wrote:
I understand the search is somehow robust to deal even with cases of hard collisions correctly.  Could someone point out the specific code that makes that happen?

Thanks Fisherman

I'm sure nobody has ever claimed that.
What is said is that it has been tested as usual: playing games.

(Now I'm still no fan of this change, and I did just happen to notice that SF isn't doing all that well in TCEC, which is most likely just a statistical aberration but... might also be the first real test to see how SF copes with an awful lot of collisions per search? Certainly too early to tell.)

Uri Blass

unread,
Sep 30, 2014, 3:51:46 PM9/30/14
to fishc...@googlegroups.com
I think that it may be interesting to see if there are tablebases positions when stockfish without tablebases cannot find the right move because of hash collisions.

The way to check it can be to generate some thousands of random positions from 6 piece tablebases of long mates(mates in 30-50 moves) and see if new stockfish(with 100 million nodes per position) perform worse because of the new hash code or not. 

m_ste...@yahoo.com

unread,
Oct 1, 2014, 12:42:36 AM10/1/14
to fishc...@googlegroups.com
@Ronald

Marco once mentioned that collisions were just an efficiency issue so I (perhaps incorrectly) assumed there was some way of handling them.
"Our code allows collisions and there is not a problem with collisions apart from inefficiency…"
https://github.com/mcostalba/Stockfish/pull/132#issuecomment-28180066
I guess a better question I would like to ask is what actually happens after a hard collision occurs?


As far as current TCEC, I think you are correct about it being a statistical aberration because I believe the switch to 16 bit keys happened before the FRC special event in which Stockfish did very well.


I also tested a 21 bit key patch which is the most we can currently pack in but it failed because the implementation is a bit slower.
http://tests.stockfishchess.org/tests/view/53df84850ebc592db1a06432

Uri Blass

unread,
Oct 1, 2014, 2:11:04 AM10/1/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Stockfish does not crash even after long searchs so it is obvious that stockfish code allows collision.

The main question is not if stockfish's code allow position.

Maybe a collision can cause stockfish to show a mate score for a drawing move in tablebase position or to show a draw score in a tablebase position when you have a forced mate but the question is what is the probability that it happens and if the probability is higher after a long search.

In other words 
1)what is the probability that it happens with 1 core after 1000000 nodes?
2)What is the probability that it happens with 1 core after 100,000,000 nodes?

Stefan Geschwentner

unread,
Oct 1, 2014, 4:25:25 AM10/1/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
The TT-patch was commited at June 28 but the Version which played at TCEC-FRC event is dated from June 26. So this patch is not tested on very long time control.
If we want simulate on our STC the hash pressure under TCEC conditions we have to use a hash around 2.65 MB or LTC 10,6 MB by using one core.

There are many tests to this topic but i don't now if there the finaly commited version was tested. There was so many discussion and testing that i'have lost track!

Perhaps we should try a retest.

My result based on following numbers:
- TCEC hash: 16 GB = 16384 MB
- TCEC time: 120 min = 7200 sec
- TCEC speed: 18 Mn/s
- STC time: 15 sec
- STC speed: 1.4 Mn/s

So STC-hash = (STC-time / TCEC-time) * (STC-speed / TCEC-speed) * TCEC-Hash
                    = (15 / 7200) * (1.4 / 18) * 16384 ~ 2.65 MB

m_ste...@yahoo.com

unread,
Oct 1, 2014, 5:10:47 AM10/1/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I was wrong about which version was used in the TCEC FRC. Good catch Stefan. Sorry for the misinformation.

m_ste...@yahoo.com

unread,
Oct 3, 2014, 1:29:22 AM10/3/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I have scheduled a low priority test (STC 2MB hash) to see how much elo we lose if we reduce the key by 2 more bits which should result in 4 times as many hard collisions. If we don't lose much/anything I think that would indicate 16 bits is enough. If we lose a lot then perhaps 16 bits is already too few.
http://tests.stockfishchess.org/tests/view/542e32f80ebc5944e6bdf4bb

Stefan Geschwentner

unread,
Oct 3, 2014, 2:08:59 PM10/3/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Good idea. I'am interrested in the result.

Ronald de Man

unread,
Oct 3, 2014, 4:52:26 PM10/3/14
to fishc...@googlegroups.com
On Friday, October 3, 2014 7:29:22 AM UTC+2, m_ste...@yahoo.com wrote:
If we don't lose much/anything I think that would indicate 16 bits is enough.

Unless the negative impact of 16 bits is only felt at really long time control (such as TCEC-like).

At the very short time controls used in testing, the "absolute quality" of the moves won't be very high and some inaccuracy might not have much of an effect.
The more time control is increased, the closer SF needs to get to "perfection", but the inaccuracies might form a barrier on the way to perfection that SF can't cross.

I'm only speculating. (And I'm very biased on this particular point: I do not like this patch at all.)

Uri Blass

unread,
Oct 3, 2014, 5:30:01 PM10/3/14
to fishc...@googlegroups.com
I think that we need to see the minimal number of bits for different time controls.
If 14 is enough for short time control we should try 12 and if 12 is enough we should try 10.

After we find the minimal number of bits that we need for 15+0.05 we may try the same for 60+0.05 and 240+0.05 to see if this number is increasing.

m_ste...@yahoo.com

unread,
Oct 5, 2014, 6:09:18 AM10/5/14
to fishc...@googlegroups.com
Ok the results of 14 bits vs 16 bits at STC 2MB hash are:

ELO: -1.84 +-2.2 (95%) LOS: 4.7%
Total: 40000 W: 7925 L: 8137 D: 23938

I think less than 2 elo isn't too bad. This is how I interpret it… 16 bits has some unknown number of collisions and therefore an unknown elo loss relative to an ideal no collisions version. 14 bits has 4 times as many collisions (75% more) as 16 bits which only results in an additional 2 elo loss. I therefore "assume" that the unknown elo loss resulting from the original 25% of collisions relative to no collisions is smaller than 2 elo. The 2 elo should be more than made up for by squeezing 50% additional entries in the hash which is why the patch passed in the first place. Still, I would like to schedule another STC 2MB test with 12 bits to see if it produces an additional elo loss which should be greater than 2 elo to confirm this reasoning.

Secondly given the current unexpectedly poor performance at TCEC I think it is worth verifying that collisions scale as expected with TC and hash size. That is I would like to schedule the same 14 vs 16 test but at LTC and 8MB hash. The elo loss should NOT be significantly larger than the 2 elo we measured at STC 2MB.

Finally if someone wants to speculate… Do you think that collisions are more likely to result in Stockfish playing many slightly sub optimal moves(hard to notice) or a few outright blunders(easy to notice)?

Gary Linscott

unread,
Oct 5, 2014, 12:58:17 PM10/5/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Sure, sounds interesting!

X

unread,
Oct 6, 2014, 7:33:10 AM10/6/14
to fishc...@googlegroups.com
If 16 bits is deemed not enough then it's possible to store ((32 bits of key) XOR move) instead of (16 bits of key, move) , and validate the move is legal or MOVE_NONE (which usually needs to happen anyway) when reading TT. For speed, don't check move in qsearch. This doesn't need extra memory and would decrease collisions a lot.

Uri Blass

unread,
Oct 7, 2014, 2:33:10 AM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
The surprising result of 12 bits suggest that in order not waste computer time it is better to try to test with less bits because I want to see significant drop at short time control and 12 bits is not enough for it.

Maybe start testing with 4 bits and 6 bits is better in order to see if you lose more elo with longer time control and more hash and 20K games is hopefully enough to see a significant difference.

m_ste...@yahoo.com

unread,
Oct 7, 2014, 7:37:05 PM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Updated results:
12 bit STC 2MB
ELO: -1.41 +-2.2 (95%) LOS: 10.3%
Total: 40000 W: 8143 L: 8305 D: 23552

14bit LTC 8MB so far
ELO: -0.49 +-2.4 (95%) LOS: 34.7%
Total: 27206 W: 4655 L: 4693 D: 17858

I would like to thank Thomas Zipproth whose counting TT errors post
https://groups.google.com/forum/?fromgroups=#!topic/fishcooking/Yh2DstiRPS4
made me realize that in a steady state (full hash) the hash size has no effect on the number of collisions. Only the key size does.

That means my 12bit STC test will have about the same number of collisions per move as my 14bit LTC test. The test results show that these bit counts are essentially enough for these time controls and nps. Since TCEC searches about (120min * 60sec/min * 18Mn/s) / (15sec * 1.4Mn/s) ~= 6000 times more nodes per move it needs 12 to 13 bits more for the key than fishtest STC needs to maintain the same number of total collisions per move. I think it is worth determining the minimum number of bits needed for STC and I will schedule another STC test with 8 bits 20K games along Uri's suggestion to see how it does. We can then add 12 or 13 bits and that should be the minimum for TCEC. Even more bits are required for postal or overnight analysis obviously. I'm starting to think that unfortunately the sardines patch is in fact a problem because if 16 bits was to be enough for TCEC only 4 bits would have to be enough for STC :(

Gary Linscott

unread,
Oct 7, 2014, 8:27:59 PM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
An interesting thought experiment is what if we stored 2^48 buckets?  Then we would consider ourselves to have no collisions, but of course, there would be a huge number of collisions, we just aren't able to detect them with a 64 bit zobrist.  I'm not sure how the math works, but clearly 2^47 buckets is worse than 2^48, and 2^46 is worse than 2^47.  But, by how much?

At TCEC 16Gb = 2^29 tt clusters of 3 entries each, so we have 2^45 bits of hash key that we use.  Out of the 64 bits, that leaves 19 bits unaccounted for, so each bucket will store 2^19 ~ 500k different 64 bit hash keys.  That's very different from a STC search using 2mb = 2^16 tt clusters.  That is leaving 32 bits unaccounted for, so each bucket has to store ~4 billion different keys.

With ~2^155 total chess positions possible, we have a huge number of potential collisions at 64 bits anyway (although probably not likely, as chess engines search such a small space of the total tree).  It's a hard problem to analyze!

m_ste...@yahoo.com

unread,
Oct 7, 2014, 9:11:16 PM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
On Tuesday, October 7, 2014 5:27:59 PM UTC-7, Gary Linscott wrote:
> An interesting thought experiment is what if we stored 2^48 buckets?  Then we would consider ourselves to have no collisions, but of course, there would be a huge number of collisions, we just aren't able to detect them with a 64 bit zobrist.  I'm not sure how the math works, but clearly 2^47 buckets is worse than 2^48, and 2^46 is worse than 2^47.  But, by how much?
>

The amazing thing is that more buckets is NOT better once you fill the hash(and this happens across moves because the hash doesn't get cleared). You will get less collisions per each bucket but the same number of total collisions. Basically you select a bucket (from a few or many buckets) and then compare your key to the key in the bucket. The chance of the keys being randomly/falsely the same ONLY depends on the size of the keys. The more nodes you search the more such comparisons you make each time exposing yourself to a potential collision and accumulating the risk.

Uri Blass

unread,
Oct 7, 2014, 9:15:09 PM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I think that it is possible that the same number of collisions cause bigger rating reduction at faster time control and I guess that you will see bigger difference in rating with 8 bits short time control relative to 10 bits long time control.

Note that I do not suggest to test 10 bits long time control unless you see rating reduction of at least 10 elo at short time control with 8 bits and I suggest to reduce the number of bits until you see at least 10 elo reduction in playing strength and only when you see it test again at longer time control with 2 more bits.

m_ste...@yahoo.com

unread,
Oct 7, 2014, 9:45:55 PM10/7/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Agree with all u said Uri. If no one objects I'll also cancel the rest of the 14 bit LTC test since I think we already got what we needed from it.

One additional clarification. The statement that only the key size matters for total collisions is basically only true if you search significantly more nodes through the course of the game than you have buckets in the hash. This is true in most circumstances and in TCEC. i.e. the hash gets full relatively quickly. If you had a huge hash like 2^48 then you would avoid collisions because you would never fill it and reach a steady state.

lucas....@gmail.com

unread,
Oct 8, 2014, 2:08:20 AM10/8/14
to fishc...@googlegroups.com
Thank you. Your tests are interesting. They prove, once again, that:
1/ 16-bits are enough
2/ no sign of degradation as time control increases. seems evenopposite (but not significant).

Joachim Rang

unread,
Oct 8, 2014, 2:49:15 AM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Wait a minute: All test so far show only a small loss even with 12 bits (this is what - 16x times more hash collisison?) and you somehow conclude that:


"the sardines patch is in fact a problem  because if 16 bits was to be enough for TCEC only 4 bits would have to be enough for STC"

I can't follow you here, sorry.

Joachim Rang

unread,
Oct 8, 2014, 2:55:20 AM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
On Wednesday, October 8, 2014 3:45:55 AM UTC+2, m_ste...@yahoo.com wrote:
Agree with all u said Uri.  If no one objects I'll also cancel the rest of the 14 bit LTC test since I think we already got what we needed from it.

I'm against cancelling the test. It is not flawed and should run till the end. Fixed number of game tests are supposed to run a a priori determined nunmber of games and should only aborted if there is a problem with the test itself.

Joachim Rang

unread,
Oct 8, 2014, 3:04:38 AM10/8/14
to fishc...@googlegroups.com
I think the 8 bit key test should run to 40k games as well for comparison reasons.

m_ste...@yahoo.com

unread,
Oct 8, 2014, 7:36:08 AM10/8/14
to fishc...@googlegroups.com
Thanks for your comments.

@Lucas
1/ I agree that the tests prove 16 bits is more than enough at fishtest TC's ONLY. In fact 12 bits(maybe less) is enough for STC.

2/ The reason we see no degradation from 14 bits STC to 14 bits LTC is because 14 bits are also more than enough for both TCs.
If 14 bits have (almost) no collisions at STC then having 4 times as many collisions at LTC will still be (almost) no collisions.

TCEC searches about 6000!! times more nodes per move than fishtest STC. That means a collision is 6000 times more likely on any given move. To compensate for a 6000 fold increase in collisions requires somewhere between 12 (2^12=4096) and 13 (2^13=8192) extra bits. So whatever minimum number of bits we find out to be the minimum for STC will have to be at least 12 bits more for TCEC. We should know that number soon.

@Joachim
1/ Yes. I'm saying that TCEC needs minimum 12 more bits than fishtest STC.

2/ I posted to see if anyone had objections to canceling the now IMO no longer appropriate LTC test so since you object I won't cancel it.
Note though that I scheduled it before Thomas posted his results
https://groups.google.com/forum/?fromgroups=#!topic/fishcooking/Yh2DstiRPS4
and I didn't realize that a larger hash size doesn't reduce collision rate once it's full.

3/ We are just trying to find the minimum number of bits that loses around 10 elo at STC now. 20K games is enough for that.

Fisherman

Marco Costalba

unread,
Oct 8, 2014, 8:19:35 AM10/8/14
to m_ste...@yahoo.com, fishc...@googlegroups.com
 So whatever minimum number of bits we find out to be the minimum for STC will have to be at least 12 bits more for TCEC.   


Why ?

Your above statement would be valid if a single collision corresponds to a changed and bogus root move. But this is far from proven.

Actually on a single search you can have many collision that do not impact root move, especially when you search very deep. Indeed after each ID iteration all the previous collision are harmless, so it is only the collision on the last iteration that could theoretically impact root move, but also in that case is far from clear.

So your calculations are just guessing and hand waiving but are based on nothing. 
 

Uri Blass

unread,
Oct 8, 2014, 9:37:22 AM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I totally agree and in order to claim that you need more bits for longer time control you need to prove that you need more bits for 60+0.05 relative to 15+0.05 when the hash is proportional to the time control.

I am finally happy that it seems that you lose significant number of elo points 
and so far
8 bits and 2 mbytes and 15+0.05 show -36.17 +-8.7

The interesting question to test is if you lose more elo from 
8 bits and 8 mbytes and 60+0.05

If we do not find that you lose more elo then it means that there is no reason to be afraid of elo loss in TCEC time control

Joachim Rang

unread,
Oct 8, 2014, 10:54:59 AM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com

@Joachim
1/ Yes.  I'm saying that TCEC needs minimum 12 more bits than fishtest STC.  

 

I hear you saying that but like Marco I don't understand your reasoning. For me it seems you are just stating something but I don't understand why? Of course hash collisions will increase when you search longer, but the errors per read/write should not, so why would it be more harmful for longer time controls?
 

Uri Blass

unread,
Oct 8, 2014, 4:37:07 PM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I think that it may be the opposite and the main disadvantage of hash collisions is at short time control

Unfortunately nobody designed a test of 20000 games for key8 with 8 mbytes hash and 60+0.05 and I wonder if it is ok if I simply reschedule key8 for these conditions.

I think that results are more interesting than results of key10

m_ste...@yahoo.com

unread,
Oct 8, 2014, 5:22:11 PM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
@Marco
Hi Marco.
I hope I can clarify. My statement doesn't require that a single collision correspond to a change in root move.
I even believe that most don't. I only require that each collision has some non zero probability of affecting
the root move. Then if you increase the number of collisions the total probability of affecting the root move
also goes up. If that total probability was tiny to begin with increasing collisions doesn't matter much.
If the total probability was already somewhat significant increasing collisions in that case will matter a lot.
Since the last iteration of a search on a fast machine at long TC searches many more nodes than the last iteration
of a search on a slow machine at short TC the number of collisions will be higher and the chance of affecting the
root move will also be higher. To keep the probability constant you need to add one bit to the key for every
doubling of nodes searched. The TCEC machine searches about 6000 times more nodes on its last iteration than
fishtest STC so that works out to more than 12 extra bits.

@Joachim
Yes the errors per read/write will not change but there is more reads and writes so more total errors. It's the
total per move that is important not the rate. Any collision has the potential to screw up the search. Kind of
like Russian roulette.

@Uri
1) Yes I agree and have scheduled an 8 bit LTC 8MB hash test.
http://tests.stockfishchess.org/tests/view/5435a9a00ebc593bff3043e2
If the results are NOT significantly worse than the 8 bit 2MB STC I will admit being wrong about the effects of TC.
If they are significantly worse I hope others will be convinced that TC matters. Stay tuned!

2) If you now think it may be the opposite please explain why and schedule any necessary tests to show it is so.

Joseph Ellis

unread,
Oct 8, 2014, 5:51:11 PM10/8/14
to fishc...@googlegroups.com
If some false value does screw up the search, then shouldn't it be re-searched fairly quickly?

Plus, if the best move changes, we allow more time.  So it is only a significant danger if we are already near max time.

Uri Blass

unread,
Oct 8, 2014, 5:52:30 PM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
1)Thanks for scheduling a test for 8key with 8 mbytes at long time control.

2)We will see by the result if you lose less elo or more elo at long time control.
My guess may be wrong but my guess is that you lose less elo in the new test.

I will explain my reasons.
I think that the main problem with collision is when they happen close to the root.

I think that bigger hash and longer time control mean that the distance to the root is higher and it means that the mistakes have smaller probability to change the root move. 

Note that I use stockfish for analysis of correspondence games with 1024 mbytes hash and 3 cores and at this point of time I saw no evidence for bad moves after many hours of search so my feeling is that errors are relatively less  important when you
go deep in the tree because every bad move close to the root usually has many ways to refute and it is enough to refute it by one way.

Marco Costalba

unread,
Oct 8, 2014, 6:00:49 PM10/8/14
to m_ste...@yahoo.com, fishc...@googlegroups.com
I think is the density of collisions (collisions per nodes)  that counts, not the absolute value. 

A collision far deep in the search tree has a much smaller probability to back propagate to root node than a collision at small depth. So in case of LTC a collision that on average is deeper than at STC it is also on average less dangerous and this counterbalance on a qualitative basis the increase of absolute number of collisions at LTC

m_ste...@yahoo.com

unread,
Oct 8, 2014, 7:09:39 PM10/8/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I concede that all you guys understand how the search behaves much better than I do so I take your opinions in that area over mine. Let's just see how the test results come out. Go fishtest!

Uri Blass

unread,
Oct 9, 2014, 1:06:06 PM10/9/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
I do not claim to be sure that I understand how the search behaves and I only guess.

The result that I see convince me that there is no risk at TCEC time control.

The only open question is about correspondence games(I strongly believe that there is no significant risk but not totally sure).

In order to check it,   it is possible to try to test key8 with 2 mbytes hash at 60+0.05 to see if you lose significantly more elo relative to 15+0.05 with 2 mbytes hash.
If the elo loss is nearly the same then I can feel sure that there is no problem in correspondence games even if you use only 2 mbytes hash
because you can translate 28 elo loss with 8 bits probably to not more than  28/(2^(16-8)) elo loss with 16 bits(and practically nobody use 2 mbytes for long analysis). 

Note that I divide by 2^8 based on comparison between key8 and key10
key8 showed 28.03 elo loss
key10 showed 5.79 elo loss that is not more than 28.03/(2^(10-8))=28.03/4>7

m_ste...@yahoo.com

unread,
Oct 9, 2014, 2:13:36 PM10/9/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
Unless the 8bit LTC finishes differently than it started so far
ELO: -22.88 +-4.0 (95%) LOS: 0.0%
Total: 10400 W: 1515 L: 2199 D: 6686
I am now convinced by the data that there is no problem at long TC either.
Very good news!
I may still run a 20k 7.5'+0.05 1MB 8 bit to confirm it does even worse than STC because it's a very cheap test.

@Uri
If you think a 8bit 2MB LTC is worth it I leave it to you to schedule it.

Uri Blass

unread,
Oct 9, 2014, 2:43:40 PM10/9/14
to fishc...@googlegroups.com, m_ste...@yahoo.com
After more thinking I decided that I will probably do 8 bits 4 MB LTC at low priority(-3)

If you can multiply the hash by 2 and multiply the time control by 4 without a bigger loss in elo(not more than 28 elo loss)
then it is enough for me to feel sure that there is no problem with 1024 mbytes hash at correspondence game with the hardware of today.

Ronald de Man

unread,
Oct 9, 2014, 7:33:11 PM10/9/14
to fishc...@googlegroups.com
On Wednesday, October 8, 2014 2:27:59 AM UTC+2, Gary Linscott wrote:
An interesting thought experiment is what if we stored 2^48 buckets?

With 2^48 buckets, only 16 bits of a 64-bit hash key will be left to uniquely identify a position within a bucket. With 3 entries per bucket that means 1 false hit every 2^16/3 probes that should not have hit. (This assumes a saturated table.)

Basically, with such a hash table size one should use longer keys (i.e. more than 64 bits). (Of course not with the current approach which stores only 16 bits anyway.)
 
Then we would consider ourselves to have no collisions

We would not. It is only reasonable to use a hash table with 2^48 buckets if we search long enough to actually fill them. So we may assume all entries to be filled. Then we have reached the steady state with the false hit rate that I indicated above. So we should be well aware of the very large number of collisions.

 

At TCEC 16Gb = 2^29 tt clusters of 3 entries each, so we have 2^45 bits of hash key that we use.  Out of the 64 bits, that leaves 19 bits unaccounted for, so each bucket will store 2^19 ~ 500k different 64 bit hash keys.  That's very different from a STC search using 2mb = 2^16 tt clusters.  That is leaving 32 bits unaccounted for, so each bucket has to store ~4 billion different keys.

Just assume that the hash table is filled. The TCEC table is large, but TCEC searches are long, so the large table still gets filled (and anyway, the table is not cleared between moves!). Then the false hit rate becomes 1 every 65536/3 positions that should not have hit. (Most probes do not hit, but some do. That explains that the number looks more like 1 in 24000 than 1 in approx 22000. But 1 in 65536/3 is good enough as approximation for any table size.)

Reply all
Reply to author
Forward
0 new messages