Sign in to follow this  
checkmarkgames

Turn Based Strategy AI

Recommended Posts

checkmarkgames    165
I have been working on a new turn based strategy game best described as a fantasy version of Advanced Wars, though certainly with a style all its own. I have reached the point in the project where it is time to create the AI computer player. Looking around for advice, I see lots of high level ideas being discussed, but nothing specifically for a turn based game.

So I thought I would do something about that and will be sharing my progress and related code snippets over at my dev blog as I work on development of the AI. The first post in the series is now available from [url="http://www.checkmarkgames.com/2012/03/building-strategy-game-ai.html"]http://www.checkmarkgames.com/2012/03/building-strategy-game-ai.html[/url]
Part 2 is also now available: [url="http://www.checkmarkgames.com/2012/03/turn-based-strategy-ai-part-2.html"]http://www.checkmarkgames.com/2012/03/turn-based-strategy-ai-part-2.html[/url]

At this point I am not sure how exactly this will turn out. Perhaps the lack of specific tutorials means that this will come together quickly, perhaps I will never finish. Regardless, I am going to share the progress (or lack thereof). So if you have any interest in the topic, or know a lot about it and want to give advice or a critique, stop on by.

-Mark
[url="http://www.checkmarkgames.com"]www.checkmarkgames.com[/url]

Share this post


Link to post
Share on other sites
checkmarkgames    165
Just posted the next part. This time I added a simple influence map the AI uses to weight its movements

[url="http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-3.html"]http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-3.html[/url]

Share this post


Link to post
Share on other sites
checkmarkgames    165
Part 4, in which the AI is given high level goals.

[url="http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-4.html"]http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-4.html[/url]

This took much longer to bring together than the previous installments. I am certainly getting out of my comfort zone. Any and all comments are most welcome.

Share this post


Link to post
Share on other sites
leopardpm    162
Just wanted to say that I am following your progress with great interest and encourage you to continue to develop your project as well as keep updating this thread - its quite enjoyable to follow you with your trials and tribulations!

Thank You!

Share this post


Link to post
Share on other sites
checkmarkgames    165
Thanks leopardpm, I am glad others are finding this interesting and it is always nice to hear from them.

I just posted Part 5: [url="http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-5.html"]http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-5.html[/url]

This time I added some key code behind the order in which the AI moves units, as well as what units it builds each turn and where. The results show a great improvement.

Share this post


Link to post
Share on other sites
checkmarkgames    165
[quote name='willh' timestamp='1335537842' post='4935393']
Great stuff. Really cool to see the progression, and the guest commentator is awesome. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
[/quote]

Glad you are enjoying it. My 9yr old son was very elated to hear you liked his commentary

Share this post


Link to post
Share on other sites
checkmarkgames    165
Part 6: [url="http://www.checkmarkgames.com/2012/05/turn-based-strategy-game-ai-part-6.html"]http://www.checkmarkgames.com/2012/05/turn-based-strategy-game-ai-part-6.html[/url]

The AI is updated to make use of special Leader abilities (CO Powers in the context of Advanced Wars).

Share this post


Link to post
Share on other sites
jsj795    265
I really love the progress on this :) The game looks promising and also gave me a lot of ideas on how I would code my enemy AI

Share this post


Link to post
Share on other sites
checkmarkgames    165
More progress, getting closer to the goal. In part 7 here, in addition to some small tweaks, the AI now detects which player is winning and losing and changes its behavior accordingly.

[url="http://www.checkmarkgames.com/2012/05/continued-from-part-6-syntaxhighlighter.html"]http://www.checkmarkgames.com/2012/05/continued-from-part-6-syntaxhighlighter.html[/url] Edited by checkmarkgames

Share this post


Link to post
Share on other sites
CRyback    112
Great approach, and even greater that you're sharing this. Thanks, helps a newbie like me grasp some AI stuff quite easily [img]http://public.gamedev.net//public/style_emoticons/default/wink.png[/img]

Share this post


Link to post
Share on other sites
willh    160
Im really enjoying following your progress. It's satisfying technicallY, and I can't help but feel warm and fuzzy knowing how your son is involved. :). Its really cool how enthusiastic he gets about the different tricks you add, and he asks some really good questions.

I'm particularly interested in seeing you apply the GA optimization. Have you thought about keeping the top N strategies, so that maybe you could have different play styles that are of the same difficulty?

Keep up the great work!

Share this post


Link to post
Share on other sites
checkmarkgames    165
It is always good to hear people are watching. Including my son has been a huge help, as having someone to talk to makes the naration so much easier. I understand now why sports commentators come in pairs. I have been looking forward to using a GA ever since I started this project. Will be finding out soon enough if it will make a difference.

Share this post


Link to post
Share on other sites
BlueSalamander    966
Thank you for this interesting blog. Your AI looks like a worthy opponent now.
The AI in Advance Wars was quite good but it ignored the fact that one of the units was absolutely better than the rest: the heavy tank.
In the final battle the AI had tonnes of money but it did not use it to buy lots of heavy tanks and that was its downfall.

Share this post


Link to post
Share on other sites
We figured that the AI (of Advance Wars) requires 5 soldier type units, with soldier oriented COs (like Sami or Sensei) make the AI require at least 8 soldier units. These build orders are built into the AI to keep them weak. Players also get first turn advantage against the AI.

In player vs player battles, the most built unit is the infantry because it has the most cost efficiency to hold territory. Artillery is the major source of damage dealer, and the infantry takes on the role of damage takers. No your tanks are not damage takers, infantry are damage takers, and that's why I don't like role playing games calling damage takers as tanks since damage takers are infantry. [i]Tanks are melee damage dealers[/i]. Artillery are ranged damage dealers, and they are the most cost efficient unit in the game for player versus player. All the other unit takes on support roles. Most player vs player is mass infantry and sufficient artillery. Heavy tanks are less cost efficient against the artillery without support. Remember that any high tier unit requires the support of low tier units. It's rare for high level player vs player to use high tier units.

Do you know how the scoring works with Advance Wars? Getting a good score in campaign is not the same as being a good player in player versus player game at all. In fact, it teaches players to tech up to high tier units that have lower cost efficiency. High tier unit has better unit count efficiency where players have a cap of 50 units. Unless players are near the cap, or there's an intense trench warfare (massive infantry lines and artillery that makes your rear line artillery too far to shoot), high tier units tend to not be worth the effort to make. If a player sees that a long stalemate occurs with a trench warfare, rockets are suitable units to make as they have more range than artillery. Since every unit counts as 1 unit towards the 50 unit cap, it becomes a time to transition towards high tier units only if (1) the player has enough fund to maintain recruit at all bases, (2) the player will ensure the running average unit count does not fall and (3) the new units must reach the front lines without losing grounds. If the running average unit count falls, it means their unit lack defense, and they need to build unit with more cost efficient defense, typically the infantry. If they lose grounds, then they need faster damage takers to the front line, so focus on those. Low tier units are more cost efficient as damage takers. We measure damage efficiency by how many hits it takes to kill a unit. Two hit kill is still two hit kill. Even 9 damage is still two hit kill and has the same battle performance as 5 damage in most cases.

Simple good tip for Turn Basd Strategy: Always recruit from the frontal bases first, and always try to recruit from all bases (unless you're saving for teching up to a high tier unit). Unless the unit cap is limiting, always try to get the maximum possible units because units hold spaces on the 'game board'. Clumping up units is a good way to ensure that ranged unit can have a safe place to fight behind. In fact, player versus player focus on having cost efficient infantry lines. Cheap Melee units at the front with the Cheap Range unit behind them [i]tends [/i]to be the most cost effective strategy. Lines of battles are realistic to the medieval time period. When games don't like the clumping effect, it's because of a stalemate like situation where any minor mistake will show up many turns later that the player cannot coordinate where their mistake is at. Or maybe small mistakes disappear because the lines collide is so much.

Focus Fire increase the battle power in a quadratic fashion, while lines of melee are simply linear increase the battle power. Remember: Linear Warriors (melee units), Quadratic Wizards (ranged units that focus fire). Ranged units that don't focus fire increase power linearly just like melee units. Thus, if the trench warfare is too deep, even short ranged unit becomes "melee" units by their incapacity to focus fire. This is the time to bring in long ranged units.

[b]How to test AI. [/b]Have each of your AI play as player 1, and player 2. At least 30 games as player 1 and at least 30 games as player 2. Statistics require at least 30 to create a 'normal' distribution. And with that distribution, compare the first turn advantage. Each change in the condition will need fine tuning. Of course, each modification to offset the first turn advantage requires you to start the gathering of data again from the beginning because data is strictly related to the condition. You need to gather these data to ensure that your AI work equally as either player 1 or player 2 and still have the same chance of victory. Each map may individually require different amount of resource for player 2 to offset the first turn advantage, so you need to test out each map individually.

Share this post


Link to post
Share on other sites
checkmarkgames    165
An excellent amount of information and insight Platinum_Dragon, thank you so much for taking the time to leave this comment. I was not aware of the tendancy of multiplayer Advance Wars games to tend towards large amounts of infantry and artillery. I hope to make all units useful with this game, and it looks like a lot of testing and tweaking is in my future.

Share this post


Link to post
Share on other sites
checkmarkgames    165
Part 8 is finally finished. This time I used a Genetic Algorithm to try to evolve a better AI player. Check out the results here:

[url="http://www.checkmarkgames.com/2012/06/turn-based-strategy-game-ai-part-8.html"]http://www.checkmarkgames.com/2012/06/turn-based-strategy-game-ai-part-8.html[/url]

Share this post


Link to post
Share on other sites
jsj795    265
I'm actually developing a turn-based strategy myself, and I've been having trouble with AI. Your blog posts have made me realize many points that I can incorporate for my game! Thank you so much :)

Share this post


Link to post
Share on other sites
Here's a good link: http://warswiki.warscentral.com/Score

It's about how Advance Wars determine the player's performance. If you instead use a similar method of adding the value from multiple goals, and ultimately try to maximize the overall value, then your AI may be more dynamic. Have multiple goals that are calculated independently.[list=1]
[*](SPEED) Try to win as fast as possible, create a time limit for perfect score and a decay formula.
[*](POWER / ATTACK EFFICIENCY) Try to cause as much damage as possible, with killing enemy units worth a whole lot.
[*](TECHNIQUE / ATTRITION) Try to build a whole lot of units. Measure the percent of remaining forces.
[/list]

In 1 & 2, set you have set points for destroying enemy units.
In 3, you have points earn for gaining gold, but it should be modify so that the AI gain points for building units.

You need to make the building of high tier unit worth points using a multiplier so that high tier units are worth more than their cost by a significant amount. This will cause the AI to try to build as many high tier units first, and using the remaining gold to build units. The AI needs to maximize the amount of units it has, but needing a priority in having high tier units. Losing a unit should be worth the amount of points gain for building the unit plus the amount of points gain for gaining the gold. With this in effect, the AI will try to preserve its units.

A simple formula for earning points for unit is (Points Earn = Unit Tier * Unit Cost). This will allow the AI to maximize with the strongest possible units it can build. Of course, this is not the best strategy since high tier units need support from low tier units. I believe the attrition objective will counter the effect of purely building high tier units. Two opposing objective will mean that your AI should find a range of equilibrium, not a fix position.

Summary:[list]
[*]You want to have multiple independant goals that will sum up together.
[*]Maximizing the overall total score is what you want your AI to do.
[/list]
Other Notes:[list]
[*]You AI will never be as powerful as strong players, but average players may find them a challenge.
[*]Remember that a larger percentage of player population are more casual than the 20th Century gamers.
[/list]

Share this post


Link to post
Share on other sites
checkmarkgames    165
@jsj795 Glad it has been of use to you, please let me know if you discover anything of interest while developing your own AI

@Platinum_Dragon Once again a great bit of information! I am currently using various unit ratios to determine what the AI should build. So that it tries to build the unit type that is furthest away from its current ideal ratio. That seems to be working good so far, but it is good to know of the alternate you suggest.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this