1599 views

Skip to first unread message

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:

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?

- 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?

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.

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

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

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

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.

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

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

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?

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

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

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.

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

http://tests.stockfishchess.org/tests/view/542e32f80ebc5944e6bdf4bb

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.

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

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.

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

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

Oct 5, 2014, 12:58:17 PM10/5/14

to fishc...@googlegroups.com, m_ste...@yahoo.com

Sure, sounds interesting!

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.

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.

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

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 :(

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!

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

>

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.

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.

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

1/ 16-bits are enough

2/ no sign of degradation as time control increases. seems evenopposite (but not significant).

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.

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.

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.

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

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.

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

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?

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

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.

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.

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.

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.

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

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!

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

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.

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.

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.

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

Search

Clear search

Close search

Google apps

Main menu