Author: Robert Hyatt
Date: 21:33:32 01/25/00
Go up one level in this thread
On January 25, 2000 at 18:50:25, Ernst A. Heinz wrote: >On January 25, 2000 at 17:34:41, Robert Hyatt wrote: >> >> [...] >> >>>As far as I know, Hsu was always convinced that MVV/LVA with >>>futility pruning in the quiescence search was the right way >>>to go -- he already wrote about it in his Ph.D. thesis. Even >>>"ChipTest" did it exactly like this I suppose. >>> >> >>So far as I know, he didn't do futility pruning in the q-search. When we had >>the original discussion in r.g.c, I mentioned that SEE was making my code in >>Crafty (and Cray Blitz since I did it the same way there) over 50% faster than >>pure MVV/LVA ordering. He asked for details. At that point, I realized that >>there were two distinct issues: (1) ordering moves with SEE vs MVV/LVA. (2) I >>was doing a type of futility pruning (tossing out captures that were hopeless.) >> >>I then reworded my note and tried tests. I first found that SEE was about 10% >>better than MVV/LVA, looking at the tree size. And since SEE was pretty cheap >>in bitboards, overall it was faster as well. I then found that tossing bum >>captures was a 50% gain. He thought that would cause problems. We had a long >>discussion, with several test positions. >> >>I can certainly be wrong about whether he used it or not, but he certainly >>said that he was looking at _all_ captures at the time of the discussion which >>was somewhere around 1993-1994... >> >>So his doing some sort of futility tossing was a surprise to me... I didn't >>notice this in his thesis as I was more interested in the parallel search >>stuff. > >I just reread the passages that I referred to in his Ph.D. thesis. They >are on pages 18 and 19. There he definitely mentions and explains the >mechanism, possibility, and power of futility cutoffs in the quiescence >search. > >However, he does not explicitly state whether he actually used them. So >this was only my intutive assumption. But he might have introduced them >only later as you say -- the thesis text does not really clarify the >issue of when and how exactly the futility cutoffs where introduced in >his hardware designs. > >>Not even the branching factor? > >As Christophe already remarked, the effective branching factor visible >from the log times that you posted is *** REALLY *** surprising. > >Some possible explanations that I deem reasonable follow below. > > 1. The search of DB-2 actually performed some slight forward > pruning (e.g. normal futility pruning at frontier nodes with > a conservative cutoff margin). > > 2. Enhanced transposition-table cutoffs worked really well for > the search of DB-2 in this respect. > > 3. The logs on the WWW pages of IBM contain garbage. > >There are surely more such explanations -- please add them to the >list such that we can try to figure out what is going on here! > >=Ernst= 4. I totally discount 3. If they were going to post faked stuff, they would have posted realistic looking fake stuff. 5. They don't seem to search the same way I do. IE after I finish a 12 ply search, when I start pondering, I start at depth=11. I played the move at ply=1, I am anticipating (so I pseudo-play the move at ply=2) leaving a 10 ply search already done. I notice that in their logs they don't do this it seems... at least not as I do... I saw an N ply search, and after starting the 'pondering search' they started at depth 6, 7 etc again. That might produce some nice branching factors for the early iterations, although it doesn't explain the ones for the deeper searches. 6. They _might_ just be very good tree search theoreticians. I personally believe that Hsu and Campbell know as much about alpha/beta searching as any of us, and just possibly more...
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.