Author: Robert Hyatt
Date: 07:39:45 11/30/02
Go up one level in this thread
On November 30, 2002 at 09:27:20, scott farrell wrote: >This is a continuration from another thread, but I need some help in >understanding this. > >Some of the engines "failed-high" detecting the move, before they had fully >completed the ply. > >Uri and I cant understand how they detect or report this. Simple. When you start an iteration, you should use some sort of aspiration window, rather than setting alpha=-infinity and beta=+infinity. In the case of Crafty, if the score for iteration N-1 was +.30, then I might start the search at iteration N with alpha=0, beta=+60 to try to bracket the expected score. This makes the search tree smaller as you can prune lines that lose or win material quickly. However, if you really do suddenly see a path to win a pawn, that score will be >= +.60, which means the search returns beta rather than a true score. You have to re-set beta to something larger and search again to get the true score. That is a "fail high". > >See the output from an engine below. >At depth 10 is says : Nf6 >At a partial depth 11 (fail-high) it says Nf4! ++ 9 (without a Pv) >with a few more minutes it gets a PV for depth 11. >How come it didnt get a score for Nf6 first, and detected Nf4 as an outstanding >move? > >Scott > >The position was : >[D]2rr3k/1p4p1/1P2b2p/p1Bnpp1q/8/Q1P2PP1/P6P/RB3RK1 b - - 0 26 > > >Posted by scott farrell (Profile) on November 30, 2002 at 03:19:18: > >In Reply to: Re: what does "fail high" mean? posted by scott farrell on November >30, 2002 at 02:48:29: > > >On November 30, 2002 at 02:48:29, scott farrell wrote: > >>On November 30, 2002 at 01:37:01, Uri Blass wrote: >> >>>On November 29, 2002 at 22:34:40, scott farrell wrote: >>> >>>>On November 29, 2002 at 21:12:55, Scott Gasch wrote: >>>> >>>>>On November 29, 2002 at 17:22:20, Will Singleton wrote: >>>>> >>>>>>2rr3k/1p4p1/1P2b2p/p1Bnpp1q/8/Q1P2PP1/P6P/RB3RK1 b - - 0 26 >>>>>> >>>>>>Solution times (amd 1.6ghz): >>>>>> >>>>>>Yace not in 5 min >>>>>>Crafty not in 5 min >>>>>>Aristarch 3:48 min >>>>>>Gromit 3:12 min >>>>>>Ruffian 44 sec >>>>>>CM9000 5 sec >>>>>> >>>>> >>>>>Monsoon fails high in 2:16 and resolves a PV in 4:27. >>>>> >>>>> 1u +0.35 00:00:00.02 11 PV= a4 <+0.00> >>>>> 1u +1.35 00:00:00.05 57 PV= Nf4 <+0.00> >>>>> 1. +1.35 00:00:00.08 77 PV= Nf4 <+0.00> >>>>> 2- +0.57 00:00:00.13 190 **FL** -- >>>>> 2u -0.47 00:00:00.14 302 PV= Ra8 1. Bd3 <+0.00> >>>>> 2u -0.36 00:00:00.15 380 PV= Rc6 1. Qxa5 <-1.00> >>>>> 2u -0.10 00:00:00.16 448 PV= Nf6 1. Qxa5 <-1.00> >>>>> 2. -0.10 00:00:00.21 508 PV= Nf6 1. Qxa5 <-1.00> >>>>> 3. +0.59 00:00:00.27 1635 PV= Nf6 1. Qxa5 e4 <-1.00> >>>>> 4u +0.64 00:00:00.31 6748 PV= Rc6 1. Bd3 Nxb6 2. Bxb6 Rxb6 [Q] >>>>> > 3. Qxa5 [Q] <+0.00> >>>>> 4. +0.64 00:00:00.38 9055 PV= Rc6 1. Bd3 Nxb6 2. Bxb6 Rxb6 [Q] >>>>> > 3. Qxa5 [Q] <+0.00> >>>>> 5+ +1.40 00:00:00.47 22433 Nf6! ++ >>>>> 5. +1.49 00:00:00.63 42341 PV= Nf6 1. Bd6 Bc4 2. Re1 Qxf3 3. Bxe5 >>>>> > [Q] <+0.00> >>>>> 6. +1.52 00:00:00.93 90963 PV= Nf6 1. Bd6 e4 2. fxe4 fxe4 3. Bc2 >>>>> > <+0.00> >>>>> 7. +1.77 00:00:01.49 209895 PV= Nf6 1. Bc2 Rd2 2. Rf2 Rxf2 3. Bxf2 >>>>> > Qxf3 4. Qxa5 [Q] <+0.00> >>>>> 8. +1.77 00:00:03.82 698640 PV= Nf6 1. Bc2 Rd2 2. Rf2 Rxf2 3. Bxf2 >>>>> > Qxf3 4. Qxa5 <+0.00> >>>>> 9+ +2.52 00:00:05.36 994464 Nf6! ++ >>>>> 9. +2.71 00:00:08.69 1812429 PV= Nf6 1. Bd6 Bc4 2. Rf2 e4 3. g4 Nxg4 >>>>> > 4. fxg4 Qxg4+ [+] 5. Bg3 Rd1+ >>>>> > [Q] 6. Kg2 [Q] <-1.00> >>>>>10. +3.02 00:00:26.78 5824368 PV= Nf6 1. Bd6 Bc4 2. Rf2 e4 3. Bc2 >>>>> > e3 4. Rg2 Qxf3 5. Re1 <+1.00> >>>>>11+ +3.77 00:02:16.62 28726569 Nf4! ++ >>>>>11. +5.19 00:04:27.40 58248289 PV= Nf4 1. gxf4 Rd2 2. Bf2 [threat] >>>>> > Qxf3 3. Qxa5 Bd5 4. Qxd5 [threat] >>>>> > Qxd5 5. Bxf5 Rf8 6. c4 Qxc4 [Q] >>>>> > <+3.00> >>>> >>>>How do you guys get this sort of output? >>> >>>I also do not understand it. >>> >>>Monson finished depth 10 with Nf6 in the pv but I do not see pv for Nf6 at depth >>>11. >>> >>I think they must be doing something like, start depth 11 with a window of say >>3.5 to 3.6. This "fails-high" where any one branch can prove it can do atleast >>as good at 3.6 using soft alpha/better bound, or they actually used say >>3.5-3.77. Assuming that fail-low are real fast, and the search ussually fails >>low, then they ussually dont waste much time. I report fail-low at the root, to >>see this sort of this, using -INFINITY to INFINITY, you dont get fail low at the >>root. So after the fail-high, they know atleast one move is dramatically better, >>but not exatly how much better, or if there is also another real good move which >>is better. When they re-search, they search with say 3.77-INFINITY. >> >>My hashtable/hash alorithm doesn't have data/smarts to do window searches like >>this. What extra info do I need, I current store the type of bound (a/b/exact), >>and the score, and do Robert H's fail low/fail hi routine if enough depth. >> >>>Does it start analyzing Nf4 and not Nf6 at depth 11? >>>> >>>>My engine doesnt report the final move Nf4 until it has fully analysed that >>>>move, and hence already has the PV. >>> >>>I do not understand. >>> >>>Do you use normal alpha beta? >>> >>>I try to find if other moves are better than the best move that I found. >>>For that purpose I use a window of 0.01 pawns. >>> >>>If they are better I have a fail high and increase the size of the window from >>>0.01 pawns to something bigger than 0.01 pawns. >>> >>We are saying the same thing, I use PVS, but have to have fully searched a move >>at each ply first. They did something smarter than us. Or are you saying 0.01 >>pawns from previous iteration, say from ply 10 in this example. >>>Uri >Just thinking some more, they may be detecting the fail-high somewhere other >than at the root, say near the leaves somewhere, a nice high score, that is >unlikely to be rebutted, it might be detected by the null-move, but the search >continues to find out if it can force anything better deeper in the tree. > >Scott
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.