NoAI Branch - An AI Framework

[GeekToo]

Looking good Fingon and Caeddyn, I cannot achieve those numbers using only passenger buses ( max profit I get in the first year so far is 26000 in the test scenario). Seems like tossing in some coal truck is an idea I should consider. The problem with the football stadium does sound familiar..

I've been working on my pathfinder, it is working quite nicely now. I did have some problems with crossing roads on slopes, that's solved now.

To test that I used a little test scenario, I thought it would be nice to put it here, so pathfinder developers can also stress their pathfinders a little.

[Zephyris]

These AIs never cease to impress me, I really can't wait until rail building is available to see what you guys come up with! I do have a couple of questions about these AIs though;
What are their long term potentials? Profit over 5 years is one thing but managing a network of roads for 50 years coping with industry closure, crashes and overloaded stations is another. Do these AIs have any frameworks for coping with these things? I am particularly interested in how they cope with very overloaded bus stops, something the old AI is notorious for...
Do they have any "designed stupidity"? A perfect AI should beat a human player, and many of these AIs seem to be approaching this level. Are there switches in place for making these AIs more stupid? It would link nicely with the old AI difficulty setting, and I would like to have some chance of beating them!

[GeekToo]

Do they have any "designed stupidity"? A perfect AI should beat a human player, and many of these AIs seem to be approaching this level. Are there switches in place for making these AIs more stupid? It would link nicely with the old AI difficulty setting, and I would like to have some chance of beating them!

Difficulty setting could be set by slowing the AI's down, so the AI does wait a number of ticks before executing the next action. Funny you ask this question, today I wondered how well a human player would perform in the test scenario. It would be nice if an experienced human player did play the test scenario and published the results. I did try it with my AI today, and I could beat them very easily, but it is interesting to see what the goals for the AI compared with a human are.

[Caeddyn]

Mine does not upgrade vehicles yet. It doesn't look very hard to add in though, there's autorenew functions under AICompany. It also doesn't look for industry closures.

However it does have a framework in place to make sure there are not too many vehicles going to a certain station. I orginally had a system set up where it would build just one road station, then upgrade it when it got too crowded. But it wasn't working too well with multiple AIs in the game, so I just have it build the whole thing at once. Currently (if breakdowns are on) the road should be overcrowded before the station is.

Right now I haven't included any "designed" stupidy into my AI. My plan is to first make one that's good. Then it should not be hard to make one that just builds worse routes, builds slower, and makes too many or not enough vehicles.

[Bilbo]

Do they have any "designed stupidity"? A perfect AI should beat a human player, and many of these AIs seem to be approaching this level. Are there switches in place for making these AIs more stupid? It would link nicely with the old AI difficulty setting, and I would like to have some chance of beating them!

Difficulty setting could be set by slowing the AI's down, so the AI does wait a number of ticks before executing the next action. Funny you ask this question, today I wondered how well a human player would perform in the test scenario. It would be nice if an experienced human player did play the test scenario and published the results. I did try it with my AI today, and I could beat them very easily, but it is interesting to see what the goals for the AI compared with a human are.

AI could be always slowed down to the point even inexperienced humans could beat it. IMHO much better than AI building horrible constructions as it does current "old AI".

There could be also extra setting for "aggresivity" - whether and how often will AI try to be really competitive, like using exclusive rights (of course only in cities where such actions would be economically viable, not just to annoy player) and directly competing with you (trying to get goods from same industry, building buses in same city as you...), etc ...
Still, even at maximum aggresivity it shouldn't resort to unfair tactics like blocking the player with "purchase land" tool, etc ... Some advanced skilled players may want to turn aggresivity to maximum to have extra challenge.
Perhaps settings to "other side" would end up with "very kind" AI that will rather avoid competing with player and more or less trying to build far away from any player structures. Default would be some "neutral" setting.

I could try the test scenario myself ...

[T-Unit]

I dont think the "easy" AI should be as bad as the original. It should be good enough to give them a good challenge, and let them learn how to build networks efficiently. Easy would be set as default upon first starting the game so that the new players can then use the building technique of the AI to start to learn how to make money. It should be able to be used as a competitor AND a tutor.

[Zephyris]

I suppose what I meant was "plausible stupidity", like not building the exact right number of vehicles for a route or not noticing an industry with high production. I completely agree that we don't want AI as stupid as the old one. As T-Unit unit said, the AI should be able to teach new users the way to do things well, without absolutely owning them...

[corne]

Maybe some dice system for the AI. When the AI has found an industry with high production he rolls a dice and if it rolls >3 he leaves it alone for the next 10 searches or something.

[corne]

Looking good Fingon and Caeddyn, I cannot achieve those numbers using only passenger buses ( max profit I get in the first year so far is 26000 in the test scenario). Seems like tossing in some coal truck is an idea I should consider. The problem with the football stadium does sound familiar..

I've been working on my pathfinder, it is working quite nicely now. I did have some problems with crossing roads on slopes, that's solved now.

To test that I used a little test scenario, I thought it would be nice to put it here, so pathfinder developers can also stress their pathfinders a little.

How does your AIs handle those steep slopes?
I used the A* algorithm for pathfinding but it definitively suck for roadbuilding so I'm going to write a custom pathfinder, but i can't seem to avoid those slopes correctly.

[Caeddyn]

How does your AIs handle those steep slopes?
I used the A* algorithm for pathfinding but it definitively suck for roadbuilding so I'm going to write a custom pathfinder, but i can't seem to avoid those slopes correctly.

Every slope tile my A* search comes across it increases g by 2 instead of just 1. Obviously that's not its real cost, but it's been working fine so far so I haven't bothered trying to figure out the correct amount.

[corne]

But how did you implement A*? I never did any pathfinding before but this is the best I've come up with so far. (Don't mind the incompleteness of the road)

[Fingon]

It looks fine already, but you should also make road bends more expensive in the G of your algorithm, the roads will look nicer and more straight then. You can detect if it wants to build a bend by also using the previous roadtile as input parameters of the G calculator.
In my A* , a bend costs 1.5 times the normal cost, and a slope costs 2.5 times the cost. A "slope" for now is "any tile that is not completely flat", so even if it can build a flat road using foundations, it is still seen as a slope. I still have to improve that a bit. You can play with the values all you like and the results will be different. However the more difficult you make it to find a "good" path, the more tiles the algorithm will check, so the slower the pathfinding will become. Mine spends over a month (ingame) just to try to find a good path.

The combination of bends and steep slopes is also a problem :

problem.PNG (18.09 KiB) Viewed 2085 times

It first checks if the sloped tile is buildable. It is. (upper hill)
Then it checks if the turn to the right is buildable. It is. (lower hill)
Then it tries to build the two together. It fails. The two pieces of road can exist separately, but they can not be combined.
My solution for this (so far) is to just check all possibilities, again using 3 tiles as input (previous, current, next). Not too pretty but it works.

[Caeddyn]

I just learned A* about 2 weeks ago, so I'm by no means an expert. Two articles that helped me out were A* Pathfinding for Beginners and
Using Binary Heaps in A* Pathfinding. There's also some links in those articles to more information.

What Fingon said is correct, though. You need to have a higher cost for turns. Also make sure you're using Manhattan distance.

[corne]

Ah thanks both. I'll try to play around a bit with the costs.
One last question and then I'm going to code Does your algorithm build while searching or when it's done finding the whole path?

[Caeddyn]

Ah thanks both. I'll try to play around a bit with the costs.
One last question and then I'm going to code Does your algorithm build while searching or when it's done finding the whole path?

Mine only builds when it's finished searching. It doesn't even build the stations till after it's done.

[broodje]

How does it cope with another player, or city changing the landscape between starting to search for a route and completing it? i believe the default AI coped with it by building in short sections, and then searching for the next part of the route. That way it minimizes the chance the found route will be altered. Will your AI have to start again with searching for a route then? Especially if it takes a long time to compute a route this can make the AI very slow on busy maps (Fingon was even talking about a month for a route to be computed).

[corne]

Building in sections is an interesting solution to cope with other players. You could also check the tile when it's trying to build the road on it and if it's suddenly not buildable try to find a buildable tile close to it and do another pathfinding from there.

Another thing, that binary heap sorting is much faster and besides that it also fixed my cornering problem, so thanks for that I think I made a mistake with my original sorting function.

[Caeddyn]

How does it cope with another player, or city changing the landscape between starting to search for a route and completing it? i believe the default AI coped with it by building in short sections, and then searching for the next part of the route. That way it minimizes the chance the found route will be altered. Will your AI have to start again with searching for a route then? Especially if it takes a long time to compute a route this can make the AI very slow on busy maps (Fingon was even talking about a month for a route to be computed).

My pathfinder doesn't take more than a day to search for the distances I have it do. That's because it uses C++ instead of Squirrel. I made a modification to the NoAI API to include an A* pathfinder.

Originally I was making the whole thing out of Squirrel. But, as Fingon said, it would take about month for me to calculate a route that was 130 tiles long. And that was with only 1 AI player. With more it would take longer. Though my algorithm was totally unoptimized. A binary heap combined with a hash table seems the way to go.

However you can still adjust if it takes a long time to calculate a route. Just run a test build using AITest and if it finds a spot where it can no longer build, you can try to find a way around. I was too lazy to do that, so I redid everything in C++. I'm just coding this for fun so I don't really mind if it's hard for other people to use it.

[Fingon]

Yes, mine is completely in SQ so that's why it is slow. I'm already fearful of train routes, as those can be much longer. Probably a multi-tier pathfinder will be the way to go (or do it in C++, but I also want the thing to be useable out of the box, by other people). By the way, that "month" is because of the Sleep(). If i don't use Sleep() then the game just hangs for a second and then the path is found .
On the other hand, most of the time an AI is doing nothing with its time, because it does not have any money to build a route (truck income is slow). So I'm considering to use the time when it has no money to pre-compute a route, and then build that as soon as it has enough money.

And yes, sometimes the landscape changed since the original path was computed. My solution is very straightforward : If the path from tile A to tile B can not be built (A and B are usually not next to eachother, but always are on a straight line), for whatever reason, then a new path from A to B is searched (recursion).

[Zephyris]

Surely including pathfinders in the API would make the route calculation much faster whilst still allowing the flexibility of squirrel? Variables penalties for tile types could be included to allow full customisation of an AI...