rails-devel — List for discussion of Rails development

Re: [Rails-devel] Automated testing for Rails

[Erik V. <eri...@xs...>]

Looks very good to me. 

I generally agree with your proposals. Just one remark: can't the tree
hierarchy be better reversed?
For what it's worth: I would tend to select a game first, then look what
saved files/test cases exist for that game.

And a warning: most of the saved files I have sent you off-list do NOT
constitute valid games. 
The revenues have often been faked, either to construct a particular test
case, or just because I was lazy.
Never trust my saved files!

Erik.

-----Original Message-----
From: Stefan Frey [mailto:ste...@we...] 
Sent: Tuesday 23 March 2010 19:53
To: Development list for Rails: an 18xx game
Subject: [Rails-devel] Automated testing for Rails

I have added automated regression testing for Rails in CVS.

How does it work:
* For a set of Rails save files (which are known that they are correct) game

reports are created and stored alongside with the save files.
Then each time the tests are run, each game is replayed by Rails on the new 
code base and the game reports are compared to the stored ones. 

* Anytime a difference in the game reports occurs, this test reports the
error 
and displays the first line, where the game reports deviate.

More instructions and comments for developers see attached text file. In 
addition I have added an example report of a current test run.

Stefan

I have not uploaded my preliminary test suite so far, as I want to ask for 
opinion on the tree structure first.

My proposal is:

Convention for file names:
{18xx}_{noMap - if used}_{author}_{nb of players}_{end round}_{end 
condition}_{special remarks}

-> Bug reports
The game name should include the bug number if possible.
below that with categories, that still have to be defined. 

-> Finished games
real plays
below that with one folder for each 18xx

-> Pbem games
currently running pbem games
below that with one folder for each 18xx

-> Test cases
hand crafted settings for specific testing
below that with one folder for each 18xx

-> Test games
simulated games
below that with one folder for each 18xx

[Rails-devel] Automated testing for Rails

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

I have added automated regression testing for Rails in CVS.

How does it work:
* For a set of Rails save files (which are known that they are correct) game 
reports are created and stored alongside with the save files.
Then each time the tests are run, each game is replayed by Rails on the new 
code base and the game reports are compared to the stored ones. 

* Anytime a difference in the game reports occurs, this test reports the error 
and displays the first line, where the game reports deviate.

More instructions and comments for developers see attached text file. In 
addition I have added an example report of a current test run.

Stefan

I have not uploaded my preliminary test suite so far, as I want to ask for 
opinion on the tree structure first.

My proposal is:

Convention for file names:
{18xx}_{noMap - if used}_{author}_{nb of players}_{end round}_{end 
condition}_{special remarks}

-> Bug reports
The game name should include the bug number if possible.
below that with categories, that still have to be defined. 

-> Finished games
real plays
below that with one folder for each 18xx

-> Pbem games
currently running pbem games
below that with one folder for each 18xx

-> Test cases
hand crafted settings for specific testing
below that with one folder for each 18xx

-> Test games
simulated games
below that with one folder for each 18xx

Re: [Rails-devel] Rails 1.2.2 is available.

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

For 1.2.2 that is easy:
* Fix of the missing activation done button in repay loan phase (=> 1856)
* Fix of map zoom bug (=> 1851)
* Added tile upgrades for 1889

Maybe we can add a changelog text file to CVS. I would have no problem to add 
my changes to that (most of the time it only requires a simply copy of the 
commit message).

STefan


On Monday 22 March 2010 00:57:34 Justin Rebelo wrote:
> Where can I find a changelog of new features/changes in releases? I
> checked in the tarball but didn't see anything.
>
> On Sun, Mar 21, 2010 at 11:01 AM, brett lentz <bre...@gm...> wrote:
> > This releases fixes a critical bug that affects the playability of
> > 1856.
> >
> > All users of 1.2 should update to 1.2.2.
> >
> > The new release may be downloaded from here:
> > https://sourceforge.net/projects/rails/files/
> >
> > ---Brett.
> >
> > -------------------------------------------------------------------------
> >----- Download Intel&#174; 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
>
> ---------------------------------------------------------------------------
>--- Download Intel&#174; 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

Re: [Rails-devel] Rails 1.2.2 is available.

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

On Sun, Mar 21, 2010 at 4:57 PM, Justin Rebelo <jus...@gm...> wrote:
> Where can I find a changelog of new features/changes in releases? I
> checked in the tarball but didn't see anything.
>


There isn't a formal changelog beyond the CVS change history.


---Brett.

Re: [Rails-devel] Rails 1.2.2 is available.

[Justin R. <jus...@gm...>]

Where can I find a changelog of new features/changes in releases? I
checked in the tarball but didn't see anything.

On Sun, Mar 21, 2010 at 11:01 AM, brett lentz <bre...@gm...> wrote:
> This releases fixes a critical bug that affects the playability of
> 1856.
>
> All users of 1.2 should update to 1.2.2.
>
> The new release may be downloaded from here:
> https://sourceforge.net/projects/rails/files/
>
> ---Brett.
>
> ------------------------------------------------------------------------------
> Download Intel&#174; 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
>

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 13:41:30 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Sun, Mar 21, 2010 at 2:30 PM, alexti <al...@sh...> wrote:
>
> Yes, I use brute-force approach of going through all possible routes that
>> include a token. Why interaction with another train will be more
>> complicated in this case? It still can't re-use the same track. Or are
>> there games where it can?
>
>
> Yes, but that actually makes it easier -- you just calculate the routes  
> of
> the trains that can reuse track independently of the others (such as TGV  
> in
> 1826, 4D in 18Neb, etc).
Ok, that's a good news.

> The problem is when they can't reuse track, you have to choose the  
> optimal
> run for all trains together, not independently.  It is often the case  
> that
> the optimal run for running multiple trains is not an optimal run for any
> one of the trains by itself.  Therefore, you must evaluate all the  
> trains at
> the same time, which in a brute force algorithm gets you back to n!^m.
I agree, but I am not sure that in practice it's that bad. Asymptotic  
behaviour may look scary, but we're dealing with a bound case. I'm  
assuming that m is relatively small (m<=4 ?). One of the factors that  
severely limits graph growth is a train length (because there's no point  
to include any edges that can not be reached from any station by a train  
of given length). I think that "unlimited" diesel or express trains would  
have to be part of the worst case scenario.

>> Perhaps it can be tested? There is no need to have complete support of
>> such games in Rails to make experiment. We could create a graph
>> representing "difficult case" and run algorithm on it.
>>
>
> Yes, though it could take time to manually build the graph the way your
> algorithm wants it.

>> > Some I would look at would be 18US, 18C2C (for sheer size and the  
>> ability
>> > for a company to run lots of large trains), 1844 (which adds tunnels  
>> and
>> > mountains that affect the route score), and 1860.
>> Unfortunately, I don't own any of them :(
>>
>
> The complete rules are available for at least 18US and 1844, and ps18xx
> includes the map/tiles for all of them.

Are there some cases you would consider examples of "difficult" ones that  
are available in some kind of format? From some PBEM games perhaps? It  
might be relatively easy to convert them into the graph I need. And it's  
difficult to get an impression of what realistic end game layout would be  
without playing the game.

Alex.

Re: [Rails-devel] Automatic route calculation

[Erik V. <eri...@xs...>]

-----Original Message-----
From: alexti [mailto:al...@sh...] 
> - From your description I conjecture that  you already maintain a  
> dictionary
> that maps tile ids to your vertix/edge defintions. In that case that  
> would
> easy to add, if the data format is used can be converted to xml. Rails
> maintains a similar definition file in tiles/tiles.xml.
Unfortunately, I don't have such dictionary, because I was entering all  
tiles in the definition (connectivity) form. However from your description  
it seems that the tiles in Rails are maintained in a very similar form so  
the conversion algorithm will be very similar to what I use right now.

[EV] That is also my conclusion.

----------------------------------------------------------------------------
----
From: John A. Tamplin [mailto:ja...@ja...] 
Obviously if some new construct is invented for a game the algorithm will
have to be extended to support it.  I just don't see much point in
implementing something where the basic algorithm can't support the various
things we already know exist (it doesn't need to be implemented at first,
but it needs to be extensible without rewriting the basic algorithm).

[EV] On the other hand, I doubt if we can reasonably expect anyone to
predict what that extendable-to-all-cases algorithm will be. Neither could
we predict, for instance, the right basic structure of the Rails core code
when we started this project - it has already gone through fairly extensive
refactoring efforts. So, as long as route handling and revenue calculation
remain as pluggable as possible, I would see no problem in starting with the
simple cases and then improve.

Erik.

Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 2:30 PM, alexti <al...@sh...> wrote:

> I am still unconvinced that this would be that relevant - in most games
> there's less than 200 tiles and there's probably 3-4 links per tile on
> average. That means less than 1000 edges even in the endgame, so it
> doesn't seem that we need to look at the asymptotic properties here. But I
> am familiar only with a limited subset of 18xx titles, are there any that
> exceed this number by much?


It really doesn't take a big number for n! to become intractable.

As a real-world example, we found that IE6 used an n^3 algorithm for CSS
evaluation in a certain scenario.  Back when IE6 was written, there wasn't a
lot of complicated AJAX apps that built complicated DOMs with lots of CSS
rules, but we found with Google AdWords a particular CSS rule caused IE6 to
compute for over 3 minutes to respond to a mouse move event!  Needless to
say, interactive performance was suboptimal :).

This was with a few thousand DOM nodes and a few hundred CSS rules.  If it
were an n! algorithm, it would have become unusable with a few dozens of
each.

Yes, I use brute-force approach of going through all possible routes that
> include a token. Why interaction with another train will be more
> complicated in this case? It still can't re-use the same track. Or are
> there games where it can?


Yes, but that actually makes it easier -- you just calculate the routes of
the trains that can reuse track independently of the others (such as TGV in
1826, 4D in 18Neb, etc).

The problem is when they can't reuse track, you have to choose the optimal
run for all trains together, not independently.  It is often the case that
the optimal run for running multiple trains is not an optimal run for any
one of the trains by itself.  Therefore, you must evaluate all the trains at
the same time, which in a brute force algorithm gets you back to n!^m.


> That's ok. I'm assuming that the bonus table is specific to the current
> phase (it also gets updated as privates change hands etc). Doubling a
> single city is also fine as it doesn't matter what train (if only one
> allowed) will benefit from it.


Normally in those cases only the train making the E-W/N-S/whatever run gets
to double that stop, and it may or may not include any other bonuses that
could be applied to that city.


> Perhaps it can be tested? There is no need to have complete support of
> such games in Rails to make experiment. We could create a graph
> representing "difficult case" and run algorithm on it.
>

Yes, though it could take time to manually build the graph the way your
algorithm wants it.


> > Some I would look at would be 18US, 18C2C (for sheer size and the ability
> > for a company to run lots of large trains), 1844 (which adds tunnels and
> > mountains that affect the route score), and 1860.
> Unfortunately, I don't own any of them :(
>

The complete rules are available for at least 18US and 1844, and ps18xx
includes the map/tiles for all of them.

-- 
John A. Tamplin

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 12:22:30 -0600, brett lentz <bre...@gm...>  
wrote:


> Yes, running the calculation in a separate thread is a good idea. This
> would also allow use to begin calculations for the next OR during the
> Stock Round.
Starting calculations asynchronously is likely problematic. Typically the  
operating company will lay/upgrade tile and it will often affect the  
optimal route set, so I am not sure what can be calculated before such  
track lay is done. But perhaps we could do it while the player decides  
whether to place station or not (at least placing the station is much less  
common).

> I agree, there should be a tunable timeout value just so we don't take
> more than 30 seconds or so to return any value.
>
> Also, one thing that might be neat to have after the initial
> implementation is a way to suggest routing "hints". For example, in
> 1830, allow the use to select that they want their route to hit New
> York, Boston, and Philadelphia.  That gives us some concrete
> information that would speed up the calculations quite a bit, I'd
> expect.
I was thinking about using such hints automatically (by selecting high  
value cities first), but it is difficult to guarantee that the best routes  
are selected without checking all of them. It seems that all it achieves  
is to finds the routes that will eventually be declared best sooner. I  
think there's some potential in this approach, but it requires to be able  
to determine at some point that no other route set can improve on already  
found one. That would require some special order of route iteration and  
some more sophisticated logic wrt bonuses...

If we accept user hints as "requirement" (routes that don't hit New York,  
Boston and Philadelphia won't be considered at all) it may improve  
performance, but I am not sure if this is desirable approach. Perhaps it  
all depends on how fast the automatic calculation will really be.

Alex.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 12:09:29 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Sun, Mar 21, 2010 at 1:35 PM, alexti <al...@sh...> wrote:

>> I am not sure what is n in O(n!), but I don't think that asymptotic is
>> particularly useful in the given context. On the actual maps number of
>> vertices and edges is relatively small and because of 18xx track and  
>> route
>> rules dependency is not proportional to n! for that range of n.
>
>
> If you generate all possible routes and then check to see if they are  
> legal
> and calculate their route, then it converges on n! in the number of  
> edges as
> the connectivity graph becomes more full.  If you try and limit the  
> routes
> chosen at the time based on the trains, then you run into all the issues  
> I
> mentioned above.  When you have m trains, the brute force approach  
> amounts
> to investigating n!^m possibilities (fortunately for most games the train
> limit goes down as the complexity of the track graph goes up, but  
> consider
> running 4 big trains in the endgame of 18C2C for example).
I am still unconvinced that this would be that relevant - in most games  
there's less than 200 tiles and there's probably 3-4 links per tile on  
average. That means less than 1000 edges even in the endgame, so it  
doesn't seem that we need to look at the asymptotic properties here. But I  
am familiar only with a limited subset of 18xx titles, are there any that  
exceed this number by much?

>
>
>> I have not played 18US, but I have tried setting up artificial examples  
>> of
>> rather
>> convoluted track and for single route set evaluation it was fine (though
>> for AI it was causing problems).
>
>
> Typical endgame positions with the simplified plain track wind up with a
> large number of paths around various junctions, so the number of possible
> paths to consider goes up dramatically.
I agree that simplified track produces more edges and more possible routes.

>> Expresses should work with this approach
>>
>
> How do you propose handling them?  To me, it seems like they are  
> problematic
> because they are essentially infinite length trains that choose the best  
> n
> nodes (with one of them having to be a token).  That seems like it  
> requires
> a brute-force approach of going through all possible routes that include  
> a
> token, and then the interaction of that with a second train gets
> complicated.
Yes, I use brute-force approach of going through all possible routes that  
include a token. Why interaction with another train will be more  
complicated in this case? It still can't re-use the same track. Or are  
there games where it can?

>> As long as such bonus is '+' it would work. But if it's something like
>> "multiply by X" it would cause difficulties - that's the case I was
>> thinking about when discussing the need to iterate over possible  
>> bonuses.
>> If such bonus exists you would likely want to include other bonuses into
>> this route (rather than into another). Of course, that's only applicable
>> if the multiplier applies to other bonuses and if those bonuses can only
>> be used by a single train.
>>
>
> Several games have bonuses that are +x/city where x varies by phase, or
> allowing you to double one city on the route.
That's ok. I'm assuming that the bonus table is specific to the current  
phase (it also gets updated as privates change hands etc). Doubling a  
single city is also fine as it doesn't matter what train (if only one  
allowed) will benefit from it.

>> > Maybe I am missing it, but I don't see where you are covering running
>> > multiple trains where they can't reuse the same track.
>> I remove used edges from the connectivity graph before checking for the
>> next train.
>>
>> > You can't simply
>> > choose the optimal run for trains individually, you have to choose  
>> them
>> > all
>> > together which adds another factor to brute-force search.
>> When talking about optimal run for the train I meant for the given route
>> (as provide by route iteration part of the algorithm). In a way you can
>> look at this approach as first partitioning the graph into all possible
>> combinations of N partitions (such that every partition contains at  
>> least
>> one station) where N is number of trains and then finding the most
>> valuable partition set. Essentially it's the same except storing all
>> partitions would take too much memory, so it's done on-the-fly.
>
>
> Ok, so you are talking about generating all possible routes then, which  
> gets
> us back to n!^m.  I suggest this cannot be made fast enough for some  
> games.
Perhaps it can be tested? There is no need to have complete support of  
such games in Rails to make experiment. We could create a graph  
representing "difficult case" and run algorithm on it.

>> That could never hurt, but I don't really expect the problem as I was  
>> able
>> to do at least hundreds calculations per second.
>> Which games do you think would be the hardest to calculate? From my
>> observations, it's the bonus rules that cause more of performance hit  
>> then
>> the board size, but it might be specific to my implementation.
>
>
> Some I would look at would be 18US, 18C2C (for sheer size and the ability
> for a company to run lots of large trains), 1844 (which adds tunnels and
> mountains that affect the route score), and 1860.
Unfortunately, I don't own any of them :(

Alex.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 11:12 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 11:59:01 -0600, brett lentz <bre...@gm...>
> wrote:
>
>> On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
>>> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
>>> wrote:
>>>
>>>> http://en.wikipedia.org/wiki/Big_O_notation
>>>>
>>>> O(n!) means that for each vertex/edge that's added to the calculation,
>>>> the time it takes for the algorithm to reach a solution grows by a
>>>> factorial order of magnitude.
>>> Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that
>>> if
>>> you go from 1000 to 2000 than your time will increase by 2000!/1000!
>>> factor. In 18xx games there is also an interesting property of adding an
>>> edge unconnected to the station does not increase time at all and this
>>> is
>>> not uncommon in many games (at first because the track is not connected
>>> and later because it is blocked).
>>>
>>> Alex.
>>
>> You're right. Our problem isn't strictly the traveling salesman (which
>> is usually where O(n!) is seen).  I don't expect your algorithm to be
>> O(n!), but maybe closer to O(n^2) or O(2n).
>>
>> ---Brett.
>
> Unfortunately, I haven't done any formal analysis of my algorithm and I
> didn't know what is its asymptotic behaviour and how it behaves on a more
> typical range of n. Besides, on the modern hardware there are some
> interesting dependencies related to the memory speed vs CPU speed. There's
> a dramatic performance drop when the working data set stops fitting into
> the cache.
>
> Talking about software design, should the route calculation be run in a
> separate thread, so that the user doesn't experience "screen freeze" if
> for some reason it's taking too long? Also, as John has suggested, we
> could time-out or let the user cancel the calculations in those cases.
>
> Alex.

Yes, running the calculation in a separate thread is a good idea. This
would also allow use to begin calculations for the next OR during the
Stock Round.

I agree, there should be a tunable timeout value just so we don't take
more than 30 seconds or so to return any value.

Also, one thing that might be neat to have after the initial
implementation is a way to suggest routing "hints". For example, in
1830, allow the use to select that they want their route to hit New
York, Boston, and Philadelphia.  That gives us some concrete
information that would speed up the calculations quite a bit, I'd
expect.

---Brett.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 11:59:01 -0600, brett lentz <bre...@gm...>  
wrote:

> On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
>> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
>> wrote:
>>
>>> http://en.wikipedia.org/wiki/Big_O_notation
>>>
>>> O(n!) means that for each vertex/edge that's added to the calculation,
>>> the time it takes for the algorithm to reach a solution grows by a
>>> factorial order of magnitude.
>> Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that  
>> if
>> you go from 1000 to 2000 than your time will increase by 2000!/1000!
>> factor. In 18xx games there is also an interesting property of adding an
>> edge unconnected to the station does not increase time at all and this  
>> is
>> not uncommon in many games (at first because the track is not connected
>> and later because it is blocked).
>>
>> Alex.
>
> You're right. Our problem isn't strictly the traveling salesman (which
> is usually where O(n!) is seen).  I don't expect your algorithm to be
> O(n!), but maybe closer to O(n^2) or O(2n).
>
> ---Brett.

Unfortunately, I haven't done any formal analysis of my algorithm and I  
didn't know what is its asymptotic behaviour and how it behaves on a more  
typical range of n. Besides, on the modern hardware there are some  
interesting dependencies related to the memory speed vs CPU speed. There's  
a dramatic performance drop when the working data set stops fitting into  
the cache.

Talking about software design, should the route calculation be run in a  
separate thread, so that the user doesn't experience "screen freeze" if  
for some reason it's taking too long? Also, as John has suggested, we  
could time-out or let the user cancel the calculations in those cases.

Alex.

Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 1:35 PM, alexti <al...@sh...> wrote:

> I've looked through discussions (I've found some from about couple of
> months ago, I am not sure how to find all of them). I think that there's
> no magic bullets and some games will require extending the logic, but if
> we could support the games currently supported in Rails that would
> probably be already useful. Then when new games are added, required
> modifications can be made. I think that's the only approach, because even
> if some algorithm can be devised that will handle all game rules out of
> the box, someone will eventually design new 18xx game that would not fit
> into it :)


Obviously if some new construct is invented for a game the algorithm will
have to be extended to support it.  I just don't see much point in
implementing something where the basic algorithm can't support the various
things we already know exist (it doesn't need to be implemented at first,
but it needs to be extensible without rewriting the basic algorithm).


> I am not sure what is n in O(n!), but I don't think that asymptotic is
> particularly useful in the given context. On the actual maps number of
> vertices and edges is relatively small and because of 18xx track and route
> rules dependency is not proportional to n! for that range of n.


If you generate all possible routes and then check to see if they are legal
and calculate their route, then it converges on n! in the number of edges as
the connectivity graph becomes more full.  If you try and limit the routes
chosen at the time based on the trains, then you run into all the issues I
mentioned above.  When you have m trains, the brute force approach amounts
to investigating n!^m possibilities (fortunately for most games the train
limit goes down as the complexity of the track graph goes up, but consider
running 4 big trains in the endgame of 18C2C for example).


> I have not played 18US, but I have tried setting up artificial examples of
> rather
> convoluted track and for single route set evaluation it was fine (though
> for AI it was causing problems).


Typical endgame positions with the simplified plain track wind up with a
large number of paths around various junctions, so the number of possible
paths to consider goes up dramatically.


> Expresses should work with this approach
>

How do you propose handling them?  To me, it seems like they are problematic
because they are essentially infinite length trains that choose the best n
nodes (with one of them having to be a token).  That seems like it requires
a brute-force approach of going through all possible routes that include a
token, and then the interaction of that with a second train gets
complicated.


> As long as such bonus is '+' it would work. But if it's something like
> "multiply by X" it would cause difficulties - that's the case I was
> thinking about when discussing the need to iterate over possible bonuses.
> If such bonus exists you would likely want to include other bonuses into
> this route (rather than into another). Of course, that's only applicable
> if the multiplier applies to other bonuses and if those bonuses can only
> be used by a single train.
>

Several games have bonuses that are +x/city where x varies by phase, or
allowing you to double one city on the route.


> > Maybe I am missing it, but I don't see where you are covering running
> > multiple trains where they can't reuse the same track.
> I remove used edges from the connectivity graph before checking for the
> next train.
>
> > You can't simply
> > choose the optimal run for trains individually, you have to choose them
> > all
> > together which adds another factor to brute-force search.
> When talking about optimal run for the train I meant for the given route
> (as provide by route iteration part of the algorithm). In a way you can
> look at this approach as first partitioning the graph into all possible
> combinations of N partitions (such that every partition contains at least
> one station) where N is number of trains and then finding the most
> valuable partition set. Essentially it's the same except storing all
> partitions would take too much memory, so it's done on-the-fly.


Ok, so you are talking about generating all possible routes then, which gets
us back to n!^m.  I suggest this cannot be made fast enough for some games.


> That could never hurt, but I don't really expect the problem as I was able
> to do at least hundreds calculations per second.
> Which games do you think would be the hardest to calculate? From my
> observations, it's the bonus rules that cause more of performance hit then
> the board size, but it might be specific to my implementation.


Some I would look at would be 18US, 18C2C (for sheer size and the ability
for a company to run lots of large trains), 1844 (which adds tunnels and
mountains that affect the route score), and 1860.


> I think that under 0.2s is a good goal for anything interactive - that's
> sort of interval people don't see as "delay".


Sure, fast is better than slow.  I am just saying that people using this as
a moderator are probably running it on a laptop, and a netbook or an old
laptop (I could even hope for an Android phone version) is going to be a lot
slower than a current desktop.  Since route calculation by hand always takes
at least a few seconds (and in the endgame of games with 12 trains can take
far longer), I think 5s on such hardware is a fine upper limit to shoot for.

-- 
John A. Tamplin

[Rails-devel] Rails 1.2.2 is available.

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

This releases fixes a critical bug that affects the playability of
1856.

All users of 1.2 should update to 1.2.2.

The new release may be downloaded from here:
https://sourceforge.net/projects/rails/files/

---Brett.

Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
> wrote:
>
>> http://en.wikipedia.org/wiki/Big_O_notation
>>
>> O(n!) means that for each vertex/edge that's added to the calculation,
>> the time it takes for the algorithm to reach a solution grows by a
>> factorial order of magnitude.
> Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that if
> you go from 1000 to 2000 than your time will increase by 2000!/1000!
> factor. In 18xx games there is also an interesting property of adding an
> edge unconnected to the station does not increase time at all and this is
> not uncommon in many games (at first because the track is not connected
> and later because it is blocked).
>
> Alex.

You're right. Our problem isn't strictly the traveling salesman (which
is usually where O(n!) is seen).  I don't expect your algorithm to be
O(n!), but maybe closer to O(n^2) or O(2n).

---Brett.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

I agree that we should target to make the route calculation accurate.  
Though it might be ok to say that in some particular game it might produce  
sub-optimal results in specific circumstances and alert players that they  
need to double-check the routes. If we display them it can hopefully  
simplify the task.

Alex.

On Sun, 21 Mar 2010 11:45:29 -0600, 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.
>


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

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

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.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>  
wrote:

> http://en.wikipedia.org/wiki/Big_O_notation
>
> O(n!) means that for each vertex/edge that's added to the calculation,
> the time it takes for the algorithm to reach a solution grows by a
> factorial order of magnitude.
Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that if  
you go from 1000 to 2000 than your time will increase by 2000!/1000!  
factor. In 18xx games there is also an interesting property of adding an  
edge unconnected to the station does not increase time at all and this is  
not uncommon in many games (at first because the track is not connected  
and later because it is blocked).

Alex.
-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

[Rails-devel] 1835 Prussian

[Erik V. <eri...@xs...>]

The code I have just checked in (after I noticed 1.2.2 being out) deals with
part of the Prussian formation in 1835. 
The process basically works, but is so far only triggered at round ends, not
yet at buying the firsat 4/4+4/5-trains.

This has had some side consequences in various classes, and more will
follow, but I don't expect any other games to be affected.

Erik.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Hi Stefan,

On Sun, 21 Mar 2010 06:02:15 -0600, Stefan Frey <ste...@we...> wrote:

> Some quick questions and comments:
>
> - I prefer your definition of the graph to the one in tiles.xml  
> (inherited
> from the tiledesigner) as you only have to count edges and you do not  
> have to
> consider that you are not allowed to visit the same side (a node/vertex  
> in
> Rails) twice. Rails defines tile 25 (the green Y) with two edges that  
> both
> start from the same side  (see tiles.xml), but only one of each edge can  
> be
> used per revenue turn.
I was not clear on distinction between tile definitions and connectivity  
graph, but I've elaborated on that in another message. Basically, they are  
separate and the tile definition is similar to what you describe.

>
> - Is your algorithm implemented in Java and what is the calculation time  
> for
> standard hardware and a reasonable difficult setting? (Your text below  
> seems
> to imply close to zero, if you can use it for AI).
It's in C++ and on 2 year old machine I see times < 0.01s, but "reasonable  
difficult setting" is something rather difficult to quantify. In practice  
I was finding that the worst case for the performance is not the end game  
but just before 4s come out, when everyone has 3-4 trains and the track  
has already been formed to allow multiple ways to run those short trains.

>
> - From your description I conjecture that  you already maintain a  
> dictionary
> that maps tile ids to your vertix/edge defintions. In that case that  
> would
> easy to add, if the data format is used can be converted to xml. Rails
> maintains a similar definition file in tiles/tiles.xml.
Unfortunately, I don't have such dictionary, because I was entering all  
tiles in the definition (connectivity) form. However from your description  
it seems that the tiles in Rails are maintained in a very similar form so  
the conversion algorithm will be very similar to what I use right now.

Alex.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

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

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

Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 10:35 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 10:27:18 -0600, John A. Tamplin <ja...@ja...> wrote:
>
>> On Sun, Mar 21, 2010 at 1:43 AM, alexti <al...@sh...> 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.
> I am not sure what is n in O(n!), but I don't think that asymptotic is
> particularly useful in the given context. On the actual maps number of
> vertices and edges is relatively small and because of 18xx track and route
> rules dependency is not proportional to n! for that range of n. I have not
> played 18US, but I have tried setting up artificial examples of rather
> convoluted track and for single route set evaluation it was fine (though
> for AI it was causing problems).
>


http://en.wikipedia.org/wiki/Big_O_notation

O(n!) means that for each vertex/edge that's added to the calculation,
the time it takes for the algorithm to reach a solution grows by a
factorial order of magnitude.

---Brett.

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Sun, 21 Mar 2010 10:27:18 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Sun, Mar 21, 2010 at 1:43 AM, alexti <al...@sh...> wrote:
>
>> 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.
>>
>
> Yes, I am talking about the actual algorithm.  Please see the archives  
> for
> several long discussions on the idea, but I will bring up a few specific
> points here.
I've looked through discussions (I've found some from about couple of  
months ago, I am not sure how to find all of them). I think that there's  
no magic bullets and some games will require extending the logic, but if  
we could support the games currently supported in Rails that would  
probably be already useful. Then when new games are added, required  
modifications can be made. I think that's the only approach, because even  
if some algorithm can be devised that will handle all game rules out of  
the box, someone will eventually design new 18xx game that would not fit  
into it :)

> I'm not sure I get the value of having a fixed set of vertices inside the
> tile -- why not just have them where they are needed?  A #57 tile for
> example, has only one interior vertex, and a #8 tile has none.  It seems
> like what you want to do is just maintain a connectivity graph of hex  
> edges
> and scoring points (actually, you will probably want several connectivity
> graphs for different train types, like one ignoring dots for trains that
> ignore them).
The primary advantage that map lookups are replaced with arithmetics which  
means that, for example, checking for backtracking only involves simple  
arithmetics instead of having to lookup a vertex and check if it's on the  
tile edge. I use the method you've suggested for the tiles description  
though.

I am not sure about benefits of separate graphs for various dot treatment.  
If the company has a mix of express and non-express trains removing the  
used edges would become more complicated if the graphs are separate; and  
if the dots counting is optional you would have to make decision to count  
them or not during the route evaluation anyway.

> 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.
I am not sure what is n in O(n!), but I don't think that asymptotic is  
particularly useful in the given context. On the actual maps number of  
vertices and edges is relatively small and because of 18xx track and route  
rules dependency is not proportional to n! for that range of n. I have not  
played 18US, but I have tried setting up artificial examples of rather  
convoluted track and for single route set evaluation it was fine (though  
for AI it was causing problems).

> If you try to take into account the train types to avoid evaluating all
> possible routes, then you run into the following problems:
>
>    - trains that can skip stops, like 1846's n/m trains and 1844's 8E  
> trains
Expresses should work with this approach, I am not entirely sure about  
1846's n/m. It might be simple to add support of them, but there might be  
some pitfalls related to bonuses.

>    - trains that can substitute types of stops (like n+m trains)
Those should be easy to handle, I think.

>    - bonuses given when particular sets of stops are included on the  
> route
As long as such bonus is '+' it would work. But if it's something like  
"multiply by X" it would cause difficulties - that's the case I was  
thinking about when discussing the need to iterate over possible bonuses.  
If such bonus exists you would likely want to include other bonuses into  
this route (rather than into another). Of course, that's only applicable  
if the multiplier applies to other bonuses and if those bonuses can only  
be used by a single train.

>    - games that allow a train to run through one fully blocked city, like
>    1860
This is an interesting one...
>    - games that have choices about stops that give money to the company
>    instead of the dividend, like halts in 1860
I don't know 1860, but this sounds problematic. Is it something like mail  
runs in 1853? If so, that makes "best" undefined - there may be trade off  
between higher revenue for the company and higher dividend.

> Maybe I am missing it, but I don't see where you are covering running
> multiple trains where they can't reuse the same track.
I remove used edges from the connectivity graph before checking for the  
next train.

> You can't simply
> choose the optimal run for trains individually, you have to choose them  
> all
> together which adds another factor to brute-force search.
When talking about optimal run for the train I meant for the given route  
(as provide by route iteration part of the algorithm). In a way you can  
look at this approach as first partitioning the graph into all possible  
combinations of N partitions (such that every partition contains at least  
one station) where N is number of trains and then finding the most  
valuable partition set. Essentially it's the same except storing all  
partitions would take too much memory, so it's done on-the-fly.


> I really think that a pure brute-force algorithm is not going to be  
> suitable
> for many of the games out there.  Many years ago, when desktops were  
> about
> as powerful as my phone is now, I wrote a route calculation algorithm for
> 1830-style games that transformed the problem into a flow graph problem  
> and
> used max-flow/min-cut to compute the best route for a set of trains.
>  Unfortunately, I have lost that code and it was also not extensible for
> many of the other train types that have been added in new designs.
>
> Maybe we can start with a brute-force algorithm with a user-settable  
> timeout
> where it aborts processing if it is just going to take too long, so that
> games that can make use of it can benefit from it and then in the  
> endgame of
> the more complicated games users will have to go back to counting  
> manually.
That could never hurt, but I don't really expect the problem as I was able  
to do at least hundreds calculations per second.
Which games do you think would be the hardest to calculate? From my  
observations, it's the bonus rules that cause more of performance hit then  
the board size, but it might be specific to my implementation.

> My personal belief is that for basic route calculation after the player  
> has
> completed their move we should shoot for 5 seconds on a 5-year-old  
> laptop.
>  Note that this doesn't help while placing track, such as running various
> what-if scenarios to help the player would require the algorithm be an  
> order
> of magnitude faster.
I think that under 0.2s is a good goal for anything interactive - that's  
sort of interval people don't see as "delay".

> Likewise, an AI player would need to evaluate routes
> in many possible positions for lookahead and evaluating opponents' likely
> moves, so it would need route calculation to be another order of  
> magnitude
> faster than that.
Yes, I've encountered this problem with AI. AI is a separate can of worms  
though - brute-forcing through the stock round doesn't work well either  
even if you've already determined your target operating round priorities.  
I am actually amazed how that old 1830 AI managed to play even at the  
level it did :)


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Bug fix release 1.2.2?

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

Yup. I was planning on doing the release today.

---Brett.



On Sun, Mar 21, 2010 at 3:55 AM, Stefan Frey <ste...@we...> wrote:
> Brett:
> I would like to commit my changes that allow regression testing for Rails.
> Could we have the bug fix release out of the door before that?
>
> The changes include a few changes to some of the base classes to allow Rails
> to process several different 18xx games in sequence and to the ReportBuffer
> class, as the comparison is based on the game report.
>
> I would prefer to have the bug fix release out without those changes, which
> might include some side effects.
>
> The other possibility would be to branch, but I do not know exactly how to
> branch and merge with cvs. Do we have a decision already about the future
> system? I would be glad about svn as I use that for work as well and it seems
> to be well integrated to eclipse.
>
> Stefan
>
>
> On Friday 19 March 2010 22:02:01 brett lentz wrote:
>> Should we do a 1.2.2 release for this?
>>
>>
>> ---Brett.
>>
>> On Fri, Mar 19, 2010 at 1:53 PM, Erik Vos <eri...@xs...> wrote:
>> > This problem was indeed caused by the Stefan's fix. That fix was
>> > basically correct, as my way to allow done in this case was a shortcut
>> > that broke the (unwritten) rules. But the purpose of that shortcut
>> > (enabling Done) was not reinstated in any other way.
>> >
>> > I have now done it in the regular way. Done will now be enabled after
>> > repaying loans.
>> >
>> > Erik.
>> >
>> >
>> > -----Original Message-----
>> > From: Stefan Frey [mailto:ste...@we...]
>> > Sent: Friday 19 March 2010 17:05
>> > To: rai...@li...
>> > Subject: Re: [Rails-devel] Fwd: Problem with Rails 1.2
>> >
>> > Erik:
>> > from the description alone I guess that this is caused by a bug fix of
>> > mine on the undo mechanism. Do you remember our discussion about the
>> > change from the postcondition check (which requires the use of state
>> > variables) for the done button to a precondition check (which avoids
>> > that).
>> >
>> > It seems that there is a case not covered in the 1856 repay loan action
>> > step
>> >
>> > yet, that does not set the doneAllowed variable. Thus it might be a good
>> > guess to check the preconditions there.
>> >
>> > I look forward to checking in my automated testing procedures which
>> > hopefully
>> > reduce those side-effects of refactoring.
>> >
>> > STefan
>> >
>> > On Friday 19 March 2010 16:10:49 brett lentz wrote:
>> >> ---------- Forwarded message ----------
>> >> From: Arne Östlund <arn...@gl...>
>> >> Date: Thu, Mar 18, 2010 at 11:27 PM
>> >> Subject: Problem with Rails 1.2
>> >> To: rai...@li...
>> >>
>> >>
>> >> Hi Brett/Erik
>> >>
>> >> We are playing an 1856 PBeM campaigne. Due to an error with Rails
>> >> 1.1.3 I tried to recreate our moves in Rail 1.2 to current status by
>> >> redo some turns. But when I repayed the Loans for LPS after an
>> >> withhold, one OR before the CGR formation, the game stalled. The only
>> >> option I got was to Undo. So we can not pass this state and continue
>> >> the game!
>> >>
>> >> /Arne Östlund
>> >
>> > -------------------------------------------------------------------------
>> >--- --
>> > Download Intel&#174; 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
>> >
>> >
>> > -------------------------------------------------------------------------
>> >----- Download Intel&#174; 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
>>
>> ---------------------------------------------------------------------------
>>--- Download Intel&#174; 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
>
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; 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
>

Re: [Rails-devel] Automatic route calculation

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

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.