[Rails-devel] An all-trains-at-once approach (LONG)

[Jonathan F. <jo...@ya...>]

Here's an idea for 18xx company revenue computation that I have been
kicking around for a while, and never gotten around to trying because I
didn't ever find the time to set up test situations for it (basically
the reason I've only ever lurked on this list).  This is a cleaned-up
transcript of me describing it to the Code Review Bear.
http://sjbdeveloper.blogspot.com/2006/03/teddy-bear-code-reviews.html

Generally speaking, the idea is that instead of calculating all
possible routes for each train and then trying combinations of all the
trains until you find a set that doesn't overlap or conflict, don't
even generate conflicting routes in the first place.

Suppose that we had a data structure which composed into a single
"routing state" object: (a) a pointer to the map being used for route
segment tracing, (b) a pointer to the set of trains being run, and (c)
a route for each train that contains both the revenue points (stations,
towns, off-board, specials) and the track between them (you need this
for conflict clarification, in case there are parallel routes between
two revenue points).

Such an object could be constructed any time any part of a route
computation comes under analysis.  It is not necessary that the map
represent the current state of play, so that you can evaluate future
tile placement or theoretical runs with no enemy tokens.  It is not
necessary that the set of trains represent the actual holding of a
company, so that you can compute destination runs, "borrowed diesel"
operations, or testing for whether a company even has a legal run or
route to a tile lay.  It is not necessary that the train->route
assignment represent a "good" run, so that it can represent an
intermediate point on a search.

I propose that a fundamental operation on this object is "what are all
the possible ways that any one train can have its route extended by one
route segment?"  This operation takes into account all route segments
that are precluded due to already being obstructed by other existing
routes, being obstructed by enemy tokens, or by not being appropriate
for the type of train (narrow-gauge or off-board), and does not include
those as possible results.  It DOES include any extensions that would
not be legal as they stand (not all connected [1860], or have a route
ending in a village [1829]), because they might be extended further to
eventually come to be legal states after all, and can't be discounted.

This state object together with the operator to generate route
extensions satisfy the state space conditions for generalized search
algorithms, e.g. as shown in Russel & Norvig, 1995, pp. 72ff.

Breadth-first search would run like this:

for each possible assignment of trains to tokens {
  create a route state where each train has a 0-length "route" at its
  token and put that state on the queue;
  // Example: 3 2-trains and 3 tokens would have 27 starting states.
}

bestState = null;
while the route state queue is not empty {
  pull routeStateParent off the queue;
  routeStateChildren = routeStateParent.getRouteExtensions();

  if ( routeStateChildren.isEmpty() ) {
    // Parent can't be extended any further, due to trains being out of
    // movement points or being blocked.
    if ( routeStateParent.revenue() <= bestState.revenue() ) {
      // In some games you might want to hang on to less-than-best if
      // there are other features, like halts or exploration.
    }
    else if ( ! routeStateParent.runIsLegal() ) {
      // This is where you kick out a run for game-rule reasons.  If
the
      // reason is "all trains still have 0-length routes", then keep
      // track of the possibility that this company may not be required
      // to own trains at all.
    }
    else {
      bestState = routeStateParent;
    }
  }
  else {
    for each child {
      // It MIGHT be possible to prune here, if it's possible to figure
      // out that there's NO possible good extension of this child,
      // e.g. if a 2038 ship doesn't have enough movement left to reach
      // a base.
      enqueue the child;
    }
  }
}
return bestState;

[Note: At the point where it might be possible to prune, it also might
be possible to determine that this child is equivalent to another state
already queued.  For example, a single train going from token T1 to
token T2 is equivalent to one going the other way, so you wouldn't have
to put the second one on the queue, but actually figuring this out
might be more expensive than just living with it.]

---

I think we all understand that the best route for a long train is not
necessarily equal to the best route for a shorter train plus however
many additional revenue points it can reach, but here's a test case
that makes this really clear:

  20 ---- 20T ---- 10 ---- 10 ---- 50
           \
            \
             -- 10 ---- 10 ---- 50

(The company's only token is at station "T".)

Trains         Best Revenue
2              40
3              50
4              90 (NOT 60)
2,2            70
2,3            80
3,3            90
4,3            140 (NOT 100)
4,4            180 (NOT 150)

This is basically the reason that route-finding does not appear to have
a simple recursive/memoization/dynamic-programming solution.

---

What does this mean in terms of the hex-level API?

I think it's important to use the API to raise the focus from the
individually conflicting arcs on individual tiles to conflicts between
"route segment"s, which is the term the players (and game rule coders)
will be thinking in.  I've deliberately left the term a bit fuzzy, but
I think it should mean something like "all of the track arcs, across
arbitrary many tiles, that connect one revenue/bonus/gamestate map
feature to the next one, in any possible train route according to the
rules of this game".

For 1830-ish games, this is rather simply following the track from one
city/village to the next.

For 1860-ish games, which allow skipping of villages/halts, there are
city-to-village route segments that conflict with
city-to-city-beyond-that-village route segments along the same track.

For 1844-ish games, where some trains count hexes rather than stations,
one route segment may take more than one "point" of capacity, and that
will affect future route extension calculations for that train.

For 2038, there is a choice of making every route segment be "one
movement point" or making a route segment be "however far to the next
mine you are actually going to pick up from".  If you were going to
list every one in the entire map that might be memory-intensive, but
you probably never need to do that since the conflictsWith() check is
so simple.

It might be desirable to make it so that the decision of whether to
precompute the list of route segments every time the map changes is up
to the individual game, not baked into the core algorithm.

In any case, it is clear to me that a RouteSegment class, far from
being a burden to maintain as an "intermediate" data structure,
represents a key point of "impedance matching" to bridge overall
thinking from the hex level to the route level.

So, having thought this far, here is some more pseudocode:

getRouteExtensions()
{
  for each train in the routeState that has movement remaining {
    for each "live" end of the current train route {
      // Ends might not be live if they've gone off-board or have
      // otherwise dead-ended in this routeState, including enemy
      // tokens.  2038 ships always only have one live end.
      for each routeSegment from this endpoint {
        if (game-specific reason this train can't use this segment) {
          // This is the check for H-trains going beyond their movement
          // limit [1844], or for going to a different city on a tile
          // you've visited [1829], or for a segment that skips
villages
          // when used with a train that actually can't [1860] or
          // vice-versa [18Scan].
        }
        else if (routeSegment.conflictsWith(routeState.allSegments()))
{
          // This test is where the bitvectors John is talking about
          // could come in handy.
        }
        else {
          // Good enough to try.
          copyState = routeState.copy();
          extend this train's route in copyState by routeSegment;
          record movement usage for this train; // Might be zero.
          add copyState to resultSet;
        }
      }
    }
  }
  return resultSet;
}

Hm, after all this, I see I haven't really handled double-heading, but
I think that issue can be handled in the representation of the train
set.

It's also possible that rather than having the map and the trainSet be
in the routeState, to save time on object copying, that they would be
"global" to the entire search tree.  There would also have to be a
RouteResult object type that did contain all these details, for
representing the result of route searching to the rest of the program.

Anyway, I enjoyed thinking about this, so I hope it helps.

-- Jonathan