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.

[sunsmountain]

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.

If they would succeed in making a generally competent AI I would already be afraid, actually. Because competence already implies being able to handle different tactics. And when you really get down to it, there are no such things as sneaking or smashing, there are only positions, vectors, attack rolls, casualties, etc.

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.

And the AI has the possibility of calculating all possible outcomes in advance, vastly outweighing any historical general. Perhaps not during battle, as it is constrained by time. But that will be the only safeguard against an AI simply outsmarting us.

[DensterNY]

If they would succeed in making a generally competent AI I would already be afraid, actually. Because competence already implies being able to handle different tactics. And when you really get down to it, there are no such things as sneaking or smashing, there are only positions, vectors, attack rolls, casualties, etc.

I meant competent as opposed to completely incompetent which is what we've had since RTW with the AI. As it stands it cannot cope with nearly any tactic that the human player has to offer so it would be a refresher for the AI to behave at a minimum as it did in MTW. At least then it fought as an army and moved and positioned itself to its maximum advantage as opposed to attacking pell mell with no strategy at all.

And the AI has the possibility of calculating all possible outcomes in advance, vastly outweighing any historical general. Perhaps not during battle, as it is constrained by time. But that will be the only safeguard against an AI simply outsmarting us.

Although I understand your concept that the AI has the computer's raw calculating ability at its disposal it really wouldn't benefit in this situation even given a fast enough processor. First, it could evaluate the troops, terrain and quality of general of its opposition then guess what the enemy may do and then calculate from there but this is only effective against another AI general who'd behave in an expected manner. However, a human AI can and will do any number of unexpected things which would mean the AI's original calculation would be thrown out. And as it was busy trying to recalculate what to do the human general would be butchering their troops and routing them from the field.

I believe it was Julius Caesar who was asked about field strategies and he answered something to the effect, "Show me my men and show me my enemies and then I'll give you strategy and tactics." So in order to have a challenging AI we would need one schooled in the arts of war, disciplined, intuitive and battle experienced.

[Tamur]

So in order to have a challenging AI we would need one schooled in the arts of war, disciplined, intuitive and battle experienced.

Which is exactly the thrust of my initial post in this (very interesting) discussion -- it is possible to give an AI the base rules, discipline, and experience you speak of. Intuitiveness, that's a different story of course.

Or at least it is possible in theory. Reality, that's yet to be determined.

[Vladimir]

So there is little possibility of creating a code that seeks "pleasure" and avoids "pain"? That's how humans learn on a very basic level and should be easy to codify.

[sunsmountain]

So there is little possibility of creating a code that seeks "pleasure" and avoids "pain"? That's how humans learn on a very basic level and should be easy to codify.

Nope, pleasure of the individual is not pleasure if it causes the majority of the group pain, but the individual wouldn't know. Like a general charging itself at enemy ranks. Highly pleasurable for the general. Highly painful for the army and the player.

Forcing the individual to listen to the group would work better, but isn't very adaptive.

[DensterNY]

Likewise the pain of one may be for the benefit of the group. I sacrifice my weakest troops or my most heavily armored troops sometimes to draw arrows so that I can close in with the rest of my army for melee. So this kinda complicates the whole essence of trying to program an AI to think like a human general, trying to think of the larger strategic plan.

Actually, in thinking about the whole idea of how an AI should be organized and directed I've come to realize that its just way too complicated to create an effective AI general. We simply want to be challenged by an opponent who can think like a human and this simply cannot be created as of yet with an AI.

Perhaps, one day but not yet... hehe, then it would be the precursor to Cyberdyne, the Terminators, John O'Connor, etc... "Oh no we taught the computers how to fight and learn and conquer and now they've come for us."
(Sorry, I just finished my summer finals and feeling elated here)

[Tamur]

congrats on finishing up finals, summer is Not the time to be in school

Regarding the case you mention (sacrificing a unit to the larger objective), this is relatively straightforward. The AI needs a single overriding goal, which breaks into multiple meta-goals, which each translate into a sequence of individual unit moves. If one of the meta-goals is to draw the enemy out of a defencive position, the AI will have a few options to do this with (advance a unit who will obviously be butchered, run cavalry at the archers in front and then withdraw, start up the long-range missile fire, etc).

This is not quite theoretically anymore, since I've got a good ways into designing both a campaign and battlemap AI API. Quite the enjoyable summer project --- no graphics to deal with, so it moves quickly.

[BDC]

Perhaps, one day but not yet... hehe, then it would be the precursor to Cyberdyne, the Terminators, John O'Connor, etc... "Oh no we taught the computers how to fight and learn and conquer and now they've come for us."
(Sorry, I just finished my summer finals and feeling elated here)

At least they'd be limited to medaeval era weaponry. Oh no the musketeers have cunningly outflanked us. Ah well. Shoot them anyway.

[DensterNY]

congrats on finishing up finals, summer is Not the time to be in school

I agree completely. The mind is closed off to studying when it is hot and beautiful out. I will try and avoid summer studies in the future.

Regarding the case you mention (sacrificing a unit to the larger objective), this is relatively straightforward. The AI needs a single overriding goal, which breaks into multiple meta-goals, which each translate into a sequence of individual unit moves. If one of the meta-goals is to draw the enemy out of a defencive position, the AI will have a few options to do this with (advance a unit who will obviously be butchered, run cavalry at the archers in front and then withdraw, start up the long-range missile fire, etc).

This is not quite theoretically anymore, since I've got a good ways into designing both a campaign and battlemap AI API. Quite the enjoyable summer project --- no graphics to deal with, so it moves quickly.

Well then I am looking forward to seeing the fruits of this project if you're going to share this with the community. Also, I am glad to see that someone has taken effort into dealing with the frustration that we have with the AI. Its easy enough to complain about an ineffectual AI but to actively work on designing a good one is a different thing altogether.

I like your idea though to break up the AI's single overriding goal into a series of meta-goals which makes more sense. Perhaps that's the problem the AI has too much to handle in a completely open field but if it tried instead to follow steps such as draw out enemy, nullify their archers, smash one flank, etc... then it would be more successful.

[sunsmountain]

Its easy enough to complain about an ineffectual AI but to actively work on designing a good one is a different thing altogether.

What would be even more helpful, I think, is creating battle replays showing CA where the current (RTW) AI goes wrong.

[poo_for_brains]

Have you seen Ituralde's thread about the german magazine article? Allegedly, the AI's been worked on extensively, so perhaps CA already know where their mistakes were in RTW

[Tamur]

yes, it's definitely heartening.

sunsmountain's post made me think it would be good to do just that -- collect replays that specifically show bad AI behaviour and analyse what could be happening to cause it.

Is this being done by anyone? If not, I'd be happy to host them on my own server, as long as the bandwidth demands don't become too large. I'll look around a bit and see if there's anything like this happening on the web.