Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Graph Traversal

by lhoward (Vicar)
on Nov 08, 2000 at 22:16 UTC ( [id://40586] : perlquestion . print w/replies, xml ) Need Help??

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 spanning-tree algorithm can be used to produce a close-to-optimal 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.

Replies are listed 'Best First'.
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:
    1. Each depot gets an key, a float between 0 and 1
    2. To determine a tour, sort the depots by key
    3. Visit the depots in sorted-by-key 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 "cross-over" 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 well-formed tour).

    I've used this approach in a machine-scheduling problem with good results. Easily coded, unlike breaking out the heavy machinery of integer programming. Good luck.
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".

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/.
      This problem has one feature that make is distinct from the classic TSP (Travelling Salesman Problem). In the TSP you must visit every node exactly once. Even if a node is very far away it must be visited. In my case I only need to visit as many nodes as possible in so many moves and can safely ignore nodes that are "too far away".

      I've tried adpoting spanning-tree approach to solving the TSP with moderate success. But I have already done better with an algorithm of my own.

        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.

RE: Graph Traversal
by Blue (Hermit) on Nov 09, 2000 at 00:54 UTC
    A slight change on the question may give you a better perspective. Instead of "how do I pass over the most given a specified location", instead figure out "given X moves, what is the best starting position & path". This gives you a one time problem, which you may be able to apply more resources to. Once you do that, you have a single sub-optimal day where you move to your new starting location, and then you just cycle through the pattern and it's reverse on alternate days.

    =Blue might be eaten by a grue...

      Only thing is with the game you're not allowed to choose your starting position. Every day you start at the same location. So it effectively is already a one-time problem.

      I don't make the rules... I just have to live by 'em.

Re: Graph Traversal
by brick (Sexton) on Nov 09, 2000 at 01:38 UTC
    I worked on a vaguely similar problem--nodes-path-ish--and
    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
Automate it all!
by orkysoft (Friar) on Nov 08, 2000 at 23:20 UTC
    While you're at it, give it a HTTP-client 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.
      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.
        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?
Re: Graph Traversal
by MadraghRua (Vicar) on Nov 11, 2000 at 02:45 UTC
    Another alternative is to try a non-hierarchical 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 non-hierarchical analysis...

    yet another biologist hacking perl....

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.