Welcome back to our series (part 1 here) on building the Powargrid AI! Michiel here again, and this time I'll look at the general tactics the AI uses. Our generic AI quickly became known as the "skirmish" AI, since it should be able to play a nice game of Powargrid on the skirmish maps. No mess, no fuss - just you against them, in a no-holds-barred fight to the last power plant.
We also created several specialized AIs for the various campaign missions, and Willem will tell you more about those in the next part of the series.
We also created several specialized AIs for the various campaign missions, and Willem will tell you more about those in the next part of the series.
I already mentioned the basic steps the AI goes through:
- defend its own power plants
- advance towards the opponent
- attack whatever is in its way
- finally, blow up the opponent's power plants
This is it! Well, this and another 1000 lines of code.
This core logic has stayed mostly unchanged, but we've tweaked the internals of each step over a period of several months, slowly making it smarter and meaner. At first, we had to give the AI a large head start (starting it off with more power plants than the player) but as it improved, we were having a hard time keeping up! Now,the AI will give you a good fight even if evenly matched. Three power plants against your two is hard, and we've not been able to beat the current version if you give it four power plants. There's a setting to give it five, if you're feeling particularly brave ;-)
Yeah, good luck with that. Let me know if you win!
After going through its main loop, there's some housekeeping to be done: maybe it should build another power plant, or build some substations to store any leftover power.
Decision making
What to attack? Where to build a new power plant? Which weapons to charge? Those are all decisions the AI has to make. We've decided on a simple approach for all of these: make a list of things, then assign them a score based on how good they are.
For example, if we're figuring out which weapons to charge:
For example, if we're figuring out which weapons to charge:
- Can it hit a power plant? +1000 points! Does that power plant only have one hitpoint left? Add another 1000!
- Is it in our way, according to our pathfinding? That's 150 points.
- Is it a weapon? Can it hit one of our power plants? 200 points. It can't? Still scary, 10 points.
- Anything else? Well OK, have 5 points for being the wrong colour.
These numbers were determined by rigorous science I mean exquisite math well actually mucking with it until it looked good. Hey, we're not the only ones!
Then, just sort everything by their total score, and work your way down the list, charging each weapon which has more than the minimum score (or we run out of power).
One of the moves in the game, overcharging your power plants, had us pondering for a while. Overcharge, in case you haven't played the game yet (why not? go ahead, I'll wait!), boosts a power plant's output, but also damages it each turn, and you can't turn it off, so it's a a choice not to make lightly.
The AI will use it in two cases: defensively, if it's about to lose a power plant, it'll overcharge it to get some extra juice out of it. Offensively, it will overcharge a power plant only if it has more power plants than the opponent, and it could reach a strategically valuable tile but doesn't quite have enough power to get there. Again, simple rules, but the AI still manages to surprise us with a sudden charge every now and then.
The AI will use it in two cases: defensively, if it's about to lose a power plant, it'll overcharge it to get some extra juice out of it. Offensively, it will overcharge a power plant only if it has more power plants than the opponent, and it could reach a strategically valuable tile but doesn't quite have enough power to get there. Again, simple rules, but the AI still manages to surprise us with a sudden charge every now and then.
Randomness
A* is great, but it is a deterministic algorithm: if you give it the same inputs, it'll give you the same results every time. In a game, this is generally not what you want. Especially in a grid based game, it's very obvious: even though "up, up, right" is equivalent to "right, up, up" and "up, right, up" in terms of getting where you want to go, the AI would have a fixed preference for one option.
To remedy that, we add a small random amount to every cost we calculate for A*. Not enough to make it choose a suboptimal path, but just random enough so that it'll make slightly different choices every time. And the effect is huge: if you look at the red and blue AIs fighting each other behind the main menu (tip: press F10 to hide the menu for a better look at the action), you'll notice that no two games are the same. In fact, we've been unable to predict which one will win, even though they are both running the same algorithms in every game they play! All because of a tiny, tiny bit of randomness.
To remedy that, we add a small random amount to every cost we calculate for A*. Not enough to make it choose a suboptimal path, but just random enough so that it'll make slightly different choices every time. And the effect is huge: if you look at the red and blue AIs fighting each other behind the main menu (tip: press F10 to hide the menu for a better look at the action), you'll notice that no two games are the same. In fact, we've been unable to predict which one will win, even though they are both running the same algorithms in every game they play! All because of a tiny, tiny bit of randomness.
The difference between the AI and a human is still quite visible, though. The AI is very good at math but lacks the high level overview a human player has. It doesn't see "obvious" moves where a single power line would block off and defend a large section of the board, for example. It also doesn't realize that if it had built a tower one tile away, it would be able to hit two targets at once. On the other hand, I regularly have it happen to me that I think it's left me an opening, I rush forward, and it turns out I don't have enough power to actually get there. Which it already knew, of course.
Campaign missions
So after a while, we had built a pretty decent, generic AI - put it on the field and it'll come for you! However, the campaign missions need a bit more flavour than just having differently coloured pieces rushing at you headlong, so each campaign mission is additionally scripted to make your opponents more interesting. As you play the campaign, you may notice the first couple of moves are always the same. That's the first couple of turns of the mission script being run. You can't really call that AI - it's just us deciding what we want it to do, specifically.
DO THIS BECAUSE REASONS
In addition, the AI needs to know about mission objectives. For example, in the "Dam It!" mission, it'll only attack the dam, not your power plants. In "Welcome to the Jungle", the red blobbies are trying to blast their way into some ancient ruins, while trying to keep you out of their valley, and you'll have to learn some new tricks to make it there in time!
However, in later missions, once the game's afoot, we can generally just check for some specific conditions, and then just turn it over to the generic AI. This also allows us to quickly test out missions. After designing the initial layout of the grid, we can just throw in one or more AIs and quickly get a feel for how it'll play. Willem would like to tell you more about that process, so I'll leave that to him, in a future blog post!
RSS Feed