Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Mon Sep 25, 2017 8:36 pm

All times are UTC




Post new topic  Reply to topic  [ 45 posts ]  Go to page 1 2 3 Next
Author Message
PostPosted: Thu Sep 25, 2008 7:54 pm 
Offline
Engineer
Engineer

Joined: Fri Aug 08, 2008 11:35 am
Posts: 107
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:
File comment: Version 385
rondje.tar [180 KiB]
Downloaded 837 times

_________________
OtviAI
Rondje om de kerk (AI)


Last edited by Maninthebox on Wed Jan 05, 2011 2:35 pm, edited 10 times in total.
Top
   
PostPosted: Thu Sep 25, 2008 8:53 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Mon May 31, 2004 9:21 am
Posts: 1292
Brilliant! Thanks for posting guys :)

_________________
The only thing necessary for the triumph of evil is for good men to do nothing.


Top
   
PostPosted: Sun Sep 28, 2008 11:13 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
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.


Top
   
PostPosted: Tue Jan 06, 2009 12:48 pm 
Offline
Engineer
Engineer

Joined: Fri Aug 08, 2008 11:35 am
Posts: 107
Updated AI to reflect changes in road API; tarballs are as usual in the first post :)

_________________
OtviAI
Rondje om de kerk (AI)


Top
   
PostPosted: Tue Jan 06, 2009 1:30 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Mon May 31, 2004 9:21 am
Posts: 1292
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.


Top
   
PostPosted: Tue Jan 06, 2009 4:27 pm 
Offline
Engineer
Engineer

Joined: Fri Aug 08, 2008 11:35 am
Posts: 107
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.

_________________
OtviAI
Rondje om de kerk (AI)


Top
   
PostPosted: Wed Mar 11, 2009 12:37 pm 
Offline
Engineer
Engineer

Joined: Sat Aug 19, 2006 6:13 pm
Posts: 20
Hmm... I copy the file in the right folder, but can't load it... why?

Can someone help me please...


Top
   
PostPosted: Wed Mar 11, 2009 12:42 pm 
Offline
Tycoon
Tycoon

Joined: Thu Dec 20, 2007 12:49 pm
Posts: 3653
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: 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.


Top
   
PostPosted: Wed Mar 11, 2009 1:20 pm 
Offline
Engineer
Engineer

Joined: Fri Aug 08, 2008 11:35 am
Posts: 107
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 :)

_________________
OtviAI
Rondje om de kerk (AI)


Top
   
PostPosted: Sat May 02, 2009 9:57 pm 
Offline
Transport Coordinator
Transport Coordinator
User avatar

Joined: Sun Jul 13, 2008 12:57 am
Posts: 313
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

_________________
Building Powargrid: a turn based strategy game


Top
   
PostPosted: Sat May 02, 2009 10:02 pm 
Offline
President
President
User avatar

Joined: Sun Jun 03, 2007 10:22 pm
Posts: 950
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


Top
   
PostPosted: Sun May 03, 2009 12:28 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Thu Feb 07, 2008 2:06 pm
Posts: 378
Location: Glasgow
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.


Top
   
PostPosted: Sun May 03, 2009 12:48 pm 
Offline
Transport Coordinator
Transport Coordinator
User avatar

Joined: Sun Jul 13, 2008 12:57 am
Posts: 313
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?

_________________
Building Powargrid: a turn based strategy game


Top
   
PostPosted: Sun May 03, 2009 1:59 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Thu Feb 07, 2008 2:06 pm
Posts: 378
Location: Glasgow
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.


Top
   
PostPosted: Mon May 04, 2009 5:30 pm 
Offline
Transport Coordinator
Transport Coordinator
User avatar

Joined: Sun Jul 13, 2008 12:57 am
Posts: 313
Oh, I should've probably added that I fixed it and it's working now :)

_________________
Building Powargrid: a turn based strategy game


Top
   
PostPosted: Tue May 26, 2009 10:14 am 
Offline
Engineer
Engineer

Joined: Fri Aug 08, 2008 11:35 am
Posts: 107
Our creative use of the constructor is no longer appreciated it seems :cry:

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

_________________
OtviAI
Rondje om de kerk (AI)


Top
   
PostPosted: Tue May 26, 2009 10:24 am 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Thu Feb 09, 2006 7:15 pm
Posts: 3815
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).


Top
   
PostPosted: Fri May 29, 2009 3:39 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Thu Feb 21, 2008 7:05 pm
Posts: 146
Location: boring city in the middle of nowhere,Israel.
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.


Top
   
PostPosted: Fri May 29, 2009 7:48 pm 
Offline
Transport Coordinator
Transport Coordinator
User avatar

Joined: Sun Jul 13, 2008 12:57 am
Posts: 313
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:

_________________
Building Powargrid: a turn based strategy game


Top
   
PostPosted: Fri May 29, 2009 8:29 pm 
Offline
President
President
User avatar

Joined: Sun Jun 03, 2007 10:22 pm
Posts: 950
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:


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 45 posts ]  Go to page 1 2 3 Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2017 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2017.
Hosted by Zernebok Hosting.