Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Branching factor, make me confuse more that ever.

Author: Dan Ellwein

Date: 06:30:28 04/05/00

Go up one level in this thread


On April 05, 2000 at 00:57:48, Tom Kerrigan wrote:

>This is just a semantic argument. What you call stuff depends on how you look at
>it.
>
>1) If you think a chess program searches the chess game tree, then the tree's
>branching factor will be 38, although only a tiny fraction of that tree is
>actually visited.
>
>2) If you consider the chess program's search tree separate from the chess game
>tree, then the branching factor is 3 (or whatever).
>
>I think it's pretty shortsighted to delcare one viewpoint correct and the other
>incorrect. It just depends on who you ask. But I think we both agree that (2) is
>more common. Might as well use it.
>

found this 'tidbit' at http://www.npac.syr.edu/copywrite/pcw/node342.html

"The problem with [this] brute-force approach is that the size of the tree
explodes exponentially.

The ``branching factor'' or number of legal moves in a typical position is about
35.

In order to play master-level chess a search of depth eight appears necessary,
which would involve a tree of 35^8 or about 2 x 10^12 leaf nodes.

Fortunately, there is a better way.

Alpha-beta pruning is a technique which always gives the same answer as
brute-force searching without looking at so many nodes of the tree.

Intuitively, alpha-beta pruning works by ignoring subtrees which it knows cannot
be reached by best play (on the part of both sides).

This reduces the "effective branching factor" [quotes added] from 35 to about 6,
which makes strong play possible."

regards...

PilgrimDan


>-Tom



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.