Jump to content

  • Log In with Google      Sign In   
  • Create Account


Turn Based Strategy AI


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
27 replies to this topic

#1 checkmarkgames   Members   -  Reputation: 165

Like
4Likes
Like

Posted 29 March 2012 - 03:36 PM

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 http://www.checkmarkgames.com/2012/03/building-strategy-game-ai.html
Part 2 is also now available: http://www.checkmarkgames.com/2012/03/turn-based-strategy-ai-part-2.html

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
www.checkmarkgames.com

Sponsor:

#2 Druzil   Members   -  Reputation: 562

Like
0Likes
Like

Posted 29 March 2012 - 05:22 PM

This is great stuff!

#3 Jaap85   Members   -  Reputation: 241

Like
0Likes
Like

Posted 30 March 2012 - 02:18 PM

Very interesting indeed, keep up the interesting posts!

#4 checkmarkgames   Members   -  Reputation: 165

Like
2Likes
Like

Posted 02 April 2012 - 11:20 PM

Just posted the next part. This time I added a simple influence map the AI uses to weight its movements

http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-3.html

#5 Jaap85   Members   -  Reputation: 241

Like
0Likes
Like

Posted 03 April 2012 - 11:10 AM

Looks great, i wonder what your next step will be!

#6 checkmarkgames   Members   -  Reputation: 165

Like
1Likes
Like

Posted 17 April 2012 - 11:21 PM

Part 4, in which the AI is given high level goals.

http://www.checkmarkgames.com/2012/04/turn-based-strategy-game-ai-part-4.html

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.

#7 leopardpm   Members   -  Reputation: 148

Like
1Likes
Like

Posted 19 April 2012 - 03:19 PM

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!

#8 checkmarkgames   Members   -  Reputation: 165

Like
2Likes
Like

Posted 26 April 2012 - 10:12 PM

Thanks leopardpm, I am glad others are finding this interesting and it is always nice to hear from them.

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

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.

#9 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 27 April 2012 - 08:44 AM

Great stuff. Really cool to see the progression, and the guest commentator is awesome. :)

#10 checkmarkgames   Members   -  Reputation: 165

Like
1Likes
Like

Posted 27 April 2012 - 10:44 PM

Great stuff. Really cool to see the progression, and the guest commentator is awesome. Posted Image


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

#11 checkmarkgames   Members   -  Reputation: 165

Like
2Likes
Like

Posted 07 May 2012 - 11:31 PM

Part 6: http://www.checkmarkgames.com/2012/05/turn-based-strategy-game-ai-part-6.html

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

#12 Seongjun Kim   Members   -  Reputation: 223

Like
0Likes
Like

Posted 07 May 2012 - 11:38 PM

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

#13 checkmarkgames   Members   -  Reputation: 165

Like
1Likes
Like

Posted 09 May 2012 - 09:06 PM

Glad to hear you are enjoying it. I hope this will end up being useful to you also!

#14 checkmarkgames   Members   -  Reputation: 165

Like
2Likes
Like

Posted 20 May 2012 - 09:56 PM

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.

http://www.checkmarkgames.com/2012/05/continued-from-part-6-syntaxhighlighter.html

Edited by checkmarkgames, 20 May 2012 - 09:58 PM.


#15 CRyback   Members   -  Reputation: 112

Like
0Likes
Like

Posted 21 May 2012 - 10:32 AM

Great approach, and even greater that you're sharing this. Thanks, helps a newbie like me grasp some AI stuff quite easily Posted Image

#16 Tipotas688   Members   -  Reputation: 86

Like
0Likes
Like

Posted 21 May 2012 - 11:28 AM

Very nice, I'll keep your topic for future reference Posted Image

#17 willh   Members   -  Reputation: 160

Like
2Likes
Like

Posted 21 May 2012 - 06:06 PM

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!

#18 checkmarkgames   Members   -  Reputation: 165

Like
0Likes
Like

Posted 21 May 2012 - 09:21 PM

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.

#19 BlueSalamander   Members   -  Reputation: 625

Like
0Likes
Like

Posted 22 May 2012 - 04:55 AM

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.

#20 Platinum_Dragon   Members   -  Reputation: 162

Like
0Likes
Like

Posted 23 May 2012 - 06:11 AM

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. Tanks are melee damage dealers. 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 tends 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.

How to test AI. 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.
I use QueryPerformanceFrequency(), and the result averages to 8 nanoseconds or about 13 cpu cycles (1.66GHz CPU). Is that reasonable?
I though that the assembly equivalent to accessing unaligned data would be something similar to this order:
  • move
  • mask
  • shift
  • move
  • mask
  • shift
  • or
So it seems reasonable to say that it takes 14 cycles for unaligned data since we'll have to do the series of instructions once to access and once to assign?




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS