AI in a turn based strategy game

Game Mechanics Artificial Intelligence
#1

Hi,

My name is Peter Norberg and I’ve been working on a strategy game together with my brother since early 2011. Now that we are getting closer to launching the multi-player version we’re starting to look at an AI for a single-player version. This is currently a side-project but I thought I would share our progress if anyone is interested.

Anyway, I’ve only started by discussing our pathfinder:
http://www.risingempires.com/netherlords/?p=24
This weekend I intend to start writing about the AI structure (all it’s modules and how they will interact with each other).

I’m new to this and hope to learn a lot with this project. Insights, ideas or thoughts are welcome!

Best regards,

Peter

#2

One thing that I would suggest you think about is a major performance issue: Pathfinding can be expensive when used incorrectly (Expensive in the wasted cycles type of way). A lot is based on how your game’s movement system is implemented and how collisions/units affect a unit’s ability to move across a map.

Some thoughts (Since I haven’t read a lot about your system or the intended game, or how the system will actually work.) If units cause the traversable edges of your map to change (Meaning if a unit ‘blocks’ travel through it’s current position) then there is a high likely hood that you will run into something called Thrashing. Basically, this means that it’s likely that each turn a unit takes will result in it needing to find another path across the map (Depending on density of units, etc., etc.)

Further, for Pathfinding, having a 2D array doesn’t matter as much. Really, you just have to have a reliable way to fetch the list of adjacent edges. Often, this can, at least partially, be handled by the 2D array system that many games use, however that only works when you can make some assumptions about the game in general. In your case, if the method you’ve got (The Sectors) works, then you shouldn’t be worrying too much about it (While I tend to prefer the 2D array method for a grid, I recognize the fact that it often comes down to a ‘When all you have is a hammer’ sort of sentiment).

#3

An empire can have multiple armies in the same sector, so as long as there’s no one else it should be ok. But when, for example, a civilian army wants to move around an army from another empire (you don’t send settlers/workers into the path of armed soldiers) or you want to pass by an army belonging to an empire you have a NAP with (you’re not allowed to enter sectors controlled by empires you’ve a NAP with), then what you describe will happen. I haven’t added the code for these special circumstances yet (will be added in method getAdjacent). But how to avoid armies re-calculating their paths when this happens I don’t know.

That’s what I thought but it’s always good to hear it from someone else as well… :slight_smile:

Cheers!

#4

It sounds like your movement interface is going to be something like Civilization? Where all of your units move at once (Or at least they all have a set number of movement points, and move sequentially before ending your turn), then all other sides get to move? Or is it more like Final Fantasy Tactics, where each unit (Army, whatever) moves individually (Meaning that one from my side goes, one from yours goes, etc. depending on speed or something else)?

Also, 2D arrays aren’t terrible, especially if there are strict, coordinate based rules for movement like in Chess. It’s only when you start to add in other rules that it gets to be different/odder.

#5

The movement system is more like Final Fantasy Tactics, with simultaneous movement. First all empires (player and AI) issue their orders to all their armies and fleets. And when the player press ‘end turn’ all armies/fleets move at the same time according to their initiative. A force with a low initiative moves before a force with a higher initiative. The initiative value depend on what type of troop it is and its size.

We like this system with simultaneous movement since you must guess how your opponent will move when you plan what to do and then everything moves at the same time.

I’ve written the first post of the AI overview now:
http://www.risingempires.com/netherlords/?p=74
I’ll try to complete the next part of the AI overview this weekend.

Cheers!

#6

How are you planning on handling collisions/interruptions then?

I ask this because the way you describe it, it is likely that “faster” armies will always get to go first and will ted to interrupt/prevent other other units from being able to move where they wish which can lead to frustrating blocking techniques.

Basically, say you issued a task “Move to this position and attack Army X” to one of your Army A and enemy Army Y is given the task “Move to this position and Attack Army A”. Army Y moves into a position that prevents Army A from moving close enough to attack Army X this turn, will it attempt to move and then lose its attack phase because it can’t reach X, or will your AI be robust enough to make a decision that if it can’t attack X then it can attack Y, and perhaps destroy it, so that it won’t be blocked again next turn. (And if it’s not robust enough, could the other side decide to pull X backwards, stringing you along a bit so that it can constantly put Y in your way and score several unopposed hits?)

It’s a sort of swarm movement issue that can be quite the pain in the rear to decide upon, since it can give initiative a much higher bonus/value than you would expect.

#7

Armies that move into the same sector will engage each other in combat with the loser being destroyed or forced to retreat to a ‘safe’ sector.

An army with a low initiative that moves before a slow enemy army can move into the same sector as the slow enemy army and lock it in combat. This means that when the slow enemy army tries to move it’s not possible as it’s been attacked. When the battle has finished AND if the slow enemy army won it will be able to continue its movement.

This means, just as you describe that faster armies can be used to prevent the movement of slower armies of another empire. But generally faster armies will be lighter and less strong as initiative depend a lot on the size of the army, or if the faster army is as strong as the slow army it might mean that it’s lots of cavalry and then it’s a lot more expensive than the slow army. It comes with a cost and the player with the slower army might have one more army of the same size which the player with the faster army can’t afford.

If an army is stopped when it tries to move into a sector controlled by an empire which it has a NAP with its movement is now cancelled and must be re-set the next turn.

#8

Previously I’ve written about our pathfinder and a lot about how we want the AI to work at large. Yesterday I posted the second post about the Scout AI (the sub-AI that is responsible for exploring and updating knowledge about the world) which goes into more detail with the code for exploring how much we know of each landmass.

If you’re interested you can find out more here:
http://www.risingempires.com/netherlords/?p=144

I appreciate all tips and hints of how to make the code I show run faster or use less memory…

Cheers!

#9

We’ve completed the work on our scout AI for the moment and I’ve started working on the settlement AI. The settlement AI is responsible for developing and making sure that everything works smoothly in towns and cities. Army and fleet production is done when requested by other sub-AIs and is not directly controlled by the settlement AI.

I’ve posted the game mechanics for how a settlement collects food:
http://www.risingempires.com/netherlords/?p=222

Tonight I hope to finish the article on how a settlement consider its food situation and take the appropriate actions.

Cheers!

#10

I’ve now completed the article about the strategic AI. This is an utility-based AI with the capcity to perform multiple actions each turn, all depending on the available resources. We haven’t implemented economy in its reasoning but when that’s complete we’ll have an AI that can control its empire with some success.

If you’re interested you can read more and look at the code here:
http://www.risingempires.com/netherlords/?p=358

I’m not sure what next article will be about. I’ll probably take a look at the AI class and how it operates. I hope you all have a good weekend! :slight_smile:

#11

Time passes quickly around christmas but work continues on the Rising Empires AI and I’m proud to say that the first version is completed. I’ve run a number of simulations to test it’s features and abilities and summarized it in this article: http://www.risingempires.com/netherlords/?p=430.

So far I’ve only been checking some global statistics when I’ve been running my simulations in order to see how it changes as I optimise the different sub-AIs performance. When I start to run simulations for the next version of the AI which will be capable of attacking and defending itself I’ll need to check the performance of the individual AIs as well. Note that these simulations is done to test and optimise sub-AIs and I’ve yet to come to optimising the strategic AI. This will first be done when there is plenty of more actions that it can perform.

#12

Before christmas I told you I would write an article on my AI class and I finally got around to actually doing it yesterday. The article goes through the AI class but more importantly we take a closer look the AI.update method, the method that runs the AI process, and in which order all sub-AIs and advisors are processed.

This is important as, for example, the scout AI generates information that later is needed by other sub-AIs. The article can be found here:
http://www.risingempires.com/netherlords/?p=470

I’ve also ‘completed’ how the AI attack other empires cities and towns and is now trying to make the AI able to react to attacks as well. If it sees an enemy army coming it must be able to rush some armies to defend it or in the worst case mount a counter attack to retake the city. This is fun to do but also rather complex. When a city is captured we must create a dedicated garrison army for it. Might sound easy but I must go back and change the code for how settlement AIs and the planner work with garrisons as the best choice it to split off a part of the conquest army to create the garrison, not create an objective with the task of building a new army and sending it to the captured city (which gonna take a long time).

I hope you’ll have a good weekend!

#13

We’ve now uploaded the first beta build of Rising Empires on Google Play. If you are interested in testing the current status of the AI we would appreciate all comments. The AI haven’t been trained yet, which means that it can’t evaluate the different types of actions in a good way, but it works… :smiley:

Cheers!

#14

The work on our AI for Rising Empires goes forward and today we release the 4th version. The articles on my blog do not contain much code snippets at the moment but if you’re interested in my thoughts as the AI gets more and more complex head over to ‘Words of the Netherlords’:
http://www.risingempires.com/netherlords/?p=677
Let me know if there is any specific part of the AI code that you want me to discuss in an article.

I hope you all have a good weekend! Cheers!