Author: Robert Hyatt
Date: 07:44:22 04/25/01
Go up one level in this thread
On April 25, 2001 at 09:02:48, Vincent Diepeveen wrote:
>On April 24, 2001 at 23:56:26, Christophe Theron wrote:
>
>>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...
>>
>>
>>
>>
>>I was not aware of that.
>
>>But given that Deep Blue reached ply depths higher than what I have written
>>above, I have good reasons to believe that their BF was indeed well below 4.
>
>without hashtable, fullwidth, hardware timing, parallel problems,
>huge qsearch, singular extensions.
>
>WITH nullmove and WITH hashtable and WITH SE and recaptures i never
>get even to 15 ply...
So what? _I_ get to 15 plies regularly in 3 minute searches. I don't believe
you have implemented SE either. the fail-high singular test is interesting to
do.
>
>>So they were using a selective algorithm.
>
>>I wonder what it was.
>
>No they weren't using a selective algorithm.
>
>Hsu even writes in IEEE99 uses a typical 12 ply search as example.
>
>The only thing which is not clear is how many plies he did in
>hardware.
>
>If they were selective like now is said then that would mean
>that deep blue was the tactical worst program ever build as for
>a simple tactical trick they needed 8 ply to find it:
>
>---------------------------------------
>--> 16. Qd3 <-- 24/91:38
>---------------------------------------
>hash guess Nd5c7,Guessing Nc7
> 6(4)[b3](29)[Qc3](30) 30^ T=1
>qd3c3 Qe7d8 bg6f7 Pa7a5 bg3c7N Qd8c7b qc3c7Q Kc8c7q bf7e6P Bb7f3n
> 6(5)[Qc3](61) 61^ T=1
>qd3c3 Qe7d8 bg6f7 Pa7a5 bg3c7N Qd8c7b qc3c7Q Kc8c7q bf7e6P Bb7f3n
> 6(5)[Qc3](16)[c3](32)[c4](46) 46 T=5
>pc2c4 Qe7b4 pb2b3 Bf8d6 bg3d6B Qb4d6b ra1a7P
> 7(5) #[c4](23)####################################################[Ra3](41)# 41
> T=10
>ra1a3 Bb7d5 bg3c7N Kc8c7b qd3b5P Nd7b6 re1a1 Qe7b4
> 8(6) #[Ra3](11) 11v T=14
>ra1a3 Bb7d5 bg3c7N Kc8c7b qd3b5P Nd7b6 re1a1 Pa7a5 qb5d5B Pe6d5q
> 8(6) #[Ra3](26)##################################################### 26 T=58
>ra1a3 Bb7d5 re1a1 Bd5c4 qd3d2 Kc8b7 bg3c7N Kb7c7b ra3a7P
> 9(6) #[Ra3](35)#<ch> 'Bc6'
>---------------------------------------
>--> Bb7c6 <--
>---------------------------------------
> 35 T=172
>ra1a3 Bb7d5 bg3c7N Kc8c7b qd3b5P Nd7b6 re1a1 Pa7a5 ra3a5P Ra8a5r ra1a5R Qe7b4
>
>this is from hashtable. It is the pv of the 10th ply there.
>Every move which has a N or b or whatever behind it means it's a capture
>so extended.
>
> 3(4) 30^ T=0
> bg6f5 Qe7b4
>
>Does the above look like a 7 ply search to you?
>No it looks like a 3 ply search to me
>
> 3(5) 48 T=0
> bg6f5 Qe7b4
>
>Does the above look like a 8 ply search to you?
>It is the same pv. It's even the same depth. Hardware processors
>just do 1 ply extra.
<sigh>
Never seen the hardware. Never seen the software. Never seen them play
and watched the screen. Yet you know _exactly_ what they are doing?
>
> 4(5) 48 T=0
>bg6f5 Qe7b4
>
>Now they get to a 4 ply search.
>
> 5(5)[Bf5](18) 18v T=0
>bg6f5 Qe7b4 re1e6P
>
>Only now we see more plies. The bigger search depth allows
>more extensions behind pv. it gets more serious now.
>
>We all know the publications from the deep blue team on extensions how
>they limited them. it's limited depending upon search depth. Each ply
>they allow at most 2 extensions. I do not have this limit in diep
>as i control my extensions better!
Extensions are _not_ limited on search depth. Don't know where you are getting
that from but it is wrong. They simply adopted the sound policy that any two
consecutive plies can not extend by more than 2 plies _together_. This is
from their IEEE journal. If one ply extends twice, then the one before or
after has to have no extensions.
>
> 5(5)[Bf5](54)[c4](78) 78^ T=0
>pc2c4 Nd5b4
> 5(5)[c4](97) 97 T=1
>pc2c4 Nd5b4
> 6(5)[c4](87) 87 T=2
>pc2c4 Nd5b4 qd3c3
>
>Is the above line a 11 ply PV? No way. Not even 6 ply. It's just 3 ply!
Do _all_ of your 12 ply searches have 12 moves in them? Mine don't. Due
to hashing, during a game most of my PVs end in <HT> and are way shorter
than the indicated depth. Does this mean _I_ am not searching to depth
14 when I say I am???
If you look at their logs and only pick the ones with short PVs you can prove
anything you want. But it is invalid. As other searches look perfectly
normal...
>One move deep blue always seems to get for free somehow in its pv.
>Note that c4 attacks a piece and that Nb4 moves that piece away.
>Simplistic case of a threat extension. Qc3 again attacks the piece
>and gets away from the attack. So we again see here 1 normal move and
>2 extensions. Very easy to extend all that. The search depth allows
>the extensions as the depth to which things are allowed to get extended
>has to do with the search depth.
>
That is totally bogus and you know it. If you extend like that the search
will blow up totally. And their articles explain how they extend. And it
did _not_ extend on stupid threats. Just read the JICCA articles.
>Why do the hardware processors remain at (5) here all the time?
>Because only now they get one ply extra!
No... because of the speed balance between the SP and the chess processor.
If you don't understand that, then explaining how their search works is
going to be impossible.
>
> 7(5) #[c4](87)##################################################### 87 T=3
>pc2c4 Nd5b4 qd3e2 Pb5c4p qe2c4P Nd7b6
>
>See all the captures, that's all too simplistic to call this a 12 ply
>search. This realy is a 2 ply search with loads of extensions.
>
>As all processors need like 0.5 seconds timeout for just a few nodes a few
>hardware processors already need 3 seconds.
>
There is no "timeout". A processor can search a tree in microseconds if you
give it the right depth limit. Please don't make up stuff and then claim it
is fact. Most of what you have said is just wild speculation and way off base.
> 8(6) #[c4](57) 57v T=8
>pc2c4 Nd5b4 qd3e2 Pb5c4p qe2c4P Nd7b6 qc4c6B Nb4c6q ra1a7P Nc6a7r
> 8(6) #[c4](56)#[Bf5](117) 117^ T=16
>bg6f5 Kc8b7 re1e6P Qe7b4 re6c6B Kb7c6r bf5d7N Kc6d7b nf3e5 Kd7e6 ne5g6 Qb4b2p
>qd3e4
>
>So finally at 8 ply Bf5 is found. Good lord. If this is 14 ply then
>deep blue is the tactical worst program ever!
Or it saw something that others miss?
>
>Even a program that doesn't use a single extension finds this tactical
>win sooner as 14 ply. Not to mention a hardware processor which does
>loads of things in qsearch and even extends extra ply if needed.
The q-search is pretty simple in DB as reported by Hsu. The hardware doesn't
extend a ply just for fun either. Would make _zero_ sense to do so.
>
>How to ever explain that this is a 14 ply search to find a tactical
>trick which i find if i turn on recaptures also at 8 ply.
>
>note shredder4 even in preprocessor version which hardly has
>king safety found it at 8 ply with recaptures. Shredder4 is
>forward pruning like hell but still finds this as it has recaptures.
>Yes it finds it because this is a tactical shot, NOT a positional shot...
>
>If it needs a 14 ply search to find this tactical shot
>then Deep Blue was the biggest joke program ever made!
>
>The long search line you see are all extensions which automatically get
>triggered in PV, as detecting SE moves in PVs is easier and all captures
>it seems to extend anyway.
>
> 8(6) #[Bf5](148) 148^ T=18
>bg6f5 Kc8b7 re1e6P Qe7b4 re6c6B Kb7c6r bf5d7N Kc6d7b qd3f5 Kd7c6 qf5e6 Kc6b7
>qe6d5N
>
>5 of the plies are captures. Leaves 8 ply. 2 moves are a check and
>we can go on like that.
Except they _never_ extended "captures"...
>
>Not a single normal move here.
>
>See however at 6[5] where 3 more or less normal plies are shown.
>That's not a 11 ply search...
>
> 8(6) #[Bf5](137)##################################################### 137 T=37
>bg6f5 Pe6f5b re1e7Q Bf8e7r pc2c4 Pb5c4p qd3c4P Nd5b4 ra1a4 Kc8b7
> 9(6) #[Bf5](137)#[TIMEOUT] 137 T=184
>bg6f5 Pe6f5b re1e7Q Nd5e7r qd3c3 Pa7a5 ra1a5P Ra8a5r qc3a5R Ne7d5 qa5a6 Bc6b7
>qa6e6 Kc8d8 qe6f5P
>---------------------------------------
>--> 17. Bf5 <-- 23/88:25
>---------------------------------------
>
Why didn't you comment on the _above_ PV? Doesn't seem to quite fit in your
"this is a 9 ply search model?"
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.