Fail-High / Fail-Low in mate situations...

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Steve Maughan
Posts: 1041
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Fail-High / Fail-Low in mate situations...

Post by Steve Maughan » Sat Aug 24, 2013 3:24 pm

Maverick has a problem.

It's illustrated in the diagram below. In this case Maverick has found a mate in 14 from a previous search. So when it starts searching Nf7 fails high on the first few ply due to the stored value in the hash table. When the search window is increased Maverick must find the mate, which it doesn't due to lack of depth. So it fails low. This results in the nasty fail-high followed by fail-low pattern. I know it's not a big issue but is there any way to stop this?

Thanks,

Steve
Image
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Fail-High / Fail-Low in mate situations...

Post by sje » Sat Aug 24, 2013 3:29 pm

To catch all mate/lose scores, it is necessary to search with a wide open α/β window.

(I have the glyphs for "α/β " stored on a text file snippet. I hope they show up correctly in others' browsers.)

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Fail-High / Fail-Low in mate situations...

Post by xmas79 » Sat Aug 24, 2013 3:35 pm

Maverik has no problem at all. Its a normal behaviour, see my first post about failhigh. Very long post and analisys.

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by hgm » Sat Aug 24, 2013 5:01 pm

Seems you are doing something inconsistently. If the hash hit makes it fail high in the aspiration window, that same hash hit should still make it fail high with the open window, right?

User avatar
Steve Maughan
Posts: 1041
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by Steve Maughan » Sat Aug 24, 2013 5:09 pm

Hi H.G,

The fail high is based on the hash entry from the previous search. But the re-search doesn't have the depth to see the mate - which results in a fail low.

Maybe it's normal. It's certainly ugly.

One way around it would be to only do a hash cut-off if the age of the entry is current. So "old" hash entries are used for move ordering only.

Steve
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
JVMerlino
Posts: 958
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Fail-High / Fail-Low in mate situations...

Post by JVMerlino » Sat Aug 24, 2013 5:29 pm

Hi Steve,

Can you post the position? Would be interested to see how Myrddin behaves.

jm

User avatar
Steve Maughan
Posts: 1041
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by Steve Maughan » Sat Aug 24, 2013 5:36 pm

Hi John,

Its the old "mate in 30" chestnut:

[pgn]
[Event "Who can make the most ridiculously long mate puzzle"]
[Site "?"]
[Date "1000 BC"]
[Round "?"]
[White "Mate in 30"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "5n2/B3K3/2p2Np1/4k3/7P/3bN1P1/2Prn1P1/1q6 w - -"]

1. Neg4+ {16s} Kf5 {0s} 2. Nh6+ {1s} Ke5 {0s} 3. Nf7+ {2s}
Kf5 {0s} 4. Nd6+ {2s} Ke5 {0s} 5. Ng4+ {1s} Kd5 {1s}
6. Ne3+ {2s} Ke5 {2s} 7. Nf7+ {2s} Ke4 {0s} 8. Ng5+ {7s}
Ke5 {1s} 9. Nf3+ {19s} Ke4 {1s} 10. Nxd2+ {2s} Ke5 {3s}
11. Nf3+ {4s} Ke4 {1s} 12. Ng5+ {11s} Ke5 {1s} 13. Nf7+
{5s} Ke4 {1s} 14. Nd6+ {4s} Ke5 {1s} 15. Ng4+ {2s} Kd5 {0s}
16. Nf6+ {5s} Ke5 {1s} 17. Nf7+ {9s} Kf5 {1s} 18. Nh6+ {4s}
Ke5 {0s} 19. Nhg4+ {2s} Kf5 {0s} 20. Ne3+ {3s} Ke5 {2s}
21. Nfg4+ {24s} Ke4 {1s} 22. Nf2+ {2s} Ke5 {1s} 23. Nxd3+
{7s} Ke4 {0s} 24. Nf2+ {3s} Ke5 {0s} 25. Nfg4+ {5s} Ke4
{0s} 26. Nf6+ {3s} Ke5 {0s} 27. Nc4+ {4s} Kf5 {0s} 28. Nd6+
{3s} Ke5 {0s} 29. Ng4+ {3s} Kd5 {0s} 30. c4# {1s} *[/pgn]

Play up to and including 15...Kd5 and let your engine think until it finds 16. Nf6+ and mate in 15. The move forward two moves and see if it find Nf7+ mate in 14.

Steve
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by hgm » Sat Aug 24, 2013 5:39 pm

Steve Maughan wrote:The fail high is based on the hash entry from the previous search. But the re-search doesn't have the depth to see the mate - which results in a fail low.
That still doesn't explain it. If the re-search does not have the depth to see the mate, the aspirated search should not have had the depth to see it either. The re-search is not any deeper than the aspirated search, right? And a hash hit that has sufficient depth for one should have sufficient depth for the other.

Or is the problem that by the time the re-search is done, the hash entry for the mate is overwritten? That would suggest there is something seriously wrong in your replacement algorithm.

User avatar
Steve Maughan
Posts: 1041
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by Steve Maughan » Sat Aug 24, 2013 5:50 pm

Hi H.G.

If the previous search found the mate in 15 (Nf6+), the path and mate score will hopefully be stored in the hash table. This means on the next search it plays Nf7+ with a zero width window and gets an immediate fail-high cutoff due to the mate value stored in the hash table. It then opens the search window and tries to find the mate. However, at the lower ply it does not have the depth to see it and so fails low.

Note I do not do hash cutoffs at PV_NODES.

I think I have concluded it's just an artifact of Maverick's search.

Thanks,

Steve
http://www.chessprogramming.net - Maverick Chess Engine

Sven
Posts: 3698
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Fail-High / Fail-Low in mate situations...

Post by Sven » Sat Aug 24, 2013 5:52 pm

hgm wrote:
Steve Maughan wrote:The fail high is based on the hash entry from the previous search. But the re-search doesn't have the depth to see the mate - which results in a fail low.
That still doesn't explain it. If the re-search does not have the depth to see the mate, the aspirated search should not have had the depth to see it either. The re-search is not any deeper than the aspirated search, right? And a hash hit that has sufficient depth for one should have sufficient depth for the other.
I gave a similar comment to Natale in his long thread a while ago, but he still thinks that everything works well and the behaviour of his engine which he initially found suspicious were expected. I still do not believe that, and tend to believe the same as you. But without the source code it is hard to prove that there is an error.

Sven

Post Reply