thanks,
vince
not every node in a game will get a cutoff...for example, the base
position.
such nodes "set" the alpha and beta values to "beat".
James
vince wrote:
> if each ply involves branching of 3-6 options, then why do many chess
> programs seem to search 20 or 30 some options before moving to the
> next
> ply? i refer to programs that display something like 8 ply (x/25),
> where x
> is the option it is considering out of 25 total. i frequently see it
> going
> all the way to 25/25 before going to the next ply.
>
> thanks,
> vince
--
Komputer Korner
The inkompetent komputer
Note that my true email is still kor...@netcom.ca
I don't often check the email of the sympatico address.
James F. Long wrote:
> vince wrote:
> >
> > if each ply involves branching of 3-6 options, then why do many
> chess
> > programs seem to search 20 or 30 some options before moving to the
> next
> > ply? i refer to programs that display something like 8 ply (x/25),
> where x
> > is the option it is considering out of 25 total. i frequently see
> it going
> > all the way to 25/25 before going to the next ply.
> >
> > thanks,
> > vince
>
> not every node in a game will get a cutoff...for example, the base
> position.
> such nodes "set" the alpha and beta values to "beat".
>
> James
--
: thanks,
: vince
You are confusing two terms: (1) actual branching factor and (2)
effective branching factor.
Actual branching factor in chess is approximately 38, averaged
over an entire game.
Effective branching factor is roughly sqrt(actual branching
factor) due to alpha/beta. It can be reduced further by selectively
throwing some moves out (which makes the actual branching factor
lower of course, which reduced the effective branching factor as
well.) Also, things like null-move search, razoring, and other things
that reduce the depth on certain branches effectively reduces the
branching factor as well "apparently" anyway...
--
http://www.demon.co.uk/oxford-soft
Komputer Korner <kor...@netcom.ca> wrote in article
<3395CCC8...@netcom.ca>...
> The 3 to 6 number you heard about is the search cost per ply and not
> branches. There
> are an average of 34-38 moves in every middlegame position, but each
> succeeding
> ply takes 4-6 times longer than all the previous plies in total.
As Gillgasch has pointed out (to you, Korner) before, its NOT 4-6
Chris Whittington
>
> vince wrote:
>
> > if each ply involves branching of 3-6 options, then why do many chess
> > programs seem to search 20 or 30 some options before moving to the
> > next
> > ply? i refer to programs that display something like 8 ply (x/25),
> > where x
> > is the option it is considering out of 25 total. i frequently see it
> > going
> > all the way to 25/25 before going to the next ply.
> >
> > thanks,
> > vince
>
>
>
Not always. Sometimes :-) At the base of the tree every move will be
looked at. The first move will be searched exhaustively. If it was the
*best* move, all others will be cutoff quickly. If another move comes
along
that looks better, it will be searched exhaustively also. In most
nodes,
though, a fail high at the top of the move list will eliminate examining
other moves, legal or not.
James
> order moves of the tree go so fast
> is that because of good move ordering, the alpha beta cutoffs work
> extremely well and the branches
> are cutoff more than when examining the best moves. You have been given
> the impression that
> sometimes the lower order moves were not examined, but they actually
> were. It is because they
> were examined so quickly your eyes couldn't follow it. The reason that
> they were examined
> quickly is because of alpha beta cutoffs which I explained above.
>
> James F. Long wrote:
>
> > vince wrote:
> > >
> > > if each ply involves branching of 3-6 options, then why do many
> > chess
> > > programs seem to search 20 or 30 some options before moving to the
> > next
> > > ply? i refer to programs that display something like 8 ply (x/25),
> > where x
> > > is the option it is considering out of 25 total. i frequently see
> > it going
> > > all the way to 25/25 before going to the next ply.
> > >
> > > thanks,
> > > vince
> >
> > not every node in a game will get a cutoff...for example, the base
> > position.
> > such nodes "set" the alpha and beta values to "beat".
> >
> > James
>
assumptions are ply 7 is reached in 7 sec, ply 8 at (cumulative) 27 sec,
ply 9 at 87 sec, and ply 10 at 267 sec. time per move is 180 sec, both
players use all time. also assume a 100% hit rate, giving the upper limit
of the benefit. with no pvs heuristic, and no pondering, each move reaches
9.52 ply. with both pvs and pondering the 10th ply is reached (after a few
iterations). after a (half) move, the player drops back to the 9th ply,
searches for 180 sec up to the 10th, then cycles back to the 9th ply again.
if 1 ply is worth 200 points, the maximum gain woud be about 100 points
with perfect pondering.
from what i have heard, this seems substantiated. bob hyatt stated he got
over 100 with crafty vs crafty, which should be close to perfect. at a 50%
hit rate, assume the gain is 50 points. the time gain is about 50% (287
sec vs 180 sec). if doubling time is worth 70 points, it would amount to
about 40 (based on 2^.58). i realize i may be flamed with all these
assumptions, but at the same time the estimates may close.
vince
: Not always. Sometimes :-) At the base of the tree every move will be
: looked at. The first move will be searched exhaustively. If it was the
: *best* move, all others will be cutoff quickly. If another move comes
: along
: that looks better, it will be searched exhaustively also. In most
: nodes,
: though, a fail high at the top of the move list will eliminate examining
: other moves, legal or not.
: James
A fail high really can't let you avoid searching the other moves, because
one of the other moves can turn out to be even better than the move that
failed high.
The *only* case where I don't search all moves at the root of the tree is
when I run out of time on the last iteration. Otherwise *every* root move
is searched, although all but the first generally go by in a flash...
It is "possible" to avoid searching all the root moves, as was done back
in Mac Hack, by somehow sorting the moves into "try" and "don't try"
categories. It's the don't try that is a killer of course (this is called
forward pruning) because if you label a move "don't try" you can *never*
play that move...
<snip>
> : Not always. Sometimes :-) At the base of the tree every move will be
> : looked at. The first move will be searched exhaustively. If it was the
> : *best* move, all others will be cutoff quickly. If another move comes
> : along
> : that looks better, it will be searched exhaustively also. In most
> : nodes,
> : though, a fail high at the top of the move list will eliminate examining
> : other moves, legal or not.
>
> : James
>
> A fail high really can't let you avoid searching the other moves, because
> one of the other moves can turn out to be even better than the move that
> failed high.
>
> The *only* case where I don't search all moves at the root of the tree is
> when I run out of time on the last iteration. Otherwise *every* root move
> is searched, although all but the first generally go by in a flash...
>
> It is "possible" to avoid searching all the root moves, as was done back
> in Mac Hack, by somehow sorting the moves into "try" and "don't try"
> categories. It's the don't try that is a killer of course (this is called
> forward pruning) because if you label a move "don't try" you can *never*
> play that move...
I'm not sure I understand you here. Do you not, when NOT searching the
base
position, simply return beta if *any* move with a returned score greater
than
beta is found?
I said that all moves at the base are searched (excepting time "cutoffs"
and
forward pruning tricks), and all other positions in the search are
subject to
the cutoff if score >= beta....is this not correct?
if (value > alpha) {
alpha = value;
if (value >= beta) {
update_killer_moves(move,ply);
update_history_moves(move,depth);
return beta;
} // fail high
} // best move
Please let me know if I'm missing something here...
James
: <snip>
Yes, but we are in iteration "N". When Search() returns beta, Iterate()
then has to relax beta, and call Search again, with the same depth that we
were working on, so that we can get a score for this move. *then* we still
have to search the rest of the root moves before going to iteration N+1...
: I said that all moves at the base are searched (excepting time "cutoffs"
: and
: forward pruning tricks), and all other positions in the search are
: subject to
: the cutoff if score >= beta....is this not correct?
yes. I was responding to this:
: > : though, a fail high at the top of the move list will eliminate examining
: > : other moves, legal or not.
We don't get away with not searching those moves. We don't search them
just now, because we have a fail-high move that needs resolving, but as soon
as we re-search the fail high move with a larger beta value, we then must
come back and search the remainder of the moves at the root, before we can
go on to the next iteration...
: if (value > alpha) {
chrisw wrote:
> As Gillgasch has pointed out (to you, Korner) before, its NOT 4-6
>
> Chris Whittington
>
Now I'm lost. *actual* tree size increases by a factor of roughly 38
for each additional ply. Pure alpha/beta reduces this to a factor of
roughly 5-6. Forward pruning, selective "de-extensions" like null move
and razoring, and other ideas can drop this to 2-3...