Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 12:09:29 -0600, John A. Tamplin <ja...@ja...> wrote:

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

>> 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 am still unconvinced that this would be that relevant - in most games  
there's less than 200 tiles and there's probably 3-4 links per tile on  
average. That means less than 1000 edges even in the endgame, so it  
doesn't seem that we need to look at the asymptotic properties here. But I  
am familiar only with a limited subset of 18xx titles, are there any that  
exceed this number by much?

>
>
>> 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.
I agree that simplified track produces more edges and more possible routes.

>> 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.
Yes, I use brute-force approach of going through all possible routes that  
include a token. Why interaction with another train will be more  
complicated in this case? It still can't re-use the same track. Or are  
there games where it can?

>> 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.
That's ok. I'm assuming that the bonus table is specific to the current  
phase (it also gets updated as privates change hands etc). Doubling a  
single city is also fine as it doesn't matter what train (if only one  
allowed) will benefit from it.

>> > 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.
Perhaps it can be tested? There is no need to have complete support of  
such games in Rails to make experiment. We could create a graph  
representing "difficult case" and run algorithm on it.

>> 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.
Unfortunately, I don't own any of them :(

Alex.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/