[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
&& (depth-tt.depth)>5
&& pvnode=0
&& incheck=0
{
Do something about it!
}
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?