Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Ply depth (was: Deep Blue)

13 views
Skip to first unread message

Moritz Berger

unread,
Feb 18, 1997, 3:00:00 AM2/18/97
to

One thing that I don't understand is that people tend to talk about
nodes per second or at best about 100 fold speed advantage.

I think that an important concept would be "sufficient ply depth" or
"meaningful" or even "absoulute" ply depth - I'm not talking about a
tactical horizon or something like that (whatever this might be), but
about the fact that a 4 ply improvement means more improvement in
playing strength if you start from 3 ply than it will possibly mean at
20 ply.

So the suggestion to run Rebel on a 386/16 against Crafty on a P6/200
to find out about the nps/Deep Blue issue is not meaningful in this
context, since Rebel on a 386/16 would be too far away from its
potential maximum meaningful ply depth on a P6/200, while some (Ed,
me, others ...) question if the recent improvements in the Deep Blue
hardware have done enough to improve their playing strength because
they might be _beyond_ "reasonable" depths in relation with their
extension triggers and evaluation parameters. Also fine tuning might
get almost impossible if your machine is getting more and more complex
in terms of its search tree ...

Moritz

-------------
Moritz...@msn.com

Robert Hyatt

unread,
Feb 19, 1997, 3:00:00 AM2/19/97
to

Moritz Berger (Moritz...@msn.com) wrote:
: One thing that I don't understand is that people tend to talk about

: Moritz

: -------------
: Moritz...@msn.com

The experiment won't say a thing about deep blue, of course. Hsu emailed me
that DT (1995) was searching about 3M nodes per second, not the 10M I had
given them credit for. So the 100X is also wrong. DB is now 333X faster than
DT was two years ago, which is worse from my perspective of course, because I'm
2.5 x faster than I was in 1995, thanks to the P6/200 over the P5/133. <sigh>
Maybe we can get Intel off their butts... :)

One thing I can say is that I've *never* found a particular depth, beyond which
I'd say enough... no more... There are plenty of positions that require a 16 ply
search to resolve accurately. There are some that will require 60 plies to resolve,
and those will be beyond computers for a long time, although I've seen humans find
winning lines that long. I can remember IM Mike Valvo a couple of years ago playing
a game that ended in what I thought was a draw. In chatting while he played, he
said oh, no... not a draw. I first have to relocate my king to <here> (9 moves),
then put my bishop here (5 moves), then move my queen to here, but this took about
20 moves... the entire process was 40-50 moves deep. Of course, he wasn't really
searching, he just figured out what had to be where to hold everything and then
drive the enemy king out of a blockade... no computer can solve that sort of
position tactically. I doubt any would know how to win it, although it is
certainly possible to do so positionally. In any case, here's a synopsis of
current micros and deep blue, search-wise. You draw your own conclusion:

1. the micros. Are all using some sort of tricks to reach 10-12 plies in the
middlegame. The tricks are many. null-move. Forward pruning. clever search
extensions. And all are risky. Null move has obvious drawbacks in many positions,
and the result is that we get 10-12 plies deep, but the search often acts more
like an 8 ply (or less) search, due to the way null-move works. Forward pruning
throws moves out without searching them (selective search, here) and obviously
will throw out an occasional critical move and blunder. I see this reasonably
frequently in all of them, Crafty included.

2. DB. Is searching 5-6 plies deeper than any of us, and here's the killer,
they are using *no* tricks. A full-width alpha/beta search with no null-move,
no forward pruning and no mistakes. And on top of this, they extend, using
singular extensions among other things, to really impressive depths (as though
15 or so plies is not already damned impressive. :) ) beyond that. That
deadly accurate, no compromise 15 ply search, coupled with search extensions that
take them even deeper, make for something that is nearly untouchable.

If we were talking a difference of 1-2 plies, I'd say yes, they might be close.
But we aren't we are talking 4-6 plies, *plus* accuracy, *plus* more extensions
than any of us micro guys can try due to the costs...

Again, the math. At 100K nodes per sec, Crafty is doing roughly 11 plies in
the middlegame. If we take this to 1B nodes per second, that's 10000X faster.
Since every ply costs a factor of 2 usually, up to about 3 worst case, let's
stick with 2. log(2) of 10000 is what? 13? So Crafty should hit somewhere
around 24 plies on that hardware, at that speed. Now what do you suppose they
are doing to drop this back to 15? No null move? subtract a couple of plies.
The rest goes to selective extensions. At the same speed, it is possible that
Crafty might find tactics they overlook, since it would be going full-width
to 9 plies deeper than they are. In other games, their extensions would be
crushing. The problem is, that at present, none of us are going 20+ plies,
so we are getting out-searched in the exhaustive part, and then getting out-
extended as well. There's simply no way to win with current hardware vs their
hardware. Even if their eval was crappy, which it really isn't...

So, a ply or two wouldn't be an advantage that would be worth writing home about,
although Cray Blitz suggests that it is important, because we were generally at
least two plies faster than the next closest micro, and was tactically too much
for them except in rare circumstances. However, that 6 ply handicap is tough,
the extensions make it worse, and we can't depend on their eval to make positional
blunders. There's not many cracks in their armor for the micros to slip through.
DT was bad.. this thing's monstrous...


Vincent Diepeveen

unread,
Feb 19, 1997, 3:00:00 AM2/19/97
to

>One thing that I don't understand is that people tend to talk about
>nodes per second or at best about 100 fold speed advantage.
>
>I think that an important concept would be "sufficient ply depth" or
>"meaningful" or even "absoulute" ply depth - I'm not talking about a
>tactical horizon or something like that (whatever this might be), but
>about the fact that a 4 ply improvement means more improvement in
>playing strength if you start from 3 ply than it will possibly mean at
>20 ply.
>
>So the suggestion to run Rebel on a 386/16 against Crafty on a P6/200
>to find out about the nps/Deep Blue issue is not meaningful in this
>context, since Rebel on a 386/16 would be too far away from its
>potential maximum meaningful ply depth on a P6/200, while some (Ed,
>me, others ...) question if the recent improvements in the Deep Blue
>hardware have done enough to improve their playing strength because
>they might be _beyond_ "reasonable" depths in relation with their
>extension triggers and evaluation parameters. Also fine tuning might
>get almost impossible if your machine is getting more and more complex
>in terms of its search tree ...

I agree completely with your meaningful ply depth.
I call it the tactical barrier a program must cross.
The meaning is the same.

there are however individuals in this newsgroup that don't think
that there is a meaning ful depth.

So i guess that in their minds every ply gives you x elo points,
where my vision is that
every next ply gives you less elopoints than previous one,
and if there is a big gap in your program another ply gives you
almost nothing.

>Moritz
>
>-------------
>Moritz...@msn.com
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+

Robert Hyatt

unread,
Feb 19, 1997, 3:00:00 AM2/19/97
to

Vincent Diepeveen (vdie...@cs.ruu.nl) wrote:

Let's put this in a better context. Here, we've been talking about
computer vs computer, correct? As in DB vs anyone else. So let's
stick with that particular matchup. Here's what I would claim:

the difference between ply N and ply N+1, is *not* huge. But the
difference between ply N and N+2 is bigger, and when you get to
ply N vs N+Q, where Q=6 or more, I would claim that the difference
*in computer vs computer* becomes *very signficcant*. Let's see
how the Crafty vs Rebel match goes, although it really might be
more interesting to see Rebel vs Rebel at the same 100x time handicap,
since then there's only one variable, the speed difference. In Crafty
vs Rebel, there are two degrees of freedom that will make interpreting
the data in this context less clear...

That's the subtle point you've overlooked. I have never been much
of a believer in one more ply will do it. But if I can get *six*
more plies than you, because of hardware performance, I believe that
is an obstacle you can't overcome...

And don't forget, I'm still in the computer vs computer context
here, not computer vs Kasparov. *that* I believe *is* a different
question, with a perhaps different answer. But not computer vs
computer..


Komputer Korner

unread,
Feb 21, 1997, 3:00:00 AM2/21/97
to

Robert Hyatt wrote:
>
snipped

> Again, the math. At 100K nodes per sec, Crafty is doing roughly 11 plies in
> the middlegame. If we take this to 1B nodes per second, that's 10000X faster.
> Since every ply costs a factor of 2 usually, up to about 3 worst case, let's
> stick with 2. log(2) of 10000 is what? 13? So Crafty should hit somewhere
> around 24 plies on that hardware, at that speed. Now what do you suppose they
> are doing to drop this back to 15? No null move? subtract a couple of plies.
> The rest goes to selective extensions. At the same speed, it is possible that
> Crafty might find tactics they overlook, since it would be going full-width
> to 9 plies deeper than they are. In other games, their extensions would be
> crushing. The problem is, that at present, none of us are going 20+ plies,
> so we are getting out-searched in the exhaustive part, and then getting out-
> extended as well. There's simply no way to win with current hardware vs their
> hardware. Even if their eval was crappy, which it really isn't...
>
> So, a ply or two wouldn't be an advantage that would be worth writing home about,
> although Cray Blitz suggests that it is important, because we were generally at
> least two plies faster than the next closest micro, and was tactically too much
> for them except in rare circumstances. However, that 6 ply handicap is tough,
> the extensions make it worse, and we can't depend on their eval to make positional
> blunders. There's not many cracks in their armor for the micros to slip through.
> DT was bad.. this thing's monstrous...

Bob,
in another post you said that every ply costs a factor of 2. I thought
it was about 5-8. Every body I have read has said the that each
succeeding
ply takes at least 5 times longer than the sum of all the preceeding
plies.
--
--
Komputer Korner

The inkompetent komputer.

Robert Hyatt

unread,
Feb 21, 1997, 3:00:00 AM2/21/97
to

Komputer Korner (kor...@netcom.ca) wrote:
: Robert Hyatt wrote:
: >
: snipped

: > Again, the math. At 100K nodes per sec, Crafty is doing roughly 11 plies in


: > the middlegame. If we take this to 1B nodes per second, that's 10000X faster.
: > Since every ply costs a factor of 2 usually, up to about 3 worst case, let's
: > stick with 2. log(2) of 10000 is what? 13? So Crafty should hit somewhere
: > around 24 plies on that hardware, at that speed. Now what do you suppose they
: > are doing to drop this back to 15? No null move? subtract a couple of plies.
: > The rest goes to selective extensions. At the same speed, it is possible that
: > Crafty might find tactics they overlook, since it would be going full-width
: > to 9 plies deeper than they are. In other games, their extensions would be
: > crushing. The problem is, that at present, none of us are going 20+ plies,
: > so we are getting out-searched in the exhaustive part, and then getting out-
: > extended as well. There's simply no way to win with current hardware vs their
: > hardware. Even if their eval was crappy, which it really isn't...
: >
: > So, a ply or two wouldn't be an advantage that would be worth writing home about,
: > although Cray Blitz suggests that it is important, because we were generally at
: > least two plies faster than the next closest micro, and was tactically too much
: > for them except in rare circumstances. However, that 6 ply handicap is tough,
: > the extensions make it worse, and we can't depend on their eval to make positional
: > blunders. There's not many cracks in their armor for the micros to slip through.
: > DT was bad.. this thing's monstrous...

: Bob,
: in another post you said that every ply costs a factor of 2. I thought


: it was about 5-8. Every body I have read has said the that each
: succeeding

: ply takes at least 5 times longer than the sum of all the preceeding
: plies.
: --
: --

Depends on the program. This "5" comes from Knuth/Moore's analysis of
alpha beta, which (roughly) proves that for a search to depth D, with
W moves at each ply (assume W constant so we can deal with the math here),
then minimax searches W^D nodes (^ means to the power of). Alpha beta
drops this to 2*sqrt(W^D), which is 2*W^(D/2). Since we know that
W is about 35, the typical branching factor for a plain-jane alpha-beta
search is sqrt(35) or about 6, which is what the early full-width programs
reported (chess 4.0 for example).

This branching factor is typically computed ike this.

BF = 2*sqrt(W^(D+1)) / 2*sqrt(W^D)

get rid of the 2's by division, and you get

sqrt(W^(D+1))/sqrt(W^D)

subtract

exponents to divide, let's take it in two steps...

sqrt(W^(D+1))/sqrt(W^D) = W^((D+1)/2)/W^(D/2))

you end up with sqrt(W) as the branching factor.

Now, since w=35..36..37..38 depending on whom/what you read, lets take
36 since I'm better at sqrt(36), which, as my old advanced calculul teacher
used to say "is approximately 6..."... :)

Now how can we reduce BF below 6? there are two ways:

1. reduce W. To reduce W,you have to use a selective search, and throw away
lots of moves. If you want BF=2, then W must be 4 (ugly thought, searching
4 moves, throwing away 32, right?)

2. reduce D. null move does this. Instead of throwing away a big chunk of
the moves at each ply, we simply search many of those moves to a much reduced
depth instead. (ugly thought here too, because your 10 ply search doesn't see
*every* 10 ply trick now.)

Crafty uses null move to hold this branching factor at 2-3. Rebel I don't know
about, but Ed has mentioned selective search, which probably means forward pruning
as is done in Genius and others as well. Both are prone to mistakes, but here's
the kicker. The mistakes that Crafty (and Rebel and others make) are very subtle
ones that 99.99999% of the humans simply don't see. However a program that
doesn't make that same mistake, and which searches at least to the same depth you
are, will see *every one*, and make you pay. *dearly*.

That's todays math lesson in how to reduce the branching factor to whatever
value you want. There will be a quiz next week. Question number one is can
you take the branching factor to exactly one? How? Question number two is
can you take the branching factor below 1? why or why not?

:)

brucemo

unread,
Feb 21, 1997, 3:00:00 AM2/21/97
to

Robert Hyatt wrote:

> Crafty uses null move to hold this branching factor at 2-3. Rebel I don't know
> about, but Ed has mentioned selective search, which probably means forward pruning
> as is done in Genius and others as well. Both are prone to mistakes, but here's
> the kicker. The mistakes that Crafty (and Rebel and others make) are very subtle
> ones that 99.99999% of the humans simply don't see. However a program that
> doesn't make that same mistake, and which searches at least to the same depth you
> are, will see *every one*, and make you pay. *dearly*.

I have never seen any sort of study that shows this. Is this speculation, or is this
published anywhere?

bruce

Robert Hyatt

unread,
Feb 22, 1997, 3:00:00 AM2/22/97
to

brucemo (bru...@nwlink.com) wrote:
: Robert Hyatt wrote:

: bruce

published and intuition both. Best example... Slate went from a really strong
selective search in 1975 to a full-width search in 1976. And the new program
won most of the games and was reported pretty thoroughly. Blitz in 1977 was
highly selective, it became better when it went full-width.

The intuition part is this: *how* do you selectively discard moves before
searching them? Think about some of the WAC positions where you simply hang
a queen? If you are trying to get the branching factor reduced by 1/4th,
you have to reduce the moves considered by 1/2, which is a tremendous under-
taking. If you want to reduce the branching factor (effective branching factor
I should say) from 5 to 1.5, you have to reduce the moves considered from 35+
to just over 2. That's a daunting task that no one has successfully been able
to do without making mistakes. The + is that on equal hardware, selective search
can work, because you can look deeper than I do, and there's tradeoffs that make
it attractive. But DB is a different animal. They are looking deeper than any
of us, and don't do anything selective. So they won't overlook something because
it was not considered, and *every* bug in our selective pruning will be exposed
to a *very* bright light.

Vincent Diepeveen

unread,
Feb 25, 1997, 3:00:00 AM2/25/97
to

I think that there is a big difference.

If you search 7 ply, and i only search 1 ply, then
i agree.

If i search 20 ply, and you search 26 ply,
then the % you score with 26 ply against 20 ply will not
be the same you score with 7 ply versus 1 ply.

This is also an aspect of what i call with tactical barrier:
for you i will define it depth n, for others at a certain point,
searching deeper will not give you much.

If i play 1.e4,e5 2.Nf3,Nc6 3.Nxe5?? why
would one search further than 1 ply in this position?
You just give away a piece.

In this position i define the tactical barrier: 1 ply.
After 1 ply there are no important tactics anymore that will change your
move choice Nxe5 to a different choice. Searching deeper than 1 ply
in this position i would think a waste of time.

The problem is of course: a human knows that you give away a piece, but
a computer will not soon in the future know that, so it MUST search
deeper, as it is not smart enough to see that it has reached the tactical
barrier.

>That's the subtle point you've overlooked. I have never been much
>of a believer in one more ply will do it. But if I can get *six*
>more plies than you, because of hardware performance, I believe that
>is an obstacle you can't overcome...

I have a program at home, from which i mind copying the source code,
but which shouldn't be a problem to reproduce, which searches around 14
ply in middlegame after few minutes. Just counting wood.
If i play with Diep at a depth 7 ply less than this program,
you probably already can guess what the result is of that match.

The tactical-experimental program plays 1.e3 followed by
2. Qh5 or if you are lucky (depending on your move) 2.d3

Now don't tell me that he only plays this bad move because it uses nullmove :)

>And don't forget, I'm still in the computer vs computer context
>here, not computer vs Kasparov. *that* I believe *is* a different
>question, with a perhaps different answer. But not computer vs
>computer..

Of course this is not human versus computer. That's another part
of the game. that part has to to with PR, invested money versus PR,
old opponents, computer shock, mentality, the knowledge, expectations
of the human about the program, health of the human, mood of the human,
the difficulty for the human to press the reset button in your absence,
the playing style of the human, the evening before the game,
the amount of beer and luck. Although i see a strong correlation between
the computer luck and the amount of beer.

Too Optimistic players (let's sacrafice that knight) usually seem
to score less against programs than tactical suspicious players...
...positionally you outplay em anyway, so it's just a matter of not loosing
because of tactics :)

What about a match Vincent Diepeveen (around 2167 KNSB,2260 FIDE)
versus Deep Blue? They probably don't want to risk it i guess.
Or Vincent Diepeveen versus Cray Blitz-fullwidth?

I definitely don't suffer from a computer shock, nor do i suffer because of
PR reasons.
Cheap, don't need money for such a match.
I have an internet-ascii
connection. Plenty of operators over here to transfer moves to chessboards
(as humans need to play 3d for their best performance, 2d usually also
is sufficient, but i don't want to risk that).

What about it?

I guess your program searches much deeper than in 1980.
If i would win it definitely would indicate that another ply is not
as important as is better knowledge.

Vincent

B.T.W. their is a program i loose from at home on my PP200: Diep. If it
looses because of certain knowledge, then i implement it. Next game it wins.

Robert Hyatt

unread,
Feb 25, 1997, 3:00:00 AM2/25/97
to

Vincent Diepeveen (vdie...@cs.ruu.nl) wrote:

I agree. But at 7:1, I'd expect 100% wins. at 26-20, I'd still
expect a significant difference, because 6 plies is 6 plies, and
I've seen so many positions where I thought "only one more ply
and it would have avoided that." I don't think you can give up
that kind of advantage, otherwise it seems that we can do no better
than we are today using a P6.

I agree that 1 more ply is often meaningless, but it's also often
critical. But 6?


: This is also an aspect of what i call with tactical barrier:


: for you i will define it depth n, for others at a certain point,
: searching deeper will not give you much.

: If i play 1.e4,e5 2.Nf3,Nc6 3.Nxe5?? why
: would one search further than 1 ply in this position?
: You just give away a piece.

: In this position i define the tactical barrier: 1 ply.

Unless a 20 ply search later discovers that you can't take the knight
without getting busted. I can't count the number of moves I have seen
pop out of computers, and people watching say "can that work?" "doesn't
that lose a piece?" There might be a tactical barrier for every position,
but I think it might be a variant of the uncertainty principle, that you
can't figure out how deep it is, by definition, because there's nothing
to say that an exhaustive search to depth N+Q might find something even
more convincing...

: After 1 ply there are no important tactics anymore that will change your


: move choice Nxe5 to a different choice. Searching deeper than 1 ply
: in this position i would think a waste of time.

: The problem is of course: a human knows that you give away a piece, but
: a computer will not soon in the future know that, so it MUST search
: deeper, as it is not smart enough to see that it has reached the tactical
: barrier.

: >That's the subtle point you've overlooked. I have never been much
: >of a believer in one more ply will do it. But if I can get *six*
: >more plies than you, because of hardware performance, I believe that
: >is an obstacle you can't overcome...

: I have a program at home, from which i mind copying the source code,
: but which shouldn't be a problem to reproduce, which searches around 14
: ply in middlegame after few minutes. Just counting wood.
: If i play with Diep at a depth 7 ply less than this program,
: you probably already can guess what the result is of that match.

Not the same thing, however. I'm talking about "reasonable" programs,
where one has a 6 ply handicap. Not a stripped down program that either
wins on tactics or gets crushed positionally (more of the latter than
the former also). We've always had such programs. LexEntrique (not sure
about the spelling) in the 70's was an example.

But what about two decent programs, with one searching 6 plies deeper than
the other? Two programs that play relatively equally at the same depth.
What does the 6 plies gain there? A lot more than most believe, I suspect.
Ed and I are going to run a test with a 3+ ply handicap for Rebel. Let's
see how that turns out. Then I'll get him to play the same version for maybe
10 games on even time controls to calibrate them there. And then we can decide
what the 3 plies did...


: The tactical-experimental program plays 1.e3 followed by

: What about it?

How about simply Vincent vs Crafty... on a chess server... at a long
time control. I'd like to see it just for fun. You can pick the time
control, just so it's within the context of what a server will allow.
Maybe 60 180 (60 minutes initial time, 180 seconds added after every
move?)

As I've said, such a game or games would be interesting. I'd bet we could
get Lonnie to operate Rebel 8, and the other gaggle of programs he owns as
well, so we could do two vs crafty (black/white on two successive days),
then a day off, then two vs rebel, etc...

I'm game to see how it turns out...


: I guess your program searches much deeper than in 1980.


: If i would win it definitely would indicate that another ply is not
: as important as is better knowledge.

No, it would indicate you are a better player however. I don't see how
you can conclude ply vs knowledge with CB. CB got slower over the years
in depth searched, not faster, because we kept adding to the eval, and
adding to the search extensions. When we quit, the evaluation was about
8,000 lines of fortran long... quite a chunk of code. The last time I
ran it, it was barely able to hit 12 plies on the fastest machine I know
of (T90). Crafty hits 12 all the time on the P6...


: Vincent

: B.T.W. their is a program i loose from at home on my PP200: Diep. If it
: looses because of certain knowledge, then i implement it. Next game it wins.

You must not adapt very well. :) Or you are a much better programmer than
I am... or both... :)


0 new messages