[AI] Rondje om de kerk (current version: 385)

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Maninthebox
Engineer
Engineer
Posts: 107
Joined: 08 Aug 2008 11:35
Contact:

[AI] Rondje om de kerk (current version: 385)

Post by Maninthebox » 25 Sep 2008 19:54

TVTropes.org wrote:"A truly insidious AI"
Felix Atagong wrote:"A very vicious AI experiment"
"uses several unethical ways to make money"
As promised: the winning AI of the TJIP Challenge 2008, "Rondje om de kerk". In English, this means "Round around the church", as illustrated by our logo:

Image

This scene actually appeared in one of our test games, though we did change the town's name to a naughty one we found in another game :D
Of course, "Rondje om de kerk" is actually a Dutch expression, apparently from cycling and adopted by the national railroad. It actually has basically nothing to do with what our AI does, but we needed a name :)

The idea
An idea we already developed in the very early stages is to (ab)use the routes built by others. We first tried this concept manually, with three normal players and one of us leaching the routes the others built. This turned out to be both very profitable for the leecher and frustrating for the leechees. :twisted:

This formed the basis of our AI: we scan the map for serviced industies and towns (by checking for stations in the vicinity), then we follow the roads to determine which ones are connected. All the connected routes then go into a list which is sorted by estimated route profit. From this list we pick the most profitable ones to build our own stations on.

How the idea evolved into something darker...
  • A friend of ours mentioned that passengers were more profitable, as they generate profit going back and forth, while cargo trucks are empty on the way back. This led to the idea that we really don't need the trucks to go back, we can just sell them at their destination and build a new one from the profit. Although there is some loss due to vehicle devaluation (around 16% a year), it is more profitable. It has the added advantage that we can build trucks based on current profit per route and quickly adapt to vehicle jams and cargo available.
  • Especially with lots of passenger AI's running around in towns, centres tend to get crowded (might have something to do with our own testing AI: OtviAI 8) ), so we decided to build dropoff stations in the outskirts of cities and only use the centre to pick up passengers.
  • At some point we observed that we got paid as soon as we started unloading. So we now send the vehicles to the depot as soon as the profit is in, which means that we actually sell busses with roughly 30 or more passengers still in there :twisted: . Due to the shorter unloading time, we could also handle more busses/trucks per dropoff station.
  • While figuring out what generates the most company value (being the goal for the challenge) we read the source code (open source ftw) and noticed stations are actually 10 times worth the building cost. So to maximize our company value we place as many stations as we can buy at the end of the 10 year game. Because of property maintenance (and siginificant slow down of the game) we put lots of effort in optimizing the exact moment to start the map coloring process. This takes into account current cash, estimated future income, car and station maintenance till the end and the fact that we still need time to sell all current vehicles as well. Ideally we build the last station we can afford on Dec 31st and end with zero busses and close to zero cash (with maximum loan). Station maintenance on Jan 1st is a pain, but irrelevant :)
  • At some point we noticed that the constructor of the class is not limited to 10000 squirrel VM commands before being put to sleep, so we moved as much processing as possible to our constructor. Not only do we determine the best engines for all possible cargoes beforehand, we also valuate and sort each and every tile on the map to determine where to build the stations for the endgame (not all tiles are created equal). We were very happy that someone on the forum asked for functions to see whether a tile was for instance farmland. We didn't want to ask for this ourselves, as not to possibly reveal our strategy. So: thanks ;) Just in case we'd get a map with cities already connected by road, we also scanned for these and detemined where to build stations. This turned out to be a bit too computationably intensive even for us (after cleaning the dishes AND making coffee still having to wait for the beginning of a test run is no fun :P ). We reduced this to checking the 10 biggest towns for profitable connections.
Limitations/challenges
  • Ticks. Since every trip involves buying a vehicle, giving it orders, starting it, sending it to its depot and selling it and each of these actions costs a game tick, there is a limit to how many vehicles Rondje can keep running. Depending on the length of its routes, it maxes out at 300-500 vehicles; after that, there are simply not enough ticks in a day to build/sell more. We raised the limit by saving ticks wherever possible. For example, cloning an existing vehicle saves three ticks because the orders are cloned with it. If we can no longer re-invest all profit into new routes and vehicles, this means we reached the vehicle limit. At that point, we start to add buses that travel back and forth, which generate less profit but do not need to be managed.
  • Scanning the map to find new routes takes time, especially once there are lots of roads on the map. An added problem is that during mapping, the AI isn't building new vehicles (though ones that arrive at their destination are still sold). On maps with a great number of roads, Rondje won't be able to keep up with AIs that don't need to do as much processing. When a sufficient number of routes has been found, it will stop scanning and concentrate on the routes found so far.
  • During testing with OtviAI we noticed how many ticks pathfinding took, so we optimized the library pathfinder until a path that used to take thousands of ticks to find, now took less than a hundred. Based on this, we also created a specialized pathfinder purely for checking connectedness, which we use to check the actual length of a route before we decide to start using it. Since it doesn't need to perform any game altering actions, this can also be used within the constructor.
  • Traffic jams and broken routes turned out to be things you can't ignore, since the AI would happily spend all its money building vehicles which would arrive much too late or not at all, and with its money invested it couldn't build vehicles on other routes. We check for jams by looking for vehicles which are older than they should be (since we know how long a single trip should take) and are travelling slowly. If a vehicle is much older, we conclude the route might be broken. In either case, we no longer add vehicles to the route until the problem appears to be gone.
All in all, we had a great time building it and putting it to the test. Now, have fun taking it apart and looking at its private bits. Our "creative use of game mechanics" will probably be over soon, since Truebrain and Rubidium already hinted at fixing some of the exploits we used. We just hope they'll run another tournament before they do :D Anyway, the winning version was meant to run on r14357 of the NoAI branch. The current version (adopted to some of the latest changes) works with nightly 17500 and newer (version 7.3).

And remember kids...

Image

Happy hacking,
Willem, Marnix, Michiel, and Otto (Maninthebox)

====
edit: update for road API changes.
====
edit: fix rare bug (building a vehicle on a subsidized route with too little money)
====
edit: last version which is also available in BaNaNas.
====
edit: subject change and new version 309 in bananas which works in nightly 17500 and newer (7.3); adopted to payment at end of unloading.
====
edit: version 311: use 0.7.3 API; not trunk API. Also add missing function.
====
edit: version 313: fix sqrt call
====
edit: version 385: update to API 1.0 (also fixes load/save)
Attachments
rondje.tar
Version 385
(180 KiB) Downloaded 1012 times
Last edited by Maninthebox on 05 Jan 2011 14:35, edited 10 times in total.

TrueBrain
OpenTTD Developer
OpenTTD Developer
Posts: 1312
Joined: 31 May 2004 09:21

Re: Rondje om de kerk (version 1 aka svn272)

Post by TrueBrain » 25 Sep 2008 20:53

Brilliant! Thanks for posting guys :)
The only thing necessary for the triumph of evil is for good men to do nothing.

User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: Rondje om de kerk (version 1 aka svn272)

Post by Zutty » 28 Sep 2008 11:13

WOW thats a very VERY clever AI! :bow:

Totally evil, but clever. The demotivator makes it all OK though!! :twisted:

I had thought about trying to find clusters of industries so an AI could run two-way truck routes to prevent them running empty, but selling them at the end is pure genius!

I like the traffic detection idea too. I migh have to ste.. borrow that idea! :D
PathZilla - A networking AI - Now with tram support.

Maninthebox
Engineer
Engineer
Posts: 107
Joined: 08 Aug 2008 11:35
Contact:

Re: Rondje om de kerk (version 1.1 aka svn274)

Post by Maninthebox » 06 Jan 2009 12:48

Updated AI to reflect changes in road API; tarballs are as usual in the first post :)

TrueBrain
OpenTTD Developer
OpenTTD Developer
Posts: 1312
Joined: 31 May 2004 09:21

Re: Rondje om de kerk (version 1.1 aka svn274)

Post by TrueBrain » 06 Jan 2009 13:30

This time valid tar files? :p :p :p Nice to see you are still here :)
The only thing necessary for the triumph of evil is for good men to do nothing.

Maninthebox
Engineer
Engineer
Posts: 107
Joined: 08 Aug 2008 11:35
Contact:

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by Maninthebox » 06 Jan 2009 16:27

We always make valid tar files 8) it's just that openttd doesn't like them ;-)

It's a new one again btw; found a rare bug that occurs if it builds a vehicle on a subsidized route with too little money.

Matthias_87
Engineer
Engineer
Posts: 20
Joined: 19 Aug 2006 18:13

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by Matthias_87 » 11 Mar 2009 12:37

Hmm... I copy the file in the right folder, but can't load it... why?

Can someone help me please...

Yexo
Tycoon
Tycoon
Posts: 3653
Joined: 20 Dec 2007 12:49

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by Yexo » 11 Mar 2009 12:42

Matthias_87 wrote:Hmm... I copy the file in the right folder, but can't load it... why?

Can someone help me please...
Not untill you start following the directions here: http://www.tt-forums.net/viewtopic.php?f=65&t=42159
Even then, the version available for download in the first post doesn't work with the latest openttd versions but an update will come soon.

Maninthebox
Engineer
Engineer
Posts: 107
Joined: 08 Aug 2008 11:35
Contact:

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by Maninthebox » 11 Mar 2009 13:20

Aye, with the latest greatest patches (thanks Yexo!) rondje should be able to run in the latest nightlies. Running tests and trials to see whether we corrected all the api changes etc, so you can expect an upload to bananas in less then a week :)

User avatar
Michiel
Transport Coordinator
Transport Coordinator
Posts: 313
Joined: 13 Jul 2008 00:57
Contact:

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by Michiel » 02 May 2009 21:57

Now available in BaNaNaS! It requires r16181 or newer because of one of the bug fixes.
It sets UseAsRandom=false so it is not chosen when starting a random AI, you'll have to start it explicitly. We've commented out the "endgame feature" where it spams the map with stations after 10 years, by the way.

Enjoy :D

User avatar
GeekToo
President
President
Posts: 950
Joined: 03 Jun 2007 22:22

Re: Rondje om de kerk (version 1.2 aka svn275)

Post by GeekToo » 02 May 2009 22:02

Thanks! Been waiting for this for a while, to check how well Convoy performs against this winner, but was too lazy to update rondje to the latest api version myself.

Well, I'm off downloading :D

Morloth
Transport Coordinator
Transport Coordinator
Posts: 378
Joined: 07 Feb 2008 14:06
Location: Glasgow

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Morloth » 03 May 2009 12:28

Nice, congrats with your release :).

Btw, you may want to update the minimal version in BaNaNaS, because I could download it with OpenTTD version 16112 and it (of course) crashed your AI.

User avatar
Michiel
Transport Coordinator
Transport Coordinator
Posts: 313
Joined: 13 Jul 2008 00:57
Contact:

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Michiel » 03 May 2009 12:48

Oh, we jus set it to "nightly", but I guess that includes older nightlies :)
I'll update it.

Edit: set minimum version to "custom" with a revision number should do the trick, right?

Morloth
Transport Coordinator
Transport Coordinator
Posts: 378
Joined: 07 Feb 2008 14:06
Location: Glasgow

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Morloth » 03 May 2009 13:59

Michiel wrote:Edit: set minimum version to "custom" with a revision number should do the trick, right?
Nope, set it to nightly with the revision number.

User avatar
Michiel
Transport Coordinator
Transport Coordinator
Posts: 313
Joined: 13 Jul 2008 00:57
Contact:

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Michiel » 04 May 2009 17:30

Oh, I should've probably added that I fixed it and it's working now :)

Maninthebox
Engineer
Engineer
Posts: 107
Joined: 08 Aug 2008 11:35
Contact:

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Maninthebox » 26 May 2009 10:14

Our creative use of the constructor is no longer appreciated it seems :cry:

We'll post a more ehmmm... considerate version soon :)

Rubidium
OpenTTD Developer
OpenTTD Developer
Posts: 3815
Joined: 09 Feb 2006 19:15

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Rubidium » 26 May 2009 10:24

Maninthebox wrote:Our creative use of the constructor is no longer appreciated it seems
That happens when people start to file bugreports about "OpenTTD hanging" because of AIs being "creative"; people do not appreciate it if they have to wait long (without progress indication).

User avatar
davidx123
Traffic Manager
Traffic Manager
Posts: 146
Joined: 21 Feb 2008 19:05
Location: boring city in the middle of nowhere,Israel.
Contact:

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by davidx123 » 29 May 2009 15:39

well,i the only thing i can say it's...
a devios Ai.and evil.a demon that know's how to build roads(ot rather,use other one's roads).
iu found it very hard to beat whitout any demolish of city roads.
if a giot a subsidy for a to b,he will build only after i have setted a route bettween them!
evil!this ai is just evil!evil it tell you!
EVIL!
:twisted:
Your Faithful Student, Twilight Sparkle.
____
Visit my screenshot thread
Image


thanks to Supercheese for help with the GIF.cheers.

User avatar
Michiel
Transport Coordinator
Transport Coordinator
Posts: 313
Joined: 13 Jul 2008 00:57
Contact:

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by Michiel » 29 May 2009 19:48

davidx123 wrote:a devios Ai.and evil.a demon that know's how to build roads
Hahaha, thank you sir, for those kind words :mrgreen:

User avatar
GeekToo
President
President
Posts: 950
Joined: 03 Jun 2007 22:22

Re: Rondje om de kerk (version 1.3 aka svn290)

Post by GeekToo » 29 May 2009 20:29

Only way to stop this monster: be meaner. So don't give it any roads it can abuse, only build trains or planes, and setup eg Admiral to use only trains, and Rondje will have a miserable time.... :twisted:

Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 10 guests