Menu
▾
▴
rails-devel
|
From: Alex T. <al...@sh...> - 2010-03-21 00:10:11
|
Hi all, Per Brett Lentz suggestion I am moving this discussion here and reporting my message from 18x yahoo group. This is my first post here, but I have been lurking for a while. I wonder if there is an interest in adding automatic route calculation to Rails. I am trying to create AI for some of the games (and no, it's not going well), but as a side effect I have code that computes the routes. It supports some of more widely used rules (various town treatment, city and route bonuses, multipliers etc). It runs on an abstract connectivity graph, so it should not be too hard to integrate. Alex. |
|
From: alexti <al...@sh...> - 2010-04-12 04:58:03
|
Hi all, Sorry about my disappearance after raising this question couple of weeks ago. Things weren't standing still; I was in contact with Stefan, but unfortunately circumstances prevented quicker progress. Stefan has added some new functionality to Rails to lay some background framework and to simplify creation of "test problems". He has created few testing scenarios too. My original algorithm has proved to be marginal - on a relatively complex example the time was around 40 seconds. We've discussed various optimizations and I believe we have found good approach. The basic idea is to use two-phased process that runs on two different graphs. The first graph (let's call it primary graph) is built from the tiles and essentially follows one tile - 7 vertices principle (I've described this approach before and after some discussion with Stefan we've concluded that it's identical to the approach he had in mind). Essentially, one vertex is in the center of the tile and there are 6 vertices, one per tile edge. I was envisioning them inside of the tile, on the line connecting the center of the tile edge to the center of the tile (in fact, that's how I was visualizing them in my program) while Stefan was seeing the center of the tile's edge as such vertex (so adjacent tiles would have their vertices on the same spot and those vertices would be connected by [invisible] edge). This obviously describes exactly the same graph and the difference is only in how it can be thought of visually (or displayed). This primary graph is then used to generate secondary "coarse" graph. The only vertices coarse graph has corresponds to the nodes with some value (usually cities and towns). The edges of the coarse graph (I will call also them segments) are defined by possible distinct routes between its vertices. Thus there might be more than one edge connecting the same pair of vertices. This edges are built by running my original algorithm on the primary graph with the constraint requiring every route to contains exactly two nodes (vertices with value) - one at the start and another at the end. Essentially the list of these edges is the list of all possible two city/town routes. Each segment of this graph has additional characteristic - list of segments mutually exclusive with it. There are two types of exclusions - one forbids use of the related segment by any route and another forbids its use only by the same route. The first type of exclusion happens when two segments share some edge of the primary graph and the second type happens when only some vertex of the primary graph is shared (here we only consider non-terminating vertices - ones that are inside of the segment route, those vertices will have no value). This information forms coarse graph. There are multiple advantages in choosing this approach. The value of any route only depends on the nodes (vertices with values) visited, not the intermediate vertices. This considerably reduces number of possibilities to scan and it also allows to optimize the process by using "pre-packed" segment routes between the nodes. The coarse graph is company-independent - it has no token information and can be used to do route computations for any company. The coarse graph can be built incrementally. The most expensive part of building this graph is the search for all possible routes between every pair of nodes. This time can be saved if the coarse graph is updated incrementally when new tiles are laid (or upgraded). We only need to track the routes containing the newly added edges. All remaining routes are unaffected. On the "realistic" 1870 scenario we've used for testing it is taking 2-3 seconds to build coarse graph from scratch (on my rather average computer). If it's built incrementally, this time will virtually disappear. Of course, this leaves a question of game reloading (perhaps it makes more sense to rebuild it non-incrementally when the game is reloaded, or even save the coarse graph itself). The second phase of the process is to run optimal route search on the coarse graph. I am just running my original algorithm on this graph. This part takes care of source stations, hostile station blocking, visiting the same city twice and similar rules (as well as various bonus application). On the example described above this was taking 2-3 seconds. This phase has to be re-run every time on "Run trains" step of the operating round, but this response time seems acceptable. The run times I've mentioned are from my quickly put together implementation of this new approach, so I would imagine it's possible to do better just by refining the implementation and we haven't looked closely at possible algorithmic optimizations of phase 2. There are few possibly optimizations that can be applied to the primary graph too. Stefan has suggested "asterisk-edge" optimization. This is to simplify verification preventing backtracking. Idea is to mark all edges that are within the same tile with "asterisk" and then the rule preventing backtracking becomes very simple: two "asterisk" edges can be traveled consequently only if they're connected at the tile's center. This should help in phase 1 generation. There's some difficulty now though, because I'm using "transient vertex" optimization which can eliminate some edges and thus change adjacency of "asterisk" and "non-asterisk" edges. The transient vertex optimization works in the case when there's a vertex (without value) connected to exactly two other vertices (for example vertex B in A-B-C example). In this case vertex B can be removed and edges (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit, because realistic track build normally has large amount of such vertices. Another (obvious) optimization is dead-end elimination (if vertex has no value and it is connected with one other vertex only it can be eliminated). This optimization should not be used when tracking validity of track lay (for obvious reasons). There were some other ideas, such as caching results of the optimal route search and trying to eliminate some possibilities based on the values of the cities/towns on the map, but we have no concrete approach to exploit them. Hopefully, I haven't forgotten anything important. Stefan, please free to add whatever I've missed. Thanks, Alex. |
|
From: Aliza P. <ali...@gm...> - 2010-04-16 21:32:33
|
On Sun, Apr 11, 2010 at 9:58 PM, alexti <al...@sh...> wrote: > The first > graph (let's call it primary graph) is built from the tiles and > essentially follows one tile - 7 vertices principle (I've described this > approach before and after some discussion with Stefan we've concluded that > it's identical to the approach he had in mind). Essentially, one vertex is > in the center of the tile and there are 6 vertices, one per tile edge. What about double-dit and double-O cities (as well as more complex tiles that have three disjoint scoring locations...) |
|
From: alexti <al...@sh...> - 2010-04-17 04:23:46
|
On Fri, 16 Apr 2010 15:32:20 -0600, Aliza Panitz <ali...@gm...> wrote: > On Sun, Apr 11, 2010 at 9:58 PM, alexti <al...@sh...> wrote: >> The first >> graph (let's call it primary graph) is built from the tiles and >> essentially follows one tile - 7 vertices principle (I've described this >> approach before and after some discussion with Stefan we've concluded >> that >> it's identical to the approach he had in mind). Essentially, one vertex >> is >> in the center of the tile and there are 6 vertices, one per tile edge. > > What about double-dit and double-O cities (as well as more complex > tiles that have three disjoint scoring locations...) double-dit and double-O cities are 4-vertex 2-edge tiles (center vertex is not used), so they're easy to describe |
|
From: Alex T. <al...@sh...> - 2010-04-12 04:31:21
|
Hi all, Sorry about my disappearance after raising this question couple of weeks ago. Things weren't standing still; I was in contact with Stefan, but unfortunately circumstances prevented quicker progress. Stefan has added some new functionality to Rails to lay some background framework and to simplify creation of "test problems". He has created few testing scenarios too. My original algorithm has proved to be marginal - on a relatively complex example the time was around 40 seconds. We've discussed various optimizations and I believe we have found good approach. The basic idea is to use two-phased process that runs on two different graphs. The first graph (let's call it primary graph) is built from the tiles and essentially follows one tile - 7 vertices principle (I've described this approach before and after some discussion with Stefan we've concluded that it's identical to the approach he had in mind). Essentially, one vertex is in the center of the tile and there are 6 vertices, one per tile edge. I was envisioning them inside of the tile, on the line connecting the center of the tile edge to the center of the tile (in fact, that's how I was visualizing them in my program) while Stefan was seeing the center of the tile's edge as such vertex (so adjacent tiles would have their vertices on the same spot and those vertices would be connected by [invisible] edge). This obviously describes exactly the same graph and the difference is only in how it can be thought of visually (or displayed). This primary graph is then used to generate secondary "coarse" graph. The only vertices coarse graph has corresponds to the nodes with some value (usually cities and towns). The edges of the coarse graph (I will call also them segments) are defined by possible distinct routes between its vertices. Thus there might be more than one edge connecting the same pair of vertices. This edges are built by running my original algorithm on the primary graph with the constraint requiring every route to contains exactly two nodes (vertices with value) - one at the start and another at the end. Essentially the list of these edges is the list of all possible two city/town routes. Each segment of this graph has additional characteristic - list of segments mutually exclusive with it. There are two types of exclusions - one forbids use of the related segment by any route and another forbids its use only by the same route. The first type of exclusion happens when two segments share some edge of the primary graph and the second type happens when only some vertex of the primary graph is shared (here we only consider non-terminating vertices - ones that are inside of the segment route, those vertices will have no value). This information forms coarse graph. There are multiple advantages in choosing this approach. The value of any route only depends on the nodes (vertices with values) visited, not the intermediate vertices. This considerably reduces number of possibilities to scan and it also allows to optimize the process by using "pre-packed" segment routes between the nodes. The coarse graph is company-independent - it has no token information and can be used to do route computations for any company. The coarse graph can be built incrementally. The most expensive part of building this graph is the search for all possible routes between every pair of nodes. This time can be saved if the coarse graph is updated incrementally when new tiles are laid (or upgraded). We only need to track the routes containing the newly added edges. All remaining routes are unaffected. On the "realistic" 1870 scenario we've used for testing it is taking 2-3 seconds to build coarse graph from scratch (on my rather average computer). If it's built incrementally, this time will virtually disappear. Of course, this leaves a question of game reloading (perhaps it makes more sense to rebuild it non-incrementally when the game is reloaded, or even save the coarse graph itself). The second phase of the process is to run optimal route search on the coarse graph. I am just running my original algorithm on this graph. This part takes care of source stations, hostile station blocking, visiting the same city twice and similar rules (as well as various bonus application). On the example described above this was taking 2-3 seconds. This phase has to be re-run every time on "Run trains" step of the operating round, but this response time seems acceptable. The run times I've mentioned are from my quickly put together implementation of this new approach, so I would imagine it's possible to do better just by refining the implementation and we haven't looked closely at possible algorithmic optimizations of phase 2. There are few possibly optimizations that can be applied to the primary graph too. Stefan has suggested "asterisk-edge" optimization. This is to simplify verification preventing backtracking. Idea is to mark all edges that are within the same tile with "asterisk" and then the rule preventing backtracking becomes very simple: two "asterisk" edges can be traveled consequently only if they're connected at the tile's center. This should help in phase 1 generation. There's some difficulty now though, because I'm using "transient vertex" optimization which can eliminate some edges and thus change adjacency of "asterisk" and "non-asterisk" edges. The transient vertex optimization works in the case when there's a vertex (without value) connected to exactly two other vertices (for example vertex B in A-B-C example). In this case vertex B can be removed and edges (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit, because realistic track build normally has large amount of such vertices. Another (obvious) optimization is dead-end elimination (if vertex has no value and it is connected with one other vertex only it can be eliminated). This optimization should not be used when tracking validity of track lay (for obvious reasons). There were some other ideas, such as caching results of the optimal route search and trying to eliminate some possibilities based on the values of the cities/towns on the map, but we have no concrete approach to exploit them. Hopefully, I haven't forgotten anything important. Stefan, please free to add whatever I've missed. Thanks, Alex. |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-04-12 21:49:46
|
Hi Alex,
thanks for all the input below, it seems that there is really some more
performance improvement possible. And without your proposals I would not have
started such an implementation at all.
Unfortunately I do not have that much time now, but maybe some additions here
are helpful, as I had some troubles understanding your approach first.
The major issue for me was how to get around the "switch" problem: A train is
not allowed to turn around at the end of the switch and you have to leave the
hex to the neighboring one. The major idea of my solution is the definition
of a "greedy" edge: The "virtual" edges connecting the sides of the
neighboring hexes force the traveller on their path, if they came
in "non-greedy" (those are the tracks inside the hex).
In the network graphs generated the non-greedy edges are those annotated with
asteriks. A nice property is that greedyness is dominating if one merges two
edges to eliminate a vertex with only two hexes. The new edge is greedy if at
least one of them was greedy. This implies after optimization most edges are
non-greedy, usually only the brown non-station tiles will be left. This and
the dead-end elimination creates the optimized graphs in Rails.
I have attached the scenario (scenario A) that you talked below for reference
for all others, with the rails save file (does only work with the CVS version
due to the map corrections), a screenshot of the map and the optimized
network graph.
Stefan
PS: I would like to compare the results and the performance of the two
implementations (to know how much improvement is possible ...)
I did not use the exact specification I suggested (due to technical reasons):
There is only one token in E12 and I run an 8 and 10 train.
My solution run finished 12 minutes on my 4 year old laptop. Interestingly it
found already 560 after 1 second, 570 after 1 minute and then 580 after 8
minutes.
Revenue Value:580
Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE,
D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1],
10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE,
L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}
On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
> Hi all,
>
> Sorry about my disappearance after raising this question couple of weeks
> ago. Things weren't standing still; I was in contact with Stefan, but
> unfortunately circumstances prevented quicker progress. Stefan has added
> some new functionality to Rails to lay some background framework and to
> simplify creation of "test problems". He has created few testing scenarios
> too. My original algorithm has proved to be marginal - on a relatively
> complex example the time was around 40 seconds. We've discussed various
> optimizations and I believe we have found good approach. The basic idea is
> to use two-phased process that runs on two different graphs. The first
> graph (let's call it primary graph) is built from the tiles and
> essentially follows one tile - 7 vertices principle (I've described this
> approach before and after some discussion with Stefan we've concluded that
> it's identical to the approach he had in mind). Essentially, one vertex is
> in the center of the tile and there are 6 vertices, one per tile edge. I
> was envisioning them inside of the tile, on the line connecting the center
> of the tile edge to the center of the tile (in fact, that's how I was
> visualizing them in my program) while Stefan was seeing the center of the
> tile's edge as such vertex (so adjacent tiles would have their vertices on
> the same spot and those vertices would be connected by [invisible] edge).
> This obviously describes exactly the same graph and the difference is only
> in how it can be thought of visually (or displayed).
>
> This primary graph is then used to generate secondary "coarse" graph. The
> only vertices coarse graph has corresponds to the nodes with some value
> (usually cities and towns). The edges of the coarse graph (I will call
> also them segments) are defined by possible distinct routes between its
> vertices. Thus there might be more than one edge connecting the same pair
> of vertices. This edges are built by running my original algorithm on the
> primary graph with the constraint requiring every route to contains
> exactly two nodes (vertices with value) - one at the start and another at
> the end. Essentially the list of these edges is the list of all possible
> two city/town routes. Each segment of this graph has additional
> characteristic - list of segments mutually exclusive with it. There are
> two types of exclusions - one forbids use of the related segment by any
> route and another forbids its use only by the same route. The first type
> of exclusion happens when two segments share some edge of the primary
> graph and the second type happens when only some vertex of the primary
> graph is shared (here we only consider non-terminating vertices - ones
> that are inside of the segment route, those vertices will have no value).
> This information forms coarse graph. There are multiple advantages in
> choosing this approach. The value of any route only depends on the nodes
> (vertices with values) visited, not the intermediate vertices. This
> considerably reduces number of possibilities to scan and it also allows to
> optimize the process by using "pre-packed" segment routes between the
> nodes. The coarse graph is company-independent - it has no token
> information and can be used to do route computations for any company. The
> coarse graph can be built incrementally. The most expensive part of
> building this graph is the search for all possible routes between every
> pair of nodes. This time can be saved if the coarse graph is updated
> incrementally when new tiles are laid (or upgraded). We only need to track
> the routes containing the newly added edges. All remaining routes are
> unaffected. On the "realistic" 1870 scenario we've used for testing it is
> taking 2-3 seconds to build coarse graph from scratch (on my rather
> average computer). If it's built incrementally, this time will virtually
> disappear. Of course, this leaves a question of game reloading (perhaps it
> makes more sense to rebuild it non-incrementally when the game is
> reloaded, or even save the coarse graph itself).
>
> The second phase of the process is to run optimal route search on the
> coarse graph. I am just running my original algorithm on this graph. This
> part takes care of source stations, hostile station blocking, visiting the
> same city twice and similar rules (as well as various bonus application).
> On the example described above this was taking 2-3 seconds. This phase has
> to be re-run every time on "Run trains" step of the operating round, but
> this response time seems acceptable. The run times I've mentioned are from
> my quickly put together implementation of this new approach, so I would
> imagine it's possible to do better just by refining the implementation and
> we haven't looked closely at possible algorithmic optimizations of phase 2.
>
> There are few possibly optimizations that can be applied to the primary
> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
> simplify verification preventing backtracking. Idea is to mark all edges
> that are within the same tile with "asterisk" and then the rule preventing
> backtracking becomes very simple: two "asterisk" edges can be traveled
> consequently only if they're connected at the tile's center. This should
> help in phase 1 generation. There's some difficulty now though, because
> I'm using "transient vertex" optimization which can eliminate some edges
> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
> transient vertex optimization works in the case when there's a vertex
> (without value) connected to exactly two other vertices (for example
> vertex B in A-B-C example). In this case vertex B can be removed and edges
> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
> because realistic track build normally has large amount of such vertices.
> Another (obvious) optimization is dead-end elimination (if vertex has no
> value and it is connected with one other vertex only it can be
> eliminated). This optimization should not be used when tracking validity
> of track lay (for obvious reasons).
>
> There were some other ideas, such as caching results of the optimal route
> search and trying to eliminate some possibilities based on the values of
> the cities/towns on the map, but we have no concrete approach to exploit
> them.
>
> Hopefully, I haven't forgotten anything important. Stefan, please free to
> add whatever I've missed.
>
> Thanks,
> Alex.
>
> ---------------------------------------------------------------------------
>--- Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel
|
|
From: alexti <al...@sh...> - 2010-04-13 05:29:03
Attachments:
Screenshot2-1.png
|
Hi Stefan, You have made a lot of progress in implementing route calculation recently :) About the "greedy" edges: (I was calling this optimization "asterisk" optimization in my previous post). I avoid "switch" problem in a different way. My vertex definition is geographical - vertex id is its coordinates. Because of that I can check backtracking differently - my criterion is that two consecutive edges from the same hex are only allowed if they are joined at the center. This can not be derived from the graph definition formally. Essentially I have additional information in the graph that is encoded in the vertex identifiers. When I look at the train routes in your example, the sequence [B11.1, C10.NE, C10.W, C8.NE, D7.NE] doesn't look right to me - C10.W, C8.NE, D7.NE looks like backtracking. I've run the test with the setup similar identical to yours (same stations and trains), it took ~7 seconds on my machine (which is probably somewhat faster than yours, perhaps by factor of 2 or something like that - unless your laptop was really high-end when new). 2.5 seconds to build a coarse graph and 4.5 seconds to find the routes. My total was also 580 and I hope it is valid. I'm actually finding it challenging to validate correctness. Couple of times in my experiments I've seen this algorithm picking rather strange looking routes (not what I would intuitively expected to be the best), but no matter how I tried I couldn't beat them manually :) I don't have any mechanism to output the routes in the text form, so I'm attaching screenshot with those routes highlighted. On my screenshot the picture is transposed, but it doesn't have any effect on the topology of the problem. I do not have any timing indicating when these routes have been found. In a way it doesn't matter right now, until we can somehow tell that no better route is possible. Concerning your algorithm, do you do transient vertex optimization? It is probably the most important optimization on the original (primary as I called it) graph. And it should be easy to implement (because of asterisk/greedy edge approach you'd need to make it somewhat less aggressive so that the resulting edge can preserve correct "greediness". The other big optimization is two-phased approach - it's essentially reduced dimensionality of a problem by a big factor. Another big optimization for me was in efficient memory management, but that could be hard to implement in Java. I'm also not certain if it's that important anymore (since I've switched to the two-phased approach). It would be interesting to see how much change in times you can achieve by removing transient vertices. Another interesting experiment would be to time how long it would take your algorithm to find all possible routes for every city/town pair (that's what is necessary for building coarse graph). I am not sure how easy it would to modify your code to do that. I really appreciate your effort in adding this functionality to Rails. Not being Java specialist I can only help on the algorithmic side. I want to look into how the second phase works now and what can be improved there (algorithmically) so I can share these results. I could also take a look at how to [efficiently] combine transient vertex optimization with the asterisk edge approach. If we decide to go with two-phased approach (and I think we definitely should) and build the coarse graph incrementally, asterisk edge optimization becomes less important. Of course, your implementation needs asterisk edges to check backtracking which complicates things a bit. Would it be easy to be use "geographical" checking? Or is this part of code comes in some library you can't modify? Please let me know what direction you think we should put our efforts. Thanks, Alex. P.S. Sorry, I am unable to reduce the size of the screenshot much more without making it too hard to read. On Mon, 12 Apr 2010 15:49:14 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Hi Alex, > > thanks for all the input below, it seems that there is really some more > performance improvement possible. And without your proposals I would not > have > started such an implementation at all. > > Unfortunately I do not have that much time now, but maybe some additions > here > are helpful, as I had some troubles understanding your approach first. > > The major issue for me was how to get around the "switch" problem: A > train is > not allowed to turn around at the end of the switch and you have to > leave the > hex to the neighboring one. The major idea of my solution is the > definition > of a "greedy" edge: The "virtual" edges connecting the sides of the > neighboring hexes force the traveller on their path, if they came > in "non-greedy" (those are the tracks inside the hex). > > In the network graphs generated the non-greedy edges are those annotated > with > asteriks. A nice property is that greedyness is dominating if one merges > two > edges to eliminate a vertex with only two hexes. The new edge is greedy > if at > least one of them was greedy. This implies after optimization most edges > are > non-greedy, usually only the brown non-station tiles will be left. This > and > the dead-end elimination creates the optimized graphs in Rails. > > I have attached the scenario (scenario A) that you talked below for > reference > for all others, with the rails save file (does only work with the CVS > version > due to the map corrections), a screenshot of the map and the optimized > network graph. > > Stefan > > PS: I would like to compare the results and the performance of the two > implementations (to know how much improvement is possible ...) > > I did not use the exact specification I suggested (due to technical > reasons): > There is only one token in E12 and I run an 8 and 10 train. > > My solution run finished 12 minutes on my 4 year old laptop. > Interestingly it > found already 560 after 1 second, 570 after 1 minute and then 580 after 8 > minutes. > > Revenue Value:580 > Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE, > D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1], > 10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE, > L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]} > > On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote: >> Hi all, >> >> Sorry about my disappearance after raising this question couple of weeks >> ago. Things weren't standing still; I was in contact with Stefan, but >> unfortunately circumstances prevented quicker progress. Stefan has added >> some new functionality to Rails to lay some background framework and to >> simplify creation of "test problems". He has created few testing >> scenarios >> too. My original algorithm has proved to be marginal - on a relatively >> complex example the time was around 40 seconds. We've discussed various >> optimizations and I believe we have found good approach. The basic idea >> is >> to use two-phased process that runs on two different graphs. The first >> graph (let's call it primary graph) is built from the tiles and >> essentially follows one tile - 7 vertices principle (I've described this >> approach before and after some discussion with Stefan we've concluded >> that >> it's identical to the approach he had in mind). Essentially, one vertex >> is >> in the center of the tile and there are 6 vertices, one per tile edge. I >> was envisioning them inside of the tile, on the line connecting the >> center >> of the tile edge to the center of the tile (in fact, that's how I was >> visualizing them in my program) while Stefan was seeing the center of >> the >> tile's edge as such vertex (so adjacent tiles would have their vertices >> on >> the same spot and those vertices would be connected by [invisible] >> edge). >> This obviously describes exactly the same graph and the difference is >> only >> in how it can be thought of visually (or displayed). >> >> This primary graph is then used to generate secondary "coarse" graph. >> The >> only vertices coarse graph has corresponds to the nodes with some value >> (usually cities and towns). The edges of the coarse graph (I will call >> also them segments) are defined by possible distinct routes between its >> vertices. Thus there might be more than one edge connecting the same >> pair >> of vertices. This edges are built by running my original algorithm on >> the >> primary graph with the constraint requiring every route to contains >> exactly two nodes (vertices with value) - one at the start and another >> at >> the end. Essentially the list of these edges is the list of all possible >> two city/town routes. Each segment of this graph has additional >> characteristic - list of segments mutually exclusive with it. There are >> two types of exclusions - one forbids use of the related segment by any >> route and another forbids its use only by the same route. The first type >> of exclusion happens when two segments share some edge of the primary >> graph and the second type happens when only some vertex of the primary >> graph is shared (here we only consider non-terminating vertices - ones >> that are inside of the segment route, those vertices will have no >> value). >> This information forms coarse graph. There are multiple advantages in >> choosing this approach. The value of any route only depends on the nodes >> (vertices with values) visited, not the intermediate vertices. This >> considerably reduces number of possibilities to scan and it also allows >> to >> optimize the process by using "pre-packed" segment routes between the >> nodes. The coarse graph is company-independent - it has no token >> information and can be used to do route computations for any company. >> The >> coarse graph can be built incrementally. The most expensive part of >> building this graph is the search for all possible routes between every >> pair of nodes. This time can be saved if the coarse graph is updated >> incrementally when new tiles are laid (or upgraded). We only need to >> track >> the routes containing the newly added edges. All remaining routes are >> unaffected. On the "realistic" 1870 scenario we've used for testing it >> is >> taking 2-3 seconds to build coarse graph from scratch (on my rather >> average computer). If it's built incrementally, this time will virtually >> disappear. Of course, this leaves a question of game reloading (perhaps >> it >> makes more sense to rebuild it non-incrementally when the game is >> reloaded, or even save the coarse graph itself). >> >> The second phase of the process is to run optimal route search on the >> coarse graph. I am just running my original algorithm on this graph. >> This >> part takes care of source stations, hostile station blocking, visiting >> the >> same city twice and similar rules (as well as various bonus >> application). >> On the example described above this was taking 2-3 seconds. This phase >> has >> to be re-run every time on "Run trains" step of the operating round, but >> this response time seems acceptable. The run times I've mentioned are >> from >> my quickly put together implementation of this new approach, so I would >> imagine it's possible to do better just by refining the implementation >> and >> we haven't looked closely at possible algorithmic optimizations of >> phase 2. >> >> There are few possibly optimizations that can be applied to the primary >> graph too. Stefan has suggested "asterisk-edge" optimization. This is to >> simplify verification preventing backtracking. Idea is to mark all edges >> that are within the same tile with "asterisk" and then the rule >> preventing >> backtracking becomes very simple: two "asterisk" edges can be traveled >> consequently only if they're connected at the tile's center. This should >> help in phase 1 generation. There's some difficulty now though, because >> I'm using "transient vertex" optimization which can eliminate some edges >> and thus change adjacency of "asterisk" and "non-asterisk" edges. The >> transient vertex optimization works in the case when there's a vertex >> (without value) connected to exactly two other vertices (for example >> vertex B in A-B-C example). In this case vertex B can be removed and >> edges >> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit, >> because realistic track build normally has large amount of such >> vertices. >> Another (obvious) optimization is dead-end elimination (if vertex has no >> value and it is connected with one other vertex only it can be >> eliminated). This optimization should not be used when tracking validity >> of track lay (for obvious reasons). >> >> There were some other ideas, such as caching results of the optimal >> route >> search and trying to eliminate some possibilities based on the values of >> the cities/towns on the map, but we have no concrete approach to exploit >> them. >> >> Hopefully, I haven't forgotten anything important. Stefan, please free >> to >> add whatever I've missed. >> >> Thanks, >> Alex. >> >> --------------------------------------------------------------------------- >> --- Download Intel® Parallel Studio Eval >> Try the new software tools for yourself. Speed compiling, find bugs >> proactively, and fine-tune applications for parallel performance. >> See why Intel Parallel Studio got high marks during beta. >> http://p.sf.net/sfu/intel-sw-dev >> _______________________________________________ >> 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: John A. T. <ja...@ja...> - 2010-04-13 15:17:43
|
On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote: > I avoid "switch" problem in a different way. My vertex definition is > geographical - vertex id is its coordinates. Because of that I can check > backtracking differently - my criterion is that two consecutive edges from > the same hex are only allowed if they are joined at the center. This can > not be derived from the graph definition formally. Essentially I have > additional information in the graph that is encoded in the vertex > identifiers. > If I understand you correctly, this will fail for some games with complicated tiles -- also, how does it handle multiple cities per tile? -- John A. Tamplin |
|
From: alexti <al...@sh...> - 2010-04-14 05:46:23
|
On Tue, 13 Apr 2010 09:17:13 -0600, John A. Tamplin <ja...@ja...> wrote: > On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote: > >> I avoid "switch" problem in a different way. My vertex definition is >> geographical - vertex id is its coordinates. Because of that I can check >> backtracking differently - my criterion is that two consecutive edges >> from >> the same hex are only allowed if they are joined at the center. This can >> not be derived from the graph definition formally. Essentially I have >> additional information in the graph that is encoded in the vertex >> identifiers. >> > > If I understand you correctly, this will fail for some games with > complicated tiles -- also, how does it handle multiple cities per tile? That's possible. This method makes several assumptions I thought would cover all existing tiles, but there are plenty of games I am not familiar with. There are two main assumptions: (1) every rail track that leaves the tile always crosses the tile edge in the middle of the edge and does so at the right angle. (2) Every tile can be represented as 7-vertex graph. Consequently, there would be a limit of 7 separate cities per tile. Multiple cities (by that I mean tiles like "OO" or Toronto tile) are handled by assigning different cities to different vertices. There's also a boolean option indicating whether the train is allowed to visit different cities on the same tile or not (I believe this rule is different in different games). Do you have any tiles in mind that wouldn't fit into these assumptions? |
|
From: Dave M. <da...@mi...> - 2010-04-13 17:05:02
|
<html><HEAD><LINK rel=stylesheet type=text/css href="/webmail/static/deg/css/wysiwyg-3451203449.css" media=all>
<META name=GENERATOR content="MSHTML 8.00.6001.18904"></HEAD>
<BODY>
<DIV>I'm not sure what each person has done here, but I'll insert my approach.</DIV>
<DIV> </DIV>
<DIV>For a given tile edge entrance, you have to be able to figure out what it connects to.</DIV>
<DIV>It could be another edge, or a city (of some type). More complex tiles have several cities on them.</DIV>
<DIV>This is the connectivity of the tile/hex expressed by the track graphic and must be encoded for the game.</DIV>
<DIV>Note that this didn't take into account the various "splat" like tiles in some later games.</DIV>
<DIV>These could be handled with a $0 no-token, no-stop city in the middle, if that helps the graphic representation.</DIV>
<DIV> </DIV>
<DIV>For 1830 style tiles I ended up with a system of "locations" that were basically the 6 edges and two internal cities.</DIV>
<DIV>That probably was not enough for some games, but it worked for me.</DIV>
<DIV>I flattened the tile connectivity input down into a bit vector for each edge, that could be rotated as the tile was placed, </DIV>
<DIV>and then wrote a simple function for connection exploration that given an edge in, produced a list of "edges" out.</DIV>
<DIV>
<DIV>After a comparison to see if we've been there already by another route, then the edge "out"s where pushed to the adjacent tile edges to be evaluated.</DIV>
<DIV> </DIV></DIV>
<DIV>Also note that using a bit vector allowed me to produce a tile lay rule where the AND of the existing tile connectivity and the canidate tile </DIV>
<DIV>had to be the same as the existing tile bit vector.</DIV>
<DIV> </DIV>
<DIV>So, I like your graph data structure, but there must be a sense of direction in connections or keep a representation of the edge vertex.</DIV>
<DIV>I think that would preserve the correct connectivity. </DIV>
<DIV> </DIV>
<DIV>Another key issues is how to represent these "coordinates". If you can do this, then you can print out lists of a route for logging and recording.</DIV>
<DIV> </DIV>
<DIV>I went with something like <hexcoord>{<edge a-f>|<city x,y>} e.g. A23d</DIV>
<DIV> </DIV>
<DIV> and if the city had a name a function could bring that up too.</DIV>
<DIV> </DIV>
<DIV>Well, enough rambling...</DIV>
<DIV>Keep up the good work.</DIV>
<DIV>Dave.</DIV>
<DIV> </DIV>
<DIV><BR>Apr 13, 2010 11:17:48 AM, <A class=parsedEmail href="mailto:rai...@li..." target=_blank>rai...@li...</A> wrote:<BR></DIV>
<BLOCKQUOTE style="BORDER-LEFT: rgb(102,153,204) 3px solid">
<DIV class=gmail_quote>On Tue, Apr 13, 2010 at 1:28 AM, alexti <SPAN dir=ltr><<A class=" parsedEmail parsedEmail" href="mailto:al...@sh..." target=_blank>al...@sh...</A>></SPAN> wrote:<BR>
<BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=gmail_quote>I avoid "switch" problem in a different way. My vertex definition is<BR>geographical - vertex id is its coordinates. Because of that I can check<BR>backtracking differently - my criterion is that two consecutive edges from<BR>the same hex are only allowed if they are joined at the center. This can<BR>not be derived from the graph definition formally. Essentially I have<BR>additional information in the graph that is encoded in the vertex<BR>identifiers.<BR></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>If I understand you correctly, this will fail for some games with complicated tiles -- also, how does it handle multiple cities per tile?</DIV>
<DIV><BR></DIV></DIV>-- <BR>John A. Tamplin<BR><BR>
<HR SIZE=1>
<BR>------------------------------------------------------------------------------<BR>Download Intel® Parallel Studio Eval<BR>Try the new software tools for yourself. Speed compiling, find bugs<BR>proactively, and fine-tune applications for parallel performance.<BR>See why Intel Parallel Studio got high marks during beta.<BR><A class=parsedLink href="http://p.sf.net/sfu/intel-sw-dev" target=_blank>http://p.sf.net/sfu/intel-sw-dev</A><BR>
<HR SIZE=1>
<BR>_______________________________________________<BR>Rails-devel mailing list<BR><A class="parsedEmail parsedEmail" href="mailto:Rai...@li..." target=_blank>Rai...@li...</A><BR><A class=parsedLink href="https://lists.sourceforge.net/lists/listinfo/rails-devel" target=_blank>https://lists.sourceforge.net/lists/listinfo/rails-devel</A><BR></BLOCKQUOTE></BODY></html>
|
|
From: alexti <al...@sh...> - 2010-04-14 05:52:22
|
Dave, I'm using similar approach to the one you've described (with minor
differences). "Splat" tiles are represented by all possible connectivity
links (so the graph representation is the same as it would be to the
"traditional" equivalent of "splat" tile. Unlike your approach I don't
have separate city entities in the graph - they're simply attached to the
vertices. So, for example, in 1861 yellow Moscow tile there will be 3
cities attached to NW,NE and S vertices.
As far as text coordinates go I like "compass" identification - it seems
most intuitive.
On Tue, 13 Apr 2010 11:04:54 -0600, Dave Mitton <da...@mi...> wrote:
> I'm not sure what each person has done here, but I'll insert my approach.
>
> For a given tile edge entrance, you have to be able to figure out what it
> connects to.
>
> It could be another edge, or a city (of some type). More complex tiles
> have
> several cities on them.
>
> This is the connectivity of the tile/hex expressed by the track graphic
> and must
> be encoded for the game.
>
> Note that this didn't take into account the various "splat" like tiles
> in some
> later games.
>
> These could be handled with a $0 no-token, no-stop city in the middle,
> if that
> helps the graphic representation.
>
> For 1830 style tiles I ended up with a system of "locations" that were
> basically
> the 6 edges and two internal cities.
>
> That probably was not enough for some games, but it worked for me.
>
> I flattened the tile connectivity input down into a bit vector for each
> edge,
> that could be rotated as the tile was placed,
>
> and then wrote a simple function for connection exploration that given
> an edge
> in, produced a list of "edges" out.
>
> After a comparison to see if we've been there already by another route,
> then the
> edge "out"s where pushed to the adjacent tile edges to be evaluated.
>
> Also note that using a bit vector allowed me to produce a tile lay rule
> where
> the AND of the existing tile connectivity and the canidate tile
>
> had to be the same as the existing tile bit vector.
>
> So, I like your graph data structure, but there must be a sense of
> direction in
> connections or keep a representation of the edge vertex.
>
> I think that would preserve the correct connectivity.
>
> Another key issues is how to represent these "coordinates". If you can
> do this,
> then you can print out lists of a route for logging and recording.
>
> I went with something like <hexcoord>{<edge a-f>|<city x,y>} e.g. A23d
>
> and if the city had a name a function could bring that up too.
>
> Well, enough rambling...
>
> Keep up the good work.
>
> Dave.
>
>
> Apr 13, 2010 11:17:48 AM, rai...@li... wrote:
>
> On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote:
>
> I avoid "switch" problem in a different way. My vertex definition is
> geographical - vertex id is its coordinates. Because of that I can check
> backtracking differently - my criterion is that two consecutive edges
> from
> the same hex are only allowed if they are joined at the center. This can
> not be derived from the graph definition formally. Essentially I have
> additional information in the graph that is encoded in the vertex
> identifiers.
>
>
> If I understand you correctly, this will fail for some games with
> complicated
> tiles -- also, how does it handle multiple cities per tile?
>
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
|
|
From: Erik V. <eri...@xs...> - 2010-04-13 19:12:29
|
I tried a 4-train and it backtracked on hex C8. My simple and fast rule would be: if a route reaches a tile edge, then that edge *must* be crossed. If this simple rule does not fit well into graphs, I'd say: too bad for the graphs, perhaps we need a different approach. On debug logging: once a feature reaches stability, I usually cut down debug logging to a sustainable level. On reloading: yes, I think route detection should start after loading has completed. Erik. -----Original Message----- From: Stefan Frey (web.de) [mailto:ste...@we...] Sent: Monday 12 April 2010 23:49 To: Development list for Rails: an 18xx game Subject: Re: [Rails-devel] Automatic route calculation Hi Alex, thanks for all the input below, it seems that there is really some more performance improvement possible. And without your proposals I would not have started such an implementation at all. Unfortunately I do not have that much time now, but maybe some additions here are helpful, as I had some troubles understanding your approach first. The major issue for me was how to get around the "switch" problem: A train is not allowed to turn around at the end of the switch and you have to leave the hex to the neighboring one. The major idea of my solution is the definition of a "greedy" edge: The "virtual" edges connecting the sides of the neighboring hexes force the traveller on their path, if they came in "non-greedy" (those are the tracks inside the hex). In the network graphs generated the non-greedy edges are those annotated with asteriks. A nice property is that greedyness is dominating if one merges two edges to eliminate a vertex with only two hexes. The new edge is greedy if at least one of them was greedy. This implies after optimization most edges are non-greedy, usually only the brown non-station tiles will be left. This and the dead-end elimination creates the optimized graphs in Rails. I have attached the scenario (scenario A) that you talked below for reference for all others, with the rails save file (does only work with the CVS version due to the map corrections), a screenshot of the map and the optimized network graph. Stefan PS: I would like to compare the results and the performance of the two implementations (to know how much improvement is possible ...) I did not use the exact specification I suggested (due to technical reasons): There is only one token in E12 and I run an 8 and 10 train. My solution run finished 12 minutes on my 4 year old laptop. Interestingly it found already 560 after 1 second, 570 after 1 minute and then 580 after 8 minutes. Revenue Value:580 Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE, D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1], 10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE, L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]} On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote: > Hi all, > > Sorry about my disappearance after raising this question couple of weeks > ago. Things weren't standing still; I was in contact with Stefan, but > unfortunately circumstances prevented quicker progress. Stefan has added > some new functionality to Rails to lay some background framework and to > simplify creation of "test problems". He has created few testing scenarios > too. My original algorithm has proved to be marginal - on a relatively > complex example the time was around 40 seconds. We've discussed various > optimizations and I believe we have found good approach. The basic idea is > to use two-phased process that runs on two different graphs. The first > graph (let's call it primary graph) is built from the tiles and > essentially follows one tile - 7 vertices principle (I've described this > approach before and after some discussion with Stefan we've concluded that > it's identical to the approach he had in mind). Essentially, one vertex is > in the center of the tile and there are 6 vertices, one per tile edge. I > was envisioning them inside of the tile, on the line connecting the center > of the tile edge to the center of the tile (in fact, that's how I was > visualizing them in my program) while Stefan was seeing the center of the > tile's edge as such vertex (so adjacent tiles would have their vertices on > the same spot and those vertices would be connected by [invisible] edge). > This obviously describes exactly the same graph and the difference is only > in how it can be thought of visually (or displayed). > > This primary graph is then used to generate secondary "coarse" graph. The > only vertices coarse graph has corresponds to the nodes with some value > (usually cities and towns). The edges of the coarse graph (I will call > also them segments) are defined by possible distinct routes between its > vertices. Thus there might be more than one edge connecting the same pair > of vertices. This edges are built by running my original algorithm on the > primary graph with the constraint requiring every route to contains > exactly two nodes (vertices with value) - one at the start and another at > the end. Essentially the list of these edges is the list of all possible > two city/town routes. Each segment of this graph has additional > characteristic - list of segments mutually exclusive with it. There are > two types of exclusions - one forbids use of the related segment by any > route and another forbids its use only by the same route. The first type > of exclusion happens when two segments share some edge of the primary > graph and the second type happens when only some vertex of the primary > graph is shared (here we only consider non-terminating vertices - ones > that are inside of the segment route, those vertices will have no value). > This information forms coarse graph. There are multiple advantages in > choosing this approach. The value of any route only depends on the nodes > (vertices with values) visited, not the intermediate vertices. This > considerably reduces number of possibilities to scan and it also allows to > optimize the process by using "pre-packed" segment routes between the > nodes. The coarse graph is company-independent - it has no token > information and can be used to do route computations for any company. The > coarse graph can be built incrementally. The most expensive part of > building this graph is the search for all possible routes between every > pair of nodes. This time can be saved if the coarse graph is updated > incrementally when new tiles are laid (or upgraded). We only need to track > the routes containing the newly added edges. All remaining routes are > unaffected. On the "realistic" 1870 scenario we've used for testing it is > taking 2-3 seconds to build coarse graph from scratch (on my rather > average computer). If it's built incrementally, this time will virtually > disappear. Of course, this leaves a question of game reloading (perhaps it > makes more sense to rebuild it non-incrementally when the game is > reloaded, or even save the coarse graph itself). > > The second phase of the process is to run optimal route search on the > coarse graph. I am just running my original algorithm on this graph. This > part takes care of source stations, hostile station blocking, visiting the > same city twice and similar rules (as well as various bonus application). > On the example described above this was taking 2-3 seconds. This phase has > to be re-run every time on "Run trains" step of the operating round, but > this response time seems acceptable. The run times I've mentioned are from > my quickly put together implementation of this new approach, so I would > imagine it's possible to do better just by refining the implementation and > we haven't looked closely at possible algorithmic optimizations of phase 2. > > There are few possibly optimizations that can be applied to the primary > graph too. Stefan has suggested "asterisk-edge" optimization. This is to > simplify verification preventing backtracking. Idea is to mark all edges > that are within the same tile with "asterisk" and then the rule preventing > backtracking becomes very simple: two "asterisk" edges can be traveled > consequently only if they're connected at the tile's center. This should > help in phase 1 generation. There's some difficulty now though, because > I'm using "transient vertex" optimization which can eliminate some edges > and thus change adjacency of "asterisk" and "non-asterisk" edges. The > transient vertex optimization works in the case when there's a vertex > (without value) connected to exactly two other vertices (for example > vertex B in A-B-C example). In this case vertex B can be removed and edges > (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit, > because realistic track build normally has large amount of such vertices. > Another (obvious) optimization is dead-end elimination (if vertex has no > value and it is connected with one other vertex only it can be > eliminated). This optimization should not be used when tracking validity > of track lay (for obvious reasons). > > There were some other ideas, such as caching results of the optimal route > search and trying to eliminate some possibilities based on the values of > the cities/towns on the map, but we have no concrete approach to exploit > them. > > Hopefully, I haven't forgotten anything important. Stefan, please free to > add whatever I've missed. > > Thanks, > Alex. > > --------------------------------------------------------------------------- >--- Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > Rails-devel mailing list > Rai...@li... > https://lists.sourceforge.net/lists/listinfo/rails-devel |
|
From: Erik V. <eri...@xs...> - 2010-04-13 19:22:32
|
Note that this didn't take into account the various "splat" like tiles in some later games.These could be handled with a $0 no-token, no-stop city in the middle, if that helps the graphic representation. This wouldn't work, as a city can be visited only once. In Rails, the graphics and the graphs are completely separate. The "new" tiles #81 etc, as in 18EU (visually represented as 3 tracks meeting in the center), are internally represented the same way as the "old" versions: with 3 separate tracks connecting 3 edges. Same thing can be done with 4- and even 6-edge connect-all tiles. So this is not really a problem. Erik. |
|
From: Dave M. <da...@mi...> - 2010-04-14 01:22:51
|
<html> <body> On 4/13/2010 03:22 PM, Erik Vos wrote:<br> <blockquote type=cite class=cite cite=""> <font face="Arial, Helvetica" size=2 color="#0000FF"> </font>Note that this didn't take into account the various "splat" like tiles in some later games.These could be handled with a $0 no-token, no-stop city in the middle, if that helps the graphic representation.<font face="Arial, Helvetica" size=2 color="#0000FF"> <br> </font> <br> <font face="Arial, Helvetica" size=2 color="#0000FF">This wouldn't work, as a city can be visited only once. </font></blockquote><br> You're going to have to work on that for some types of trains. Like those that ignore some types of cities.<br><br> The point was to make it a vertex for connectivity sake. The details would have to be worked out for the implementation.<br><br> <blockquote type=cite class=cite cite=""> <br> <font face="Arial, Helvetica" size=2 color="#0000FF">In Rails, the graphics and the</font> <font face="Arial, Helvetica" size=2 color="#0000FF">graphs are completely separate. The "new" tiles #81 etc, as in 18EU (visually represented as 3 tracks meeting in the center), are internally represented the same way as the "old" versions: with 3 separate tracks connecting 3 edges. Same thing can be done with 4- and even 6-edge connect-all tiles. So this is not really a problem.<br> </font> <br> <font face="Arial, Helvetica" size=2 color="#0000FF">Erik.</font> </blockquote><br> I've seen that in one of the examples, but I'm not sure that the necessary only way to do that. In my implementation, the it was possible to draw the route in a different color directly replacing tile track. That simply required the route highlighting code to call the track draw code on a per segment basis.<br><br> My map and route code simply used the same UI routines to draw the track. It's not hard if you have a unifying concept underneath.<br><br> FWIW:<br> Dave.<br><br> </body> </html> |
|
From: brett l. <bre...@gm...> - 2010-04-14 01:42:02
|
On Tue, Apr 13, 2010 at 6:15 PM, Dave Mitton <da...@mi...> wrote: > On 4/13/2010 03:22 PM, Erik Vos wrote: > > Note that this didn't take into account the various "splat" like > tiles in some later games.These could be handled with a $0 no-token, no-stop > city in the middle, if that helps the graphic representation. > > This wouldn't work, as a city can be visited only once. This really depends on the game. Some games allow re-visiting cities as long as the route taken isn't using the same segment of track more than once. I believe 1830 has no restriction for visiting the same city multiple times, so long as track isn't duplicated. Also, there's OO cities where it's legal to hit different "sides" of the same city with the same train on a single run even if hitting the same city with the same train is otherwise forbidden. ---Brett. |
|
From: Dave M. <da...@mi...> - 2010-04-14 01:56:07
|
On 4/13/2010 09:41 PM, brett lentz wrote: >On Tue, Apr 13, 2010 at 6:15 PM, Dave Mitton <da...@mi...> wrote: > > On 4/13/2010 03:22 PM, Erik Vos wrote: > > > > Note that this didn't take into account the various "splat" like > > tiles in some later games.These could be handled with a $0 > no-token, no-stop > > city in the middle, if that helps the graphic representation. > > > > This wouldn't work, as a city can be visited only once. > > >This really depends on the game. > >Some games allow re-visiting cities as long as the route taken isn't >using the same segment of track more than once. > >I believe 1830 has no restriction for visiting the same city multiple >times, so long as track isn't duplicated. > >Also, there's OO cities where it's legal to hit different "sides" of >the same city with the same train on a single run even if hitting the >same city with the same train is otherwise forbidden. In which case they shouldn't be considered the "same" city. Consider that a hex can contain multiple cities. Invent a nomenclature that works. Here's the problem that drove me nuts; How to keep track of which OO city is has the Erie home base token on it, given whatever rotation of the OO Green and then Brown tile is placed. You will want to paint the token on the right one. Hint: it comes back to the connectivity. The city follows the prior connectivity of the hex/tile. Dave. >---Brett. > >------------------------------------------------------------------------------ >Download Intel® Parallel Studio Eval >Try the new software tools for yourself. Speed compiling, find bugs >proactively, and fine-tune applications for parallel performance. >See why Intel Parallel Studio got high marks during beta. >http://p.sf.net/sfu/intel-sw-dev >_______________________________________________ >Rails-devel mailing list >Rai...@li... >https://lists.sourceforge.net/lists/listinfo/rails-devel |
|
From: Stefan F. (web.de) <ste...@we...> - 2010-04-13 23:01:50
Attachments:
revenue_discussion.txt
|
Hi Alex and all others... ... discussing revenue calculation. It seems to spur a lot of interest. Sorry for the long post (if one includes the text document), but I try to answer most of the asked and some of the not-yet asked questions. And it seems that the algorithms already improve from the fruitful discussion. Some talk about the concepts are in the attached text document, that was easier to edit. This is the good thing of commit early and often. One of its disadvantages are the embarrassing errors in the early releases. I list those at the end of the attachment and hopefully it will clarify some of the problems you ran into. Good news first: * Running Times After hunting them down and adding a new concept (the revenue prediction - see attachment) evaluation time is now down to 1-2 seconds for a 8 and 10 train on the A scenario on my laptop. Without revenue prediction it runs for 1-2 minutes. Both runs have identical results. * Optimal Solution (?) The other thing is that my implementation suggests a (slightly) different path than Alex' which results in an increase of revenue. The change is that the 8 train does not have the 10 - 30 - 30 ( that is Alexandria and Baton Rouge in 1870, the right bottom in Alex graph - it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and SouthWest on the map, the right top in Alex graph). Thus it runs for 20 more. It now pays off that we have independent algorithms running, that can find flaws in each others (like you did for mine). Stefan |
|
From: alexti <al...@sh...> - 2010-04-14 06:00:24
|
Hi Stefan,
Don't worry about embarrassing errors! I have one somewhere and I don't
even know where :) - I don't know why my algorithm doesn't find the
optimal solution you've mentioned - it's supposed to, it's completely
brute force and it should check every combination, but apparently it
doesn't. I suspect I have a bug in my new 2-phased code where I determine
which segments connecting cities are mutually exclusive.
I wonder, how do you plan to do the "best route estimates" in general.
When the various train and bonus rules are added ("free" towns, express
trains, doubling trains, East-West runs, bonuses for connecting pairs of
cities etc...) evaluating what should be in the optimal route is going to
be rather complex. It's also important to figure out how to quickly find
pretty good set of routes, thus cutting off a lot of the search tree.
The times start to look promising, even the complete run finishing in 1-2
minutes is pretty good. With one-phased algorithm it was taking ~40
seconds on my machine to do complete search.
Thanks,
Alex.
On Tue, 13 Apr 2010 17:01:37 -0600, Stefan Frey (web.de)
<ste...@we...> wrote:
> Hi Alex and all others...
> ... discussing revenue calculation. It seems to spur a lot of interest.
>
> Sorry for the long post (if one includes the text document), but I try to
> answer most of the asked and some of the not-yet asked questions.
> And it seems that the algorithms already improve from the fruitful
> discussion.
>
> Some talk about the concepts are in the attached text document, that was
> easier to edit.
>
> This is the good thing of commit early and often. One of its
> disadvantages are
> the embarrassing errors in the early releases. I list those at the end
> of the
> attachment and hopefully it will clarify some of the problems you ran
> into.
>
> Good news first:
>
> * Running Times
> After hunting them down and adding a new concept (the revenue prediction
> - see
> attachment) evaluation time is now down to 1-2 seconds for a 8 and 10
> train
> on the A scenario on my laptop. Without revenue prediction it runs for
> 1-2
> minutes. Both runs have identical results.
>
> * Optimal Solution (?)
> The other thing is that my implementation suggests a (slightly)
> different path
> than Alex' which results in an increase of revenue.
> The change is that the 8 train does not have the 10 - 30 - 30 (
> that is Alexandria and Baton Rouge in 1870, the right bottom in Alex
> graph -
> it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and
> SouthWest
> on the map, the right top in Alex graph). Thus it runs for 20 more.
>
> It now pays off that we have independent algorithms running, that can
> find
> flaws in each others (like you did for mine).
>
> Stefan
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
|
|
From: Stefan F. <ste...@we...> - 2010-04-16 16:36:23
|
Hi Alex,
I do not have much time now, but I will try to give some answers below.
On Wednesday 14 April 2010 08:00:19 alexti wrote:
> Hi Stefan,
>
> Don't worry about embarrassing errors! I have one somewhere and I don't
> even know where :) - I don't know why my algorithm doesn't find the
> optimal solution you've mentioned - it's supposed to, it's completely
> brute force and it should check every combination, but apparently it
> doesn't. I suspect I have a bug in my new 2-phased code where I determine
> which segments connecting cities are mutually exclusive.
My guess for a potential reason and my main problem how efficient your 2-phase
approach is: Does you really create all possible paths between two stations
in the first phase? This could be a quite large set, I assume, or do you rule
some out, because they appear to be not optimal? And if I follow your
approach correctly, you need a two dimensional boolean array of that squared
size, to indicate which potential routes share at least one edge.
I really like the idea, but I would like to know the dimension of that array
first. The really neat thing is that it can be combined with revenue
prediction and would allow really fast solutions for even more complex case,
when we have considered so far.
>
> I wonder, how do you plan to do the "best route estimates" in general.
> When the various train and bonus rules are added ("free" towns, express
> trains, doubling trains, East-West runs, bonuses for connecting pairs of
> cities etc...) evaluating what should be in the optimal route is going to
> be rather complex. It's also important to figure out how to quickly find
> pretty good set of routes, thus cutting off a lot of the search tree.
A very condense answer here:
A) The revenue prediction at each point of the search tracks divides the set
of trains into two subsets, which I call past and future trains. The same is
true for the current train, which can be separated into a past (half-)train
and a future (half-)train as well: Assume it is a 10 train, which has visited
a 4 stations already. That is a 4 past train and a 6 future train.
B) Past trains are evaluated with revenue function like you do. For the future
trains there exist two lists (one for cities, one for towns) of the maximum
amount of revenue you can generate for a given length. Those lists are the
cumulated revenue of the stations sorted by revenue potential. For the
current train there is the additional cap that the combination of the past
value and the future value of the half train cannot exceed the future value
of the full train length.
C) During preparation I even cut train lengths to the maximum amount of
stations which are available to the railroad. Thus a Diesel is in fact a nb
of stations length train and if a railroad reaches 3 cities and 10 towns and
runs a 5+5 train, it gets converted to a 3+7.
That helps to determine that I can terminate a running train, because there
are no more stations out to visit.
D) Trains are characterized by 5 attributes so far: cities, towns,
ignoreTowns, multiplyCities, multiplyTowns.
This allows to define the train types you suggested above.
express = ignoreTowns set to true
free towns = set towns for each train to the maximum of towns the railroad has
doubling trains = use the multiples
The prediction function uses the multiplier and the train lengths similar
to the evaluation function.
E) Bonuses
I have not incorporated any kind of bonus so far. My current idea is to define
bonuses by combinations of vertexes which have to be visited to get the
bonus.
The bonus itself can be revenue increase (or even decrease think about the
elbe crossing in HH) or change of the cities or town multipliers.
Sometimes the bonuses are mutually exclusive or only available to one train
instead of all of them. I would like to make that definition as generic as
possible to capture most of the types.
For prediction the thing is simple: In general I assume that a future train
will score each and every bonus, unless it is already used by a past train
(and it was a bonus which is only available once). By this assumption I am on
the safe side.
F) Finding a good route quickly
One optimization I do:
I sort all vertexes by revenue potential and by this at each junction the
train moves to the vertex with the best revenue potential and it starts at
the most valuable start vertex.
The other thing is that the search is depth-first, thus each train will try to
run as long as possible. The latter combinations are usually those which are
shorter. From my experience the best solution is always found in the first
5-10% of the running time (if it runs without revenue predicition).
But one could easily create degenerated networks, that will make the
prediction completely worthless: Consider that each station is surrounded by
a complex network of tracks, but each station is not linked to any other. In
that case the best run will be zero, but it will take a lot of time to find
this out. In that case your algorithm will excel.
But how often do find that case in 18xx?
I hope that gives some more insight.
Stefan
>
> The times start to look promising, even the complete run finishing in 1-2
> minutes is pretty good. With one-phased algorithm it was taking ~40
> seconds on my machine to do complete search.
>
> Thanks,
> Alex.
>
>
> On Tue, 13 Apr 2010 17:01:37 -0600, Stefan Frey (web.de)
>
> <ste...@we...> wrote:
> > Hi Alex and all others...
> > ... discussing revenue calculation. It seems to spur a lot of interest.
> >
> > Sorry for the long post (if one includes the text document), but I try to
> > answer most of the asked and some of the not-yet asked questions.
> > And it seems that the algorithms already improve from the fruitful
> > discussion.
> >
> > Some talk about the concepts are in the attached text document, that was
> > easier to edit.
> >
> > This is the good thing of commit early and often. One of its
> > disadvantages are
> > the embarrassing errors in the early releases. I list those at the end
> > of the
> > attachment and hopefully it will clarify some of the problems you ran
> > into.
> >
> > Good news first:
> >
> > * Running Times
> > After hunting them down and adding a new concept (the revenue prediction
> > - see
> > attachment) evaluation time is now down to 1-2 seconds for a 8 and 10
> > train
> > on the A scenario on my laptop. Without revenue prediction it runs for
> > 1-2
> > minutes. Both runs have identical results.
> >
> > * Optimal Solution (?)
> > The other thing is that my implementation suggests a (slightly)
> > different path
> > than Alex' which results in an increase of revenue.
> > The change is that the 8 train does not have the 10 - 30 - 30 (
> > that is Alexandria and Baton Rouge in 1870, the right bottom in Alex
> > graph -
> > it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and
> > SouthWest
> > on the map, the right top in Alex graph). Thus it runs for 20 more.
> >
> > It now pays off that we have independent algorithms running, that can
> > find
> > flaws in each others (like you did for mine).
> >
> > Stefan
|
|
From: alexti <al...@sh...> - 2010-04-17 04:42:01
|
Hi Stefan,
On Fri, 16 Apr 2010 10:36:14 -0600, Stefan Frey <ste...@we...> wrote:
> Hi Alex,
> I do not have much time now, but I will try to give some answers below.
>
> On Wednesday 14 April 2010 08:00:19 alexti wrote:
>> Hi Stefan,
>>
>> Don't worry about embarrassing errors! I have one somewhere and I don't
>> even know where :) - I don't know why my algorithm doesn't find the
>> optimal solution you've mentioned - it's supposed to, it's completely
>> brute force and it should check every combination, but apparently it
>> doesn't. I suspect I have a bug in my new 2-phased code where I
>> determine
>> which segments connecting cities are mutually exclusive.
>
> My guess for a potential reason and my main problem how efficient your
> 2-phase
> approach is: Does you really create all possible paths between two
> stations
> in the first phase? This could be a quite large set, I assume, or do you
> rule
> some out, because they appear to be not optimal? And if I follow your
> approach correctly, you need a two dimensional boolean array of that
> squared
> size, to indicate which potential routes share at least one edge.
Yes, I create all possible direct routes (not visiting anything else of
value) for each city pair.
The number of those doesn't seem to be very large. Typically, you will
rarely see more than 50 city/towns on the map, so that's 2500 pairs and
it's hard to imagine that there would be more than 4 routes per pair on
average, so 10000 seems like a reasonable upper bound. 2D-boolean array
would take 10^4*10^4/8 ~ 10Mb which is not a big issue. In practice I
don't actually use 2-D boolean array - instead for each segment I keep a
list of segment ids it shares edges with, but I suspect that from the
performance point of view 2-D boolean array is a better option. I'm going
to try it when I get time. It's probably necessary two have 2 such arrays
- one for shared edges and another for shared vertices (to allow quick
check for the single-train route).
>
> I really like the idea, but I would like to know the dimension of that
> array
> first. The really neat thing is that it can be combined with revenue
> prediction and would allow really fast solutions for even more complex
> case,
> when we have considered so far.
Yes, those approaches can be combined perfectly.
>> I wonder, how do you plan to do the "best route estimates" in general.
>> When the various train and bonus rules are added ("free" towns, express
>> trains, doubling trains, East-West runs, bonuses for connecting pairs of
>> cities etc...) evaluating what should be in the optimal route is going
>> to
>> be rather complex. It's also important to figure out how to quickly find
>> pretty good set of routes, thus cutting off a lot of the search tree.
>
> A very condense answer here:
>
> A) The revenue prediction at each point of the search tracks divides the
> set
> of trains into two subsets, which I call past and future trains. The
> same is
> true for the current train, which can be separated into a past
> (half-)train
> and a future (half-)train as well: Assume it is a 10 train, which has
> visited
> a 4 stations already. That is a 4 past train and a 6 future train.
>
> B) Past trains are evaluated with revenue function like you do. For the
> future
> trains there exist two lists (one for cities, one for towns) of the
> maximum
> amount of revenue you can generate for a given length. Those lists are
> the
> cumulated revenue of the stations sorted by revenue potential. For the
> current train there is the additional cap that the combination of the
> past
> value and the future value of the half train cannot exceed the future
> value
> of the full train length.
>
> C) During preparation I even cut train lengths to the maximum amount of
> stations which are available to the railroad. Thus a Diesel is in fact a
> nb
> of stations length train and if a railroad reaches 3 cities and 10 towns
> and
> runs a 5+5 train, it gets converted to a 3+7.
> That helps to determine that I can terminate a running train, because
> there
> are no more stations out to visit.
>
> D) Trains are characterized by 5 attributes so far: cities, towns,
> ignoreTowns, multiplyCities, multiplyTowns.
>
> This allows to define the train types you suggested above.
> express = ignoreTowns set to true
> free towns = set towns for each train to the maximum of towns the
> railroad has
> doubling trains = use the multiples
> The prediction function uses the multiplier and the train lengths similar
> to the evaluation function.
>
> E) Bonuses
> I have not incorporated any kind of bonus so far. My current idea is to
> define
> bonuses by combinations of vertexes which have to be visited to get the
> bonus.
>
> The bonus itself can be revenue increase (or even decrease think about
> the
> elbe crossing in HH) or change of the cities or town multipliers.
> Sometimes the bonuses are mutually exclusive or only available to one
> train
> instead of all of them. I would like to make that definition as generic
> as
> possible to capture most of the types.
>
> For prediction the thing is simple: In general I assume that a future
> train
> will score each and every bonus, unless it is already used by a past
> train
> (and it was a bonus which is only available once). By this assumption I
> am on
> the safe side.
Ok, I got the idea. It makes sense to me. Efficiency of it will probably
vary depending on the game - those that have a lot of "free" towns, or
those that have massive bonuses would make it harder to cut down the
search tree quickly.
And I agree with your approach to bonuses - that's what I'm doing too.
Defining (and applying) them is not hard.
> F) Finding a good route quickly
> One optimization I do:
> I sort all vertexes by revenue potential and by this at each junction the
> train moves to the vertex with the best revenue potential and it starts
> at
> the most valuable start vertex.
That's a good idea. I suppose if we combine it with 2-phased approach we
could just look at the most valuable cities and try to find a route
linking them which should be very quick, then we'll have a good chance
that most of the rest of the search tree will be cut off.
I also think that with 2-phased approach it's probably worth removing
unreachable part of the graph (due to station blocking). In my experience
(of some cut-throat games) it's very typical that companies are rather
restricted in what they can reach :)
Thanks,
Alex.
> The other thing is that the search is depth-first, thus each train will
> try to
> run as long as possible. The latter combinations are usually those which
> are
> shorter. From my experience the best solution is always found in the
> first
> 5-10% of the running time (if it runs without revenue predicition).
>
> But one could easily create degenerated networks, that will make the
> prediction completely worthless: Consider that each station is
> surrounded by
> a complex network of tracks, but each station is not linked to any
> other. In
> that case the best run will be zero, but it will take a lot of time to
> find
> this out. In that case your algorithm will excel.
> But how often do find that case in 18xx?
>
> I hope that gives some more insight.
>
> Stefan
>
>>
>> The times start to look promising, even the complete run finishing in
>> 1-2
>> minutes is pretty good. With one-phased algorithm it was taking ~40
>> seconds on my machine to do complete search.
>>
>> Thanks,
>> Alex.
>>
>>
>> On Tue, 13 Apr 2010 17:01:37 -0600, Stefan Frey (web.de)
>>
>> <ste...@we...> wrote:
>> > Hi Alex and all others...
>> > ... discussing revenue calculation. It seems to spur a lot of
>> interest.
>> >
>> > Sorry for the long post (if one includes the text document), but I
>> try to
>> > answer most of the asked and some of the not-yet asked questions.
>> > And it seems that the algorithms already improve from the fruitful
>> > discussion.
>> >
>> > Some talk about the concepts are in the attached text document, that
>> was
>> > easier to edit.
>> >
>> > This is the good thing of commit early and often. One of its
>> > disadvantages are
>> > the embarrassing errors in the early releases. I list those at the end
>> > of the
>> > attachment and hopefully it will clarify some of the problems you ran
>> > into.
>> >
>> > Good news first:
>> >
>> > * Running Times
>> > After hunting them down and adding a new concept (the revenue
>> prediction
>> > - see
>> > attachment) evaluation time is now down to 1-2 seconds for a 8 and 10
>> > train
>> > on the A scenario on my laptop. Without revenue prediction it runs for
>> > 1-2
>> > minutes. Both runs have identical results.
>> >
>> > * Optimal Solution (?)
>> > The other thing is that my implementation suggests a (slightly)
>> > different path
>> > than Alex' which results in an increase of revenue.
>> > The change is that the 8 train does not have the 10 - 30 - 30 (
>> > that is Alexandria and Baton Rouge in 1870, the right bottom in Alex
>> > graph -
>> > it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and
>> > SouthWest
>> > on the map, the right top in Alex graph). Thus it runs for 20 more.
>> >
>> > It now pays off that we have independent algorithms running, that can
>> > find
>> > flaws in each others (like you did for mine).
>> >
>> > Stefan
>
>
>
> ------------------------------------------------------------------------------
> Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> 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: John A. T. <ja...@ja...> - 2010-03-21 00:46:05
|
Yes, though see the archives for details about why it may be harder than you think. John A. Tamplin (Android) On Mar 20, 2010 8:12 PM, "Alex Tikhonov" <al...@sh...> wrote: Hi all, Per Brett Lentz suggestion I am moving this discussion here and reporting my message from 18x yahoo group. This is my first post here, but I have been lurking for a while. I wonder if there is an interest in adding automatic route calculation to Rails. I am trying to create AI for some of the games (and no, it's not going well), but as a side effect I have code that computes the routes. It supports some of more widely used rules (various town treatment, city and route bonuses, multipliers etc). It runs on an abstract connectivity graph, so it should not be too hard to integrate. Alex. ------------------------------------------------------------------------------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ Rails-devel mailing list Rai...@li... https://lists.sourceforge.net/lists/listinfo/rails-devel |
|
From: alexti <al...@sh...> - 2010-03-21 05:43:53
|
I am not completely sure if you were referring to the difficulties of the algorithm or the difficulties of the integration, but I assume it's former. Perhaps I should explain how the algorithm works to make things more clear. There are two parts to the algorithm - route selection and route evaluation. Route selection is performed on the abstract connectivity graph (which is a vector of edges and a associative map of vertices). Each edge is a pair of vertex coordinates on 2-D grid (I use specific encoding that allows to go between these vertices and hexes (or tiles) and back by simple arithmetics). Vertex information contains some basic data, such as whether there is a town at this vertex, if it's blocked [by station markers of other companies], current town/city value etc... The way this connectivity graph is defined takes care of handling use of track segments and visiting same cities. It would be easier to show he method on the picture, but I will try to describe it here. Let's say we have a hex oriented so that one side is facing north, another south and the other 4 NW, SW, NE and SE. For each hex there will be 13 vertices. One in the center (#0), 6 vertices each in the middle of the hex edge (#1-#6, #1 is North, counting clockwise) and 6 more in the middle of the line connecting each of vertices #1-#6 to the center. Vertices #1-#6 will be shared with other adjacent hexes. Let's say we have green Y tile (two gently curving tracks from S to NW and from S to NE). Connectivity graph for such tile will be (2-8,8-10,10-4,6-12,12-10). 10-4 edge represents the bottom of "Y" and this ensures that only one of the track segments on this tile can be used. This definition method also takes care of defining tiles such as yellow and green Toronto from 1856 or Moscow from 1861. In general the search for optimal routes work by selecting a route, evaluating its value, removing the used edges from the graph and running the search again on the remaining graph (with remaining trains). Then choosing the "next" route and repeating the process, until the set of routes with the highest total value is found. In the route selection process there are 3 direction of iteration: "head", "tail" and "branch". "Head" and "tail" is extending (by one edge) from the head or from the tail (each route starts from the station) and "branch" is replacing last added edge with the possible alternative. This guarantees to iterate over every possible route (here by route I mean route in graph terms, it's not necessarily a valid route in 18xx terms). In practice, I'm using few optimizations to eliminate complete scan, but that's probably unimportant for non-AI use. The route evaluation part needs to be aware of the rules of the specific games. Route evaluation logic gets a proposed route as a vector of vertices it visits. As a result it gives a value and the vector of vertices it has used (this is used for optimization by skipping the routes that just an extension from the unused side). In a simple case evaluation would be simple - just total values of the best subset of cities and towns, but various bonuses make things more complicated. I'm using a bonus table containing various bonuses and their requirements. Bonuses can be: add extra value to the vertex, multiply value of the vertex, add value to the route (for example if 2 specific locations are visited) etc... Bonuses can be defined as sets if it's necessary to allow only one bonus from the set to be applied. Because of that, the route evaluation algorithm has to return updated "bonus usage context". There may be a need to iterate over bonus choices (such as not apply some bonus when possible), but I am not sure what game has such set of possible bonuses to require it. I haven't done such iteration because it would be bad for AI case (because of performance), for non-AI case, it's probably not a big issue. Some parts of the route evaluation code might need to be updated for specific games, but such updates should not affect the logic for anything else. Two types of trains I am aware of that might require more thought are hex trains and "N out of M" trains. Essentially, my current assumption is that for any route candidate the optimal route use (meaning use of trains and bonuses) can always be determined if both head and tail vertices are used. Alex On Sat, 20 Mar 2010 18:17:41 -0600, John A. Tamplin <ja...@ja...> wrote: > Yes, though see the archives for details about why it may be harder than > you > think. > > John A. Tamplin (Android) > > On Mar 20, 2010 8:12 PM, "Alex Tikhonov" <al...@sh...> wrote: > > Hi all, > > Per Brett Lentz suggestion I am moving this discussion here and reporting > my message from 18x yahoo group. > > This is my first post here, but I have been lurking for a while. I wonder > if there is an interest in adding automatic route calculation to Rails. I > am trying to create AI for some of the games (and no, it's not going > well), but as a side effect I have code that computes the routes. It > supports some of more widely used rules (various town treatment, city and > route bonuses, multipliers etc). It runs on an abstract connectivity > graph, so it should not be too hard to integrate. > > Alex. > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > 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. <ste...@we...> - 2010-03-21 17:21:29
|
John: I have only a very basic knowledge about graph theory, but from my background as econometrician I wonder, if there is a need to search for the true maximum. Is there no equivalent to solve such a problem similar to the search for the global maximum of numerical functions, where one can employ simulated annealing or genetic algorithms to get close to the optimum? Usually that is as good enough for macro-economist to optimize social welfare, should that not be sufficient for a 18xx player ;-) And if one player thinks he can do better, still let him do so? Stefan On Sunday 21 March 2010 17:27:18 John A. Tamplin wrote: > A brute-force search of all possible routes is O(n!), and is really only > feasible (even on modern machines) for 1830-like games. Games like 18US > that have simplified plain track tend to have a couple orders of magnitude > more possible routes. |
|
From: John A. T. <ja...@ja...> - 2010-03-21 17:45:57
|
On Sun, Mar 21, 2010 at 1:21 PM, Stefan Frey <ste...@we...> wrote: > I have only a very basic knowledge about graph theory, but from my > background > as econometrician I wonder, if there is a need to search for the true > maximum. Is there no equivalent to solve such a problem similar to the > search > for the global maximum of numerical functions, where one can employ > simulated > annealing or genetic algorithms to get close to the optimum? > Close to the optimum run is going to pretty annoying for a player who needed the optimal run to buy their permanent train. Usually that is as good enough for macro-economist to optimize social > welfare, > should that not be sufficient for a 18xx player ;-) > And if one player thinks he can do better, still let him do so? > I'm just not sure there is much point including it if it can't be correct. If it is accurate most of the time, then people will depend on it and not notice when it is wrong, and if it is rarely right people will just turn it off and ignore it. -- John A. Tamplin |
|
From: brett l. <bre...@gm...> - 2010-03-21 17:56:46
|
On Sun, Mar 21, 2010 at 10:45 AM, John A. Tamplin <ja...@ja...> wrote: > On Sun, Mar 21, 2010 at 1:21 PM, Stefan Frey <ste...@we...> wrote: >> >> I have only a very basic knowledge about graph theory, but from my >> background >> as econometrician I wonder, if there is a need to search for the true >> maximum. Is there no equivalent to solve such a problem similar to the >> search >> for the global maximum of numerical functions, where one can employ >> simulated >> annealing or genetic algorithms to get close to the optimum? > > Close to the optimum run is going to pretty annoying for a player who needed > the optimal run to buy their permanent train. >> >> Usually that is as good enough for macro-economist to optimize social >> welfare, >> should that not be sufficient for a 18xx player ;-) >> And if one player thinks he can do better, still let him do so? > > I'm just not sure there is much point including it if it can't be correct. > If it is accurate most of the time, then people will depend on it and not > notice when it is wrong, and if it is rarely right people will just turn it > off and ignore it. There are cases where SimTex's 1830 route calculator is wrong and doesn't find the optimal route. It's not perfect, but it's very usable. I think the right approach is to have route calculation as an option, and iteratively improve it after we've got it functional. It makes sense to also take a modular approach to route calculation, and allow ourselves the space to develop multiple calculation algorithms that can be used. > -- > John A. Tamplin ---Brett. |
×
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