TVTropes.org wrote:"A truly insidious AI"
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:Felix Atagong wrote:"A very vicious AI experiment"
"uses several unethical ways to make money"
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
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.
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
), 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 . 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 
). We reduced this to checking the 10 biggest towns for profitable connections.
- 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.
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...
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)
====
edit: version 411: update to 1.11
