• Advertisement
Sign in to follow this  

AI found in Advance Wars? (or simlar turn-based strategy games)

This topic is 4578 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys, I'm working on a small turn based strategy game similar to Advance Wars or Military Madness or Fire Emblem. What AI techonologies are useful for a game like this? How feasible is to use newer techs like GAs or NNs to come up with a challenging computer opponent? If possible, I'd like to author a pretty good AI solution without writing a huge clump of "if" branches. Any advice?

Share this post


Link to post
Share on other sites
Advertisement
I would suggest keeping it simpler. NNs and GAs are often more trouble than they are worth, and even though they have the capability to 'learn' it is a challenge in itself to set up the means of them learning, and if not set up properly they can learn to be stupid.

I'm not familiar with the specific games you mention but a TBS AI can easily be done with much simpler techniques. Check out the book Programming Game AI by Example if you want an excellent source of most of the different aspects of AI used in games.

Share this post


Link to post
Share on other sites
I'm also making a game like advance wars at the moment. I just wrote my AI code, and it works pretty well. Basically, I used a finite state machine for each unit that consisted of instructions like advance, retreat, etc. When the AI is advancing, they seek out one of the player's units to attack. When the AI is retreating, they seek cover to hide behind. Although it sounds very simplistic, it actually works quite well.

Share this post


Link to post
Share on other sites
Well, I'm slowly walking towards the goal of writing a 3D version of Advance Wars myself.

I've thought about the AI component, and here's more or less how I would do it.

I would code filters that would create "influence maps" (IM). For each grid on the map, define if it can be taken by the enemy, if the enemy can attack there, by how many units, if it can attack from just land, or by air and/or sea, etc...

Having influence maps also allows me to dinamicly (in the middle of the level) to change the stats of a Tank, or all tanks, or all units in a faction. Because the game isn't specificly looking at the tank's capabilities, but instead the IM the unit generates...

After I'm happy with the various influence maps this will require, I'll then code a state machine with "outside switches". Generals have personalities. When confronted with the same situation, some would confront the enemy head on, and impact as much damage as possible. Others would create a tactical ring around neutral buildings so that they would have enough time to capture them. Others would call reinforcements from the air, etc, etc...

So, that "master" state machine would be governed with "weights", and each General would have its own set of Weights. This would create varying behaviour between diferent Generals.

I'll also make it so MODders can extract the AI plugin, and rewrite it, globally or just per General. A part of the AI will also be governed by Lua scripts, where all the weights for a certain General, amongst other settings will be setup.

Hope it helped.

Share this post


Link to post
Share on other sites
The AI in Advance Wars is actually pretty bad. I found a pretty good summary of what it does here.

But having "bad" AI doesn't make it a bad game. It just means that playing against the AI becomes completely different than playing against a human. The challenge is to learn how the AI thinks, and to use that to outsmart it. One example is that the AW AI totally hates infantry units. If you put an infantry unit anywhere near one of his buildings, he will use every means necessary to destroy it. So, a good tactic is to send in a bunch of "human shield" units that prevent your other units from being attacked.

One thing that would improve the AI a lot is if it would actually look ahead a few turns. This is how chess AIs work: Deep Blue would search every possible move up to 31 turns deep (with pruning). Even if the AW AI could only search a few moves deep, this would be a major improvement.

This is what I'd recommend if you wanted to make a good AI: a search function that just searches every possible sequence of moves. Since the branching factor would be really high, you would probably have to prune the search, which means that you evaluate if a move is just outright bad, and that you don't bother searching on the obviously bad moves.

Also you can restrict your search even further. You can make assumptions like "if a tank is in range of someone, he should attack". So then, if the tank has several choices of who to attack, you just search through each one of them. (instead of searching through every possible thing that the tank could do). This particular assumption might not be the best, because at some point it might be in the AI's interest to place the tank in a defensive position and not actually attack anyone. But you get the idea.

NNs and GAs would be overkill I think.

Share this post


Link to post
Share on other sites
Quote:
Original post by pinacolada
The AI in Advance Wars is actually pretty bad. I found a pretty good summary of what it does here.

But having "bad" AI doesn't make it a bad game. It just means that playing against the AI becomes completely different than playing against a human. The challenge is to learn how the AI thinks, and to use that to outsmart it. One example is that the AW AI totally hates infantry units. If you put an infantry unit anywhere near one of his buildings, he will use every means necessary to destroy it. So, a good tactic is to send in a bunch of "human shield" units that prevent your other units from being attacked.

One thing that would improve the AI a lot is if it would actually look ahead a few turns. This is how chess AIs work: Deep Blue would search every possible move up to 31 turns deep (with pruning). Even if the AW AI could only search a few moves deep, this would be a major improvement.

This is what I'd recommend if you wanted to make a good AI: a search function that just searches every possible sequence of moves. Since the branching factor would be really high, you would probably have to prune the search, which means to evaluate whether a move is just outright bad, and to skip searching the obviously bad moves.

NNs and GAs would be overkill I think.


arghh.... totally right from a technical standpoint, totally wrong from a Game Design standpoint...

You see, you cannot implement and unbeatable AI, or the player will lose interest immediatly. The AI engine has to be configurable enough so that you can "improve" it as the levels progress.

That's the jobs of the Weights I described in my earlier post. On an early level just assign too much importance to defending your ranged units, and the human player will have no problem in taking the HQs using his infantry... or something along those lines...

One thing I'll agree, NNs and GAs are overblown, and, if we where team mates on a GameBoy Advance project, both would be out of the question, as the unit does not have that level of processing power...

Share this post


Link to post
Share on other sites
Quote:
Original post by Prozak
arghh.... totally right from a technical standpoint, totally wrong from a Game Design standpoint...

You see, you cannot implement and unbeatable AI, or the player will lose interest immediatly. The AI engine has to be configurable enough so that you can "improve" it as the levels progress.



I don't want it to be unbeatable, I just think it would be more fun if the AI was on a level playing field with you. You'll notice that in every level of Advance Wars, the AI starts with 2-3 times more buildings/income than you. This is to compensate for the fact that the AI is pretty bad. If the AI was smarter, then we could have levels where you and the AI start with exactly the same number of resources, which I think would be more fun and interesting.

Also as far as needing to have the AI "improve"; It's pretty easy to start with an algorithm that represents the "best possible" AI, and then f with it so that it purposefully plays badly. You can just say "on easy mode, the AI only looks 1 turn deep, and it has X chance to pick a move which is not the best, or Y chance to flip out and do something completely dumb. On medium, it only looks 3 turns deep.. etc etc etc".

Share this post


Link to post
Share on other sites
Thanks for the replies.

My thinking for applying GAs or NNs was that it might save me from writing lots of specialized one-shot code that I've found with some titles I've worked with. I'm not concerned about the limitations of the GBA, but I understand it might be overkill (plus, it might be difficult to represent the problem or search space in such a way to be used for GAs).

So right now I'm hearing strong support of Influence Mapping and Finite State Machines with weights. Looking ahead a couple a turns sounds interesting too. I'll have to think about how I could acomplish that especially with dozens of units on the screen.

Any more insights are appreciated. Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by Prozak
Quote:
Original post by pinacolada
The AI in Advance Wars is actually pretty bad. I found a pretty good summary of what it does here.

But having "bad" AI doesn't make it a bad game. It just means that playing against the AI becomes completely different than playing against a human. The challenge is to learn how the AI thinks, and to use that to outsmart it. One example is that the AW AI totally hates infantry units. If you put an infantry unit anywhere near one of his buildings, he will use every means necessary to destroy it. So, a good tactic is to send in a bunch of "human shield" units that prevent your other units from being attacked.

One thing that would improve the AI a lot is if it would actually look ahead a few turns. This is how chess AIs work: Deep Blue would search every possible move up to 31 turns deep (with pruning). Even if the AW AI could only search a few moves deep, this would be a major improvement.

This is what I'd recommend if you wanted to make a good AI: a search function that just searches every possible sequence of moves. Since the branching factor would be really high, you would probably have to prune the search, which means to evaluate whether a move is just outright bad, and to skip searching the obviously bad moves.

NNs and GAs would be overkill I think.


arghh.... totally right from a technical standpoint, totally wrong from a Game Design standpoint...

You see, you cannot implement and unbeatable AI, or the player will lose interest immediatly. The AI engine has to be configurable enough so that you can "improve" it as the levels progress.

That's the jobs of the Weights I described in my earlier post. On an early level just assign too much importance to defending your ranged units, and the human player will have no problem in taking the HQs using his infantry... or something along those lines...

One thing I'll agree, NNs and GAs are overblown, and, if we where team mates on a GameBoy Advance project, both would be out of the question, as the unit does not have that level of processing power...


You should read up on minimax and alpha beta searches, Prozak. By limiting the depth that the computer can search for the next best move, you can control the difficulty. Obviously an AI that only looks ahead 3 moves would be worse than one that looks ahead 8 moves.

Searching ahead would be a good way to implement an AI that doesn't cheat and makes dumb moves when it's dumb, and smart moves when it is smart. Difficulty can be changed just by changing a single value.

My experience with these types of games is that they are pretty dumb. Always attacking me when I have the high ground and stuff. You could probably just have the units attack the target in range that would take the most damage from the attack.

If you want to do any kind of game state searching, then you might want to just look at moves that result in an attack, and pick the one that puts the AI in the best position. You could just do state-based stuff for the rest of it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zefrieg
You should read up on minimax and alpha beta searches, Prozak. By limiting the depth that the computer can search for the next best move, you can control the difficulty. Obviously an AI that only looks ahead 3 moves would be worse than one that looks ahead 8 moves.


I think this sounds cool, but can it work for a game like Advance Wars where *all* enemy units make a move before the player's turn is over?

In chess, the opponent only moves one peice at a time, so if you're looking ahead for 8 turns then you're only looking ahead 8 moves. But in Advance Wars your opponent may very well move dozens of units before their turn is up. Won't this make looking ahead any number of turns unmanagable?

Or am I not getting you?

Share this post


Link to post
Share on other sites
Assume you have 10K units.
Assume they each has 6 possible moves.
Assume they can do each of there moves on 12 different objects.
Assume you are searching 3 deep.

Thats (10000*6*12)^3 = 3.73248 × 10^17

No way yo ucan search that.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by DangerCode
Hi guys,

I'm working on a small turn based strategy game similar to Advance Wars or Military Madness or Fire Emblem.

What AI techonologies are useful for a game like this? How feasible is to use newer techs like GAs or NNs to come up with a challenging computer opponent?

If possible, I'd like to author a pretty good AI solution without writing a huge clump of "if" branches.

Any advice?


If you are familiar with these games, Nice Coder, you would know that the most units he might see might be 20-30 on a game map at once. If he only looks at plays that result in attacks, then he could reduce his search space to something around chess pretty easily.

You are right though, Nice Coder, it would be difficult to search 3 deep with what you described. Unfortunately, that really doesn't pertain to DangerCode's game at all.

Share this post


Link to post
Share on other sites
Quote:
Original post by DangerCode
Quote:
Original post by Zefrieg
You should read up on minimax and alpha beta searches, Prozak. By limiting the depth that the computer can search for the next best move, you can control the difficulty. Obviously an AI that only looks ahead 3 moves would be worse than one that looks ahead 8 moves.


I think this sounds cool, but can it work for a game like Advance Wars where *all* enemy units make a move before the player's turn is over?

In chess, the opponent only moves one peice at a time, so if you're looking ahead for 8 turns then you're only looking ahead 8 moves. But in Advance Wars your opponent may very well move dozens of units before their turn is up. Won't this make looking ahead any number of turns unmanagable?

Or am I not getting you?


Well, you certainly wouldn't brute force something with so many moves. You would basically have to pick out specific moves that might have the highest utility like a stronger unit attacking a weaker opponent.

Also, you don't have to look at the game from the perspective of the whole board either. You could break it down into layers. Perhaps at the highest level you look at the number of units in say a 4x4 square region. Obviously, if the player has 5 units in that area, and the computer has 1, then it might be good for the computer to pull that unit back to a 4x4 square region that has more computer units. If the computer has an equal or greater amount of units in a 4x4 square region, you might run alpha beta on that section to determine what moves the units contained within should do to maximize damage to the opponent and minimize damage to themselves.

Doing something like this would have the computer look at the game from a territorial perspective while being able to focus in on individual units and maximize their play.

Share this post


Link to post
Share on other sites
The problem with that type of aproach Zefrieg, and the point I was trying to make in my previous post, is that it is mechanical, much like Chess.

In Chess, when playing the computer, you often feel the computer isnt making much sense at all in his choice of moves, it only "clicks in" for you later.

So, there are two paths to AI design, the one that will bring the most profit, to the AI, and the one that will feel the most Human, to the Human.

My experience tells me that using FSM and IM is the best choice when you want to make the player feel he is facing a clever oponent, isntead of a mechanical opponent.

Share this post


Link to post
Share on other sites
Quote:
Original post by Prozak
The problem with that type of aproach Zefrieg, and the point I was trying to make in my previous post, is that it is mechanical, much like Chess.

In Chess, when playing the computer, you often feel the computer isnt making much sense at all in his choice of moves, it only "clicks in" for you later.

So, there are two paths to AI design, the one that will bring the most profit, to the AI, and the one that will feel the most Human, to the Human.

My experience tells me that using FSM and IM is the best choice when you want to make the player feel he is facing a clever oponent, isntead of a mechanical opponent.


That computer chess opponent isn't making much sense to you, because it is looking ahead further than you can.

If you want to use pure influence maps for low level strategy, then it will seem as though the AI is planning. Unfortunately, it is only reacting, and any human player that can look ahead a few moves is going to wipe the floor with it.

DangerCode said he wanted a challenging opponent, not one that requires you pit the player against impossible odds to give him a challenge.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zefrieg
Quote:
Original post by Prozak
The problem with that type of aproach Zefrieg, and the point I was trying to make in my previous post, is that it is mechanical, much like Chess.

In Chess, when playing the computer, you often feel the computer isnt making much sense at all in his choice of moves, it only "clicks in" for you later.

So, there are two paths to AI design, the one that will bring the most profit, to the AI, and the one that will feel the most Human, to the Human.

My experience tells me that using FSM and IM is the best choice when you want to make the player feel he is facing a clever oponent, isntead of a mechanical opponent.


That computer chess opponent isn't making much sense to you, because it is looking ahead further than you can.

If you want to use pure influence maps for low level strategy, then it will seem as though the AI is planning. Unfortunately, it is only reacting, and any human player that can look ahead a few moves is going to wipe the floor with it.

DangerCode said he wanted a challenging opponent, not one that requires you pit the player against impossible odds to give him a challenge.


Oh Yeah?! Well... you suck!

Share this post


Link to post
Share on other sites
I have not played the games mentioned but in my experience with wargames, you need not be worrying about making the AI too smart, you need to be concerned with making it smart enough. I have never faced a computer AI that can realistically challenge a human unless it has extreme odds on its side or the game is very simplistic as with chess.

In the game I am doing, I have divided the AI into two logical areas, what I call the tactical AI and the strategic AI. In my case I have a command structure which means I can give broadbased non-specific orders from the general (strategic AI) and then get the units to implement the details (the tactical side). I actually copied this concept from old fashioned table top wargame rules where they applied massive delays to changing the 'Actions' of a unit and these 'Actions' applied restrictions to how each unit could behave.

Getting the tactical side of things going doesn't seem to be much of a bother really. Each 'Action' has a bunch of rules associated with it which, I think, a state machine will handle quite nicely. I have implemented a 'memory' in my state machine so that it doesn't chop and change but goes through with what it is doing but I have yet to test this properly to see how this is going to work out.

Getting the strategic side of things working is a heck of a lot harder and is absolutely critical (well it is to my game anyway) to providing a significant challenge to a human. I am looking at creating two modules to start off; a terrain analysis module and a force analysis module. These combined should analyse the environment and create an influence map that takes into account what I am facing, what I have and what the terrain is like. I then want to try an use some sort of pattern matching system to match it up with the best broad strategy which is then used to decide on the orders (Actions) for each unit. This pattern matching will likely be quite crude and to keep it un predictable I will try to add some sort of randoms into the mix - I have yet to even start this side of things so who knows how well this is going to work out.

It's pretty hard to explain but I hope this gives you a few ideas and I would love to hear what you come up with. Trying to get good information on this sort of thing seems to be quite hard. Almost all the AI sites I have visited seem to be fixated on either A* which is so heavily covered you can pretty much just down load a solution ready to use, or GA and NN which while they are discussed ad nauseam, they never seem to be actually applied to any real game problem. I probably should just buy a book on the subject.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Assume you have 10K units.
Assume they each has 6 possible moves.
Assume they can do each of there moves on 12 different objects.
Assume you are searching 3 deep.

Thats (10000*6*12)^3 = 3.73248 × 10^17

No way yo ucan search that.

From,
Nice coder


What game has 10,000 units? Certainly not an advance wars type game.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement