Turn Based Strategy AI

Started by
26 comments, last by checkmarkgames 11 years, 8 months ago
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).
Advertisement
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
Glad to hear you are enjoying it. I hope this will end up being useful to you also!
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
Great approach, and even greater that you're sharing this. Thanks, helps a newbie like me grasp some AI stuff quite easily wink.png
Very nice, I'll keep your topic for future reference wink.png
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!
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.
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.
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?

This topic is closed to new replies.

Advertisement