With increasing CPU robustness, and ample books, why are searches not
started at a depth of 8 ply, or even deeper for tournament time controls?

Clearly, the number of modes/sec has become so fast as to make the shallower
plys a formality for housekeeping, such as hash tabling, repetitions,
castling, blunder checks, among other things.

Is there a huge disadvantage to starting a search at a deep ply? Assuming
the time is around 3 minutes for the full search. The benefit is: if it
takes 3 minutes to get to 9 ply, and 6 minutes to get to 10ply, why not save
the 3 minutes and go right to 10.

"Derek Wildstar" wrote in message
. net...
With increasing CPU robustness, and ample books, why are searches not
started at a depth of 8 ply, or even deeper for tournament time controls?

Clearly, the number of modes/sec has become so fast as to make the
shallower
plys a formality for housekeeping, such as hash tabling, repetitions,
castling, blunder checks, among other things.

Is there a huge disadvantage to starting a search at a deep ply? Assuming
the time is around 3 minutes for the full search. The benefit is: if it
takes 3 minutes to get to 9 ply, and 6 minutes to get to 10ply, why not
save
the 3 minutes and go right to 10.

The information gathered in the lower plies is needed to speed up the search
at the deeper plies.

It's faster to search 1-2-3-4-5-6-7-8-9-10 plies than it is to search 10
plies
because of this.

--
GCP

From: "Derek Wildstar"
Date: 01/10/03 04:21 GMT Daylight Time
Message-id: WKreb.641006$YN5.491935@sccrnsc01


"Gian-Carlo Pascutto" wrote in message
...
"Derek Wildstar" wrote in message
. net...
With increasing CPU robustness, and ample books, why are searches not
started at a depth of 8 ply, or even deeper for tournament time
controls?

Clearly, the number of modes/sec has become so fast as to make the
shallower
plys a formality for housekeeping, such as hash tabling, repetitions,
castling, blunder checks, among other things.

Is there a huge disadvantage to starting a search at a deep ply?
Assuming
the time is around 3 minutes for the full search. The benefit is: if it
takes 3 minutes to get to 9 ply, and 6 minutes to get to 10ply, why not
save
the 3 minutes and go right to 10.

The information gathered in the lower plies is needed to speed up the
search
at the deeper plies.

It's faster to search 1-2-3-4-5-6-7-8-9-10 plies than it is to search 10
plies
because of this.

Understood, but, isn't the information gained by searching 10 ply, used in
searching 11? Therefore, if the lost time is under three minutes (in the
above example) a net gain is achieved...follow?


You're missing Gian-Carlo's point, I fear, which is that it's faster to search
1-2-3-4-5-6-7-8-9-10-11 plies than it is to search 11 plies.

It's faster to search 1-2-3-4-5-6-7-8-9-10-11-12 plies than it is to search 12
plies.

It's faster to search 1-2-3-4-5-6-7-8-9-10-11-12-13 plies than it is to search
13 plies.

It's faster to search: 1-2-3-4-5-6-7-8-9-10-1.... are you getting this, yet?

Cheers
Mark

"Derek Wildstar" skrev i meddelandet
news:Lxseb.648783$uu5.105748@sccrnsc04...

"Mhoulsby" -remove- wrote in message
...

It's faster to search 1-2-3-4-5-6-7-8-9-10-11-12 plies than it is
to
search 12
plies.

It's faster to search 1-2-3-4-5-6-7-8-9-10-11-12-13 plies than it
is to
search
13 plies.

It's faster to search: 1-2-3-4-5-6-7-8-9-10-1.... are you getting
this,
yet?



Absolutely, however...it's a question of precisely *how much* faster
and
under what conditions. I suspect that it is faster to ignore the
lower plys
and jump right in to a deeper search, and I'd like to prove it, or
set up an
experiment to test that theory.

If it takes 3 minutes to search to 9 ply and then 6 more minutes to
10
ply.... would a 'virgin' search to 10 ply take *less* than 9 minutes
total?

NO.

That is the point of the other poster. :-)

The thing is that 1-2-3-4-5-6-7 might take 10 s. How much can you save
on that?


Bo Persson


I think we all understand the concepts, it's making sure we all
understand
what each of us is trying to get across.

:-)

If it takes 3 minutes to search to 9 ply and then 6 more minutes to 10
ply.... would a 'virgin' search to 10 ply take *less* than 9 minutes
total?

This will vary highly, but in the general case you can expect it to be
slower than searching every ply. But what's worse, there's no guarantee
it'll actually finish in any reasonable time! What move are you going to
play when time runs out then?

--
GCP

"Derek Wildstar" skrev i meddelandet
news:iYDeb.475377$Oz4.303553@rwcrnsc54...

"Derek Wildstar" wrote in message
. net...
With increasing CPU robustness, and ample books, why are searches
not
started at a depth of 8 ply, or even deeper for tournament time
controls?

Clearly, the number of modes/sec has become so fast as to make the
shallower
plys a formality for housekeeping, such as hash tabling,
repetitions,
castling, blunder checks, among other things.

Is there a huge disadvantage to starting a search at a deep ply?
Assuming
the time is around 3 minutes for the full search. The benefit is:
if it
takes 3 minutes to get to 9 ply, and 6 minutes to get to 10ply,
why not
save
the 3 minutes and go right to 10.



I appreciate the responses, but none of them provide any
quantitative data,
just subjective notions. Clearly a question like this needs data to
prove or
disprove it, and since I don't have a method to test an initial
brute force
search greater than a depth of 1, and then compare that same engine
to the
start at 1-ply method I guess it will remain unanswered.

Ok, if you don't belive the 3 posters that have already answered, you
are of course free to consider it unanswered.

Everybody else know the answer though. :-)


Bo Persson

Derek Wildstar wrote:

"Derek Wildstar" wrote in message
. net...
With increasing CPU robustness, and ample books, why are searches not
started at a depth of 8 ply, or even deeper for tournament time controls?

Clearly, the number of modes/sec has become so fast as to make the
shallower
plys a formality for housekeeping, such as hash tabling, repetitions,
castling, blunder checks, among other things.

Is there a huge disadvantage to starting a search at a deep ply? Assuming
the time is around 3 minutes for the full search. The benefit is: if it
takes 3 minutes to get to 9 ply, and 6 minutes to get to 10ply, why not
save
the 3 minutes and go right to 10.



I appreciate the responses, but none of them provide any quantitative data,
just subjective notions. Clearly a question like this needs data to prove or
disprove it, and since I don't have a method to test an initial brute force
search greater than a depth of 1, and then compare that same engine to the
start at 1-ply method I guess it will remain unanswered.



The point of the iterated search is to learn things from a shallow search
that can be applied to make a deeper search more efficient. Most notably
the transposition/refutation table passes move ordering information from
the depth N search to the depth N+1 search.

In general, going 1-2-3-4-5-6-7-8-9-10 will take _significantly_ less time
than just starting at 10. And even worse, where do you start if you start
directly at N? IE if you start too shallow you finish too soon and play a
move after a shallow search. If you start too deep you get no move back
and now you have no way to choose a move at all.

Iterated search has two significant advantages over non-iterated:

(1) It makes time-control handling much easier. You just keep going
deeper and deeper until you run out of time.

(2) it greatly improves alpha/beta efficiency by making the move ordering
better. IE the best root move at 9 plies will likely be the best (or at
least a good first attempt) at ply=10. Ditto for all the other moves at
various depths within the tree...



--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170

"Bo Persson" wrote in message
...


Ok, if you don't belive the 3 posters that have already answered, you
are of course free to consider it unanswered.

Everybody else know the answer though. :-)


Bo Persson


Maybe they do know, but a mere no isn't enough...I'll stick with Bob's
answer, it has sufficient detail and logic to meet my criteria and my
understanding. It's not like I'm being stubborn or anything.

Derek Wildstar wrote:

"Robert Hyatt" wrote in message
...

The point of the iterated search is to learn things from a shallow search
that can be applied to make a deeper search more efficient. Most notably
the transposition/refutation table passes move ordering information from
the depth N search to the depth N+1 search.

In general, going 1-2-3-4-5-6-7-8-9-10 will take _significantly_ less time
than just starting at 10. And even worse, where do you start if you start
directly at N? IE if you start too shallow you finish too soon and play a
move after a shallow search. If you start too deep you get no move back
and now you have no way to choose a move at all.

Iterated search has two significant advantages over non-iterated:

(1) It makes time-control handling much easier. You just keep going
deeper and deeper until you run out of time.

(2) it greatly improves alpha/beta efficiency by making the move ordering
better. IE the best root move at 9 plies will likely be the best (or at
least a good first attempt) at ply=10. Ditto for all the other moves at
various depths within the tree...


Thanks for the detail Bob, and of course, it's hard to go against your
experience and techniques. Especially when your answer makes good sense.

Just note this is not my idea. The first example of this I saw was in
1976 with Davit Slate and Larry Atkin's program. At first I thought it
was wasteful for the reasons you suggested. But when I tried it, it
was better.

Therefore since move ordering is so important in increasing efficiency of
search (by establishing 'good' alpha and beta), if you start with a deep
search, the lack of a 'vetted' move order defeats any time saved by not
completing a shallower search. Only by initial shallow iterative seraching
can a move order be established that sufficiently prunes the tree and has
the best 'chance' of returning the best eval of all the positions (in the
time alotted)

Correct...


I would surmise that you would state, emphatically, the only way to generate
an appropriate move order list, is by a shallow iterative search. If this is
true, then its somehow become a 'law' of chess programing, which is fine if
it's the only way. Finally, even if there was a way to generate a move
order list without searching shallow, unless it is a) quicker then current
methods b) fits in the time alotted c) as accurate as shallow iteration,
it's not a realistic alternative.


The problem is all about move ordering. If we could do it perfectly, we
would just order and take the first move without doing a search. If we could
do it near perfectly, we might do the same. But, as you surmise, ordering is
tough. In an exhaustive or full-width search, you can depend on captures to
be the best move most of the time, because looking at all moves results in
lots of hung material. But once you cull the obviously lemon-type moves,
the remainder of the move ordering is difficult. Well-known ideas like
killers, history moves, come to mind, but none are as good as a move
that was proven best in this position by the depth N-1 search you (hopefully)
just finished.

The better the ordering, the better you drive the total search space
toward the Knuth/Moore lower-bound for alpha/beta game tree search
space for that particular depth.



Is there any example of what I'm describing? I would really like to explore
this issue in greater depth, I believe there is merit in futher
investigation, even if, ultimately, I prove in all circumstances that all
searches *must* start at 1-ply.


I don't know of any proof, as this has been more of an experimental
science effort to date. But just looking at some chess positions will
show you the problem. The "best" move needs to be played first whenever
possible, throughout the tree, for optimal alpha/beta cutoffs. But
identifying this "best" move is _not_ easy. There have been _many_
attempts at recognizing such moves heuristically, but there are so many
exceptions that break such assumptions. Just try to write a piece of
code that will order a "smothered-mate initiator" first. And remember
that when there is really a smothered mate possibility, you have to
order that move first (IE Nf7+ Kg8 Nh6+ Kh8 Qg8+ Rxg8 Nf7#) so you
have to get Nf7+ ordered first, but _only_ when it leads to a forced
mate. IE if f7 is defended by one piece, then you need a second knight
that hits f7. If it is defended by two pieces, forget about it. That
is really an easy case for a human to understand, but to push it forward
into a computer algorithm that works with near 100% reliability is not
easy. And then you realize that the smothered mate on f7 is but one
special case of _many_ similar themes.

Trying to do that kind of move ordering results in move ordering code
that is many tens of thousands of lines long, while the iterated search
approach only adds a couple of hundred lines, total.

My real suspicion is that by the time you write code that is good
enough, it will be no faster than just doing the N-1 search. And since
the iterated search will be much simpler, it will have fewer bugs and
produce fewer glitches.

I once did that kind of code in my first chess program back in the
late 1960's and early 1970's. But the code got so big that I eventually
dumped it all and did the iterated approach. I've never "looked back".








--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170

Robert Hyatt writes:

...
Trying to do that kind of move ordering results in move ordering code
that is many tens of thousands of lines long, while the iterated search
approach only adds a couple of hundred lines, total.

My real suspicion is that by the time you write code that is good
enough, it will be no faster than just doing the N-1 search. And since
the iterated search will be much simpler, it will have fewer bugs and
produce fewer glitches.

Bob has this exactly right. I have a modest Othello program which uses
*only* iterated search (and a pretty good Eval function). I started
work on this program some 20 years ago, after watching the computer
chess efforts of the previous 20 years. Over time, I (have students)
experiment with adding this or that feature to try to improve things.
Almost always, the result is that time spent on doing iterated search
has the best payoff.

And, it really is "almost free" - both in lines of code and instructions
executed.


--
Kenneth Sloan
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/