[RC5] Tree search algorithms and the next d.net

Jon Loeliger jdl at jdl.com
Tue Apr 20 18:23:34 EDT 1999


So, like Greg Hewgill was saying to me just the other day:
> On Mon, Apr 19, 1999 at 01:10:34PM -0700, Adam Zilinskas wrote:
> > Hmmm this makes me think of a different kind of D.net.
> 
> The OGR search is indeed a tree search. It is a very broad tree
> compared to its depth - for an N-mark ruler it is N levels deep, but
> the number of leaves under a given node can easily exceed 100 for N
> between 20 and 30.

I assume here by "leaves under a given node", you really don't
mean "terminal leaves of the search space", but rather a typical
"branching factor" at any internal node of the search tree.  Right?

Anyway, tree search algorithms are fairly well understood and
sometimes clever tricks can be used to limit the actual search
space.  I have not given any thought to the OGR tree search space,
so I was wondering: if someone else has thought about it more,
do you know if it is susceptible to any variant of alpha-beta
minimax pruning?

Typically this technique is applied in game-tree searches
where a move at one ply is followed by a counter move at the
next deeper ply and compared to sibling branches to refute
and thus limit search space there.

Similarly, a "killer heuristic" can be used to out-right prove
that certain search-spaces are no longer viable and need not
be searched further.

Again, I've not studied the OGR problem at all, and am just
tossing out known tree-searching heuristics to be pondered by
someone who just might know better...

jdl

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list