lhoward has asked for the
wisdom of the Perl Monks concerning the following question:
This is more of a general computer science/graph traversal
question than a perl question; but I'm coding in perl
and I know that this is a very smart crowd so I thought I'd see what
help you could offer.
I've recently started playing the online game CashWars (note:
this post is not a troll to get people to play CashWars, but if you
do want to try it out, use the following link CashWars
and I will get some nominal credit for refering you).
The game is played on a 721x721 grid. Every day you get
so many moves (I'm currently at 350 per day, but you can have
as many as 600). Moving 1 square horizontally or vertically
costs 1 movement point. Certain squares contain resources (Oil)
that you can gather. You can only gather resources from
a particular square once per day. I have a large list of the squares that
contain oil. What I am trying to do is compute an "optimal or near optimal path"
to visit as many oil squares as possible in a given number of
moves from a particular starting location.
I've already tried out a few algorithms:
 weighting  I weigh each of the 4 squares adjacent to the current
square based on some function of the distance from that square to
nearby untapped squares with oil in them. I've tried a few diffrent weighting algorithms and this hueristic
has worked ok.
 spanning tree  I read that a spanningtree algorithm can be
used to produce a closetooptimal solution to the Travelling Salesman Problem so I decided
to give it a try. It did slightly better than the weighting algorithm, but I feel I could
do better (since my problem isn't the classic TSP "visit every node in the minimum # of moves" problem, it is "visit
as many nodes as possible in N moves" which is slightly diffrent and would lead to diffrent optimizations).
 limited game tree  I store the 200 current best paths, then I add all possible moves to each one, and then rate the paths again;
keeping only the 200 best out of that lot (best is determined by total path length to # of oil suqares ratio). This
is the best algorithm so far, but I still feel that I can do better.
I'd like the other monk's thoughts about any other
hueristics or algorithms that I could try that
might give a good solution to this "visit as many X as possible
in Y moves" problem.
I can post my code for any of those algorithms I've
tried already if anyone is interested.
Re: Graph Traversal
by nop (Hermit) on Nov 08, 2000 at 23:53 UTC

All this effort for a game?!?
But since the problem
is interesting...
As the problem is certainly NP, try hueristics.
Simulated annealing, GAs, tabu search; whatever. The hard part is how you encode the problem. One clever way uses a sort sequence:
 Each depot gets an key, a float between 0 and 1
 To determine a tour, sort the depots by key
 Visit the depots in sortedbykey order. Return to base (closing the loop) as late as possible (eg going to one more depot would leave you insufficient moves to get home).
Start by randomly assigning keys. Your original tour will be horrible. Improve the tour by any optimization hueristic (annealing, tabu, genetic algs) with reasonable mutuation operators such as
 randomly swap the keys of two depots
 randomly peturb the keys of some depots
 randomly "crossover" two tours, by taking key values from each
The nice thing about the encoding is that it creates/maintains good subtours, and is robust to mutations
(every list of keys is a wellformed tour).
I've used this approach in a machinescheduling problem with good results. Easily coded, unlike breaking out the heavy machinery of integer programming. Good luck.
nop
 [reply] 
Travelling Salesman Problems
by tedv (Pilgrim) on Nov 08, 2000 at 23:40 UTC

If you want some good insight into travelling salesman
problems, try playing the board game Elflands by Alan Moon.
I've only played it a few times, but I'm sure that after
10 games, I'd have a much better feel for coming up with
an adequate TSP solution. Note that the perfect TSP solution
is an NP complete problem, so don't aim for the optimal
solution. Aim for "good enough".
Ted  [reply] 
Re: Graph Traversal
by Fastolfe (Vicar) on Nov 08, 2000 at 22:18 UTC

This sounds exactly like a 'travelling salesman' problem. I don't have anything specific to offer you, but perhaps you can adapt some of the algorithms/research done against this to your own problem. Just s/distance/number of moves/.  [reply] [d/l] 

 [reply] 

I don't think it's that different. It's just a weighting
problem with a threshold. Give each node a weight and
divide by distance and you have a rough heuristic for how
important it is to get there. Choose an appropriate threshold
and you've reduced it to the TSP. In theory, a slightly better
solution is to make a large graph and weight entire sections
of the graph (ie. groups of nodes). This tells you that 9
average nodes are better than 1 great node and 8 worthless ones.
But that's just another way of simplifying N nodes into 1 node,
and you still have to apply a heuristical threshold to end up
with a the TSP again.
Ted
 [reply] 

RE: Graph Traversal
by Blue (Hermit) on Nov 09, 2000 at 00:54 UTC

 [reply] 

 [reply] 
Re: Graph Traversal
by brick (Sexton) on Nov 09, 2000 at 01:38 UTC

I worked on a vaguely similar problemnodespathishand
we ended up making a tree of paths, sorting it depthwise and
breadthwise and then finding an optimized path. You may want
to consider looking at the discrete computing stuff, things
isomorphisms and node graphing. There's a red book with white
webs all over the cover, who's author I can't remember. The
title is something like Discrete Algorithms; it was pretty
helpful.
B.  [reply] 
Automate it all!
by orkysoft (Friar) on Nov 08, 2000 at 23:20 UTC

While you're at it, give it a HTTPclient interface to save yourself a couple of hours of your time. Cashwars is boring, even with only the standard (200? 50? I can't recall, I quit when I went on holiday to Canada :) moves per day.  [reply] 

Actually, the programs that I have work with
CashBrowser.
Cahsbrowser is a
UI for CashWars that makes it much easier to play
(it has a visual map of the game, you can move to a location by
clicking on it and it'll move you there across multiple squares, etc...). My programs load the map file that CashBrowser produces.
My program then produces as "automover" file (basically a list of waypoints) that CashBrowser
can load and uses to do all its movement. I just start up CashBrowser once a day and let
it do all the work. What I'm working on is generating a better file
for the automover to use.
 [reply] 

Cool, this sounds like a good "Free Lunch" thingy for those who have bandwidth >:> >:> >:>
But how much time will it take to figure out how it all works, eh?
 [reply] 


Re: Graph Traversal
by MadraghRua (Vicar) on Nov 11, 2000 at 02:45 UTC

Another alternative is to try a nonhierarchical binning approach. Use euclidian distances as a means of measuring distances between your grid, bin your distances in terms of distance between your important grids. Select the bin with the least travel cost, hopefully meaning it is optimized. You could use successive series of nodes to organize your moevments and help cut down on travel costs
Just do a web search on nonhierarchical analysis...
MadraghRua yet another biologist hacking perl....  [reply] 
Re: Graph Traversal
by Anonymous Monk on Jun 26, 2009 at 17:53 UTC

One possible hurestic and can be modeled as gravitational pull between all resource and current location.
Like comet gets attracted to large bodies.  [reply] 

