Menu
▾
▴
Re: [Rails-devel] Implementation details for revenue calculation
|
From: alexti <al...@sh...> - 2010-06-10 03:41:42
|
Stefan, I completely agree that AI issue is not an issue of coding at all. From my attempts I have feeling that the task if far from trivial. I was trying to use naive approach and implement it "as I would play". So basically, in the given situation - let's say in the stock round, I would consider what tile my company would lay in the following OR and where it would be important to place token, so if there's a contention I might be inclined to do some buy-selling to readjust operating order. But, of course, that have additional implications of affecting who could buy what trains, so the advantages of better track lay would have to be weighted against (possible) drawbacks of worse train purchase order. And, of course, other players could do some stock manipulation to affect the operating order too. And then I need to consider if someone might withhold to make a critical train purchase, but whether the company would have enough money or not would depend on its track lay possibilities of which would be affected by the companies operating earlier. And, of course, that order is also uncertain. So the end result is while I can compute individual projections, such as number of "what if" scenario, I can't brute-force every viable possibility and I am not certain how to filter them out. And that's not even considering that I'm overlooking something which I do mentally, but don't include into the algorithm (which seemed to happen more often than not). Besides all those difficulties, this approach would at best lead to AI that plays about at the level of one or more players (such as myself) who participated in development. And this doesn't solve the issue of dealing with different games. My current conclusion is that naive approach will not work and the best approach is to study AI (which is certainly actively researched area) (or to get AI expert as a volunteer on the team :) ). My knowledge of AI development is essentially nil. I just thought it is an interesting task and start doing it without having any background. In terms of software design, I think the best approach would be to let AI use its internal data and query the moderator via some interface. I think that AI will have to run in separate thread(s) and it's easier to isolate it from the moderator. Wrt 2-phased approach. Thanks for the detailed explanation - it confirms what I've thought from your previous message. I know why my ordering and timing do not fluctuate - for me vertex id is its geographical coordinate, so I have determined order everywhere (even though it doesn't make sense). Alex. On Wed, 09 Jun 2010 16:19:16 -0600, Stefan Frey (web.de) <ste...@we...> wrote: > Alex, > take your time: This is something to have fun. > > On the issue of implementing AI: > > I think this is not so much an issue of coding in Java or something > else, but > having good ideas, sketching out a prototype and/or defining the > interfaces > to the actual moderator program. A first question would be if the AI > should a > simplified/abstracted API to query the current state of the game and > communicate its actions or should work directly with the Rails > objects/actions. But if you choose the first approach you could program > against an abstract API and then later an intermediate layer could > facilitate > the communication between the AI and the rails program. > > Thus I agree with Brett, that you are invited to add to the project. At > least > I would already be interested to have a look at your current > implemetation > and run tests on it. Most likely no one would complain (???), if you > commit > your code or your designs/ideas to the Rails repo at some separate > directory > (maybe Brett could suggest a good location). > > On the issue of the phase two route ordering: > > Maybe I have not put down things clearly enough. > > Thus repeating the main finding: > For the two phase I first select "cheap" (few overlaps) routes first > (regardless of the value of the vertex at the end) and only as a second > criteria to use the value of the vertex. This allows to find quickly a > good > solution, at least for those scenarios we have defined. In consequence > this > allows to cut the search tree earlier and decreases search time. > > I suspect that you still assume that I use the route length only as > secondary > criteria. > > An example avoids any ambiguity, see below. > > Stefan > > Assume you start at vertex A and there are two routes to vertex B (value > 40) > which have costs (overlaps) of 2 and 4, and two routes to vertex C > (value 10) > with costs of 0 and 2. > > Then from A the routes are selected in this sequence: > 1) route to C (10) with cost 0 > 2) route to B (40) with cost 2 > 3) route to C (10) with cost 2 > 4) route to B (40) with cost 4 > > Initially I only sorted on value, with undefined ordering of the routes > to the > same vertex: > 1) or 2) route to B (40) with cost 2 > 1) or 2) route to B (40) with cost 4 > 3) or 4) route to C (10) with cost 0 > 3) or 4) route to C (10) with cost 2 > As I retrieved the edges from a HashSet, the ordering really changed > between > invocations, even I started the identical scenario, implying the > different > run times. I assume that in your implementation, you do not explicitly > define > an ordering, but running the same scenario still had the same ordering > implied (if you want to test that, try an explicit randomization). > > The run times below for the value ordering use the route costs as a > second > criteria, thus having well defined run times, but worse compared to the > sort > on the route costs first. > Ordering is now: > 1) route to B (40) with cost 2 > 1) route to B (40) with cost 4 > 3) route to C (10) with cost 0 > 4) route to C (10) with cost 2 > > > > On Wednesday 09 June 2010 03:16:53 alexti wrote: >> Stefan, >> >> My comments are inline >> >> > I have a first phase two prototype working. In fact it was not a too >> > difficult >> > task, as I only create a multigraph with new edges, that define the >> new >> > routes. >> > >> > Then I define "EdgeTravelSets", which define edges that are mutually >> > exclusive. This is tracked by the calculator using reference counters, >> > as each >> > edge might be excluded by several others. >> >> I'm keeping a vector of exclusions for each edge. I haven't investigated >> what approach is more efficient. In the testcases I ran I've never seen >> this being a bottleneck, so my guess is that the storage method is >> probably unimportant for performance. >> >> > The first results are promising so far and I believe I found the cause >> > for the >> > difference in number of evaluations compared to your implementation. >> > The main issue is that on a two phase graph the selection of >> neighbors is >> > different to the original one (by definition). >> > >> > The effect was that the search for the 4-train set (8, 5+5, 4D, 6E) >> took >> > between 30 - 140 seconds (compared to 70 seconds without). >> >> What did the time depend on? I always had very stable times for any >> scenario we've tried. For the example above it was ~30 seconds, perhaps >> with 1 second spread. >> >> > At first glance it was amazing that the run time did strongly vary and >> > the >> > fact that the best route is found remarkebly late in the process >> sheds >> > more >> > light, why you believe that my revenue predicitor is of the magic >> type. >> > >> > I still sort the neighbors by value, but the ordering of the >> (potentially >> > multiple) routes to them is random, as they are retrieved from a >> HashSet. >> > The ordering of routes is important for the revenue predictor to work >> > well. >> > Finding a good solution quick is important. >> >> This is a very good point - I choose edge iteration order more or less >> randomly - I don't use any criteria to sort them. I kind of thought of >> trying to make more intelligent choice, but didn't come up with any good >> criterion. >> >> > Without phase two optimization, the choice to visit the most valuable >> > (neighboring) vertex is clearly the optimal approach, as each neigbor >> is >> > one >> > track piece away. Thus the "costs" of each neighbor is identical. >> > >> > If you have done a phase two optimization, the most valuable vertex >> can >> > be >> > quite far away, thus blocking several track pieces at the same time >> and >> > ruling out a lot of other connections. Thus for phase two the cost of >> > each >> > neighboring vertex vary substantially. Accordingly the cost has to be >> > considered: The number of edges excluded must be an additional >> important >> > criteria to select the routes. >> > >> > Take an example: >> > Is it better to run for a nearby 20 vertex (which excludes one other >> > route) or >> > the far away 50 vertex (which excludes three other routes and >> potentially >> > bypasses the 10 vertex). There is no clear answer, but our preliminary >> > results and my experiences with 18xx routes, implies that it is >> usually >> > better to go for nearby stations first and save track first. >> > >> > Thus two approaches are possible: >> > * Use Nb of edges excluded as a first criteria, value as a second >> only. >> > (Thus >> > minimize costs first, then maximize revenue). >> > In that case you would run to the 20 first. >> > >> > * Or combine the two and use something like cost-modified value >> > approach. For >> > example choose the ratio between value and number of routes excluded >> > (including the route selected). >> > In that case you would run to the 50 first. (20/2 = 10, 50/4 = 12.5) >> > >> > I have implemented the ordering based on the first idea (cost-based) >> and >> > the >> > time is now stable an 24 seconds run for the 4 train set, thus running >> > time >> > decreased by factor 3. >> >> I like your idea, I think it's a good criterion. My intuitive feeling is >> that (1) is a better approach. I agree that in normal 18xx games the >> routes follow specific pattern - generally people try to connect >> valuable >> location by the shortest route and the long scenic routes between two >> cities/towns is usually a sign of a well blocked map :) >> >> > Number of evaluations one pass (70 seconds) >> > 480961 evaluations, 2935133 predictions and 8828871 edges travelled. >> > >> > Number of evalutaions two pass with cost ordering (24 seconds) >> > 475533 evaluations, 2910152 predictions and 2841394 edges travelled >> > >> > Number of evaluations two pass with value ordering (81 seconds) >> > 1421981 evaluations, 7302480 predictions and 8297888 edges travelled >> > >> > It seems that edge travelling is the time limiting factor in my >> > approach, but >> > that is not surprising as evaluation and prediction is pretty cheap >> > given the >> > continuous update of the run values. >> >> I want to try to use your approach to the edge ordering, but currently I >> took my implementation apart, because I wanted to restore vector >> computation functionality (which I broke when I added predictor) and >> this >> proves to be quite challenging (and, besides, the summer finally came >> here >> >> :) ) >> : >> > To compare the validity of my approach, this are my figures about >> > vertices and >> > edges: >> > >> > In scenario A the phase two graph consists of 23 vertices and 57 >> > edges/routes. >> > There are several routes that overlap with 9 other routes (J3.1 -> >> J9.1, >> > K4.1 -> J3.1,J9.1 -> M2.1,K4.1 -> M2.1). >> > In scenario B the numbers are 20 vertices and 151 edges/routes. >> > The route that overlaps with most others is E8->D5 (over 19 hexes) >> that >> > shares >> > track with 111 other routes. >> >> I think I had the same numbers. >> >> Alex. >> >> --------------------------------------------------------------------------- >> --- ThinkGeek and WIRED's GeekDad team up for the Ultimate >> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the >> lucky parental unit. See the prize list and enter to win: >> http://p.sf.net/sfu/thinkgeek-promo >> _______________________________________________ >> Rails-devel mailing list >> Rai...@li... >> https://lists.sourceforge.net/lists/listinfo/rails-devel > > > > ------------------------------------------------------------------------------ > ThinkGeek and WIRED's GeekDad team up for the Ultimate > GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the > lucky parental unit. See the prize list and enter to win: > http://p.sf.net/sfu/thinkgeek-promo > _______________________________________________ > Rails-devel mailing list > Rai...@li... > https://lists.sourceforge.net/lists/listinfo/rails-devel -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/ |
