Computer Chess Club Archives




Subject: Re: About False Fail Highs, professionals, and MTD searches

Author: Tony Werten

Date: 23:39:29 04/12/02

Go up one level in this thread

On April 12, 2002 at 15:08:51, Gian-Carlo Pascutto wrote:

>To start off, I want you all to take a quick look at the
>two following logs.
>The first is from Fritz 7, the second from Shredder 6.
>26.Rb7+ Kc6 27.R7xb4 Rxb4 28.Bxb4 Kd5 29.Rxd3+ Kc4 30.Re3 Rxe3
>  +-  (1.78)   Depth: 6/17   00:00:00  21kN
>26.Rb7+ Kc6 27.R7xb4 Rxb4 28.Bxb4 Kd5 29.Rxd3+ Kc4 30.Re3 Rxe3 31.fxe3 Kxb4
>  +-  (1.78)   Depth: 7/21   00:00:00  46kN
>  +-  (1.81)   Depth: 7/21   00:00:01  74kN
>26.Rxf7 Re2 27.Rb7+ Kc5 28.Bxb4+ Kc6 29.Rxg7 d2
>  +-  (1.84)   Depth: 7/21   00:00:01  82kN
>  +-  (1.88)   Depth: 7/22   00:00:01  113kN
>  +-  (2.03)   Depth: 7/22   00:00:01  123kN
>26.Bxb4 Rxb4 27.Rb7+ Kc6 28.R7xb4 Re1+ 29.Ka2 d2
>  +-  (2.16)   Depth: 7/22   00:00:01  140kN
>  +-  (1.88)   Depth: 8/22   00:00:02  158kN
>26.Bxb4 Rxb4 27.Rb7+ Ka5 28.Ra3+ Ra4 29.Ra7+ Kb6 30.R3xa4
>  +-  (1.84)   Depth: 8/23   00:00:03  196kN
>  +-  (1.88)   Depth: 8/23   00:00:03  247kN
>  +-  (2.03)   Depth: 8/23   00:00:03  273kN
>26.Rxf7 Re2 27.Rb7+ Kc6 28.R7xb4 Rd5 29.Rb6+ Kc7 30.Rb7+ Kd6 31.R3b6+
>  +-  (2.16)   Depth: 8/23   00:00:03  315kN
>  2.00	 0:00 	+0.28 	6.Ne5 O-O (141) 28.2
>  2.00	 0:00 	+0.30++	6.Qd3 Nc8 (386) 38.6
>  2.00	 0:00 	+0.31 	6.Qd3 Nbc6 (562) 51.0
>  2.00	 0:00 	+0.34++	6.a3 Bxc3+ 7.bxc3 Nf5 (878) 10.8
>  2.00	 0:00 	+0.37 	6.a3 Bxc3+ 7.bxc3 O-O (960) 11.7
>  3.00	 0:00 	+0.31 	6.a3 Bxc3+ 7.bxc3 O-O 8.Qd3 (1.573) 17.2
>  4.00	 0:00 	+0.17 	6.a3 Bxc3+ 7.bxc3 O-O 8.Qd3 d5 9.cxd5 Bxd5 (3.858) 23.6
>  4.00	 0:00 	+0.18++	6.Qd3 Bxc3+ 7.bxc3 Bc8 (5.421) 26.9
>  4.00	 0:00 	+0.18 	6.Qd3 O-O 7.Bxe7 Qxe7 8.Ng1 (8.727) 32.9
>  5.00	 0:00 	+0.10 	6.Qd3 O-O 7.a3 Bxc3+ 8.bxc3 f6 9.Bf4 (20.072) 44.1
>  5.00	 0:00 	+0.11++	6.a3 Bxc3+ 7.bxc3 Bxf3 8.gxf3 d5 9.cxd5 Nxd5 (20.507) 44.6
>  5.00	 0:00 	+0.11 	6.a3 Bxc3+ 7.bxc3 O-O 8.Rc1 d5 9.cxd5 exd5 (21.549) 44.0
>  5.00	 0:00 	+0.12++	6.Qb3 Bxc3+ 7.Qxc3 Bxf3 8.Qxf3 Nd5 9.Bxd8 Kxd8 (26.941)
>  5.00	 0:00 	+0.12 	6.Qb3 Bxc3+ 7.Qxc3 O-O 8.Bf4 Nbc6 9.Ng1 (30.312) 47.2
>  6.00	 0:01 	-0.05 	6.Qb3 Na6 7.a3 Bxc3+ 8.Qxc3 f6 9.Bf4 O-O (70.114) 55.3
>  6.00	 0:01 	-0.04++	6.Qd3 O-O (73.372) 55.5
>  6.00	 0:01 	-0.03 	6.Qd3 O-O 7.a3 Bxc3+ 8.bxc3 Nbc6 9.c5 (85.695) 55.7
>  6.00	 0:01 	-0.02++	6.Bxe7 Bxe7 7.e4 Na6 8.Ne5 (110.658) 57.2
>  6.00	 0:02 	+0.01 	6.Bxe7 Bxe7 7.e3 c5 8.Be2 cxd4 9.Qxd4 O-O (119.562) 57.3
>  6.00	 0:02 	+0.02++	6.e3 Bxc3+ 7.bxc3 Bxf3 8.gxf3 Nbc6 9.a3 (130.227) 57.7
>  6.00	 0:02 	+0.15 	6.e3 Bxc3+ 7.bxc3 f6 8.Bf4 e5 9.dxe5 O-O 10.exf6 Rxf6
>(141.644) 58.7
>  7.01	 0:03 	+0.18 	6.e3 Bxc3+ 7.bxc3 f6 8.Bf4 e5 9.dxe5 O-O 10.Bd3 (183.860)
>  8.01	 0:05 	+0.22 	6.e3 Bxc3+ 7.bxc3 f6 8.Bf4 e5 9.dxe5 O-O 10.Bd3 Nbc6
>11.exf6 (330.335) 62.6
>As far as we know, these programs are based on PVS frameworks.
>(When I'm talking about fail high, I mean on a different than
>the first move, not the aspiration window thing)
>So, what's wrong with the picture?
>-> These programs have _no_ false-fail highs! <-
>I spent some time looking at output from Fritz
>and Shredder, and I saw zip, nada, niente, nothing.
>Of course, if your program doesn't print the initial
>fail high, you wont see false fail highs either, but
>then you always have full reliable mainvariations to go
>with them. If you look above, you see that this is not
>the case. So I presume what they print out is the initial
>fail high.
>How is this possible?
>Even worse, there are two other things that are fundamentally
>1) Fritz seems to use a very (0.05-0.15) small window when
>doing the research on the FH move, and opens it up gradually.

Don't know what Frans is doing but here is what I do in XiniX:

I search the first move and get score back. Next moves are searched with
(score,score+1). If it fails high, I research with (score,score+200). If this
will failhigh as well, then I print "Fail high" and start searching the move
again with progressive windows (score+pawn, score+knight,score+queen,MATE)
The reason I do this is because most failhighs are small, so I save some nodes.
If I'm winning a queen, it takes more time than directly searching with an open
window, but who cares, winning a queen is winning the game anyway.

What happened a while back, was that a move would fail high (on score+1), do the
"check research" (ie score+200), fail high again, print out "fail high" and then
fail low (on score+pawn). What happened was that new ab-windows would trigger
new extensions etc. This can be solved (almost) by making sure that during the
search for the first move, all extensions are triggered, ie search with
(-MATE,MATE) ie drop aspiration search.

BTW all searches (after he first) are done with alfa=score so every search can
still fail low.



>2) Shredder has _variations_ to go with the initial fail-highs
>I thought about (1), and my initial guess was that they do
>the small window researches to check whether the move is a
>real fail high, be able to reject it without doing an open-window
>research, and save some time because of the smaller window.
>That can't be it. If a move would be, say, only 0.03 better,
>you'd fail low and have to do another research to figure out
>if the move is a real fail high or not. Moreover, the moves
>that fail high the first time always end up being the PV.
>Essentially, Fritz has no false fail highs. I'm clueless as
>to what's happening here.
>So I moved to (2). Something to note is that these variations
>aren't always complete nor do they always make sense. They're
>likely coming out of the hashtable. I can get my thing to
>have similar behaviour by storing best moves even on fail-lows.
>Although this is essentially unreliable, the first 2-3 moves
>usually are correct, and this is consistent with what I see
>in Shredder. So perhaps this little mistery is partly solved.
>However, we also see that Shredder _never_ has false fail
>Perhaps these program have a search so stable that they simply
>don't happen? Sounds unlikely doesn't it?
>Do they have a trick which they use to determine whether a
>fail high is real or not? I don't see how this could be
>I have another thought, which may or may not be related to
>these issues.
>Why don't MTD(n,f) searchers have trouble with this? If the
>PVS can have a fail high/fail low sequence, couldn't this
>happen with MTD(n,f) as well? As far as I see, the result
>would be that the MTD quits (it has converged, after all)
>and ends up with the move that corresponds to the false-fail
>high one in PVS. These are often blunders. Why doesn't this

This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.