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.