Author: Christophe Theron
Date: 18:38:51 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=
Futility or extended futility pruning does not change the branching factor of
deep searches. I'm surprised that you and Bob keep focusing on this. It has
absolutely no importance.
QSearch is, as well, irrelevant when we talk about BF.
I add:
4. the sample of time to reach a given depth that Bob has found in the logs is
not representative.
I think somebody should seriously take the time to extract more BF data from the
logs.
This discussion is really interesting.
Christophe
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.