Re: [Rails-devel] Route calculation: Train length heuristic

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Erik,
it is already implemented (in a local branch, otherwise I would have not been 
able to report running times). 

However I want to run some more tests before pushing it.

The answer to your question is no:I it does not require a train config 
attribute as the train domination is implemented as a Comparator (method) in 
the NetworkTrain class.

So the train conditions could be checked automatically, however there can be 
certain conditions in specific games that break the heuristic, for example 
bonuses that are only valid for specific trains (e.g. if in 18AL players 
decide to have the director assign the named train themselves).

As the heuristic is only necessary in games with very long trains (as in 1830, 
1856, 1870) I want to be on the safe side and only activate the heuristic in 
those games after some tests by providing a global switch as an attribute to 
the RevenueManager in game.xml.

Stefan

On Tuesday, August 09, 2011 11:14:47 am Erik Vos wrote:
> Stefan,
> 
> Do you plan to implement this heuristic in Rails?
> Would it require a new TrainType config attribute, like <TrainType
> name="6+6" ... dominates="6,5+5"/>?
> 
> Erik.
> 
> > -----Original Message-----
> > From: Stefan Frey [mailto:ste...@we...]
> > Sent: Tuesday, August 09, 2011 7:03 AM
> > To: Development list for Rails: an 18xx game
> > Subject: [Rails-devel] Route calculation: Train length heuristic
> > 
> > A year ago I suggested another heuristic to improve the speed of the
> > revenue calculation.
> > 
> > The idea is to use what 1830 players automatically do:
> > If you calculate a run for a 4 and a 3 train, you already know that you
> 
> will end
> 
> > up with a longer route (more stations) for the 4 train and a shorter
> > route
> 
> for
> 
> > the 3 train. Similar for running a Diesel and a 5 train.
> > 
> > However this knowledge is not taken into account by the current
> > algorithm. Things unfortunately are not that easy for all 18xx as it are
> > in 1830. For example in 1835 one cannot tell this ex-ante for a
> > combination of a
> 
> 5+5
> 
> > and a 6 train. That in fact is one the reasons why calculating the
> 
> Preussian
> 
> > routes is not an easy task.
> > 
> > Another exceptions are: If trains score differently for the same route
> > (Express (xE) and Double (xD) trains) or if hex trains run jointly with
> 
> standard
> 
> > trains.
> > 
> > ** The formal definition of train domination:
> > 
> > If the "better" train A can run all routes that the "weaker" train B and
> 
> train A
> 
> > scores identical revenue on all routes as B, then I define that train A
> > dominates train B.
> > 
> > If A dominates B I write this as A>B, otherwise the trains are either
> 
> identical
> 
> > (A=B) or neither dominates (A<>B).
> > 
> > If train A dominates train B, the length of the route of train A will
> 
> always be
> 
> > longer or at least equally long as that of train B.
> > (Length of the route is the number of stations scored.)
> > 
> > ** Examples should make this clearer.
> > 
> > In 1830 it is easy:  D>6>5>4>3>2
> > 
> > In 1835 it is
> > 6+6 > 5+5 > 4+4 > 3+3 > 2+2
> > 6 > 5 > 4 > 3 > 2
> > 6+6 > 6, 5+5 > 5, 4 +4 > 4, 3+3 > 3, 2+2 > 2
> > 6 > 3+3, 4 > 2+2
> > But for example: 6 <> 5+5, 5 <> 3+3 etc.
> > 
> > ** Implementation
> > The implementation is pretty straight forward and only requires a few
> 
> lines
> 
> > of code in the revenue calculator. The major change is to order the
> > trains
> 
> by
> 
> > the criteria "train domination". Then the calculator assigns the initial
> 
> train
> 
> > length for the dominated train not with the maximum length of that train,
> > but with the (current) route length of the dominating train. This ensures
> 
> that
> 
> > the dominating train will always have the longer route assigned.
> > 
> > ** Speed improvement
> > I did run the scenarios of Aliza Panitz 1856 triple Diesel of CGR
> 
> scenarios and
> 
> > came to the following running times (more statistics on number of routes
> > evaluated and when the best solution was found see below).
> > 
> > For the simpler network (A) running times decrease from around 5 minutes
> > to
> > 3.5 minutes (my CPU is more powerful than Alizas ...).
> > For the extensive network (B) running times decrease from around 1 hour
> > to around 30 minutes.
> > 
> > Overall the improvement it seems that the speed is improved by around 50%
> > to 200%, so time to wait is down by 33% to 66%, which is not bad.
> > 
> > But as it can be clearly seen by comparison with a double Diesel
> > scenarios
> 
> the
> 
> > exponential characteristic of the algorithm is still very clear.
> > 
> > So I still hope that John Tamplin can give some hints on his lost flow
> 
> algorithm
> 
> > for those who want to run triple Diesel more often.
> > 
> > Stefan
> > 
> > ** Stats
> > 
> > => Aliza Scenario 1856 A:
> > 31 vertices with 41 edges
> > 10 startvertices
> > 
> > Values:
> > Single D: 700
> > Double D: 920
> > Triple D: 1120
> > 
> > Single D: 0 second / 6.2k Evaluations, 6.2k Predictions
> > 
> > Without dominant trains:
> > Double D: 3 seconds / 1.3M Evaluations, 1.4M Predictions Triple D: 290
> > seconds / 114.9M Evaluations, 129.5M Predictions
> > (Solution: 25 seconds / 13.4M Evaluations, 14.7M Predictions)
> > 
> > With dominant trains:
> > Double D: 1 second / 323k Evaluations, 385k Predictions Triple D: 206
> 
> seconds
> 
> > / 87.4M Evaluations, 98.0M Predictions
> > (Solution: 20 seconds / 9.1M Evaluations, 10.0M Predictions)
> > 
> > => Aliza Scenario 1856 B:
> > 34 vertices with 50 edges
> > 10 startvertices
> > 
> > Values:
> > Single D: 790
> > Double D: 1280
> > Triple D: 1440
> > 
> > Single D: 0 second / 53.3k Evaluations, 53.3k Predictions
> > 
> > Without dominant trains:
> > Double D: 12 seconds / 4.8M Evaluations, 5.1M Predictions Triple D: 3551
> > seconds / 1473M Evaluations, 1709M Predictions
> > (Solution: 41 seconds / 16.9M Evaluations, 17.7M Predictions)
> > 
> > With dominant trains:
> > Double D: 5 seconds / 1.9M Evaluations, 2.3M Predictions Triple D: 1926
> > seconds / 832M Evaluations, 962M Predictions
> > (Solution: 27 seconds / 11.7M Evaluations, 12.3M Predictions)
> > 
> > => Scenario 1870:
> > This is the route network used for testing a year ago,
> > 
> > 23 vertices with 57 edges
> > 1 startvertex
> > 
> > Values:
> > Single 12: 380
> > Double 12: 690
> > Triple 12: 820
> > 
> > Single 12: 0 second / 11.5k Evaluations, 23.7k Predictions
> > 
> > Without dominant trains:
> > Double 12: 4 seconds / 1.4M Evaluations, 1.9M Predictions Triple 12: 104
> > seconds / 23.4M Evaluations, 61.6M Predictions
> > (Solution: 13 seconds / 3.2M Evaluations, 6.2M Predictions)
> > 
> > With dominant trains:
> > Double 12: 4 seconds / 1.2M Evaluations, 1.7M Predictions Triple 12: 49
> > seconds / 8.1M Evaluations, 30.0M Predictions
> > (Solution: 16 seconds / 3.0M Evaluations, 9.3M Predictions)
> 
> ---------------------------------------------------------------------------
> - --
> 
> > uberSVN's rich system and user administration capabilities and model
> > configuration take the hassle out of deploying and managing Subversion
> > and the tools developers use with it. Learn more about uberSVN and get a
> > free download at:  http://p.sf.net/sfu/wandisco-dev2dev
> > _______________________________________________
> > Rails-devel mailing list
> > Rai...@li...
> > https://lists.sourceforge.net/lists/listinfo/rails-devel
> 
> ---------------------------------------------------------------------------
> --- uberSVN's rich system and user administration capabilities and model
> configuration take the hassle out of deploying and managing Subversion and
> the tools developers use with it. Learn more about uberSVN and get a free
> download at:  http://p.sf.net/sfu/wandisco-dev2dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel