Author: Vincent Diepeveen
Date: 04:31:01 10/16/02
Go up one level in this thread
On October 15, 2002 at 13:31:07, James Swafford wrote:
There is 2 things
a) theoretic branching factor without nullmove
that's true for the last so many plies of deep blue and
the theoretic truth.
b) branching factor with hashtable.
You will see that deep blue is somewhere, like all software programs
in the middle of this.
126 mln nodes a second. And it got like 12 ply with a bit more
than 3 minutes.
that's like total branching factor = 12th root from
126 mln * 180 seconds = 6.0
So the real overall b.f. which was achieved was 6.0
that's lower than the theoretic branching factor of sqrt(40^18)
which is caused by both forward pruning and first 6-8 ply using
hashtables.
But of course it's not real true.
If you watch the logfiles close you will see that this 12.2 ply is
very optimistic estimation from the deep blue team.
In the middlegame i see more like 10 to 11 ply.
Only if you add endgame to it you might get to 12.2 ply, which undoubtfully
they did.
If you average 10 to 11 ply ==> 10.5 ply
over the number of nodes:
192 seconds on average for those searches * 126MLN nodes a second
= 24192000000 nodes ==> 9.75
So in fact their branching factor was closer to 10 in the middlegame.
That's pretty close to what Schach 3.0 has.
Of course bob will argue that this is not fair because they had
overhead too and to get another ply deeper, the hardware would not
search more than what branching factor needs when getting 1 ply
deeper, which is using hashtables and reusing them too from
previous iteration of course and using transposition too.
The smallest public discussed branching factor around 1997-1999
in that respect is around 4.5, but
of course with such an inefficient parallel search, deep blue doesn't
get that at all because it is also doing singular extensions in software
search.
The 4.5 is from if i remember well crafty around 1997-1999 with experiments
without nullmove. And crafty wasn't doing dangerous extensions in those
days.
I managed with a bit more efficient move ordering to get around 4.2 back then.
Anyway we have 3 branching factors
- branching factor in hardware
- branching factor in software
- overall branching factor
People forget that in the end only the last one counts for which search
depth you get.
Even if you get 2.8 branching factor, if your overhead is a trillion nodes,
then you won't make it.
Reality is that deep blue's b.f. is looking worse than it is because of
2 things
a) the incredible overhead from hardware
b) the huge inefficiency from parallel search, estimations of 10% out of
the total nodes of 126MLN a second which it got on average is not
very realistic still IMHO.
What we also must not forget is that the average number of nodes a second
which deep blue searched is based basically upon up to those 300 MLN a second
they got in the far endgame.
Imagine how little they got in the middlegame.
We are always calculating with 100+ mln nodes a second. But we know they
got up to 300-400MLN nodes a second in endgame.
That means that in the crucial phases of opening, they must have searched
like 40 million nodes a second or so in opening?
>
>[snip]
>
>>Because deep blue didn't use nullmove for example.
>>
>>With nullmove Fritz has a branching factor defined by:
>> 2.8^depth * c
>>
>>Deep Blue has more like
>> 4.5^depth * e
>>
>>where the 'e' from deep blue is MUCH bigger than c from fritz.
>>
>>So please do not compare it.
>>
>>everyone with a calculator knows that 2.8 to the power depth is going to
>>be way way less than 4.5 to the power depth.
>>
>
>
>Agghhh!! Would you at least be consistent??? You claimed
>in another post that they need 40^9 nodes to search 18 ply.
>
>Here it is:
>
>>>You really believed all that time that
>>>deep blue searched 40^9 = 262144000000000 nodes ?
>
>
>Now you claim 4.5^18 * e? Which is it:
>sqrt(40)^18 = 6.32^18, or 4.5^18, or... ?
>
>
>--
>James
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.