Hard Rules of war: Another look at AI

[DensterNY]

I'm starting to learn how to program Macromedia Flash and the people I'm studying with were tossing around ideas for projects to work on. Since I love Total war I thought that a mini-Flash version would be fun and we discussed it for some length. (Please don't ask about it because we're all just learning so I have no idea when something presentable would even be remotely ready)

One thing that I brought up was trying to develop a competent AI that would know how to fight like a capable Medieval warlord. So from that we tried to draft informal "hard rules of war" that the AI would try to follow and the whole experience shows one way to try and hardcode a war strategy.

For instance, here were a few rules that I laid down based upon my experiences.

1. Armies should form up and retain a solid, unbroken line with a strong defensive center.
2. Skirmishers and archers will stand before the line at the outset of engagement to pelt the enemy and return to a position behind the line when the enemy has moved close.
3. Cavalry should attempt to flank by moving entirely around the enemy line or moving evasively to position themselves to attack once the lines are engaged.
4. Cavalry should never engage spearmen unless in a flanking move. Archers should never engage melee soldiers but instead position themselves to fire.
5. Armies should avoid attacking going uphill.
6. Heavy cavalry for shock charges into melee. Light cavalry to attack missle troops and light infantry.

I'm sure you guys could add plenty more basic rules but of course war doesn't work so neatly especially against a human player who can learn and change strategies on the fly. For instance, I sometimes shift my lines prior to direct engagement to confuse and break up the AI's line so would you instruct the AI to retain its position or try to change itself up to avoid being outmanuevered?

So I ask could you really try and capture the essence of war strategies with hard rules or is it doomed to be overcome by competent human players no matter what? I know that having some kind of learning and adapting AI would be the ideal but how likely this would be is a big question since programming is about handling rules and exceptions. Also, No I do not let CA off the hook on this subject because its difficult as we pay them hard cash and they make millions on these TW games.

[Lord Adherbal]

on a flat open ground it should be possible to make an AI capable of challenging any human. It's special terrain features, impassible terrain etc that make things a lot more complicated.

[Tamur]

Interesting list & question. I was thinking of doing the same sort of thing but exclusively with the diplomacy engine -- "how hard can it be" gets asked a lot, I was going to give it a go and see.

There are a lot of approaches you can take: everything from a huge list of rules (rules which can be broken by the human player to great effect, as you noted), to the game-time impossibility of a neural network.

There are other middle-of-the-road ways as well. One way that hasn't been explored terribly well for game AI is genetic algorithms. The basic idea is that any situation is a problem to be solved, with more or less optimal solutions, and solutions can be evolved by considering hundreds or millions of solutions to the same problem, then store the best result for future use and mutation. Thus the genetic aspect.

In programming terms, given a specific set of inputs, in this case:

• how many troops of what type does the enemy have
• how are they arranged
• what are their vectors (velocity and direction)
• what terrain are they standing on
• what is between them and us

what is the best troop position & vectors for the AI army?

The problem is that the list of factors to consider is not just limited to what I've listed, and can be postively Huge.

But, this sort of approach is extremely flexible because in genetic algorithms, one cannot specify rules like you were listing. The computer has to learn not to charge horsemen into sharpened wooden stakes from experience. The experience comes before the game ships (i.e. the AI is trained as part of the game development process).

Rambled on too long. I'd definitely like to see some exploration in this area rather than the endless moaning that goes on. CA have been facing a challenge greater than any other strategy game on the planet for years with the battlefield AI.

Good luck!

[sunsmountain]

So I ask could you really try and capture the essence of war strategies with hard rules or is it doomed to be overcome by competent human players no matter what?

Yes, it's a book called Sun Tzu's Art of War, and CA have already implemented it since the start. The reason they abandoned the Medieval:TW AI was because of a new engine, and they wanted 20 individual units to think for themselves (unit level AI) as well as listen to army level AI, something they found lacking in the MTW AI.

Unfortunately, they bit of more than they could chew, since individual units are now stubborn as hell and coordinate their attacks little. They are now in the process of writing the army level AI which has to calculate a respons given any situation. They think they will succeed because they think that if the army level decision is wrong, the unit level decision is still right. A human can do this. A computer might.

I'm still undecided about whether they will succeed. They haven't so far...

The problem is that the list of factors to consider is not just limited to what I've listed, and can be postively Huge.

It is. Because of that, of the factors you list, 2 are used, 3 are not:
# what are their vectors (velocity and direction)
# what terrain are they standing on
# what is between them and us

Troop type is evaluated together with relative distance to a particular unit by that unit. If it is advantageous for that unit to attack that troop type and the enemy is close, attack & run. If further away, attack & march. If disadvantageous and close, wait. If disadvantageous and further away, move away from that troop type towards a second enemy while keeping your distance with the first enemy, leading to stupid stuff like AI line breaking, all its sword units focusing on your 1 spear unit... etc. The AI should start thinking sooner rather than later.

But, this sort of approach is extremely flexible because in genetic algorithms, one cannot specify rules like you were listing. The computer has to learn not to charge horsemen into sharpened wooden stakes from experience. The experience comes before the game ships (i.e. the AI is trained as part of the game development process).

The biggest problem with these algorithms is that kind of the right answer in battle is the wrong answer. If you're kind of approaching my units from the right attack vectors, but your flank is kind of showing, I'm kind of going to butcher you. Next time, the flanks will be good, but that means the unit has turned, and then the attack vector (and essentially, timing) is wrong.

CA's approach has the black/white advantage, it either works or it doesn't. But they have to get it exactly right...

[Furious Mental]

* Use artillery to force enemy off high ground.

[DensterNY]

Good discussion and as you guys can see the minute you start to try and analyze the AI situation you realize how complicated it can be. As we've established strategy in war must be dynamic in relation to battle conditions, your enemy and the quality of their commanders. A human player can make quick decisions to accommodate changes and to take advantages and minimize disadvantages. Unfortunately, I'm not sure what guidelines the AI has in TW beyond Medieval I but there are entirely too many moments when the AI is simply stuck.

I'm not sure what could be the next step in AI development because even if they eventually figured out how to make a generally competent AI in the field then you will still have to plan for guile and deceit. I know I've won quite a few battles by sneaking shock troops/cavalry behind enemy lines and smashing into them when formally engaged.

Also, in the end the human player will simply dominate because we can learn and adapt to win. Yes, CA did reference the Art of War but as a human player I have Caesar, Scipio Africanus, Hannibal, Alexander and Genghis as my tutors.