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?

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.

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".

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.

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.

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?