Re: [Rails-devel] Automatic route calculation

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

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.


> Perhaps I should explain how the algorithm works to make things more
> clear. There are two parts to the algorithm - route selection and route
> evaluation. Route selection is performed on the abstract connectivity
> graph (which is a vector of edges and a associative map of vertices). Each
> edge is a pair of vertex coordinates on 2-D grid (I use specific encoding
> that allows to go between these vertices and hexes (or tiles) and back by
> simple arithmetics). Vertex information contains some basic data, such as
> whether there is a town at this vertex, if it's blocked [by station
> markers of other companies], current town/city value etc... The way this
> connectivity graph is defined takes care of handling use of track segments
> and visiting same cities. It would be easier to show he method on the
> picture, but I will try to describe it here. Let's say we have a hex
> oriented so that one side is facing north, another south and the other 4
> NW, SW, NE and SE. For each hex there will be 13 vertices. One in the
> center (#0), 6 vertices each in the middle of the hex edge (#1-#6, #1 is
> North, counting clockwise) and 6 more in the middle of the line connecting
> each of vertices #1-#6 to the center. Vertices #1-#6 will be shared with
> other adjacent hexes. Let's say we have green Y tile (two gently curving
> tracks from S to NW and from S to NE). Connectivity graph for such tile
> will be (2-8,8-10,10-4,6-12,12-10). 10-4 edge represents the bottom of "Y"
> and this ensures that only one of the track segments on this tile can be
> used. This definition method also takes care of defining tiles such as
> yellow and green Toronto from 1856 or Moscow from 1861.
>

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

In general the search for optimal routes work by selecting a route,
> evaluating its value, removing the used edges from the graph and running
> the search again on the remaining graph (with remaining trains). Then
> choosing the "next" route and repeating the process, until the set of
> routes with the highest total value is found. In the route selection
> process there are 3 direction of iteration: "head", "tail" and "branch".
> "Head" and "tail" is extending (by one edge) from the head or from the
> tail (each route starts from the station) and "branch" is replacing last
> added edge with the possible alternative. This guarantees to iterate over
> every possible route (here by route I mean route in graph terms, it's not
> necessarily a valid route in 18xx terms). In practice, I'm using few
> optimizations to eliminate complete scan, but that's probably unimportant
> for non-AI use.
>

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.

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
   - trains that can substitute types of stops (like n+m trains)
   - bonuses given when particular sets of stops are included on the route
   - games that allow a train to run through one fully blocked city, like
   1860
   - games that have choices about stops that give money to the company
   instead of the dividend, like halts in 1860

The route evaluation part needs to be aware of the rules of the specific
> games. Route evaluation logic gets a proposed route as a vector of
> vertices it visits. As a result it gives a value and the vector of
> vertices it has used (this is used for optimization by skipping the routes
> that just an extension from the unused side). In a simple case evaluation
> would be simple - just total values of the best subset of cities and
> towns, but various bonuses make things more complicated. I'm using a bonus
> table containing various bonuses and their requirements. Bonuses can be:
> add extra value to the vertex, multiply value of the vertex, add value to
> the route (for example if 2 specific locations are visited) etc... Bonuses
> can be defined as sets if it's necessary to allow only one bonus from the
> set to be applied. Because of that, the route evaluation algorithm has to
> return updated "bonus usage context". There may be a need to iterate over
> bonus choices (such as not apply some bonus when possible), but I am not
> sure what game has such set of possible bonuses to require it. I haven't
> done such iteration because it would be bad for AI case (because of
> performance), for non-AI case, it's probably not a big issue.
>

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


> Some parts of the route evaluation code might need to be updated for
> specific games, but such updates should not affect the logic for anything
> else. Two types of trains I am aware of that might require more thought
> are hex trains and "N out of M" trains. Essentially, my current assumption
> is that for any route candidate the optimal route use (meaning use of
> trains and bonuses) can always be determined if both head and tail
> vertices are used.
>

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.

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

The first and second scenarios are probably doable today with a brute force
algorithm for 1830-like games, and probably not doable at all for endgames
of more complicated games.

-- 
John A. Tamplin