Author: Vincent Diepeveen
Date: 05:36:57 04/25/01
Go up one level in this thread
On April 24, 2001 at 20:38:49, Robert Hyatt wrote:
>On April 24, 2001 at 15:12:03, Christophe Theron wrote:
>
>>On April 24, 2001 at 10:13:29, Albert Silver wrote:
>>
>>>On April 24, 2001 at 10:01:04, Robert Hyatt wrote:
>>>
>>>>On April 24, 2001 at 05:06:40, Amir Ban wrote:
>>>>
>>>>>On April 24, 2001 at 03:47:15, Uri Blass wrote:
>>>>>
>>>>>>the best software that is not IBM.
>>>>>>
>>>>>>Suppose there is a match of 20 games at tournament time control
>>>>>>
>>>>>>I am interested to know how many people expect 20-0 for IBM
>>>>>>How many people expect 19.5-.5?....
>>>>>>
>>>>>>If IBM expect to do better result then the average result that the public expect
>>>>>>then they can earn something from playing a match of 20 games with Deep Blue.
>>>>>>
>>>>>>I believe that a part of the public who read the claim that kasparov played like
>>>>>>an IM are not going to expect good result for IBM.
>>>>>>
>>>>>>Uri
>>>>>
>>>>>I expect DB ('97 version) to lose 8-12.
>>>>>
>>>>>Amir
>>>>
>>>>
>>>>Based on what specific facts? How many games did they lose from their debut
>>>>in 1987 through 1995 the last event they played in with other computers? Let
>>>>me see.. that would be... _one_ game. So what suggests they would do worse
>>>>today? we are all 100x slower (or more).
>>>
>>>Yes, and another thing that is being seriously overlooked is just how important
>>>speed and a ply make in comp-comp matches. One thing that time and SSDF has
>>>CLEARLY taught is that that one ply in a comp-comp match makes a world of
>>>difference. I think pitting a PC program against DB would be a massacre, even if
>>>I don't think humans (a very top GM) would do that much worse against DB
>>>(compared to DB vs. PC) as opposed to an 8-way server run PC program as will be
>>>the case here. Provided the conditions were the same, and that both matches had
>>>equal preparation of course.
>>>
>>> Albert
>>
>>
>>
>>I'm not sure I would agree with you.
>>
>>Yes, Deep Blue is way faster than PC programs (even on today's PCs) in NPS, but
>>there is something you should not forget.
>>
>>Due to Hsu's beliefs, as pointed out by Bob several times, Deep Blue is
>>essentially a brute force searcher.
>>
>>But after 3 decades of chess programming on microcomputers we all know that
>>brute force search is extremely inefficient.
>>
>>Actually brute force is increasingly inefficient as ply depth increases. Or if
>>you prefer the difference between brute force and selective searches in terms of
>>nodes to compute to reach a given ply depth growth exponentially with ply depth.
>>
>>Today, good selective programs can achieve a "branching factor" which is under 3
>>(and that includes the extra work induced by extensions). A well designed brute
>>force alpha beta searcher, without extensions, achieves a BF between 4 and 5.
>>
>>Some time ago I have found that a good brute force alpha beta implementation has
>>a BF of 4.3.
>>
>>I think current top programs have a BF which is close to 2.5, but let's say it's
>>2.8 to keep some margin.
>>
>>
>>You can compute the ratio of nodes to search by brute force divide by nodes to
>>search by selective search by:
>>
>> ratio = 4.3^depth / 2.8^depth (^ mean "power")
>>
>>
>>Now about the NPS. Deep Blue is supposed to be able to compute 200 million NPS
>>(nodes per second). Current top PC programs on fastest hardware (single CPU) can
>>compute up to 800.000 NPS, that's 1/250 of what DB can do.
>>
>>
>>At what depth the "ratio" starts to be above 250?
>>
>>Answer: at ply depth 13.
>>
>>So I suspect that Deep Blue and current top programs on top hardware (single
>>CPU) can reach ply depth 13 in the same time.
>
>You _are_ aware that DB's branching factor was well below 5? I posted the
>analysis here a year ago (Ed probably still has it as he was interested). I
>took the 1997 logs and just computed the ratio using time. They were nowhere
>near 5... not even near 4...
Bob please take into account that they have 480 chessprocessors,
before those work a bit you need a bit more depth. So the first few
plies they search slowly all processors go search more effectively,
also they have of course from previous searches some things in hash.
The 2 things together help the first few plies the branching factor
quite a lot. Of course you DIE completely when you get to a depth
which previously wasn't searched.
Very important is to get 480 processors effectively to work. Everyone
with parallel experience knows how tough it is. If someone doesn't,
talk to Rainer Feldmann :)
That explains their branching factor initially very well.
I guess the problem to get 480 processors quick to work effectively
is also explaining why they already search from move 1. They need
some hashtable load. Then the processors can get quickly to work.
Game 1, move 1. Their search:
---------------------------------------
--> ng1f3 <--
---------------------------------------
-17 T=559
Pe7e5
---------------------------------------
--> 1. .. d5 <-- 39/119:52
---------------------------------------
Guessing g3
3(4) -25 T=0
Bc8g4 ph2h3
4(5) -25 T=0
Bc8g4 ph2h3
5(5)[Bg4](-22) -22 T=0
Bc8g4 bf1g2
6(5)[Bg4](-23) -23 T=0
Bc8g4 nf3e5 Ng8f6 ne5g4B
7(5) #[Bg4](-18) -18 T=1
Bc8g4 bf1g2 Ng8f6 nf3e5 Pe7e6
8(6) #[Bg4](-21) -21 T=1
Bc8g4 bf1g2 Ng8f6 o-o Pe7e6 ph2h3
9(6) #[Bg4](-12) -12 T=4
Bc8g4 nf3e5 Bg4e6 bf1g2 Pg7g6 o-o
10(6)<ch> 'g3'
[0 sec (main.c:6581)] -12 T=13
Bc8g4 nf3e5 Bg4f5 pd2d4 Pe7e6 bc1f4
---------------------------------------
--> 2. .. Bg4 <-- 38/119:35
---------------------------------------
See the short pv lines. Definitely 10(6) pv line:
Bc8g4 nf3e5 Bg4e6 bf1g2 Pg7g6 o-o
Which is a 10 ply search, a few of those plies in software the
rest in hardware. I've heart different things on how much they
did in hardware. From 4 to 6 ply. I have no idea, but
definitely this wasn't a 10 ply search in software, as
the PV is way to short for that.
The 11 ply interrupted search is also showing only 6 ply
from which 1 is a clear extension:
Bc8g4 nf3e5 Bg4f5 pd2d4 Pe7e6 bc1f4
Let's explain this: Ne5 of course triggers an extensions
as an attacked piece attacks a piece now. So i assume
both at 10 ply pv and 11 ply pv the Bg4 to e6 or f5 move
is extended.
Now let's go to game 2 the first search:
<ch> 'c'
---------------------------------------
--> 1. e4 <-- 39/119:51
---------------------------------------
Guessing c5
3(4)[Nf3](30) 30^ T=1
ng1f3 Qd8c7
3(5) 38 T=2
ng1f3 Nb8c6
4(5) 38 T=2
ng1f3 Nb8c6
5(5)[Nf3](52) 52 T=2
ng1f3 Nb8c6
6(5)[Nf3](68) 68 T=4
ng1f3 Nb8c6 nb1c3
7(5) #[Nf3](68) 68 T=5
ng1f3 Nb8c6 nb1c3 Ng8f6
8(6) #[Nf3](59) 59 T=6
ng1f3 Nb8c6 bf1b5 Qd8b6 nb1a3
9(6) #[Nf3](66) 66 T=8
ng1f3 Nb8c6 nb1c3 Ng8f6 bf1e2 Pd7d6
10(6) #[Nf3](53) 53 T=18
ng1f3 Nb8c6 bf1b5 Ng8f6 pe4e5 Nf6g4 bb5c6N Pd7c6b
11(6)<ch> 'e5'
---------------------------------------
--> Pe7e5 <--
---------------------------------------
Even the 11 ply PV isn't 11 ply:
ng1f3 Nb8c6 bf1b5 Ng8f6 pe4e5 Nf6g4 bb5c6N Pd7c6b
the last 2 moves are captures so extended, so is Ng4
as it is attacked. So this is a 6 ply search which we
see with 6 ply in hardware or something.
As we see all PV lines are extended by 1 ply, something
i also did for years in my selective search and many
other programmers also i heart at least tried it. It's
very cheap to do that with 480 chessprocessors available.
Why not checkout PV nodes 1 ply further? Very valid idea
actually to prevent horizon effects. Nowadays i no longer
do it as i search deeper as deep blue anyway.
Some commercials still do it however in a different way:
pruning.
Best regards,
Vincent
>
>
>>
>>And it turns out that ply depth 13 can be routinely reached by today's PC
>>programs at standard time controls.
>
>Yes.. but don't forget DB was reaching depths of 15-18 in the middlegame,
>as their logs from 1997 clearly show...
No they clearly show that they reached 6 or 7 ply and that they
do loads of extensions in those few plies. If we *imagine*
another 6 ply in hardware that's 12-13 ply.
Don't invent now that they did 10 ply in hardware!
Note that this is a problem which is overlooked for a new release of
Hsu's processors. If he presses it in 0.18 technology, very common
technology nowadays, then i don't doubt that he can get 4 processors
as fast as 480 with 0.60 technology.
Hsu is a brilliant hardware designer so if he thinks it can be as
fast as 120 hardware processors i directly take that from him.
However how many plies is each processor going to search for him?
10 ply?
The deeper you search in hardware the bigger the penalty that you
do not use hashtable!!
>
>
>
>>
>>
>>But there are 2 things I'm not really taking into account here:
>>1) selective search is less reliable than brute force search
>>2) Deep Blue uses something called "Singular extensions" which increases its
>>branching factor dramatically over the BF of a simple alpha beta brute force
>>algorithm.
>>
>>
>>Point 1 is hard to evaluate.
>>
>>About point 2 we have some data suggesting that "singular extensions" is an
>>extremely expensive algorithm: while PC programs have no problem to reach ply
>>depth 13 on current hardware, Deep Blue could not go beyond ply depths 11-12 in
>>the 1997 match. Of course in some lines it was computing much deeper.
>
>Not again. Look at the logs. 11(6) is a +seventeen+ ply search.
Then we should see at least 11 ply PV's, usually even longer,
see PVs of DIEP, nearly always way longer as needed, and we should see
in his thesis that he's using nullmove, which is completely impossible
as then hardware timing is a major problem!
>
>
>
>>
>>It remains to be seen if "Singular extensions" is such an improvement. So far I
>>think that nobody has managed to prove that it is. Some people speculate it
>>could be effective only if you have a very fast computer, but only the Deep Blue
>>experiment suggests this, without further scientific proof.
>
>No. I used them in later cray blitz versions. HiTech used them as well.
>They have their good and bad points. Some micro programs have/do use them
>as well...
I use all extensions in diep nowadays (though i have temperarily
turned off recapture extensions as those were TOO expensive for me),
the basic reason is that i
search that undeep that i need to make it up tactical somehow to also
solve quickly testsets.
Positionally they do not give a thing at slow levels, but threat extensions
in general give a lot tactical.
Diep dies at search depths above 10 ply completely. My b.f. goes especially
with recapture extensions from 2.5 to 3.5, with just some threat
extensions which i do now i get to around 3.0 now, still 0.5 worse
as i would want to!
In short the b.f. is getting at least 1.0 worse because of those extensions.
So to a fullwidth search where you can get perhaps 4.3 if you have hashtables,
add first 0.5 for missing hashtables last 6 ply and add another 1.0 for
the extensions in software.
Note i also do a lot of extensions last few plies, so perhaps it's 0.8
for them.
Still that's 4.3 + 0.5 + 1.0 = 5.8 quick
Best regards,
Vincent
>
>
>>
>>
>>All this does not tell the whole story about a DB-PC match, but I hope I have
>>given some keys to help understand that the match could be closer than some
>>people expect.
>>
>>And I have only assumed a single processor PC program. A multiprocessor PC
>>program would have even greater chances of course.
>>
>>
>>
>>
>> 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.