Re: [Rails-devel] Automatic route calculation

[John A. T. <ja...@ja...>]

On Sun, Mar 21, 2010 at 1:35 PM, alexti <al...@sh...> wrote:

> I've looked through discussions (I've found some from about couple of
> months ago, I am not sure how to find all of them). I think that there's
> no magic bullets and some games will require extending the logic, but if
> we could support the games currently supported in Rails that would
> probably be already useful. Then when new games are added, required
> modifications can be made. I think that's the only approach, because even
> if some algorithm can be devised that will handle all game rules out of
> the box, someone will eventually design new 18xx game that would not fit
> into it :)


Obviously if some new construct is invented for a game the algorithm will
have to be extended to support it.  I just don't see much point in
implementing something where the basic algorithm can't support the various
things we already know exist (it doesn't need to be implemented at first,
but it needs to be extensible without rewriting the basic algorithm).


> I am not sure what is n in O(n!), but I don't think that asymptotic is
> particularly useful in the given context. On the actual maps number of
> vertices and edges is relatively small and because of 18xx track and route
> rules dependency is not proportional to n! for that range of n.


If you generate all possible routes and then check to see if they are legal
and calculate their route, then it converges on n! in the number of edges as
the connectivity graph becomes more full.  If you try and limit the routes
chosen at the time based on the trains, then you run into all the issues I
mentioned above.  When you have m trains, the brute force approach amounts
to investigating n!^m possibilities (fortunately for most games the train
limit goes down as the complexity of the track graph goes up, but consider
running 4 big trains in the endgame of 18C2C for example).


> I have not played 18US, but I have tried setting up artificial examples of
> rather
> convoluted track and for single route set evaluation it was fine (though
> for AI it was causing problems).


Typical endgame positions with the simplified plain track wind up with a
large number of paths around various junctions, so the number of possible
paths to consider goes up dramatically.


> Expresses should work with this approach
>

How do you propose handling them?  To me, it seems like they are problematic
because they are essentially infinite length trains that choose the best n
nodes (with one of them having to be a token).  That seems like it requires
a brute-force approach of going through all possible routes that include a
token, and then the interaction of that with a second train gets
complicated.


> As long as such bonus is '+' it would work. But if it's something like
> "multiply by X" it would cause difficulties - that's the case I was
> thinking about when discussing the need to iterate over possible bonuses.
> If such bonus exists you would likely want to include other bonuses into
> this route (rather than into another). Of course, that's only applicable
> if the multiplier applies to other bonuses and if those bonuses can only
> be used by a single train.
>

Several games have bonuses that are +x/city where x varies by phase, or
allowing you to double one city on the route.


> > Maybe I am missing it, but I don't see where you are covering running
> > multiple trains where they can't reuse the same track.
> I remove used edges from the connectivity graph before checking for the
> next train.
>
> > You can't simply
> > choose the optimal run for trains individually, you have to choose them
> > all
> > together which adds another factor to brute-force search.
> When talking about optimal run for the train I meant for the given route
> (as provide by route iteration part of the algorithm). In a way you can
> look at this approach as first partitioning the graph into all possible
> combinations of N partitions (such that every partition contains at least
> one station) where N is number of trains and then finding the most
> valuable partition set. Essentially it's the same except storing all
> partitions would take too much memory, so it's done on-the-fly.


Ok, so you are talking about generating all possible routes then, which gets
us back to n!^m.  I suggest this cannot be made fast enough for some games.


> That could never hurt, but I don't really expect the problem as I was able
> to do at least hundreds calculations per second.
> Which games do you think would be the hardest to calculate? From my
> observations, it's the bonus rules that cause more of performance hit then
> the board size, but it might be specific to my implementation.


Some I would look at would be 18US, 18C2C (for sheer size and the ability
for a company to run lots of large trains), 1844 (which adds tunnels and
mountains that affect the route score), and 1860.


> I think that under 0.2s is a good goal for anything interactive - that's
> sort of interval people don't see as "delay".


Sure, fast is better than slow.  I am just saying that people using this as
a moderator are probably running it on a laptop, and a netbook or an old
laptop (I could even hope for an Android phone version) is going to be a lot
slower than a current desktop.  Since route calculation by hand always takes
at least a few seconds (and in the endgame of games with 12 trains can take
far longer), I think 5s on such hardware is a fine upper limit to shoot for.

-- 
John A. Tamplin