Re: [Rails-devel] Improved revenue prediction / different scenario

[Stefan F. (web.de) <ste...@we...>]

Alex, see comments below:

On Monday 17 May 2010 01:37:17 alexti wrote:
> Stefan,
>
> I think you iterate in some completely different manner. I am still unsure
> what you do when you encounter a "branch" during the iteration. For
> example station is connected to the city with 6 exits, so when you
> consider the route from the station to this city it can continue in 5
> different directions. How do you iterate over these directions?
>

I do not exactly understand your definition of "station" and "city" above 
(maybe related to the fact that there is some confusing usage of station and  
city in Rails as well).

For the revenue calculator station is a vertex that (usually) counts for the 
train lengths and there are subtypes major (cities and equivalents) and minor 
(towns and equivalents).

I assume you mean what happens when a city/major station is encountered, which 
is connected to all sides of the hex:

The branching is easy, I will try all exits in the ordering of the neighbor 
vertex id in a depth-first manner. Actually I check the incoming exit to, but 
this will fail as the required edge is used already.

> This is an interesting idea. This operation would be equivalent to my
> "evaluation". I would imagine it's faster when you are "extending" your
> route, but when you switch between "branches" you would have to "undo" by
> removing values added in the old branch. I wonder if it's faster that
> recomputing from scratch every time...

Exactly: All encounter vertex and travel edge operations have equivalent 
un-encounter and un-travel equivalents. In fact the encounter method has a
simple boolean switch to indicate arrival/departure.
If that is faster, I do not know, most likely it will depend on the scenario.
>
> My run time is currently divided approximately 50-50 between the train
> revenue calculation and everything else (iterating over possible routes,
> including validity of those routes etc). Where do you spend most of the
> time?

I have not done any profiling so far. I am more than satisfied with the speed 
so far and currently focus on the integration of the specific features for 
the implemented games. And before profiling I would add the two-phase 
approach, that works pretty well for you.  And my target is not to add any AI 
type, thus there is no need to consider what-if scenarios.

In fact I have still one idea to improve the tree cutting especially for 
train-sets: My working title for that is train dominance. It formalizes what 
a human player usually does. Take the example you search for optimal routes 
for an 8 and a 10 train: You would never consider the combination where the 8 
trains runs a longer route than the 10 train. In fact you look for the best 
combination of a route with maximum length of 8 and one with maximum length 
of 10. Thus there is no need to evaluate any route combination, where the 10 
train runs for less stations than the 8. I still do that currently. 
You could also define that the latter 8 has to dominate the former 8.
That would be pretty easy to check, but...

What makes the things a little more difficult is the fact to consider those 
cases, where the assumption above is not valid or not that easy:

* A 5 train is not dominant to a 3+3, nor is the 3+3 dominant to the 5. But at 
least a 8 dominates the 3+3 and a 3+3 dominates the 3.
* Trains that ignore minors, are not dominant to non-ignoring trains and vice 
versa.
* Trains with an increased scoring factor, can never be dominated by longer 
trains with a lower scoring factor. Thus neither a 10 train dominates the 
doubling 4, nor vice versa.
* Train-specific bonuses makes all dominance assumptions for that train 
invalid. 

But it might be still worthwile to look into, as it could potentially promise 
a substantial speed increase for cases, where the dominance relation is well 
defined.

Stefan