1828.games: autorouting doesn't seem to understand 3+D doubling

[dfannius]

JSON: https://gist.github.com/dfannius/0e50c776fdd76bc78cd43a76dd5b6956

If NYH clicks Auto, they get their 5T running a three-stop route for $70, instead of a 3+D running the same route for $140.

[scottredracecar]

Similar problem as #6597. Autorouter probably works fine, but doesn't handle scenarios where there are fewer routes than trains.

[dfannius]

I'm not familiar with the autorouter code, but I added a bit of logging to try to see what is going on. We seem to lose some information in js_evaluate_combos. sorted_routes has 4 routes (G23-F24-E23 by a 5T worth 70, G23-F24 by a 5T worth 50, G23-F24-E23 by 3+D worth 140, and G23-F24 by 3+D worth 100); so far so good. But possibilities, the list of list of routes returned by js_evaluate_combos when we pass in sorted_routes, contains only the G23-F24-E23 by a 5T worth 70. @JoeB989, does that point to something that can be easily fixed without causing the computation in other scenarios to blow up?

[JoeB989]

Routes passed to js_evaluate_combos have been validated as standalone routes by Route.revenue (suppress_check_other: true). Route combos returned by js_evaluate_combos have been validated by Game.check_other for all routes in the combo. Any combo that Raises in is_valid_combo() is rejected. So set a breakpoint or add a puts in the catch(err) there to see the exception that causes the combo to be rejected.

[JoeB989]

My thought is that G1828:check_other is rejecting combos it shouldn't, or perhaps Route.revenue isn't being computed properly.

[JoeB989]

Also, the auto-router doesn't currently allow overlapping routes for titles that support that.

[JoeB989]

Oh, it's a degenerate case. Yes I think scott is right, it's because of the train order. There is an implicit assumption that all trains that run the same route deliver the same revenue. To your original question:

does that point to something that can be easily fixed without causing the computation in other scenarios to blow up

Maybe so ;) Sorting the trains by stops or something appropriate (like cost) should solve this particular problem. But will other games' rules break in that case? Maybe shorter/cheaper trains will deliver better revenue in certain scenarios in some games.

So the correct solution is likely more complex and needs deeper thought. The problem to solve is, what if starting combos with the first train doesn't yield the best revenue? Should it make an evaluate-combos pass starting with each train? But if there are 3 trains, would you also need to try both 2nd-trains after all three 1st-trains?

[JoeB989]

BTW a workaround is available: manually route the misbehaving train then auto-route the rest.

[JoeB989]

Thinking about it more, it may only happen in the degenerate case - not enough routes for all trains. So I think sorting trains in length order is reasonable. I actually used to do this at line 21 (sorting by cost since stops was unreliable), but since I couldn't remember why I preferred that it didn't survive code review. Let me know if you want me to make the change, otherwise be my guest.

[dfannius]

There are other titles where the revenue of a route depends on the train (some trains double like this 3+D, or have different rules for counting dits) so it would be nice if there's a general solution. sorted_routes contains all the revenue information, so in this case we do know (in principle) going in that the 3+D is "better" than the 5 for the same route. I do understand not wanting to try all n! train orderings.

If we wanted to be more brute-force I think we could even determine without too much overhead that two trains are equivalent as far as their route revenues go (just take the intersection of their routes and compare revenues) and fall back to the (now proven) all-routes-are-equal assumption almost all of the time while handling the more general case (maybe with a heuristic) when necessary.

I'm not sure what it means to sort trains by length order. We would always start by trying to route the 5 in this case, or the 3+D? I'm not sure that train length is generally a good proxy for revenue (given a route).

(I have some combinatorial optimization background but I don't know the auto-routing algorithm well, so forgive anything above that doesn't make sense for this problem.)

[JoeB989]

Yes, maybe a better approach would be to scan in route order rather than train order. That would be a disruptive change to the current algorithm :) My preference would be to solve the cases we know about (this and #6597) simply, without a major redesign. And save the redesign for a time when we want to handle trains that can share routes.

The simple immediate solution I have in mind is something like this at line 21:

trains = @game.route_trains(corporation).sort_by(&-:cost)

But if you want to work on a different combinatorial design that addresses this plus shared routes, that would be cool too

[dfannius]

My preference would be to solve the cases we know about (this and https://github.com/tobymao/18xx/issues/6597) simply, without a major redesign. And save the redesign for a time when we want to handle trains that can share routes.

That sounds great to me.