13

While playing the 18xx games (create routes for trains and try to get the most money with your trains), it sometimes takes a lot of time to find the optimal route for the trains.

Does anybody know if there is any software available to help with this problem?

  • The 1830 computer game will select (the best) routes for you, but it's a single-player game, alas. – PotatoEngineer Nov 6 '12 at 18:23
  • @Paul_Marshall: Actually it does not always select the best routes, I have seen results that could be improved upon but so far only with $20. The algorithm seems to give up after a while and not do an exhaustive search. – Anthon Mar 11 '13 at 7:33
  • 1
    I wonder if this question is similar to the traveling salesman, NP complete section of mathematics. I think i need to look closer at the rules. – user1873 Dec 20 '13 at 19:41
  • @ user1873, i think it is similar to the traveling salesman, however the number of cities is a small constant, thus it can be solved fast. – Cohensius Jul 29 at 19:39
7

Not to my knowledge.

One thing I've done to assist with this problem is to use a pile of D6's of a couple different colors.

Place a D6 on each city of one color to represent your smallest train and work your way up to your largest.

When you are finished, pick up the D6's generating your total run profit as you go.

Towards the end of the game, we usually help each other, as the diesel runs can become quite dramatic as I'm sure you're aware! It just speeds the game along as we don't want one person obsessing over his run for twenty minutes to gain an extra $10.

3

See https://www.reddit.com/r/18XX/comments/9t32gw/1846_route_finder/

The decision problem "Given this particular network, can a diesel (unbounded) train run for at least $X?" is NP-complete.

It's in NP, since the length of a route is bounded by the size of the board and its validity and payoff is easily verifiable.

It's NP-hard by a reduction from Hamiltonian path on square grids. Embed the square grid on a hex board by skewing one axis 60°. Use X-cities for vertices in the input graph and use lots of straights to connect the vertices. Place a station in an arbitrary vertex/city. There's a route worth k×n where k is the per-city dividend and n is the number of cities if and only if there's a Hamiltonian path in the input graph (with the obvious correspondence).

I don't know about hardness for bounded trains, but for practical purposes the train limit is O(1) and the train lengths are also O(1), and most notably the numbers tend to be small(ish).

For example, with 10 cities and a single 6, there are 10 choose 6 = 210 different city sets to try out. You can sort them by dividends and the answer is the first feasible route.

With 10 cities and a 5, there are 252 possibilities. With both a 5 and a 6 that's 210*252 = 52920. Once again, sorting by total dividends and finding the first feasible match should be tolerably fast.

Or maybe you find the highest-paying routes with each train unconstrained by the other, then search through two lists for a compatible match. Say you look through the 6-routes in descending order; then you have to look past the first compatible match, until you get to a 6-route which pays so little that even the best paying 5-route doesn't put you above the best match so far. Then that best match cannot be surpassed, and must be the answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.