Hash Refutation

[D Sceviour]

The problem of tree thrashing or tree explosion has been mentioned in a number of postings. Sometimes the problem is due to a missed mate in one. Here is an approach to the problem of tree explosions. In the example, start with a known mate in 14:

[d]6r1/2rp1kpp/2qQp3/p3Pp1P/1pP2P2/1P2KP2/P5R1/6R1 w - - 0 1

After 1. Rxg7+ RxR 2. Rxg7+ Ke1? 3. Rxh2 ...

the engine stores a fail-high hash value because of the win of a pawn, and stores the hash best move as Rxh2. The move Rxh2 was selected first in the move list ordering because it was an exchange.

Then the engine does a beta cutoff or null hit on this position for the next dozen or so iterations. After a search depth of say 24, the black side notices that it is losing a Queen after something like this:

1. Rxg7+ Rxg7 2. Rxg7+ Kxg7! 3. Qe7+ Kg8 4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5 7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg6+ Kh3 10. Kf2 Qc5+ 11. Kf1 Qg1+ 12. Qxg1

The principle variation has collapsed and the black side backs up to look for a refutation. White selects the hash best move as 2... Ke1 3. Rxh2? and begins to thrash for a depth of 20+ ply on a line that has no entries in the remaining hash table. Obviously the engine has missed the mate in one 3. Q-e7++ but cannot find the move until it finishes the thrash. Tree explosion due to missed mate-in-one is common.

_______________________________________________________

If you can follow so far, a solution for this problem can be called "hash refutation" and is as follows. After,

Code: Select all

   HashProbe(tt);

   if tt.value<beta
	&& tt.type=FAIL_HIGH
	&& &#40;depth-tt.depth&#41;>5 
	&& pvnode=0 
	&& incheck=0 
	&#123;
	Do something about it!
	&#125;

To verify the best move and ensure a mate is one is not missed, Schooner's solution is to set:

bestmove=NULL;

and pass the information to a trick on an Internal Iterative Deepening routine. It is a way of guaranteeing a shallow full width search on the position so nothing is missed. After all, Qe7 could be at the bottom of the move list for move selection.

Other programs use various verification searches at different points. For example, Stockfish triggers a research after a null move threat but I do not know enough about it to assume it covers the condition as a refutation. A type of triggered research was tried in Schooner without success. The above approach seems to address the problem more directly and has shown some success.

Are there any other ideas on how to reduce tree explosions, especially when mate in one is missed?

[bob]

The problem of tree thrashing or tree explosion has been mentioned in a number of postings. Sometimes the problem is due to a missed mate in one. Here is an approach to the problem of tree explosions. In the example, start with a known mate in 14:

[d]6r1/2rp1kpp/2qQp3/p3Pp1P/1pP2P2/1P2KP2/P5R1/6R1 w - - 0 1

After 1. Rxg7+ RxR 2. Rxg7+ Ke1? 3. Rxh2 ...

the engine stores a fail-high hash value because of the win of a pawn, and stores the hash best move as Rxh2. The move Rxh2 was selected first in the move list ordering because it was an exchange.

Then the engine does a beta cutoff or null hit on this position for the next dozen or so iterations. After a search depth of say 24, the black side notices that it is losing a Queen after something like this:

1. Rxg7+ Rxg7 2. Rxg7+ Kxg7! 3. Qe7+ Kg8 4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5 7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg6+ Kh3 10. Kf2 Qc5+ 11. Kf1 Qg1+ 12. Qxg1

The principle variation has collapsed and the black side backs up to look for a refutation. White selects the hash best move as 2... Ke1 3. Rxh2? and begins to thrash for a depth of 20+ ply on a line that has no entries in the remaining hash table. Obviously the engine has missed the mate in one 3. Q-e7++ but cannot find the move until it finishes the thrash. Tree explosion due to missed mate-in-one is common.

_______________________________________________________

If you can follow so far, a solution for this problem can be called "hash refutation" and is as follows. After,

Code: Select all

   HashProbe(tt);

   if tt.value<beta
	&& tt.type=FAIL_HIGH
	&& &#40;depth-tt.depth&#41;>5 
	&& pvnode=0 
	&& incheck=0 
	&#123;
	Do something about it!
	&#125;

To verify the best move and ensure a mate is one is not missed, Schooner's solution is to set:

bestmove=NULL;

and pass the information to a trick on an Internal Iterative Deepening routine. It is a way of guaranteeing a shallow full width search on the position so nothing is missed. After all, Qe7 could be at the bottom of the move list for move selection.

Other programs use various verification searches at different points. For example, Stockfish triggers a research after a null move threat but I do not know enough about it to assume it covers the condition as a refutation. A type of triggered research was tried in Schooner without success. The above approach seems to address the problem more directly and has shown some success.

Are there any other ideas on how to reduce tree explosions, especially when mate in one is missed?

First, I ran this on Crafty and didn't see any problem. It doesn't find a mate in 14, but does find a mate in 15 (this on my macbook with one thread):

Code: Select all

         24    12.96          0.77   1. Qd4 Qb7 2. Rd2 Qa7 3. Qxa7 Rxa7 4. Kd4
                                     Rd8 5. Rdg2 Rg8 6. c5 Rc7 7. Kc4 Rb7
                                     8. Kd3 Rb5 9. Kd4 Rbb8 10. Rd1 Rb7 11. Kc4
                                     Rc8 12. Rgd2 Ke7 13. Rd6
         24    13.32            ++   1. Rxg7+! (>+0.93)                   
         24    13.34            ++   1. Rxg7+! (>+1.09)                   
         24    13.35            ++   1. Rxg7+! (>+1.41)                   
         24    13.36            ++   1. Rxg7+! (>+2.05)                   
         24    13.39            ++   1. Rxg7+! (>+3.33)                   
         24    13.41            ++   1. Rxg7+! (>+5.89)                   
         24    13.96            ++   1. Rxg7+! (>+11.01)                   
         24    15.78         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2#
         24->  15.78         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2# (s=2)
         25    16.38         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2# (s=2)
         25->  16.41         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2# (s=2)
         26    17.37         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2# (s=2)
         26->  17.41         Mat15   1. Rxg7+ Rxg7 2. Rxg7+ Kxg7 3. Qe7+ Kg8
                                     4. Qe8+ Kg7 5. h6+ Kxh6 6. Qf8+ Kh5
                                     7. Qf7+ Kh4 8. Qxh7+ Kg3 9. Qg8+ Kh4
                                     10. Kf2 Qc5+ 11. Kg2 Qg1+ 12. Kxg1 Rc8
                                     13. Qg5+ Kh3 14. Qg2+ Kh4 15. Qh2# (s=2)

I don't see any particular problem. But you mentioned "beta cutoff for next 12 iterations or ...". How is this going to happen? each new iteration increases depth. That hash cutoff will no longer be used since the draft is now one ply too shallow.

There are always pathological positions where conventional move ordering fails, and when that happens we go from good alpha/beta to near minimax trees. Not much that can be done about it. I am not sure how you end up with a path that has NOTHING after a particular move. How did that hash move get stored in the first place? There must have been a tree below it.

Perhaps I am missing something,

[hgm]

The answer to Bob's issue is that the line Ke8? Rxh7 is actually deepened, (probably with hefty reductions and lots of null moves, because it is not PV) but does not change in score very much by that. The problem here is that even a deep verification on that this line has lost black only two Pawns, which is good as long as the PV gained black R for P, drops dramatically in score at quite high depth, when it discovers it actually loses a Queen on the side. The loss of 'only' two Pawns then suddenly becomes a very attractive prospect.

This is indeed a very general problem: because of a sudden drop in PV score at high depth the refutation trees of the side branches, often based on very sub-optimal barely good-enough cut moves (such as null move...), are no good anymore. When you still follow them up without Internal Iterative Deepening, you waste a lot of time on searching these moves at full depth in uncharted territory, before discovering they fail low.

The situation is easy to recognize: in the hash hit that gave you the move (here Rxh7) it also gave you a lower bound on the score (here +2 Pawns). After the PV rises from a -R to a +Q score, however, the window is raised to +5 or so. And the hashed move only 'promised' +2. I posted recently on this under the topic 'inadequate hash moves'.
When you would do IID in nodes where you do have a hash move, but with a score bound that is (not nearly) good enough for the current situation, you would discover the Qe7# alternative to Rxh7 as a refutation for Ke8? already in the first iteration.

BTW, a somewhat similar problem occurs in cases where the hash move did look good enough according to its hashed TT bound, but suffers a sudden score drop itself, making it fail low. This situation can even occur in IID without hashing, (basically hashing is a form of IID where the previous iteration was remembered from a previous search), where you found an adequate cut move at low depth, have been only searching that move for the subsequent depths, as it kept failing high and producing cutoffs, until at the ultimate depth it runs into trouble and fails low. You now basically know nothing about the remaining moves, and would try to find an alternative cut move amongst them by blindly plunging into full-depth searches, as you were already in your final IID iteration.

To address that problem I invented 'self-deepening': when you get a fail high during IID, you don't immediately skip to the next-higher iteration, but just continue to deepen only that cut move. Until it fails low (in which case you now just continue the iteration where you first discovered it, without this failed attempt having cranked up the depth for the remaining moves), or until you reach full depth (in which case you are done).

[D Sceviour]

Hello Robert Hyatt,
I am glad you are taking an interest in my chess engine project.

Schooner's output is as follows:

Code: Select all

White(1): analyze
Search Iteration =  1
PV [1] 20  d6-c6 d7-c6

Search Iteration =  2
PV [2] 20  d6-c6 d7-c6 g2-g7
PV [2] 35  h5-h6 g7-g6

Search Iteration =  3
PV [3] 43  h5-h6 g7-g6 g2-d2 c6-d6 g1-g7
PV [3] 59  d6-c6 d7-c6 g2-d2

Search Iteration =  4
PV [4] 59  d6-c6 d7-c6 g1-d1

Search Iteration =  5
PV [5] 52  d6-c6 d7-c6 g1-d1 g8-c8 g2-g7 g8-g7
PV [5] 60  h5-h6 g7-g6 d6-c6 d7-c6 g2-d2

Search Iteration =  6
PV [6] 60  h5-h6 g7-g6 g1-d1 g8-c8 e3-e2 c6-d6 d1-d6
PV [6] 66  g2-d2 g8-c8 e3-e2 c6-d6 d2-d6

Search Iteration =  7
PV [7] 70  g2-d2 c6-d6 d2-d6 f7-e7 g1-d1 g7-g5

Search Iteration =  8
PV [8] 75  g2-d2 c6-d6 d2-d6 g8-d8 g1-d1 a5-a4

Search Iteration =  9
PV [9] 80  g2-d2 c6-d6 d2-d6 g8-a8 g1-d1 a8-d8

Search Iteration =  10
PV [10] 69  g2-d2 c6-d6 d2-d6 g8-a8 d6-b6 a8-d8 g1-d1
PV [10] 75  h5-h6 g7-g6 g1-d1 g8-d8

Search Iteration =  11
PV [11] 69  h5-h6 g7-g6 g1-d1 g8-d8 g2-d2 c6-d6 d2-d6 f7-e7 d1-d2
 c7-c6
PV [11] 76  g2-d2 c6-d6 d2-d6 g8-a8 g1-d1 f7-e8 e3-d4
PV [11] 80  g1-d1 c6-d6 d1-d6 g8-a8 g2-d2 a8-d8 d2-d1

Search Iteration =  12
PV [12] 77  g1-d1 c6-d6 d1-d6 g8-a8 e3-d4 a8-a7 d6-b6 a7-a8 g2-g5

Search Iteration =  13
PV [13] 71  g1-d1 c6-d6 d1-d6 g8-a8 g2-g1 a8-a7 g1-d1 f7-e7 d1-d3
 a5-a4
PV [13] 72  g2-d2 c6-d6 d2-d6 g8-a8 d6-b6 c7-a7 g1-d1 f7-e7
PV [13] 75  h5-h6 g7-g6 g2-d2 c6-d6
PV [13] 836  g2-g7 g8-g7 g1-g7 f7-g7 d6-e7 g7-g8 e7-e8 g8-g7 h5-h
6 g7-h6 e8-f8 h6-h5 f8-f7 h5-h4 f7-h7 h4-g3 h7-g6 g3-h3 e3-f2 c6-
c5 f2-f1 c5-c4 b3-c4 c7-c4

Search Iteration =  14
PV [14] 1037  g2-g7 g8-g7 g1-g7 f7-g7 d6-e7 g7-g8 e7-e8 g8-g7 h5-
h6 g7-h6 e8-f8 h6-h5 f8-f7 h5-h4 f7-h7 h4-g3 h7-g6 g3-h3 e3-f2 c6
-c5 f2-f1 c5-c4 b3-c4 c7-c8 g6-g2 h3-h4

Search Iteration =  15
PV [15] 1064  g2-g7 g8-g7 g1-g7 f7-g7 d6-e7 g7-g8 e7-e8 g8-g7 h5-
h6 g7-h6 e8-f8 h6-h5 f8-f7 h5-h4 f7-h7 h4-g3 h7-g6 g3-h3 e3-f2 c6
-c5 f2-f1 c5-c4 b3-c4 h3-h4 f1-f2

Search Iteration =  16
PV [16] 1479  g2-g7 g8-g7 g1-g7 f7-g7 d6-e7 g7-g8 e7-e8 g8-g7 h5-
h6 g7-h6 e8-f8 h6-h5 f8-f7 h5-h4 f7-h7 h4-g3 h7-g6 g3-h4 e3-f2 c6
-c5 f2-g2 c5-g1 g2-g1 c7-c4 g6-g5 h4-h3 b3-c4

Search Iteration =  17
PV [17] 32739  g2-g7 g8-g7 g1-g7 f7-g7 d6-e7 g7-g8 e7-e8 g8-g7 h5
-h6 g7-h6 e8-f8 h6-h5 f8-f7 h5-h4 f7-h7 h4-g3 h7-g6 g3-h4 e3-f2 c
6-c5 f2-g2 c5-g1 g2-g1 c7-c4 g6-g5 h4-h3 g5-g2 h3-h4 g2-h2#
Mate in  14

Mate_in_ply= 29
elap: 6.020996600481396     limit: 7.3 seconds
Total Nodes=4289790         nps:712471
Hash: Hits=189562           Misses=585447 Collisions=78326
Researches= 2219

White(1):

Black finds it is losing a Queen at iteration 13, and mate in 29 ply follows very quickly thereafter.

_______________________________________________

Robert Hyatt asked,

How did that hash move get stored in the first place?

Good question. This has been a long time study problem so there are different results for each version tested. In the current version the move Rxh7 is searched on a PVS research at iteration 13, with hash refutation implemented. If hash refutation is turned off then different results follow. Earlier versions stored Rxh7 at iteration 3. I realize there may be difficulty in duplicating the exact moves in different engines with deep searches, but it is the principle that is trying to be made apparent.

One question: is hash refutation an anomaly that only works for Schooner, or can this be effective in other engines? I suppose that is up for me to test.
_______________________________________________

Robert Hyatt asked,

I am not sure how you end up with a path that has NOTHING after a particular move.

What are you referring to, as the usage NOTHING does not appear in the original post?

Dennis Sceviour

[D Sceviour]

Hello H.G. Muller,
Your analysis looks very good.

The self-deepening looks interesting. However, I do not understand "when you get a fail high during IID". IID is supposed to return a fail-high since we are looking for the best move in the move ordering.

[hgm]

I am talking about a fail high in a non-final iteration. Such a fail high provides a cut move, but the depth at which that move was searched would not be enough to make the node fail high. So normally you would do another iteration, (starting with that move). But if the move then fails low, you are in deep trouble, as nothing is known on any of the other moves, and the depth is already high.

The self-deepening prevents that, by guaranteeing that any fail high is searched to the full node depth, rather than just the iteration depth. Then any cutoff in an iteration is automatically a fail high of the entire node. So fail highs that do not hold until the full depth will never increase the iteration depth, and alternatives will always be searched for (and bad ones rejected) at the lowest possible depth.

[D Sceviour]

H.G.Muller wrote,

The self-deepening prevents that, by guaranteeing that any fail high is searched to the full node depth, rather than just the iteration depth.

Yes, that should result in a complete score. However, the idea with hash refutation is not to increase node counts with full depth searches, but to reduce the amount of search through better move ordering after a PV has been refuted.

[bob]

re: nothing. Probably my wording was unclear. Here's what I was referring to in your original post:

The principle variation has collapsed and the black side backs up to look for a refutation. White selects the hash best move as 2... Ke1 3. Rxh2? and begins to thrash for a depth of 20+ ply on a line that has no entries in the remaining hash table. Obviously the engine has missed the mate in one 3. Q-e7++ but cannot find the move until it finishes the thrash. Tree explosion due to missed mate-in-one is common.

the "no entries in the remaining hash table" implies (to me at least) that nothing was searched?

[D Sceviour]

Robert Hyatt asked,

...the "no entries in the remaining hash table" implies (to me at least) that nothing was searched?

H.G. Muller paraphrased the problem very well,

You now basically know nothing about the remaining moves, and would try to find an alternative cut move amongst them by blindly plunging into full-depth searches, as you were already in your final IID iteration.

[hgm]

Yes, that should result in a complete score. However, the idea with hash refutation is not to increase node counts with full depth searches, but to reduce the amount of search through better move ordering after a PV has been refuted.

Well, that is what IID is all about, right? To reduce node count by searching the poor moves only at low depth. There is no oracle that will tell you what move ordering is good. You will have to do some search for that, and you;d better not do it at full depth.