Re: [Rails-devel] Automatic route calculation

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

On Sun, 21 Mar 2010 10:27:18 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Sun, Mar 21, 2010 at 1:43 AM, alexti <al...@sh...> wrote:
>
>> I am not completely sure if you were referring to the difficulties of  
>> the
>> algorithm or the difficulties of the integration, but I assume it's  
>> former.
>>
>
> Yes, I am talking about the actual algorithm.  Please see the archives  
> for
> several long discussions on the idea, but I will bring up a few specific
> points here.
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 :)

> I'm not sure I get the value of having a fixed set of vertices inside the
> tile -- why not just have them where they are needed?  A #57 tile for
> example, has only one interior vertex, and a #8 tile has none.  It seems
> like what you want to do is just maintain a connectivity graph of hex  
> edges
> and scoring points (actually, you will probably want several connectivity
> graphs for different train types, like one ignoring dots for trains that
> ignore them).
The primary advantage that map lookups are replaced with arithmetics which  
means that, for example, checking for backtracking only involves simple  
arithmetics instead of having to lookup a vertex and check if it's on the  
tile edge. I use the method you've suggested for the tiles description  
though.

I am not sure about benefits of separate graphs for various dot treatment.  
If the company has a mix of express and non-express trains removing the  
used edges would become more complicated if the graphs are separate; and  
if the dots counting is optional you would have to make decision to count  
them or not during the route evaluation anyway.

> A brute-force search of all possible routes is O(n!), and is really only
> feasible (even on modern machines) for 1830-like games.  Games like 18US
> that have simplified plain track tend to have a couple orders of  
> magnitude
> more possible routes.
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. 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).

> If you try to take into account the train types to avoid evaluating all
> possible routes, then you run into the following problems:
>
>    - trains that can skip stops, like 1846's n/m trains and 1844's 8E  
> trains
Expresses should work with this approach, I am not entirely sure about  
1846's n/m. It might be simple to add support of them, but there might be  
some pitfalls related to bonuses.

>    - trains that can substitute types of stops (like n+m trains)
Those should be easy to handle, I think.

>    - bonuses given when particular sets of stops are included on the  
> route
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.

>    - games that allow a train to run through one fully blocked city, like
>    1860
This is an interesting one...
>    - games that have choices about stops that give money to the company
>    instead of the dividend, like halts in 1860
I don't know 1860, but this sounds problematic. Is it something like mail  
runs in 1853? If so, that makes "best" undefined - there may be trade off  
between higher revenue for the company and higher dividend.

> 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.


> I really think that a pure brute-force algorithm is not going to be  
> suitable
> for many of the games out there.  Many years ago, when desktops were  
> about
> as powerful as my phone is now, I wrote a route calculation algorithm for
> 1830-style games that transformed the problem into a flow graph problem  
> and
> used max-flow/min-cut to compute the best route for a set of trains.
>  Unfortunately, I have lost that code and it was also not extensible for
> many of the other train types that have been added in new designs.
>
> Maybe we can start with a brute-force algorithm with a user-settable  
> timeout
> where it aborts processing if it is just going to take too long, so that
> games that can make use of it can benefit from it and then in the  
> endgame of
> the more complicated games users will have to go back to counting  
> manually.
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.

> My personal belief is that for basic route calculation after the player  
> has
> completed their move we should shoot for 5 seconds on a 5-year-old  
> laptop.
>  Note that this doesn't help while placing track, such as running various
> what-if scenarios to help the player would require the algorithm be an  
> order
> of magnitude faster.
I think that under 0.2s is a good goal for anything interactive - that's  
sort of interval people don't see as "delay".

> Likewise, an AI player would need to evaluate routes
> in many possible positions for lookahead and evaluating opponents' likely
> moves, so it would need route calculation to be another order of  
> magnitude
> faster than that.
Yes, I've encountered this problem with AI. AI is a separate can of worms  
though - brute-forcing through the stock round doesn't work well either  
even if you've already determined your target operating round priorities.  
I am actually amazed how that old 1830 AI managed to play even at the  
level it did :)


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