Maybe it’s been the heat, but I’ve been a little run down lately, so I’ve been doing some serious … resting … on the weekends lately, as well as finding some simple, short-term problems to engage my programming faculties on.
I think too much multi-tasking, or multi-tasking during the wrong phase of programming, can train your brain into becoming a “make a start”er, and I like not to slip into that, so I like to find a problem or two that I figure I can tackle fairly quickly, and that I can only tackle if I can get my brains attention on it.
My only issue is that I won’t solve abstract problems. They have to be practical to me in some sense, so it can take a little effort finding a problem on which I will engage in all aspects.
This weeks problem, I will present for your entertainment, but in an abstract form ;)
Traversal
The object is to traverse from a starting node in a network to an ending node. For each evaluation we are given a different network topography and linkage.
The nodes in the network are variously connected via unidirectional links, each having 4 outgoing links to other nodes. One link is always to the next node in the path for this network, while the destination of the others is unknown, but usually back down the path.
Links are one way: If node 5 links to node 6, then it will merely be coincidince if node 6 also links to node 5.
Each node always has four outgoing connections, although the connection may lead back to the same node.
You always – can only – start at node 1.
Should be simple, but here is the catch:
You cannot see inside the network.
For any given path the network shows three resulting states:
– GOAL: Reached (or passed thru) goal node,
– Middle: Terminated in the “middle” of the network,
– Start: Terminated (or failed to leave) the first node
The branches between nodes are always the same, e.g. node 1 always has one connection to node 2.
And if you want to try it out…
telnet ww2.kfs.org 9890
The network is regenerated each time you connect so, for example, you can start by inputting four simple paths:
* Enter Path: 4
Attempt #1 … 4 : reached Middle in 1 steps
* Enter Path: 3
Attempt #2 … 3 : reached Start in 1 steps
* Enter Path: 2
Attempt #3 … 2 : reached Start in 1 steps
* Enter Path: 1
Attempt #4 … 1 : reached Start in 1 steps
I dabbled with a variety of approaches to solving it, mostly in Perl. The first was messing with AI::Genetic, while the second was a slightly more hands-on, brute force approach, but that generates an awful lot of attempts on a standard run.
If you want to take a crack at it, feel free to have your client connect to my little app above to try out your theories :)
kfsone's pittance 
27 Comments
I’m trying to get it unclouded in my head. So, basically this is a maze where we can move N, S, E or W through one-way doors (if they are there). We start at an unknown location in the maze and are trying to reach an unknown location in the maze (i.e. “you’ll know it when you get there…can’t miss it”).
The example you posted is the main thing that is confusing me (I haven’t tried your app yet). It appears that you went from node 1 to node 2, then back to node 1 (via path #3 out of node 2), then bumped your head into 3 wall arounds you at node 1. When you really would have wanted to move back to node 2 with attempt#3, and then try a path different than “3”. Correct?
Also, what is the reason…to find a good algorithm for getting through the maze, or is there a specific pattern that is always true, which we are trying to discover?
Ah, actually logging in and reading the intro clears up a lot of things.
I edited the instructions.
You *always* start at node 1, it’s all about paths.
But yes, it is very much like a maze otherwise.
Each node always has four outgoing connections, but some nodes have connections that return to the node. (Which would be a doorway that’s not there in your example, but some might see an absent exit as the end of a path).
And as a bonus. It supports /wtf :)
Okay, cool. That wasn’t too hard. But the real goal is to write code to find the best path automatically? Is this related to WWII Online, and if so, is it to find a supply route between HQ1, 2, and 3? If so, why not have it done the way I just did…with human input. Have the commanders manually input the path for their supply to take. When it becomes visual supply…they may want to do this anyway. There may be moments where they want the supply to take a longer route, but remain under better air protection.
lol..it’s a lot harder now that you’ve stopped telling us what node we hit :) I think I logged in initially while you were debugging.
Yeah, that second time took me about 5x longer. Basically, once I got to the second node I would disregard any node that resulted in Start from one of it’s paths. That’s really the only logic I used…not sure how efficient it was, but it got me there.
Ah, yes, it wasn’t supposed to be that easy (Soraz) :)
Actually, its not dissimilar to the HQ1/etc routing issues, which is why the problem interested me, but that’s not the origin problem :)
Anyone who figures out what the origin problem was, don’t post yet :)
For the first couple of nodes, that’s relatively efficient, but then it starts branching. It’s possible to get lucky and get to the goal in very short order :) But its also possible to wind up in a great twisty maze of routes.
Actually, I have a better one with 13 nodes. Maybe I’ll put that one up.
Oops, found a typo in the branch instructions, it wasn’t branching until quite late which made it fairly easy :)
If the graph is permanent in nature, i.e. the connections doesn’t shift around, if would probably work to do a full dumb traversal of all nodes connections and build a map of the grid. It looks like the links are unweighted, so the following traversal calculations are real simple, with the cost being Cost(A,B) = count(#links) between A and B.
Now, each node will have to do this traversal as part of their startup, so you would really end up with something that had n^2 link informations in each node.
Now, if the object is to _not_ have a rigid graph, due to allowing indivudual nodes to drop out (or be removed) you could still have the network map out initially, and then when it discovers a discrepency from the cached form, retrace its route.
By rigid, I mean “doesn’t change every 10ms”
Or did I misunderstand something?
Unless you have other heuristics you can apply to the network, it will always end up in record-and-retry. You can then fiddle with the traversal, either using backtracking or simple random approaches.
I got a client halfway done before cussing my puny telnet component. But first:
– Does the network change between queries?
– Will it change during the course of evaluating the route?
– Is the object of the excercise simply to map the maze in the most efficient manner?
LOL, oh. I seeee… no “You reached node #” messages now….
hmm.
Anyways, can you know how many nodes are in the graph, and how long the average route will be?
Yeah, I can’t see how a complicated version would be done without mapping it for reference. Of course, the method I use for unmapped dungeon exploration in games is usually just making left turns…of course my goal is to explore everything…not get to some location efficiently.
Soraz has a much better handle on how to do it than I. I’m not too good at math or programming.
Don’t get used to those node readouts, Soraz. I think he’s just debugging.
One almost wishes one had this document on hand:
E.F. Moore. The shortest path through a maze. In International Symposium on the Theory of Switching Proceedings, pages 285–292, Cambridge, Massachusetts, Apr. 1959. Harvard University Press.
Think of it this way — you are an algorithm, your job is to solve the network, but each time you – as an algorithm – are presented a network, it is different. However, each network you receive will remain unchanged and constant for as long as you choose to evaluate it :)
Yes, the extra debug was temporary – it gives away too much about the network :)
If you want to actually play with this programatically, I’ve written a simple Perl client for housing any kind of automatic mapping/playing with the network you wish to do, here:
http://ww2.kfs.org/traversal_client.pl
or
http://ww2.kfs.org/traversal_client.txt
HM.. I can think of several things this ‘maybe’ related too. And I like ALL of them. :-)
The puzzle itself originates outside our game, but my extended interest in it lies in my seeing other practical, game-related, purposes in exploring solutions to it.
heh, Graphs and Networks. This is a huge problem to solve in many MMO’s. Mapping the optimal course from point A in the Network to point B in the network is a very common and still a very difficult problem. Depth first searches or Breadth first searches are some basic strategies if I remember correctly.
This is a good topic on many levels.
This wikipedia article is actually fairly comprehensive on the topic:
http://en.wikipedia.org/wiki/Graph_theory
you may want to look at Dijkstra’s algorithm for finding the shortest path in a weighted graph. There are other algorithms but I have used this one before.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
blarhg. Dijkstra’s doesn’t work for hidden graphs.
it’s also for weighted stuff.
so I assume that being in the middle means that you are anywhere BUT the start or end. heh maybe next week I’ll take a crack at it when I have time to actually implement an algorithm. I dinked around by hand but it’s obviously a job for a program.
Did the genetic alg in perl work good?
As a semi-related aside, there was an interesting (and successful) attempt made at solving Hamiltonian path-related problems using strands of DNA in the mid-90s. It was only a seven node system, and took about five days worth of experimental steps, but is pretty cool all the same. Takes advantage of the fact that with chemical reactions involving trilliosn upon trillions of molecules, you are essentially performing massively parallel computations. The challenge is then to filter out the successful “answers”.
Anyway, here’s a link if anyone’s interested. Check out the first reference for the original 1994 Adleman article.
Now back to the main event… :-)
The question of weighting is irrelevant since all edges can be assigned the same positive weight eg. 1. The traditional algorithms of Dijkstra, Bellman, Ford, Floyd-Warshall etc are all useless because we don’t know G(V,E) a priori.
As to practicality I’m a little stumped as to how you can know that you have been through the goal vertex at the end of a path but not know if you are there during the traversal of the path.
Can we assume that we have a rough estimate on the number of nodes? And is the objective to make the fewest number of guesses or to make our guesses cheap to evaluate? ie. Do two 10 edge path cost the same as one 20 edge path? And is the object to find a path or to find the shortest path?
I’m sceptical about using genetic algorithms and not just because of my bias against sub-optimal solution techniques. It seems to me that with just three outcome states applying to an entire path that there is no way to evaluate the worth of any given sub-path for genetic exchange and no way to judge incremental improvement between any two paths that end in the “middle”.
You could probably map out the network by testing all the paths that get you back to the start ie. building up a big list of failed paths. But for a large network storage space and time would be issues.
Other than that throwing some very long random guesses at it and looking for a hit to pare down looks to be the simplest to implement.
Sic: Consider that reaching the goal node has an effect: destroys the network, turns on a light, or something
I put more of the details in the splash screen on my perl-based implementation of the problem.
There are 9 nodes in the source version of the problem, but I’m not, per-se, trying to solve that, I’m more interested in the problem in this sort of limbo state between where I picked it up and some of the analogies I’ve seen to it in our game.
Actually, when I was trying “blind” versions, the AI::Genetic approach was very good because genomes which avoided the branches quickly became the fittest so through natural selection the system became sensitive to the topology.
By the way – this is an exercise, not an obstacle.
Well, crap. I stumbled across the client code the other day and now I’m wondering where the hell the server implementation went.