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

Michael Bidzos mbidzos at ufl.edu
Wed Apr 21 15:08:11 EDT 1999


oh man... a sore spot!
yes i'm new at the lists, but i can't resist the opportunity to ask...
have any of you played trade wars?  keep reading please!  =)
there is a part of the game that involves calculating every possible move
from your point to another point (part of the nav system).  This takes into
account sectors that are one-way (can move into from a direction but not out
of in the same direction, etc...) among other navigational obstacles such as
starbases and enemy territory (it would be bad to end up there 'mkay?).  In
the end it displays the fastest route (via a list of sectors to go through)
to a sector that you wish to travel to.  Everything considered.
Anyways, with talk of tree searches, do any of you know the best way to
implement such an algorithm, that does NOT involve a 'branch to infinity'
search, where if you are at point 1, you can get to 2,3,4, and 5, and from
each of these, to 7, 12, 13, etc
the game has in the neighborhood of 5000 sectors, and likely more.  An
exhaustive search (exempting the creative efforts of d.net) is impractical,
especially at run-time.  Any thoughts?  'tis been done... in the original
game!  and with the power of today's personal 'puters over the old p-60, i
can't get the search practical in under 2-3 minutes, or without using a
reference 64MB dat file.  (ahem)
it needs to take about 5 seconds max  ^_^
thanks for listening,
mbidzos at ufl.edu


 ----- Original Message -----
From: Jon Loeliger <jdl at jdl.com>
To: <rc5 at lists.distributed.net>
Sent: Tuesday, April 20, 1999 6:23 PM
Subject: Re: [RC5] Tree search algorithms and the next d.net


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

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