Computer Chess Club Archives


Search

Terms

Messages

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

Author: Gian-Carlo Pascutto

Date: 12:08:51 04/12/02


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
26.Rxf7!
  +-  (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
26.Bxb4!
  +-  (1.88)   Depth: 7/22   00:00:01  113kN
26.Bxb4!
  +-  (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
26.Bxb4--
  +-  (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
26.Rxf7!
  +-  (1.88)   Depth: 8/23   00:00:03  247kN
26.Rxf7!
  +-  (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)
46.2
  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)
60.2
  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
strange:

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.

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
highs.

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
possible.

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
happen?

--
GCP



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

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