Hash cutoffs and analysis

hgm · Post by **hgm** » Mon Jun 17, 2013 5:02 pm

Now that the engine I am building (HaChu) has a hash table, the PVs it produces during analysis get very short, especially if you play the move the engine indicated, or take a move back. This of course is undesirable.

Now I understand that the usual trick to prevent this is to suppress hash cuts in PV nodes. (I know it is also possible to hash entire PVs, but I am looking for something trivial for the time being. In Joker I extracted the PV from the hash table afterwards, but this was also a pain to program, and often gave repetitive PVs.)

My question, however, is how to know I have a PV node. The engine in question does not do node classification, and has a vanilla alpha-beta search. So typically the search window will always be open.

Is the trick to look at the score indicated by the (sufficient-depth) hash hit, and only cut when it fails high or low (with the proper bound type) compared to the current window, but continue searching when it is in-window (even if the bound type was exact)?

Daniel Shawul · Post by **Daniel Shawul** » Mon Jun 17, 2013 5:08 pm

My question, however, is how to know I have a PV node. The engine in question does not do node classification, and has a vanilla alpha-beta search. So typically the search window will always be open.

I was going to suggest beta != alpha+1 before i saw this. You are going to implement Scout sooner or later so why not wait till then.
Maybe be another alternative is to compare if (alpha,beta) are exactly same as that of the root's at odd plies and the opposite (-beta,-alpha) at even plies.

Don · Post by **Don** » Mon Jun 17, 2013 7:49 pm

hgm wrote:Now that the engine I am building (HaChu) has a hash table, the PVs it produces during analysis get very short, especially if you play the move the engine indicated, or take a move back. This of course is undesirable.

Now I understand that the usual trick to prevent this is to suppress hash cuts in PV nodes. (I know it is also possible to hash entire PVs, but I am looking for something trivial for the time being. In Joker I extracted the PV from the hash table afterwards, but this was also a pain to program, and often gave repetitive PVs.)

My question, however, is how to know I have a PV node. The engine in question does not do node classification, and has a vanilla alpha-beta search. So typically the search window will always be open.

Is the trick to look at the score indicated by the (sufficient-depth) hash hit, and only cut when it fails high or low (with the proper bound type) compared to the current window, but continue searching when it is in-window (even if the bound type was exact)?

I'm not sure there is an easy way to do this if there are no null window searches and no re-searches. is that the case?

You could consider always the first child starting at the root as a PV node and pass this flag to the search, but when the second or other move comes along as best you are screwed up. I think in order to properly classify a node as a PV node you have to sometimes re-search it.

tpetzke · Post by **tpetzke** » Mon Jun 17, 2013 8:11 pm

Is the trick to look at the score indicated by the (sufficient-depth) hash hit, and only cut when it fails high or low (with the proper bound type) compared to the current window, but continue searching when it is in-window (even if the bound type was exact)?

Yes, this is the way to do it. It also enables some other tricks. But I haven't tried it myself yet.

http://talkchess.com/forum/viewtopic.ph ... 78&t=45624

Thomas...

bob · Post by **bob** » Mon Jun 17, 2013 8:33 pm

hgm wrote:Now that the engine I am building (HaChu) has a hash table, the PVs it produces during analysis get very short, especially if you play the move the engine indicated, or take a move back. This of course is undesirable.

Now I understand that the usual trick to prevent this is to suppress hash cuts in PV nodes. (I know it is also possible to hash entire PVs, but I am looking for something trivial for the time being. In Joker I extracted the PV from the hash table afterwards, but this was also a pain to program, and often gave repetitive PVs.)

My question, however, is how to know I have a PV node. The engine in question does not do node classification, and has a vanilla alpha-beta search. So typically the search window will always be open.

Is the trick to look at the score indicated by the (sufficient-depth) hash hit, and only cut when it fails high or low (with the proper bound type) compared to the current window, but continue searching when it is in-window (even if the bound type was exact)?

Here's what I do, and it works amazingly well.

When you store a hash entry, and the score is EXACT, store the PV below this node in a separate hash table. There are not very many such stores, so the overhead is effectively zero in Crafty (measured). When you do a hash probe, and you get an EXACT entry match, go to the PV table, verify that the sig matches, and just append that PV to what you have here.

I RARELY see short PVs any more. My default PV hash has 64K entries. You do need to be wary of very long PVs and make sure your program won't crash. I limit any PV to a max of 64 moves (including the root) as that is the max safe length. I've thought about increasing the limit, but the PVs can already get ridiculously long in endgame. Example:

depth time score variation (1)
38 0.62/3.45 0.59 118. Kf4 Rb2 119. Be3 Ra2 120. Ke4
Ra1 121. Bd2 Ra4+ 122. Ke5 Ra2 123.
Be3 Ra5+ 124. Ke4 Kf7 125. Bd2 Rb5
126. Kf4 Ke6 127. Bc3 Rc5 128. Bd4
Rc4 129. Ke4 Kf7 130. Ke5 Kg6 131.
Be3 Rh4 132. Bf4 Rh1 133. Be3 Ra1 134.
Ke4 Ra2 135. Bf4 Ra4+ 136. Ke5 Rb4
137. Be3 Rb2 138. Ke4 Rb5 139. Bd2
Rb1 140. Kf4 Rf1+ 141. Ke4 Rd1 142.
Be3 Ra1 143. Bd2 Ra4+ 144. Ke5 Ra2
145. Be3 Ra5+ 146. Ke4 Kf7 147. Bd2
Rb5 148. Kf4 Ke6 149. Bc3 <HT>

The <HT> on the end means the PV len reached the max of 64 plies.

edit:

After thinking a bit more, this should still work for your case as well, but you'd need to test the overhead since you will have a lot more stores where alpha < score < beta than a traditional PVS search has...

hgm · Post by **hgm** » Mon Jun 17, 2013 9:56 pm

tpetzke wrote:Yes, this is the way to do it. It also enables some other tricks. But I haven't tried it myself yet.

OK, as this added only one line of code (starting with "if(analyzeMode && ..." to make sure it has minimal impact on game playing) it was easy to try, and it did seem to work. No more short PVs. And, what is more important, it doesn't seem to have any impact on search time.

Bob's idea is neater, because it would fully preserve the grafting effect if you get a hit on an entry with larger-than-necessary draft. But it would require serious programming. So for now I am happy with the 5-minute job.

E.g. for a checks-only search of a mating problem:
Without PV cuts:

Code: Select all

 22	+79.91	568069	0&#58;05.85	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 21	+79.91	342923	0&#58;03.80	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 20	+79.91	279131	0&#58;03.02	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 19	+79.91	181380	0&#58;02.05	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 18	+79.91	155568	0&#58;01.79	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 17	+2.62	106666	0&#58;01.34	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 16	+2.70	93827	0&#58;01.17	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11
 15	-2.78	65257	0&#58;00.71	b5g10+ e10g10 h2h10+ g11f11 h10g11 g9g11 k7g11+ f11g11 g7i9 g11f11 i9h10 f11e10 h10g10 e10d10 g10f10,f10f9
 14	-7.33	51443	0&#58;00.57	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b10 e8c8 b10b11
 13	-7.42	29286	0&#58;00.32	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b11 e8d10
 12	-7.31	24063	0&#58;00.24	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b10
 11	-7.31	13484	0&#58;00.14	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5
 10	-7.53	11357	0&#58;00.10	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11
  9	-7.54	5667	0&#58;00.06	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 g7e8 e10d11 k6j5
  8	-7.56	4287	0&#58;00.04	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 g10f9
  7	-7.53	2223	0&#58;00.03	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5
  6	-7.63	1926	0&#58;00.01	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10
  5	-7.69	637	0&#58;00.00	b5g10+ g11g10 i8j9 g10g11 h2h10+
  4	-7.69	483	0&#58;00.00	b5g10+ g11g10 i8j9 g10g11 h2h10+
  3	-9.04	204	0&#58;00.00	b5g10+ g11g10 i8h8
  2	-9.07	94	0&#58;00.00	b5g10+ g11g10
  1	-9.07	52	0&#58;00.00	b5g10+ g11g10 &#123; root eval = -7.58 dif = -8.65; abs = -4.12 f=59 D=-3.99/-1.87&#125;

With PV cuts:

Code: Select all

 22	+79.91	567111	0&#58;05.94	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 21	+79.91	341990	0&#58;03.71	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 20	+79.91	278280	0&#58;03.04	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 19	+79.91	180571	0&#58;01.95	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8
 18	+79.91	154766	0&#58;01.68	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 17	+2.62	105936	0&#58;01.24	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11 c8d10
 16	+2.70	93114	0&#58;01.07	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 g9g7 i5g7 c11b10 e8c8 b10b11
 15	-2.78	64568	0&#58;00.73	b5g10+ e10g10 h2h10+ g11f11 h10g11 g9g11 k7g11+ f11g11 g7i9 g11f11 i9h10 f11e10 h10g10 e10d10 g10f10,f10f9
 14	-7.33	50948	0&#58;00.59	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b10 e8c8 b10b11
 13	-7.42	28950	0&#58;00.35	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b11 e8d10
 12	-7.31	23722	0&#58;00.29	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5 c11b10
 11	-7.31	13172	0&#58;00.15	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11 k7i5
 10	-7.53	11045	0&#58;00.12	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 e10d10 g7e8 d10c11
  9	-7.54	5423	0&#58;00.06	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 g7e8 e10d11 k6j5
  8	-7.56	4042	0&#58;00.04	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5 g10f9
  7	-7.53	2052	0&#58;00.03	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10 k6j5
  6	-7.63	1765	0&#58;00.01	b5g10+ e10g10 h2h10+ g11f11 h10g11 f11e10
  5	-7.69	561	0&#58;00.01	b5g10+ g11g10 i8j9 g10g11
  4	-7.69	422	0&#58;00.01	b5g10+ g11g10 i8j9 g10g11 h2h10+
  3	-9.04	161	0&#58;00.00	b5g10+ g11g10 i8h8
  2	-9.07	60	0&#58;00.00	b5g10+ g11g10
  1	-0.43	9	0&#58;00.00	b5g10+ &#123; root eval = -7.58 dif = -8.65; abs = -4.12 f=59 D=-3.99/-1.87&#125;

At 22 ply it only adds ~1k nodes out of 570k. (Both starting with an empty hash table, which is also why the PVs aren't too damaged in the second case.)

Daniel Shawul · Post by **Daniel Shawul** » Tue Jun 18, 2013 5:27 am

I am surprised that this IS what you were looking for. It has been the norm since Fruit days to not do hash cutoffs at PVs for the sake of longer PVs. But I switched back to the old cutoff anywhere, because ironically that is better for analysis. You would not want to start from depth=0 every time which you will if you don't probe hash tables. So I am not sure it is a good move you made by not probing in TT. I have a problem in playing draws when cutting of at TT but I am not sure if everyone has this problem. If a move in TT is stored with depth=22 and score=6.0, then you have an immediate repeating draw, scorpio takes really long to switch them. This may be because of some peculiarities in the way i handle repeations but that is the only downside for me.

hgm · Post by **hgm** » Tue Jun 18, 2013 7:23 am

I knew Fruit does this, but Fruit uses PVS, and I was just wondering how you would recognize PV nodes in vanilla alpha-beta. (This would be a concern with Bob's method also.) The code

Code: Select all

if&#40;suppressCutoffs && hash.depth >= depth && hash.score > alpha && hash.score < beta&#41;
  retrievedDepth = depth-1; // fake insufficient depth to do force final IID iteration
else
  retreivedDepth = hash.depth;

in the if(BoundsOK()) part of the probing code seems sufficient for this.

I am not sure what problem you refer to in analysis. Is it that when you analyzed a position, and it got to d=22, and now you play the PV move (which should have been analyzed to d=21, you want the output for this new position to also start at 22?

The behavior I had when using PV hash cutoffs would be that it spewed out depth 1-21 instantly, but with a PV of only a single move, and then (after some time) a long PV at 22. Because upto d=21 all daughters of the root would give hash cutoffs, so each depth would require only ~40 nodes or so. (I don't do hash probes in the root.)

Suppressing PV cutoffs only makes you search the PV move in each node, however. All side branches of the PV should still give you immediate hash cutoffs, except for the occasional overwritten entry, which would have to be re-searched and give hash hits in all its daughters. So to do get up to 21 ply should only take you 21*22/2*40 = 16K nodes, i.e. still instantly (but with PVs as long as the requested depth).

Almost all my engines use depth bootstrapping, however. So if at the d=1 iteration for the new position they do get d=20 hash hits on the root daughters, they would know afterwards they have a d=21 root result. (Assuming for simplicity that none of the root moves was extended or reduced.) Now if you think it ugly that it would repeat that same PV with ever increasing length 21 times, you could correct the iteration depth from 1 to 20 after you print the (one-move) PV, and the root would then continue with d=21 (and spit out a 21-ply PV instantly) and then with d=22 (which would not give any sufficient-depth hash hits, and would require a full search, possibly taking very long).

Daniel Shawul · Post by **Daniel Shawul** » Tue Jun 18, 2013 2:54 pm

Well you would know it is pv node if it is stored as EXACT in TT anyway so no need for node classification which i thought would be challenging.

Suppressing PV cutoffs only makes you search the PV move in each node, however. All side branches of the PV should still give you immediate hash cutoffs, except for the occasional overwritten entry, which would have to be re-searched and give hash hits in all its daughters. So to do get up to 21 ply should only take you 21*22/2*40 = 16K nodes, i.e. still instantly (but with PVs as long as the requested depth).

A depth 22 line when used for depth=3 search is useless because you are going to call eval(). It will only become usefull at higher depths, so you might as well fool the search by starting it from there which it will, if you used TT cutoffs. To make matters worse if you use always-replace scheme, your PV and other important lines will be replaced by less inferior moves at shallower depth. The problem with analysis when not doing PV cutoffs recently recieved a lot of attention (360 posts) recently
http://open-chess.org/viewtopic.php?f=5&t=1042

The problem I mentioned concerning using TT cutoff scheme and repeat draws is probably something peculiar to scorpio. If a depth=22 move is searched and stored with a score 6.00, but will be a repeation draw after opponent plays move, then starting it at that high a depth will slow down switching to other alternatives. First it will fail low, and then finding the alternative move at depth=22 takes a long time. This doesn't happen if you started from depth=1. The problem was so serieous I had to force it to start from reduced depth of d-1. But I am not sure other engines have this problem.

hgm · Post by **hgm** » Tue Jun 18, 2013 5:03 pm

Daniel Shawul wrote:Well you would know it is pv node if it is stored as EXACT in TT anyway so no need for node classification which i thought would be challenging.

That is not entirely true. It only means it was a PV node at the point where it was stored. That does not imply it will be a PV node now, as the current window might be different. You really have to test if the EXACT score lies between alpha and beta. (And if it does, it could only cause a cutoff if the TT entry was EXACT, so you won't have to test that separately.)

A depth 22 line when used for depth=3 search is useless because you are going to call eval().

Well, maybe you should not do that, then? If you are going to take the stand-pat you might as well take the hash cut. The PV won't continue beyond it either way.

It will only become usefull at higher depths, so you might as well fool the search by starting it from there which it will, if you used TT cutoffs. To make matters worse if you use always-replace scheme, your PV and other important lines will be replaced by less inferior moves at shallower depth.

That would also be a mistake (and good you point it out, because I made it too). Low-depth overwrite high-depth for the same position is only justified by the idea that you would not have re-searched if the bounds were no good. But if you did not reserach because it was PV, while the bounds were good, you should NOT replace the entry which in all aspects is superior.

But I see your point for starting at the high depth. It seems annoying, though, that you might have to wait a very long time for the first PV to appear, after moving to the next position, while the GUI has already rerased the previous PV. (And it will, if the previous position was analyzed for a long time, and it will then try to beat that.)

Hash cutoffs and analysis

Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis

Re: Hash cutoffs and analysis