Author: scott farrell
Date: 07:46:59 11/30/02
Go up one level in this thread
On November 30, 2002 at 10:39:45, Robert Hyatt wrote: >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". mmmmmmmm ........ that's what I guessed. Is there anything tricky I need to do with the research. I seem to get too many problems of search instability, and end up getting different answers to a standard -INF,INF search. In my hashtable I have the score, and a/b/exact, and do your suggestion fail high, fail low or return exact score (assuming enough depth). I am using nullmove and pvs. > > > > > >> >>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 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.