branching factor question

89 views
Skip to first unread message

vince

unread,
Jun 4, 1997, 3:00:00 AM6/4/97
to

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

James F. Long

unread,
Jun 4, 1997, 3:00:00 AM6/4/97
to

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

Komputer Korner

unread,
Jun 4, 1997, 3:00:00 AM6/4/97
to

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.

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.


Komputer Korner

unread,
Jun 4, 1997, 3:00:00 AM6/4/97
to

Every legal move still has to be looked at. The reason that the lower
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

--

Robert Hyatt

unread,
Jun 5, 1997, 3:00:00 AM6/5/97
to

vince (vj...@doubled.com) 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


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...

chrisw

unread,
Jun 6, 1997, 3:00:00 AM6/6/97
to

--
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
>
>
>

James F. Long

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

Komputer Korner wrote:
>
> Every legal move still has to be looked at. The reason that the lower

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
>

vince

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

here's another attempt to quantify the pondering benefit.

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



Robert Hyatt

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

James F. Long (wzrd...@fia.net) wrote:

: Komputer Korner wrote:
: >
: > Every legal move still has to be looked at. The reason that the lower

: 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...


James F. Long

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

Robert Hyatt wrote:
>
> James F. Long (wzrd...@fia.net) wrote:
> : Komputer Korner wrote:
> : >
> : > Every legal move still has to be looked at. The reason that the lower
>

<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

Robert Hyatt

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

James F. Long (wzrd...@fia.net) wrote:

: <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) {

Komputer Korner

unread,
Jun 7, 1997, 3:00:00 AM6/7/97
to

I know I know. Alpha beta prunes a lot off to reduce the factor down to
2-3.
. What I meant was the actual tree size is 4-8 times bigger. I must
have been too tired
when I wrote that.

chrisw wrote:

> As Gillgasch has pointed out (to you, Korner) before, its NOT 4-6
>
> Chris Whittington
>

Robert Hyatt

unread,
Jun 8, 1997, 3:00:00 AM6/8/97
to

Komputer Korner (kor...@netcom.ca) wrote:
: I know I know. Alpha beta prunes a lot off to reduce the factor down to

: 2-3.
: . What I meant was the actual tree size is 4-8 times bigger. I must
: have been too tired
: when I wrote that.

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...

Komputer Korner

unread,
Jun 8, 1997, 3:00:00 AM6/8/97
to

Yes, but the number of nodes that are actually looked at are what you
say 4-8
or 5-6 if you will. I was wrong when I said that alpha beta prunes it
down to 2 or 3.
I forgot about the other ideas of forward pruning, null move.... etc.
Reply all
Reply to author
Forward
0 new messages