Menu
▾
▴
rails-devel
|
From: Stefan F. <ste...@we...> - 2010-05-02 19:20:41
|
Alex, sorry for not answering earlier to the question about the improved revenue prediction. The scheme is simple. Assume that N is the number of trains in the trainset. First I replace the maximum revenue potential of each single train by the maximum results of running each train alone. If there are more than two trains to run: Start with J=N-1 and decrease J with each step until J=1. - Run the combined set of trains [J, ... N] and use the optimal result to predict the maximum future revenue potential of that train set. Then run the combined optimization of all trains, given the maximum revenue potential for each set [J, N], with J > 1. I would like to compare another scenario based on the track network A to check if we get the same results. The changes are: - SLSF has 4 tokens now (D5, J3, L11, E12) - Trains running are 6E, 8, 5+5, 4D (E: ignores towns, D: ignores towns and double city and offboard values) The best run I find is 1100. Total running time 78 sec. Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray) and log is attached. Stefan |
|
From: alexti <al...@sh...> - 2010-05-04 05:37:43
|
Hi Stefan,
Thanks for the explanation. I think I understand what you're doing; I
wasn't doing exactly the same and changing my algorithm brought some
improvement, but as usual it was not that big - I'm starting to feel you
have some kind of magic predictor ;-)
I've run your scenario and my algorithm found the same set of routes,
however it was able to find more scenic route between M6 and L11 for 5+5
train :) It took 46s. Here are my stats.
Routes found in 45.9643s
[4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S}
[8:290]
{N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW,A2.SE}
[10:230] {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3}
[6:240]
{N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6.SW,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11}
50,125,612 routes tried
The frustrating (to me) part is that you've done only 564,805 while I did
over 50 millions (almost 100 times more). I am not sure how you manage to
eliminate so many possibilities. I know that my algorithm doesn't handle
multiple stations efficiently - essentially it scales linearly with number
of stations. I have not thought about it yet, but it still wouldn't
explain the difference.
Maybe I'm overlooking something. Or maybe I have some bug in the
implementation that doesn't eliminate something I think it does :)
Thanks,
Alex.
On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...> wrote:
> Alex,
> sorry for not answering earlier to the question about the improved
> revenue
> prediction.
>
> The scheme is simple. Assume that N is the number of trains in the
> trainset.
> First I replace the maximum revenue potential of each single train by the
> maximum results of running each train alone.
>
> If there are more than two trains to run:
> Start with J=N-1 and decrease J with each step until J=1.
> - Run the combined set of trains [J, ... N] and use the optimal result to
> predict the maximum future revenue potential of that train set.
>
> Then run the combined optimization of all trains, given the maximum
> revenue
> potential for each set [J, N], with J > 1.
>
> I would like to compare another scenario based on the track network A to
> check
> if we get the same results.
> The changes are:
> - SLSF has 4 tokens now (D5, J3, L11, E12)
> - Trains running are 6E, 8, 5+5, 4D
> (E: ignores towns, D: ignores towns and double city and offboard values)
> The best run I find is 1100. Total running time 78 sec.
> Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray) and log is attached.
>
> Stefan
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
|
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-11 22:12:36
|
Hi Alex,
but you are still faster and get more scenic routes, thus you should not be
too concerned :-)
And I did 565k evaluations plus 5,651k predictions, compared to this number it
is only 10 times less. The only optimization (or better avoidance of
unnecessary duplication) I have not talked about is that I keep the start
vertices visited, when I move to the next start vertex. All possible routes
which include the previous start vertex are already run from that vertex.
Otherwise we should go back to much simpler examples to compare, but I do not
have much hope to get similar numbers as long as I do not have implemented
the two-phase approach.
Stefan
On Tuesday 04 May 2010 07:37:39 alexti wrote:
> Hi Stefan,
>
> Thanks for the explanation. I think I understand what you're doing; I
> wasn't doing exactly the same and changing my algorithm brought some
> improvement, but as usual it was not that big - I'm starting to feel you
> have some kind of magic predictor ;-)
>
> I've run your scenario and my algorithm found the same set of routes,
> however it was able to find more scenic route between M6 and L11 for 5+5
> train :) It took 46s. Here are my stats.
>
> Routes found in 45.9643s
> [4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S}
> [8:290]
> {N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW,A2
>.SE} [10:230]
> {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3} [6:240]
> {N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6.SW
>,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11} 50,125,612 routes tried
>
> The frustrating (to me) part is that you've done only 564,805 while I did
> over 50 millions (almost 100 times more). I am not sure how you manage to
> eliminate so many possibilities. I know that my algorithm doesn't handle
> multiple stations efficiently - essentially it scales linearly with number
> of stations. I have not thought about it yet, but it still wouldn't
> explain the difference.
>
> Maybe I'm overlooking something. Or maybe I have some bug in the
> implementation that doesn't eliminate something I think it does :)
>
> Thanks,
> Alex.
>
> On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...> wrote:
> > Alex,
> > sorry for not answering earlier to the question about the improved
> > revenue
> > prediction.
> >
> > The scheme is simple. Assume that N is the number of trains in the
> > trainset.
> > First I replace the maximum revenue potential of each single train by the
> > maximum results of running each train alone.
> >
> > If there are more than two trains to run:
> > Start with J=N-1 and decrease J with each step until J=1.
> > - Run the combined set of trains [J, ... N] and use the optimal result to
> > predict the maximum future revenue potential of that train set.
> >
> > Then run the combined optimization of all trains, given the maximum
> > revenue
> > potential for each set [J, N], with J > 1.
> >
> > I would like to compare another scenario based on the track network A to
> > check
> > if we get the same results.
> > The changes are:
> > - SLSF has 4 tokens now (D5, J3, L11, E12)
> > - Trains running are 6E, 8, 5+5, 4D
> > (E: ignores towns, D: ignores towns and double city and offboard values)
> > The best run I find is 1100. Total running time 78 sec.
> > Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray) and log is attached.
> >
> > Stefan
|
|
From: alexti <al...@sh...> - 2010-05-12 02:56:25
|
Hi Stefan, My speed advantage is likely due to two-phased approach and more efficient memory management. I still would like to get more intelligent prediction algorithm though :-) What exactly 5,651k predictions in your case mean? I've actually looked at my approach to the station handling (after checking all routes from the first station I simply mark all segments connected to this station as "used", so no other route would include this station). I can't actually come up with any better method. When you're saying you "keep start vertices visited", do you mean "stations" or you iterate in some other manner (not from the stations)? Meanwhile, I've spotted some epic stupidity in my code and after removing it my time on that example went down to 30s. I've started to work on more sophisticated predictor; but now I don't exactly understand what it is doing and it doesn't always work correctly. Even when I get it right, I am not sure if it will be any better :( I've also realized that on that 4 train case, our algorithms would easily beat human - when I look at the map it's not obvious to me at all what the best run would be :) Alex. On Tue, 11 May 2010 16:12:20 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Hi Alex, > but you are still faster and get more scenic routes, thus you should not > be > too concerned :-) > > And I did 565k evaluations plus 5,651k predictions, compared to this > number it > is only 10 times less. The only optimization (or better avoidance of > unnecessary duplication) I have not talked about is that I keep the start > vertices visited, when I move to the next start vertex. All possible > routes > which include the previous start vertex are already run from that vertex. > > Otherwise we should go back to much simpler examples to compare, but I > do not > have much hope to get similar numbers as long as I do not have > implemented > the two-phase approach. > > Stefan > > > On Tuesday 04 May 2010 07:37:39 alexti wrote: >> Hi Stefan, >> >> Thanks for the explanation. I think I understand what you're doing; I >> wasn't doing exactly the same and changing my algorithm brought some >> improvement, but as usual it was not that big - I'm starting to feel you >> have some kind of magic predictor ;-) >> >> I've run your scenario and my algorithm found the same set of routes, >> however it was able to find more scenic route between M6 and L11 for 5+5 >> train :) It took 46s. Here are my stats. >> >> Routes found in 45.9643s >> [4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S} >> [8:290] >> {N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW,A2 >> .SE} [10:230] >> {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3} >> [6:240] >> {N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6.SW >> ,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11} 50,125,612 routes tried >> >> The frustrating (to me) part is that you've done only 564,805 while I >> did >> over 50 millions (almost 100 times more). I am not sure how you manage >> to >> eliminate so many possibilities. I know that my algorithm doesn't handle >> multiple stations efficiently - essentially it scales linearly with >> number >> of stations. I have not thought about it yet, but it still wouldn't >> explain the difference. >> >> Maybe I'm overlooking something. Or maybe I have some bug in the >> implementation that doesn't eliminate something I think it does :) >> >> Thanks, >> Alex. >> >> On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...> >> wrote: >> > Alex, >> > sorry for not answering earlier to the question about the improved >> > revenue >> > prediction. >> > >> > The scheme is simple. Assume that N is the number of trains in the >> > trainset. >> > First I replace the maximum revenue potential of each single train by >> the >> > maximum results of running each train alone. >> > >> > If there are more than two trains to run: >> > Start with J=N-1 and decrease J with each step until J=1. >> > - Run the combined set of trains [J, ... N] and use the optimal >> result to >> > predict the maximum future revenue potential of that train set. >> > >> > Then run the combined optimization of all trains, given the maximum >> > revenue >> > potential for each set [J, N], with J > 1. >> > >> > I would like to compare another scenario based on the track network A >> to >> > check >> > if we get the same results. >> > The changes are: >> > - SLSF has 4 tokens now (D5, J3, L11, E12) >> > - Trains running are 6E, 8, 5+5, 4D >> > (E: ignores towns, D: ignores towns and double city and offboard >> values) >> > The best run I find is 1100. Total running time 78 sec. >> > Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray) and log is >> attached. >> > >> > 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/ |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-14 15:57:40
|
Hi Alex, see answers below. > > My speed advantage is likely due to two-phased approach and more efficient > memory management. I still would like to get more intelligent prediction > algorithm though :-) Most likely the difference is from the two-phase approach. Memory management should be irrelevant for the Java program, as all variables involved are fixed sized arrays, which are defined as final. It will be more the speed of function calls and stack handling. > > What exactly 5,651k predictions in your case mean? Evaluations count the call to the function that sums up the value of all trains after all trains are finished. Predictions count the call to the function used after each station visit. Actually the latest refactoring (I do not evaluate anymore until I reach the second station, previously I set that to zero) reduced the number of evaluations and predictions: The number of evaluations drops to 480k, the number of predictions to 2,950k, the number of edges travelled does not change. Speed improvement is minor (10-15%). > > I've actually looked at my approach to the station handling (after > checking all routes from the first station I simply mark all segments > connected to this station as "used", so no other route would include this > station). I can't actually come up with any better method. > > When you're saying you "keep start vertices visited", do you mean > "stations" or you iterate in some other manner (not from the stations)? That seems identical, except that I do not mark the edges (as they are not train specific) as used, I only do that for the vertexes (train-specific). I have an outer loop that iterates over the base tokens: After I have considered all routes from the first token, I keep that vertex as visited to avoid evaluating the identical route again. (All routes with both first and another start token are already found from the first route, this will work as long as connectivity is symmetric). > > I've also realized that on that 4 train case, our algorithms would easily > beat human - when I look at the map it's not obvious to me at all what the > best run would be :) I am long lost with founding best routes for those scenarios, but I am not a good route finder. > > Alex. > > > On Tue, 11 May 2010 16:12:20 -0600, Stefan Frey (web.de) > > <ste...@we...> wrote: > > Hi Alex, > > but you are still faster and get more scenic routes, thus you should not > > be > > too concerned :-) > > > > And I did 565k evaluations plus 5,651k predictions, compared to this > > number it > > is only 10 times less. The only optimization (or better avoidance of > > unnecessary duplication) I have not talked about is that I keep the start > > vertices visited, when I move to the next start vertex. All possible > > routes > > which include the previous start vertex are already run from that vertex. > > > > Otherwise we should go back to much simpler examples to compare, but I > > do not > > have much hope to get similar numbers as long as I do not have > > implemented > > the two-phase approach. > > > > Stefan > > > > On Tuesday 04 May 2010 07:37:39 alexti wrote: > >> Hi Stefan, > >> > >> Thanks for the explanation. I think I understand what you're doing; I > >> wasn't doing exactly the same and changing my algorithm brought some > >> improvement, but as usual it was not that big - I'm starting to feel you > >> have some kind of magic predictor ;-) > >> > >> I've run your scenario and my algorithm found the same set of routes, > >> however it was able to find more scenic route between M6 and L11 for 5+5 > >> train :) It took 46s. Here are my stats. > >> > >> Routes found in 45.9643s > >> [4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S} > >> [8:290] > >> {N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW > >>,A2 .SE} [10:230] > >> {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3} > >> [6:240] > >> {N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6 > >>.SW ,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11} 50,125,612 routes tried > >> > >> The frustrating (to me) part is that you've done only 564,805 while I > >> did > >> over 50 millions (almost 100 times more). I am not sure how you manage > >> to > >> eliminate so many possibilities. I know that my algorithm doesn't handle > >> multiple stations efficiently - essentially it scales linearly with > >> number > >> of stations. I have not thought about it yet, but it still wouldn't > >> explain the difference. > >> > >> Maybe I'm overlooking something. Or maybe I have some bug in the > >> implementation that doesn't eliminate something I think it does :) > >> > >> Thanks, > >> Alex. > >> > >> On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...> > >> > >> wrote: > >> > Alex, > >> > sorry for not answering earlier to the question about the improved > >> > revenue > >> > prediction. > >> > > >> > The scheme is simple. Assume that N is the number of trains in the > >> > trainset. > >> > First I replace the maximum revenue potential of each single train by > >> > >> the > >> > >> > maximum results of running each train alone. > >> > > >> > If there are more than two trains to run: > >> > Start with J=N-1 and decrease J with each step until J=1. > >> > - Run the combined set of trains [J, ... N] and use the optimal > >> > >> result to > >> > >> > predict the maximum future revenue potential of that train set. > >> > > >> > Then run the combined optimization of all trains, given the maximum > >> > revenue > >> > potential for each set [J, N], with J > 1. > >> > > >> > I would like to compare another scenario based on the track network A > >> > >> to > >> > >> > check > >> > if we get the same results. > >> > The changes are: > >> > - SLSF has 4 tokens now (D5, J3, L11, E12) > >> > - Trains running are 6E, 8, 5+5, 4D > >> > (E: ignores towns, D: ignores towns and double city and offboard > >> > >> values) > >> > >> > The best run I find is 1100. Total running time 78 sec. > >> > Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray) and log is > >> > >> attached. > >> > >> > Stefan > > > > ------------------------------------------------------------------------- > >----- > > > > _______________________________________________ > > Rails-devel mailing list > > Rai...@li... > > https://lists.sourceforge.net/lists/listinfo/rails-devel |
|
From: Phil D. <de...@gm...> - 2010-05-14 16:00:23
|
On 14 May 2010 16:56, Stefan Frey (web.de) <ste...@we...> wrote: >> I've also realized that on that 4 train case, our algorithms would easily >> beat human - when I look at the map it's not obvious to me at all what the >> best run would be :) > > I am long lost with founding best routes for those scenarios, but I am not a > good route finder. > On a related note, we just finished playing an 1856 game with revenue calculation on and we had 5 D runs that were in excess of $1200 by the end of the game. No way would I ever have calculated that manually. I appreciate that D runs are technically probably the easiest for revenue calc to work out but it saves a massive amount of actual game time for which I am grateful Phil |
|
From: alexti <al...@sh...> - 2010-05-15 16:55:47
|
Hi Stefan, > Memory management should be irrelevant for the Java program, as all > variables > involved are fixed sized arrays, which are defined as final. I am curious, how do you avoid dynamic memory allocation during the iteration through the routes? With the switch to the two-phased approach I also couldn't avoid some dynamic sizing in the second phase graph. >> What exactly 5,651k predictions in your case mean? > > Evaluations count the call to the function that sums up the value of all > trains after all trains are finished. Can you tell from this number how many times revenue of the route has been computed? > Predictions count the call to the function used after each station visit. > > Actually the latest refactoring (I do not evaluate anymore until I reach > the > second station, previously I set that to zero) reduced the number of > evaluations and predictions: > The number of evaluations drops to 480k, the number of predictions to > 2,950k, the number of edges travelled does not change. > Speed improvement is minor (10-15%). This sounds like what I was calling revenue of the route computation. Is it the place were you total value of cities and apply bonuses? > I have an outer loop that iterates over the base tokens: After I have > considered all routes from the first token, I keep that vertex as > visited to > avoid evaluating the identical route again. (All routes with both first > and > another start token are already found from the first route, this will > work as > long as connectivity is symmetric). Yeah, we have the same approach here (aside of marking vertex vs edge). Alex. |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-16 21:32:44
|
Alex,
answers and comments see below:
> I am curious, how do you avoid dynamic memory allocation during the
> iteration through the routes? With the switch to the two-phased approach I
> also couldn't avoid some dynamic sizing in the second phase graph.
>
I convert all information from the graph and other objects into a simple
arrays, where I define the size at the initialization of the revenue
calculator (usually to the maximum number of trains, vertices, edges etc).
Thus I never create any objects throughout the iterations.
The dynamic data arrays are:
// dynamic train data
private final int[] trainCurrentValue;
private final int[] trainMajors;
private final int[] trainMinors;
private final boolean[][] trainVisited; // dimensions: train, vertex
private final int[][] trainVertexStack; // dimensions: train, vertex
private final int[][] trainEdgeStack; // dimensions: train, edge
private final int[] trainStackPos;
private final int [] trainBottomPos;
private final int [] trainStartEdge;
// dynamic bonus data
private final int [][] bonusTrainVertices; // dimensions: bonus, train
> >> What exactly 5,651k predictions in your case mean?
> >
> > Evaluations count the call to the function that sums up the value of all
> > trains after all trains are finished.
>
> Can you tell from this number how many times revenue of the route has been
> computed?
In fact I do not sum up the revenue of the routes from vertex values each
time, but I update the currentTrainValues each time a vertex is encountered
or left. The only summation is done over the set of trains. The separation
into single trains (instead of updating a joint value) allows the revenue
prediction of the current running train.
>
> > Predictions count the call to the function used after each station visit.
> >
> > Actually the latest refactoring (I do not evaluate anymore until I reach
> > the
> > second station, previously I set that to zero) reduced the number of
> > evaluations and predictions:
> > The number of evaluations drops to 480k, the number of predictions to
> > 2,950k, the number of edges travelled does not change.
> > Speed improvement is minor (10-15%).
>
> This sounds like what I was calling revenue of the route computation. Is
> it the place were you total value of cities and apply bonuses?
As mentioned above, I do not total city values at the evaluation, but
continuously. The only summation is over trains.
Bonuses are added to the current train value when they are scored or
(un-)scored again. For each bonus/train combination a counter is initialized
with the number of required vertices (this is the bonusTrainVertices array
above). Each time a trains visit a required vertex, the counter for that
bonus is decreased. If zero is reached the bonus value is added. If the
counter increases to one again, the bonus value is subtracted.
|
|
From: alexti <al...@sh...> - 2010-05-16 23:37:21
|
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? > In fact I do not sum up the revenue of the routes from vertex values > each > time, but I update the currentTrainValues each time a vertex is > encountered > or left. The only summation is done over the set of trains. The > separation > into single trains (instead of updating a joint value) allows the revenue > prediction of the current running train. 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... 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? Alex. On Sun, 16 May 2010 15:32:28 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Alex, > answers and comments see below: > >> I am curious, how do you avoid dynamic memory allocation during the >> iteration through the routes? With the switch to the two-phased >> approach I >> also couldn't avoid some dynamic sizing in the second phase graph. >> > > I convert all information from the graph and other objects into a simple > arrays, where I define the size at the initialization of the revenue > calculator (usually to the maximum number of trains, vertices, edges > etc). > Thus I never create any objects throughout the iterations. > > The dynamic data arrays are: > // dynamic train data > private final int[] trainCurrentValue; > private final int[] trainMajors; > private final int[] trainMinors; > private final boolean[][] trainVisited; // dimensions: train, vertex > private final int[][] trainVertexStack; // dimensions: train, vertex > private final int[][] trainEdgeStack; // dimensions: train, edge > private final int[] trainStackPos; > private final int [] trainBottomPos; > private final int [] trainStartEdge; > > // dynamic bonus data > private final int [][] bonusTrainVertices; // dimensions: bonus, > train > >> >> What exactly 5,651k predictions in your case mean? >> > >> > Evaluations count the call to the function that sums up the value of >> all >> > trains after all trains are finished. >> >> Can you tell from this number how many times revenue of the route has >> been >> computed? > > In fact I do not sum up the revenue of the routes from vertex values > each > time, but I update the currentTrainValues each time a vertex is > encountered > or left. The only summation is done over the set of trains. The > separation > into single trains (instead of updating a joint value) allows the revenue > prediction of the current running train. > >> >> > Predictions count the call to the function used after each station >> visit. >> > >> > Actually the latest refactoring (I do not evaluate anymore until I >> reach >> > the >> > second station, previously I set that to zero) reduced the number of >> > evaluations and predictions: >> > The number of evaluations drops to 480k, the number of predictions to >> > 2,950k, the number of edges travelled does not change. >> > Speed improvement is minor (10-15%). >> >> This sounds like what I was calling revenue of the route computation. Is >> it the place were you total value of cities and apply bonuses? > > As mentioned above, I do not total city values at the evaluation, but > continuously. The only summation is over trains. > > Bonuses are added to the current train value when they are scored or > (un-)scored again. For each bonus/train combination a counter is > initialized > with the number of required vertices (this is the bonusTrainVertices > array > above). Each time a trains visit a required vertex, the counter for that > bonus is decreased. If zero is reached the bonus value is added. If the > counter increases to one again, the bonus value is subtracted. > > > ------------------------------------------------------------------------------ > > _______________________________________________ > 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/ |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-18 22:05:35
|
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 |
|
From: alexti <al...@sh...> - 2010-05-19 03:54:55
|
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/ |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-19 21:08:31
|
Alex, see comments below. > 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. In fact I allow any vertex to add value (no requirement for a minor/major station type), but I do not allow trains to terminate there. (That is not important for the games implemented so far, but think about the ferry bonus in 18Scan). > > I do the same, but when you reach dead-end, how do you remember what > branch (and from what vertex) to try next? As soon as a deadend is encountered (and after I started the bottom part and run other trains), I un-encounter the vertex and return the travelled edge. As the encounter calls are recursively the information is on the stack. The only need for my own stack of vertices and edges is to store the optimal run. > > 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)? > You mean in the current implementation or with train dominance? Currently simple bonuses are covered by the train-dependent vertex values, for the complex ones a boolean array controls if a bonus is active for a specific train. Special train bonuses break train dominance, another reason not for implementing it. > > 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. The scenarios where it excels compared to revenue predictions are those in which you cannot run the trains to the full length. > > 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 :) > I hope it is not too "magic", as it will most likely imply that there is something wrong. I will think about more tests to rule that out. Are you sure you have fully implemented the sequential approach of the revenue prediction for the trainset? Stefan |
|
From: alexti <al...@sh...> - 2010-05-21 03:26:14
|
Hi Stefan, On Wed, 19 May 2010 15:08:24 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Alex, see comments below. > >> 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. > > In fact I allow any vertex to add value (no requirement for a minor/major > station type), but I do not allow trains to terminate there. (That is not > important for the games implemented so far, but think about the ferry > bonus > in 18Scan). Yes, I would have to create artificial vertex in this case (because I would remove all intermediate ones). >> I do the same, but when you reach dead-end, how do you remember what >> branch (and from what vertex) to try next? > > As soon as a deadend is encountered (and after I started the bottom part > and > run other trains), I un-encounter the vertex and return the travelled > edge. > As the encounter calls are recursively the information is on the stack. > The only need for my own stack of vertices and edges is to store the > optimal > run. Oh, I see. That essentially means that you're using stack as a way to dynamically allocate memory. It probably means that function inlining is not working and the actual overhead may show up as a function call overhead. Anyway, that's something to look at in the profiler. I was hoping you've found some algorithm that was avoiding the need for dynamic memory management. >> 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)? >> > > You mean in the current implementation or with train dominance? > Currently simple bonuses are covered by the train-dependent vertex > values, for > the complex ones a boolean array controls if a bonus is active for a > specific > train. > Special train bonuses break train dominance, another reason not for > implementing it. I was thinking about both. In particular, the situations when on a given route set some bonus can be applied to one of several trains and when there're some other bonuses possible (for example one train doubles the value of its run (including bonus) and another doesn't). >> 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. > > The scenarios where it excels compared to revenue predictions are those > in > which you cannot run the trains to the full length. I am not sure about that... If the optimal route set is achieved on 4+5 routes, it wouldn't matter which one is served by 8 train and which one is by 10. I think it would only make difference on such scenarios where the optimal route sets contains routes that have length between the length of the trains (for example 6+9 routes for 8+10 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 :) >> > > I hope it is not too "magic", as it will most likely imply that there is > something wrong. I will think about more tests to rule that out. Are you > sure > you have fully implemented the sequential approach of the revenue > prediction > for the trainset? No :-) But I can't find anything missing in my implementation. I wonder if we either misunderstand what each other counts or someones counting is wrong (though mine matching function call count shown by the profiler :) ) Alex. |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-05-24 21:56:22
|
Hi Alex, answers/comments see below. Most of them delay a more detailed discussion for the time after the current release. Stefan > Oh, I see. That essentially means that you're using stack as a way to > dynamically allocate memory. It probably means that function inlining is > not working and the actual overhead may show up as a function call > overhead. Anyway, that's something to look at in the profiler. I was > hoping you've found some algorithm that was avoiding the need for dynamic > memory management. > In principle I could replace the reliance on the java stack mechanism by storing the local variables in own stack. The next step would be to remove all recursive function calls, but I have doubts that this will improve the speed substantially, if at all. I plan to install the TPFP plugin after this release to get some data on that. > > The scenarios where it excels compared to revenue predictions are those > > in > > which you cannot run the trains to the full length. > > I am not sure about that... If the optimal route set is achieved on 4+5 > routes, it wouldn't matter which one is served by 8 train and which one is > by 10. I think it would only make difference on such scenarios where the > optimal route sets contains routes that have length between the length of > the trains (for example 6+9 routes for 8+10 trains). > I was more referring that the revenue prediction improves with the train run lengths in general, not that train dominance is better in those cases. The good thing about revenue prediction is that if the network increases it gets less likely that the trains runs are short. It is very unlikely for a company to have a complex network AND not being able to run its trains for a good length. > > No :-) But I can't find anything missing in my implementation. I wonder if > we either misunderstand what each other counts or someones counting is > wrong (though mine matching function call count shown by the profiler :) ) For the next release I plan to include the two-phase approach, this should ease comparisons. > > > Alex. > > --------------------------------------------------------------------------- >--- > > _______________________________________________ > Rails-devel mailing list > Rai...@li... > https://lists.sourceforge.net/lists/listinfo/rails-devel |
|
From: alexti <al...@sh...> - 2010-05-24 23:38:25
|
Hi Stefan, On Mon, 24 May 2010 15:50:14 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Hi Alex, > answers/comments see below. > Most of them delay a more detailed discussion for the time after the > current > release. > Stefan > >> Oh, I see. That essentially means that you're using stack as a way to >> dynamically allocate memory. It probably means that function inlining is >> not working and the actual overhead may show up as a function call >> overhead. Anyway, that's something to look at in the profiler. I was >> hoping you've found some algorithm that was avoiding the need for >> dynamic >> memory management. >> > > In principle I could replace the reliance on the java stack mechanism by > storing the local variables in own stack. The next step would be to > remove > all recursive function calls, but I have doubts that this will improve > the > speed substantially, if at all. I plan to install the TPFP plugin after > this > release to get some data on that. It certainly worth profiling before trying to change those things. Results may also differ depending on particular brand of JVM one is running... > >> > The scenarios where it excels compared to revenue predictions are >> those >> > in >> > which you cannot run the trains to the full length. >> >> I am not sure about that... If the optimal route set is achieved on 4+5 >> routes, it wouldn't matter which one is served by 8 train and which one >> is >> by 10. I think it would only make difference on such scenarios where the >> optimal route sets contains routes that have length between the length >> of >> the trains (for example 6+9 routes for 8+10 trains). >> > > I was more referring that the revenue prediction improves with the train > run > lengths in general, not that train dominance is better in those cases. I agree with that. > The good thing about revenue prediction is that if the network increases > it > gets less likely that the trains runs are short. It is very unlikely for > a > company to have a complex network AND not being able to run its trains > for a > good length. You haven't seen some of our local games ;-) But in general it depends on the game, I think. Typical scenario when such things happen is when there's a single choke-point with 2-3 exits. This means that the train that passes through it effectively bisects the graph into to for the remaining trains. I had some ideas about dealing with such cases - looking at the graph and finding vertices such that removal of 2 adjacent to them splits the graph. In this situation optimization over 2 (or more) parts can be done somewhat independently. Alex. |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X