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

[alexti <al...@sh...>]

Stefan,

On Tue, 18 May 2010 16:05:27 -0600, Stefan Frey (web.de)  
<ste...@we...> wrote:

> 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).
By "stations" I meant the station markers (owned by companies). I thought  
it's more or less standard term (but now I realize that it might be just a  
local dialect). By "city" I meant cities and towns - basically any vertex  
with non-zero value.

>
> 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.
I do the same, but when you reach dead-end, how do you remember what  
branch (and from what vertex) to try next?

>> 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.
I'm sure it's possible to construct scenarios when one method or another  
will be faster. I was wondering if one method is typically better than  
another in common scenarios. Btw, how do you deal with "exclusive" bonuses  
in this scenarios (for example, train chits in 18AL)?

>>
>> 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.
I agree in principle, but I suspect that our current prediction mechanism  
already eliminate most of such cases. If you used 10 train for a short  
route, there will be only so many ways to achieve the threshold with the  
remaining trains.

I am also curious how much 2-phased approach would help your  
implementation - with your magic predictor you don't seem to spend much  
time scanning the routes anyway :)

Alex.

>
> Stefan
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/