Re: [Rails-devel] Implementation details for revenue calculation

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

Alex,
take your time: This is something to have fun.

On the issue of implementing AI:

I think this is not so much an issue of coding in Java or something else, but 
having good ideas, sketching out a prototype and/or defining the interfaces 
to the actual moderator program. A first question would be if the AI should a 
simplified/abstracted API to query the current state of the game and 
communicate its actions or should work directly with the Rails 
objects/actions. But if you choose the first approach you could program 
against an abstract API and then later an intermediate layer could facilitate 
the communication between the AI and the rails program.

Thus I agree with Brett, that you are invited to add to the project. At least 
I would already be interested to have a look at your current implemetation 
and run tests on it. Most likely no one would complain (???), if you commit 
your code or your designs/ideas to the Rails repo at some separate directory 
(maybe Brett could suggest a good location).

On the issue of the phase two route ordering:

Maybe I have not put down things clearly enough.

Thus repeating the main finding:
For the two phase I first select "cheap" (few overlaps) routes first 
(regardless of the value of the vertex at the end) and only as a second 
criteria to use the value of the vertex. This allows to find quickly a good 
solution, at least for those scenarios we have defined. In consequence this 
allows to cut the search tree earlier and decreases search time.

I suspect that you still assume that I use the route length only as secondary 
criteria.

An example avoids any ambiguity, see below.

Stefan

Assume you start at vertex A and there are two routes to vertex B (value 40) 
which have costs (overlaps) of 2 and 4, and two routes to vertex C (value 10) 
with costs of 0 and 2.

Then from A the routes are selected in this sequence:
1) route to C (10) with cost 0
2) route to B (40) with cost 2
3) route to C (10) with cost 2
4) route to B (40) with cost 4

Initially I only sorted on value, with undefined ordering of the routes to the 
same vertex:
1) or 2) route to B (40) with cost 2
1) or 2) route to B (40) with cost 4
3) or 4) route to C (10) with cost 0
3) or 4) route to C (10) with cost 2
As I retrieved the edges from a HashSet, the ordering really changed between 
invocations, even I started the identical scenario, implying the different 
run times. I assume that in your implementation, you do not explicitly define 
an ordering, but running the same scenario still had the same ordering 
implied (if you want to test that, try an explicit randomization).

The run times below for the value ordering use the route costs as a second 
criteria, thus having well defined run times, but worse compared to the sort 
on the route costs first.
Ordering is now:
1) route to B (40) with cost 2
1) route to B (40) with cost 4
3) route to C (10) with cost 0
4) route to C (10) with cost 2



On Wednesday 09 June 2010 03:16:53 alexti wrote:
> Stefan,
>
> My comments are inline
>
> > I have a first phase two prototype working. In fact it was not a too
> > difficult
> > task, as I only create a multigraph with new edges, that define the new
> > routes.
> >
> > Then I define "EdgeTravelSets", which define edges that are mutually
> > exclusive. This is tracked by the calculator using reference counters,
> > as each
> > edge might be excluded by several others.
>
> I'm keeping a vector of exclusions for each edge. I haven't investigated
> what approach is more efficient. In the testcases I ran I've never seen
> this being a bottleneck, so my guess is that the storage method is
> probably unimportant for performance.
>
> > The first results are promising so far and I believe I found the cause
> > for the
> > difference in number of evaluations compared to your implementation.
> > The main issue is that on a two phase graph the selection of neighbors is
> > different to the original one (by definition).
> >
> > The effect was that the search for the 4-train set (8, 5+5, 4D, 6E) took
> > between 30 - 140 seconds (compared to 70 seconds without).
>
> What did the time depend on? I always had very stable times for any
> scenario we've tried. For the example above it was ~30 seconds, perhaps
> with 1 second spread.
>
> > At first glance it was amazing that the run time did strongly vary and
> > the
> > fact that the best  route is found remarkebly late in the process sheds
> > more
> > light, why you believe that my revenue predicitor is of the magic type.
> >
> > I still sort the neighbors by value, but the ordering of the (potentially
> > multiple) routes to them is random, as they are retrieved from a HashSet.
> > The ordering of routes is important for the revenue predictor to work
> > well.
> > Finding a good solution quick is important.
>
> This is a very good point - I choose edge iteration order more or less
> randomly - I don't use any criteria to sort them. I kind of thought of
> trying to make more intelligent choice, but didn't come up with any good
> criterion.
>
> > Without phase two optimization, the choice to visit the most valuable
> > (neighboring) vertex is clearly the optimal approach, as each neigbor is
> > one
> > track piece away. Thus the "costs" of each neighbor is identical.
> >
> > If you have done a phase two optimization, the most valuable vertex can
> > be
> > quite far away, thus blocking several track pieces at the same time and
> > ruling out a lot of other connections. Thus for phase two the cost of
> > each
> > neighboring vertex vary substantially. Accordingly the cost has to be
> > considered: The number of edges excluded must be an additional important
> > criteria to select the routes.
> >
> > Take an example:
> > Is it better to run for a nearby 20 vertex (which excludes one other
> > route) or
> > the far away 50 vertex (which excludes three other routes and potentially
> > bypasses the 10 vertex). There is no clear answer, but our preliminary
> > results and my experiences with 18xx routes, implies that it is usually
> > better to go for nearby stations first and save track first.
> >
> > Thus two approaches are possible:
> > * Use Nb of edges excluded as a first criteria, value as a second only.
> > (Thus
> > minimize costs first, then maximize revenue).
> > In that case you would run to the 20 first.
> >
> > * Or combine the two and use something like cost-modified value
> > approach. For
> > example choose the ratio between value and number of routes excluded
> > (including the route selected).
> > In that case you would run to the 50 first. (20/2 = 10, 50/4 = 12.5)
> >
> > I have implemented the ordering based on the first idea (cost-based) and
> > the
> > time is now stable an 24 seconds run for the 4 train set, thus running
> > time
> > decreased by factor 3.
>
> I like your idea, I think it's a good criterion. My intuitive feeling is
> that (1) is a better approach. I agree that in normal 18xx games the
> routes follow specific pattern - generally people try to connect valuable
> location by the shortest route and the long scenic routes between two
> cities/towns is usually a sign of a well blocked map :)
>
> > Number of evaluations one pass (70 seconds)
> > 480961 evaluations, 2935133 predictions and 8828871 edges travelled.
> >
> > Number of evalutaions two pass with cost ordering (24 seconds)
> > 475533 evaluations, 2910152 predictions and 2841394 edges travelled
> >
> > Number of evaluations two pass with value ordering (81 seconds)
> > 1421981 evaluations, 7302480 predictions and 8297888 edges travelled
> >
> > It seems that edge travelling is the time limiting factor in my
> > approach, but
> > that is not surprising as evaluation and prediction is pretty cheap
> > given the
> > continuous update of the run values.
>
> I want to try to use your approach to the edge ordering, but currently I
> took my implementation apart, because I wanted to restore vector
> computation functionality (which I broke when I added predictor) and this
> proves to be quite challenging (and, besides, the summer finally came here
>
> :) )
> :
> > To compare the validity of my approach, this are my figures about
> > vertices and
> > edges:
> >
> > In scenario A the phase two graph consists of 23 vertices and 57
> > edges/routes.
> > There are several routes that overlap with 9 other routes (J3.1 -> J9.1,
> > K4.1 -> J3.1,J9.1 -> M2.1,K4.1 -> M2.1).
> > In scenario B the numbers are 20 vertices and 151 edges/routes.
> > The route that overlaps with most others is E8->D5 (over 19 hexes) that
> > shares
> > track with 111 other routes.
>
> I think I had the same numbers.
>
> Alex.
>
> ---------------------------------------------------------------------------
>--- ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel