rails-devel

[Rails-devel] Route calculation for huge runs

[Aliza P. <ali...@gm...>]

(Note:  my example is a what-if run-forward of a current PbeM game.
James, Jevon, Jerry, Breno, Scott, please go away.)



.

.



Rails 1.4.1, 1856, CGR running 3 Diesels. (This is not completely
absurd -- my plausible choices for the CGR in this game are 5,6; D,5;
and D,D,D.  The money doesn't work out right for D,D.  This is a very
odd game where the CGR formed with 4,5,6, and ten excellent tokens)

At first, run calculations were taking 15-20 minutes on a T60 laptop
running Windows XP.  Now, though, I've got a calculation that's been
running for well over an hour, taking 45-55% of my CPU the whole time.
The map isn't that much more developed! [added - it finally completed.
 $1440 per 10% share.]

Earlier, I was all ready to file a Rails bug because I could clearly
see a better route than what was displayed, but I stepped away from my
computer and when I came back, a better run was shown instead.  So,
one simple request:  when Rails is still calculating a run, there
should be a note on the screen saying something like "route
calculation in progress."  (Screen shot attached.  Even I can quickly
see that the light blue train should run towards the WGB tokens for an
extra $60 on the run, and in fact Rails eventually did $10 or $20
better than that.)

The next thing is that I'd like to know what was autocalculated versus
hand-entered.  A note in the logfile saying what the calculated run
was would be very useful. (Yes, I could go back in the history and
look for myself, but that's not always feasible.)

Finally, any interrupt between calculating a run and entering it
restarts the calculation -- even things like saving the file or
entering the destination of another company.  Highly annoying, though
not quite a bug.

Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Sat, Mar 12, 2011 at 4:02 PM, Aliza Panitz <ali...@gm...>wrote:

> Rails 1.4.1, 1856, CGR running 3 Diesels. (This is not completely
> absurd -- my plausible choices for the CGR in this game are 5,6; D,5;
> and D,D,D.  The money doesn't work out right for D,D.  This is a very
> odd game where the CGR formed with 4,5,6, and ten excellent tokens)
>
> At first, run calculations were taking 15-20 minutes on a T60 laptop
> running Windows XP.  Now, though, I've got a calculation that's been
> running for well over an hour, taking 45-55% of my CPU the whole time.
> The map isn't that much more developed! [added - it finally completed.
>  $1440 per 10% share.]
>
> Earlier, I was all ready to file a Rails bug because I could clearly
> see a better route than what was displayed, but I stepped away from my
> computer and when I came back, a better run was shown instead.  So,
> one simple request:  when Rails is still calculating a run, there
> should be a note on the screen saying something like "route
> calculation in progress."  (Screen shot attached.  Even I can quickly
> see that the light blue train should run towards the WGB tokens for an
> extra $60 on the run, and in fact Rails eventually did $10 or $20
> better than that.)
>
> The next thing is that I'd like to know what was autocalculated versus
> hand-entered.  A note in the logfile saying what the calculated run
> was would be very useful. (Yes, I could go back in the history and
> look for myself, but that's not always feasible.)
>
> Finally, any interrupt between calculating a run and entering it
> restarts the calculation -- even things like saving the file or
> entering the destination of another company.  Highly annoying, though
> not quite a bug.
>

This is a known issue with the current brute-force algorithm -- it was
brought up when it was being implemented.  Basically, when the number of
trains and stops goes up, the number of possible routes goes up
exponentially.

A long, long time ago, I implemented route calculation by transforming the
problem to a flow graph and running the max-flow/min-cut algorithm on it
(sorry, I no longer have this code), which avoids exponential time.
 However, I don't know how to adapt this to all the exotic rules that have
been added since then -- there may not be any better approach than brute
force to make sure no solutions are missed.

Perhaps the best approach is to take advantage of multiple cores by sharding
testing alternate routes into threads and count on hardware getting faster
:).

-- 
John A. Tamplin

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

As mentioned earlier I had started making my way down to open issues in my 
Rails mail archive, so this mail is from March 2011.

The scenario Aliza mentions is pretty extreme (three D trains for a company 
with 10 tokens) and to my knowledge this is only possible for 1856. 
So in fact my surprise was on the positive side that Rails DID actually came 
up with the final result instead of running forever.

In my tests a pure brute-force search usually already  does not finish in 
reasonable time for double D combinations on similar networks. I will focus on 
the technical details in a response to John Tamplin's reply.

This mail is a reply to Aliza's suggestions on improving the UI behavior.

> when Rails is still calculating a run, there
> should be a note on the screen saying something like "route
> calculation in progress."

This can be done. However I would only display the message if a minimum time 
elapsed (for example 5 seconds).

> The next thing is that I'd like to know what was autocalculated versus
> hand-entered.  A note in the logfile saying what the calculated run
> was would be very useful. (Yes, I could go back in the history and
> look for myself, but that's not always feasible.)

Adding this information is possible. 
(I understand "logfile" here as the game report shown in the UI and not the 
18xx.log which is written by Rails, where this information and many more is 
already included).

However I am strongly interested in your (and all others) experience if and 
how often the experienced that situation: 

As the current algorithm (in theory) guarantees the correct solution, any 
deviation between the calculated result and the correct result should be filed 
as a bug with according save file.

Bugs (especially for example in tile definitions and the code for 
initialization and optimization before the revenue calculation, which exceeds 
the code for the core algorithm by factor 10 at least) can never be ruled out, 
so please report any observed differences.

> Finally, any interrupt between calculating a run and entering it
> restarts the calculation -- even things like saving the file or
> entering the destination of another company.  Highly annoying, though
> not quite a bug.

I considered this solution: However the interruption could have changed 
anything that might have impact on the result.
For example: undo, place token. Thus I decided to restart in any case of 
interruption to be on the safe side.

Stefan

The complete mail:

On Saturday, March 12, 2011 10:02:04 pm Aliza Panitz wrote:
> (Note:  my example is a what-if run-forward of a current PbeM game.
> James, Jevon, Jerry, Breno, Scott, please go away.)
> 
> Rails 1.4.1, 1856, CGR running 3 Diesels. (This is not completely
> absurd -- my plausible choices for the CGR in this game are 5,6; D,5;
> and D,D,D.  The money doesn't work out right for D,D.  This is a very
> odd game where the CGR formed with 4,5,6, and ten excellent tokens)
> 
> At first, run calculations were taking 15-20 minutes on a T60 laptop
> running Windows XP.  Now, though, I've got a calculation that's been
> running for well over an hour, taking 45-55% of my CPU the whole time.
> The map isn't that much more developed! [added - it finally completed.
>  $1440 per 10% share.]
> 
> Earlier, I was all ready to file a Rails bug because I could clearly
> see a better route than what was displayed, but I stepped away from my
> computer and when I came back, a better run was shown instead.  So,
> one simple request:  when Rails is still calculating a run, there
> should be a note on the screen saying something like "route
> calculation in progress."  (Screen shot attached.  Even I can quickly
> see that the light blue train should run towards the WGB tokens for an
> extra $60 on the run, and in fact Rails eventually did $10 or $20
> better than that.)
> 
> The next thing is that I'd like to know what was autocalculated versus
> hand-entered.  A note in the logfile saying what the calculated run
> was would be very useful. (Yes, I could go back in the history and
> look for myself, but that's not always feasible.)
> 
> Finally, any interrupt between calculating a run and entering it
> restarts the calculation -- even things like saving the file or
> entering the destination of another company.  Highly annoying, though
> not quite a bug.

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

This is a reply to the response of John Tamplin on Aliza's scenario.

On Monday, March 14, 2011 01:02:33 am John A. Tamplin wrote:
> 
> This is a known issue with the current brute-force algorithm -- it was
> brought up when it was being implemented.  Basically, when the number of
> trains and stops goes up, the number of possible routes goes up
> exponentially.

I agree.

The current implementation is a search-tree pruning method on an optimized 
multigraph. The heuristic used for tree-pruning is revenue prediction: Is it 
still possible with the following trains/stops to exceed the already found 
best solution?).

But even if the heuristic speeds up the search drastically, it shares the 
asymptotic behavior of brute force  that search time increases exponentially 
with trains and vertices.

> A long, long time ago, I implemented route calculation by transforming the
> problem to a flow graph and running the max-flow/min-cut algorithm on it
> (sorry, I no longer have this code), which avoids exponential time.

I think I can imagine how you approached this: You define the revenue of each 
node as negative cost of an edge inside the node and then minimize the costs 
(thus maximizing revenue) of the trains treated as flow.

Even if you do not have the code any longer, can you still remember how you 
treated the issue of train length? And how did you ensure that each train at 
least visits one home token. I guess that it was some tricky adjustment of the 
graph, but maybe you can give some clues here.

>  However, I don't know how to adapt this to all the exotic rules that have
> been added since then -- there may not be any better approach than brute
> force to make sure no solutions are missed.

I agree that it potentially  makes it much harder to implement the exotic 
rules. However I would be happy to implement such an algorithm if it allows to 
speed up those scenarios that might see double or triple long trains on an 
extensive network, but have otherwise pretty standard rules.

> 
> Perhaps the best approach is to take advantage of multiple cores by
> sharding testing alternate routes into threads and count on hardware
> getting faster
> 
> :).

That is easy ;-) 

Stefan

Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Sun, Aug 7, 2011 at 1:55 AM, Stefan Frey <ste...@we...> wrote:

> > A long, long time ago, I implemented route calculation by transforming
> the
> > problem to a flow graph and running the max-flow/min-cut algorithm on it
> > (sorry, I no longer have this code), which avoids exponential time.
>
> I think I can imagine how you approached this: You define the revenue of
> each
> node as negative cost of an edge inside the node and then minimize the
> costs
> (thus maximizing revenue) of the trains treated as flow.
>
> Even if you do not have the code any longer, can you still remember how you
> treated the issue of train length? And how did you ensure that each train
> at
> least visits one home token. I guess that it was some tricky adjustment of
> the
> graph, but maybe you can give some clues here.


It has been 24 years -- I was taking a Graph Theory class in grad school,
and one of the things we had to do was transform other traditional problems
to graphs and solve them using graph theory algorithms.  At the time we were
studying the Floyd-Fulkerson algorithm, so I am sure I used that.  Most of
the transforms involved creating extra nodes to represent other constraints,
or replacing each node in the base graph with a set of nodes to represent
those constraints.  I don't remember the specifics of how I solved it, but
it worked for 1830-style trains only (which was all I knew about at the
time).

-- 
John A. Tamplin

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

see below

On Tuesday, August 09, 2011 08:22:38 am John A. Tamplin wrote:
> On Sun, Aug 7, 2011 at 1:55 AM, Stefan Frey <ste...@we...> wrote:
> > > A long, long time ago, I implemented route calculation by transforming
> > 
> > the
> > 
> > > problem to a flow graph and running the max-flow/min-cut algorithm on
> > > it (sorry, I no longer have this code), which avoids exponential time.
> > 
> > I think I can imagine how you approached this: You define the revenue of
> > each
> > node as negative cost of an edge inside the node and then minimize the
> > costs
> > (thus maximizing revenue) of the trains treated as flow.
> > 
> > Even if you do not have the code any longer, can you still remember how
> > you treated the issue of train length? And how did you ensure that each
> > train at
> > least visits one home token. I guess that it was some tricky adjustment
> > of the
> > graph, but maybe you can give some clues here.
> 
> It has been 24 years -- I was taking a Graph Theory class in grad school,
> and one of the things we had to do was transform other traditional problems
> to graphs and solve them using graph theory algorithms.  At the time we
> were studying the Floyd-Fulkerson algorithm, so I am sure I used that. 
> Most of the transforms involved creating extra nodes to represent other
> constraints, or replacing each node in the base graph with a set of nodes
> to represent those constraints.  I don't remember the specifics of how I
> solved it, but it worked for 1830-style trains only (which was all I knew
> about at the time).

John,
thanks for your comments. 
Good thing to know that first you were able to solve it (I hate working on 
unsolvable problems in my free time) and second that it did not take anything 
too extraordinary graph theory stuff to solve it. Third it shows the direction 
to go to adjust the graph to incorporate the train constraints (I have some 
ideas how to do that). An alternative might be to use a linear programming 
algorithm to solve the flow problem which (potentially) makes adding other 
constraints easier.

Can I ask you for reviewing my proposals, this might even help you retrieve 
the ideas you had 24 years ago.
Stefan

Re: [Rails-devel] Route calculation for huge runs

[Bill R. <ro...@gm...>]

On 2011-08-09, at 15:41 , Stefan Frey wrote:
> John,
> thanks for your comments. 
> Good thing to know that first you were able to solve it (I hate working on 
> unsolvable problems in my free time) and second that it did not take anything 
> too extraordinary graph theory stuff to solve it. Third it shows the direction 
> to go to adjust the graph to incorporate the train constraints (I have some 
> ideas how to do that). An alternative might be to use a linear programming 
> algorithm to solve the flow problem which (potentially) makes adding other 
> constraints easier.
> 
> Can I ask you for reviewing my proposals, this might even help you retrieve 
> the ideas you had 24 years ago.
> Stefan

Is the problem really solvable?  The planar cubic hamiltonian path problem is NP-complete (see Garey, Johnson, and Tarjan 1976, which seems to be available at http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf ).  The title of the paper involves cycles, but the text on page 713 claims it holds also for paths.  I have not verified the results of the paper, but it appears in a very good journal and so is likely to be correct.

I think the problem is equivalent to optimizing the run of only one diesel on such a graph.  Given any planar graph with degree 3, it can be implemented as an 18xx map with cities as vertices and track as edges, though the map may get pretty large (though still polynomial in the number of cities).  Imagine such a map with only one company (with a token somewhere) that owns one diesel.  That train can hit every city if and only if there is a Hamiltonian path in the original graph.

Practically this doesn't say that much, as we don't have arbitrarily large graphs, and many of the trains in 18xx games run for some constant length, but it might imply that a general purpose poly-time algorithm is going to be difficult to find.

Bill Rosgen

Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:

> Is the problem really solvable?  The planar cubic hamiltonian path problem
> is NP-complete (see Garey, Johnson, and Tarjan 1976, which seems to be
> available at
> http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf).  The title of the paper involves cycles, but the text on page 713 claims
> it holds also for paths.  I have not verified the results of the paper, but
> it appears in a very good journal and so is likely to be correct.
>
> I think the problem is equivalent to optimizing the run of only one diesel
> on such a graph.  Given any planar graph with degree 3, it can be
> implemented as an 18xx map with cities as vertices and track as edges,
> though the map may get pretty large (though still polynomial in the number
> of cities).  Imagine such a map with only one company (with a token
> somewhere) that owns one diesel.  That train can hit every city if and only
> if there is a Hamiltonian path in the original graph.
>

I don't think it is equivalent to Hamiltonian path on an arbitrary graph,
and there are polynomial solutions for Hamiltonian path on many types of
restricted graphs.  Also, you aren't actually asking is there a path that
visits all cities but instead what is the best path that can be obtained.


> Practically this doesn't say that much, as we don't have arbitrarily large
> graphs, and many of the trains in 18xx games run for some constant length,
> but it might imply that a general purpose poly-time algorithm is going to be
> difficult to find.


I agree, in particular I think being able to skip stops and double an
arbitrary stop are things that would make anything short of brute
force intractable.

-- 
John A. Tamplin

Re: [Rails-devel] Route calculation for huge runs

[Bill R. <ro...@gm...>]

On 2011-08-10, at 12:54 , John A. Tamplin wrote:

> On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:
>> I think the problem is equivalent to optimizing the run of only one diesel on such a graph.  Given any planar graph with degree 3, it can be implemented as an 18xx map with cities as vertices and track as edges, though the map may get pretty large (though still polynomial in the number of cities).  Imagine such a map with only one company (with a token somewhere) that owns one diesel.  That train can hit every city if and only if there is a Hamiltonian path in the original graph.
>> 
> I don't think it is equivalent to Hamiltonian path on an arbitrary graph, and there are polynomial solutions for Hamiltonian path on many types of restricted graphs.  Also, you aren't actually asking is there a path that visits all cities but instead what is the best path that can be obtained.

But on a cubic planar graph the Hamiltonian path problem remains NP-complete (as shown in the paper of Garey, Johnson, and Tarjan).  Cubic planar graphs can be represented as 18xx maps.  The best path on such a map, if one exists, is the one that visits all cities.  This implies that if there is a general algorithm for 18xx maps that works in the case of one company with one token and one diesel, it also can be used to decide whether or not a cubic planar graph has a Hamiltonian path.

Bill

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

see below

On Wednesday, August 10, 2011 06:54:58 am John A. Tamplin wrote:
> On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:
> > Is the problem really solvable?  The planar cubic hamiltonian path
> > problem is NP-complete (see Garey, Johnson, and Tarjan 1976, which seems
> > to be available at
> > http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20p
> > lanar%20hamiltonian.pdf).  The title of the paper involves cycles, but
> > the text on page 713 claims it holds also for paths.  I have not
> > verified the results of the paper, but it appears in a very good journal
> > and so is likely to be correct.
> > 
> > I think the problem is equivalent to optimizing the run of only one
> > diesel on such a graph.  Given any planar graph with degree 3, it can be
> > implemented as an 18xx map with cities as vertices and track as edges,
> > though the map may get pretty large (though still polynomial in the
> > number of cities).  Imagine such a map with only one company (with a
> > token somewhere) that owns one diesel.  That train can hit every city if
> > and only if there is a Hamiltonian path in the original graph.
> 
> I don't think it is equivalent to Hamiltonian path on an arbitrary graph,
> and there are polynomial solutions for Hamiltonian path on many types of
> restricted graphs.  Also, you aren't actually asking is there a path that
> visits all cities but instead what is the best path that can be obtained.
> 
> > Practically this doesn't say that much, as we don't have arbitrarily
> > large graphs, and many of the trains in 18xx games run for some constant
> > length, but it might imply that a general purpose poly-time algorithm is
> > going to be difficult to find.
> 
> I agree, in particular I think being able to skip stops and double an
> arbitrary stop are things that would make anything short of brute
> force intractable.


This reminds me of getting involved into discussions of asymptotic behaviors 
by the econometrics theory people if I ask a question how to solve an 
econometric problem in an empirical applied context: I feel intimidated and 
stupid ;-)

And usually the number of answers exceeds the number of questions by a large 
multiple...

However what I take from this is that most likely that a polynomial solution 
exists (as John was able to find one 24 years ago) to the diesel/12 train 
scenario and that the existing algorithm covers the exotic train cases.

Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Wed, Aug 10, 2011 at 1:10 AM, Stefan Frey <ste...@we...> wrote:

> However what I take from this is that most likely that a polynomial
> solution
> exists (as John was able to find one 24 years ago) to the diesel/12 train
> scenario and that the existing algorithm covers the exotic train cases.


It is certainly possible that I made some mistake, and the fact that I don't
have the code and can't remember the graph transform details makes it harder
to defend.  However, it definitely did give the correct result (as manually
calculated) in cases where Simtex gave the wrong answer, and it was quicker
on the same hardware.

However, I don't think it is worth much effort trying to recreate it,
because basically there are very few games which could make use of it
anyway.

-- 
John A. Tamplin

Re: [Rails-devel] Route calculation for huge runs

[brett l. <bre...@gm...>]

On Tue, Aug 9, 2011 at 10:10 PM, Stefan Frey <ste...@we...> wrote:
> see below
>
> On Wednesday, August 10, 2011 06:54:58 am John A. Tamplin wrote:
>> On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:
>> > Is the problem really solvable?  The planar cubic hamiltonian path
>> > problem is NP-complete (see Garey, Johnson, and Tarjan 1976, which seems
>> > to be available at
>> > http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20p
>> > lanar%20hamiltonian.pdf).  The title of the paper involves cycles, but
>> > the text on page 713 claims it holds also for paths.  I have not
>> > verified the results of the paper, but it appears in a very good journal
>> > and so is likely to be correct.
>> >
>> > I think the problem is equivalent to optimizing the run of only one
>> > diesel on such a graph.  Given any planar graph with degree 3, it can be
>> > implemented as an 18xx map with cities as vertices and track as edges,
>> > though the map may get pretty large (though still polynomial in the
>> > number of cities).  Imagine such a map with only one company (with a
>> > token somewhere) that owns one diesel.  That train can hit every city if
>> > and only if there is a Hamiltonian path in the original graph.
>>
>> I don't think it is equivalent to Hamiltonian path on an arbitrary graph,
>> and there are polynomial solutions for Hamiltonian path on many types of
>> restricted graphs.  Also, you aren't actually asking is there a path that
>> visits all cities but instead what is the best path that can be obtained.
>>
>> > Practically this doesn't say that much, as we don't have arbitrarily
>> > large graphs, and many of the trains in 18xx games run for some constant
>> > length, but it might imply that a general purpose poly-time algorithm is
>> > going to be difficult to find.
>>
>> I agree, in particular I think being able to skip stops and double an
>> arbitrary stop are things that would make anything short of brute
>> force intractable.
>
>
> This reminds me of getting involved into discussions of asymptotic behaviors
> by the econometrics theory people if I ask a question how to solve an
> econometric problem in an empirical applied context: I feel intimidated and
> stupid ;-)
>
> And usually the number of answers exceeds the number of questions by a large
> multiple...
>
> However what I take from this is that most likely that a polynomial solution
> exists (as John was able to find one 24 years ago) to the diesel/12 train
> scenario and that the existing algorithm covers the exotic train cases.
>
>

Also, don't forget... the big difference between Comp Sci theory and
real world implementations, is that in the real world it's
occasionally possible (and completely acceptable) to cheat.

If we can find a "good enough" algorithm that at least gets us mostly
correct answers most of the time while still avoiding a brute force
method, I think that has a certain amount of value. This is especially
true if we continue to allow users to be the final arbitrator on what
their run values really are.

Even Simtex's 1830 game didn't have perfect route calculation
algorithms, and I've found a number of late game positions for which
it would suggest sub-optimal routes.

Personally, if y'all want to pitch in and use Rails to try out
different algorithms and see who can come up with the best one, I
think it would be fantastic. It may even be a good foundation for
supporting AI, which has also been a long-time dream. ;-)

---Brett.

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

> 
> Also, don't forget... the big difference between Comp Sci theory and
> real world implementations, is that in the real world it's
> occasionally possible (and completely acceptable) to cheat.
> 
> If we can find a "good enough" algorithm that at least gets us mostly
> correct answers most of the time while still avoiding a brute force
> method, I think that has a certain amount of value. This is especially
> true if we continue to allow users to be the final arbitrator on what
> their run values really are.

Brett,
I think a "good enough" algorithm defined by you above is not the goal and the 
current algorithm is already better than your "good enough" algorithm.

The algorithm itself (as a descendant from brute-force enhanced by heuristics 
for tree pruning) should always result the optimal solution.
If a user is able to point out a better solution this is a bug and should be 
filed as such.

The previous discussion on the list convinced me that a "good enough" 
algorithm would be never enough to make people comfortable to use Rails.

I know that some people claim to have found calculation errors of Rails, but 
when asked for save files I never received one.
I think you should not give Rails a worse reputation than it actually 
deserves.

> 
> Even Simtex's 1830 game didn't have perfect route calculation
> algorithms, and I've found a number of late game positions for which
> it would suggest sub-optimal routes.

Do you have save files for those cases? I would like to recreate the track 
configuration with Rails.

Stefan

Re: [Rails-devel] Route calculation for huge runs

[John A. T. <ja...@ja...>]

On Wed, Aug 10, 2011 at 1:19 AM, brett lentz <bre...@gm...> wrote:

> Personally, if y'all want to pitch in and use Rails to try out
> different algorithms and see who can come up with the best one, I
> think it would be fantastic. It may even be a good foundation for
> supporting AI, which has also been a long-time dream. ;-)


AI is going to have to be able to very quickly (like in ms) evaluate
possible runs in various scenarios, because it is going to have to evaluate
many options and hopefully a few moves ahead.  For that, it doesn't have to
be accurate, just reasonably close -- but it absolutely has to be blindingly
fast.

For regular route calculation, I would hope it would be better than Simtex
-- I frequently found incorrect runs.  If we get people relying on it and
then they find it produces incorrect answers, then that will be a problem.
 I would prefer to come up with some heuristic for deciding when the
exponential approach will take too long, and then do some approximation and
label it clearly as such.

-- 
John A. Tamplin

Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

On Wednesday, August 10, 2011 07:37:29 am John A. Tamplin wrote:
> On Wed, Aug 10, 2011 at 1:19 AM, brett lentz <bre...@gm...> wrote:
> > Personally, if y'all want to pitch in and use Rails to try out
> > different algorithms and see who can come up with the best one, I
> > think it would be fantastic. It may even be a good foundation for
> > supporting AI, which has also been a long-time dream. ;-)
> 
> AI is going to have to be able to very quickly (like in ms) evaluate
> possible runs in various scenarios, because it is going to have to evaluate
> many options and hopefully a few moves ahead.  For that, it doesn't have to
> be accurate, just reasonably close -- but it absolutely has to be
> blindingly fast.
> 
> For regular route calculation, I would hope it would be better than Simtex
> -- I frequently found incorrect runs.  If we get people relying on it and
> then they find it produces incorrect answers, then that will be a problem.
>  I would prefer to come up with some heuristic for deciding when the
> exponential approach will take too long, and then do some approximation and
> label it clearly as such.

The current setup is strongly optimized for the regular calculation (the graph 
is always created from scratch and there is no easy way to simply add or 
change a tile once it is created). 

This was somehow different from Alex' approach one year ago (what happened to 
his prototype?) who tried to keep the door wide open for AI.

I agree with John that a separate approach to route calculation for AI is 
optimal. For AI you are mainly interested in finding revenue increases by 
changing the graph in several steps, thus the strategy space is again 
exponentially larger. And then you have to rely on all kind of approximations 
and "non-correct" tree pruning. And you are allowed to do so for AI.

Stefan