Attack AI improved in CMBB?

[Redwolf]

It is totally bejond me how a neural network (as in computer science neural network today) should play CM.

Anyone has any concrete ideas? How will you turn terrain, expected enemy forces, objectives, desires (like security) into suitable input? You end up programming input composition programs for each of these aspect (and many more) that are each more complicated than a complete programmed opponent. How will you teach it about different weapons in first place, without actually doing the crossproduct of all imaginable forces and training each one? This appears to be totally undoable to me.

My experience with NN is very limited, but I closly observed how a friend of mine turned video input (of a machine part) into a quality assurance optical analysis program based on a NN. That thing had a fraction of things to consider and it was no problem coming up with good/bad sample input (pictures of know good or know bad pieces), but still he spent like two years on it. It was pretty cool, though, a real chin-dropper.

[ July 26, 2002, 10:20 AM: Message edited by: redwolf ]

[KNac]

I will extend on my ideo of scripting.

Here there would be two ways to go, with their own pros and con:

-More code-like scripts (maybe made outside of the game? in ANSII) that would be interpreted by the game engine. There are lots of script-like languages but a simple code could be made for the game with few variables, identities and operator.

The pros: it would consume less time to program it, because a lot would be designer work and not additional interface and tools would be needed to code into the engine. also more open scripting like this wouls allow in a much more possibilities and combinations.

The cons: probably, because of its difficulty (even if it would be relative easy) and time to learn, it would be not used by a lot of designers, this would be real "modding" also we must add the incompatibility of script code would be very often, because of coding error, probably soemkind of debug tool should be done.

-Graphical-made scripts, added to the scenario editor, and made with hardcoded into the engine tools.

Con: not as wide in possibilities and combinations as the other (well this would depend in how deeep wants the programmer to go).

also this would take much more time to do (time consuming).

Pros: because it would be easy to use, via intarface tools (probably kinda like to the commands in-game like "move" "fast" etc) so it would be widely used for scenario designing. also the problem of script debug wouldn´t exist.

In my opinion, the second method would be selected if it would happen, because it´s not the worth of doing something that will not be used later. An other option is to go the first way, and in posterior patches add the interface and in-game tools, but I dude it will happens because BTS do not want to release incomplete products.

Elaborating a bit more about the options for scripting via in-game interface and scenario tools.

Probably you should go to 3d view to do it. And you should have a sub-menu for units "Scripting" with th available actions. For reinforcements, you should be able to place them in the 3d map. Using a combination of keys like shift-1; shift-2... shift-0 to togle the visible units (original ---> shift-0, reinforcement 1 ---> shift-1, etc).

Some of the options would be movement (in the diffrent variants: fast, move, sneak, etc) you should be able to assing the same order for a group of units, selecting them all, so placing from the start the units in formation could help. ploting movement paths should be available. other orther should be atack (in diffrent variants) and defend.

for example atack with an agressivity percentage (or 3-4 options) that should point to the amount of loses before retreating, as well as a defend command, find cover (HD for tanks/vehicles).

movement should include variables like frontage and deep. Also a few standar formation should be available (for each country) those should be hardcoded because one fo the first problem we find is, when a unit is following a path and must change direction, how it know where must it reposition it-self inside the formation (I hope I´ve explained my-self well

Also an option when u run an scenario of "Scripts on/off" should be used, if on the game will chek if scripts exist for the scenario if it they do then it will be used. While running the game, each turn the engine will chek if scripts are available for a unit and if so it will read it and intereptate (mispelling?) it.

this will allow scen designer to make a more "smarter" AI, it will screw up replayability, but u can always turn it off (remember "scripts on/off")

an other problem is when the AI will stop using scripts and when will continue to do it. I mean when enter in action. How will anwer to ruted units? How will know if the formation is broken or no?

As you see, even this way is difficult to do, I think the avility to make SOPs (and a few SOPs for the AI hardcoded) would be the way to go. More suggestions?

[Bruce70]

It is totally bejond me how a neural network (as in computer science neural network today) should play CM.

How will you turn terrain, expected enemy forces, objectives, desires (like security) into suitable input? You end up programming input composition programs for each of these aspect (and many more) that are each more complicated than a complete programmed opponent. How will you teach it about different weapons in first place, without actually doing the crossproduct of all imaginable forces and training each one?

The main quality that a NN has that a rule-based system doesn't is it's generalisation ability. While some of you grog's probably know the exact situation in which every unit has and should be used I personally just have a quick look at the stats and then generalise based on the units do know.

So first of all a NN need not be trained on every unit. Having said that it would not be a big deal to do that.

My experience with NN is very limited, but I closly observed how a friend of mine turned video input (of a machine part) into a quality assurance optical analysis program based on a NN. That thing had a fraction of things to consider and it was no problem coming up with good/bad sample input (pictures of know good or know bad pieces), but still he spent like two years on it. It was pretty cool, though, a real chin-dropper.

The example you give of visual processing is a very difficult one, arguably as difficult as each aspect of CM. Perhaps you could ask your friend why he didn't just write rules for the system since a rule-based system can handle more complicated problems (like CM) better than a NN. [sarcasm, sorry]

It is also a significantly different type of problem, so it isn't a fair comparison.

Anyone has any concrete ideas?

OK here are some concrete ideas. The task is broken up into smaller, heirarchically organised pieces.

At the top level the AI would receive as input a very low res version of the map (maybe a 5x5 grid) so that it can get a general feel of the map, like "the left flank is elevated", "the right flank is heavily wooded". It would also have some info about its own forces, nothing specific just something like 2 inf companies, 4 MBTs, etc. It would also make an estimate of the oppositions forces.

This level AI would probably come in two flavours, defence and attack. The defence version would be responsible for setting the basics of a defensive position. This would be a matter of assigning units (company level probably) to the 5x5 grid squares. The attack AI would give the opposition force estimate to the defense AI and ask it to work out a probable set up. The atack AI would then use this info to choose a general attack strategy (e.g. Attack with 1 company on the right, pin from the hill on the left with the other company). The would take the form of giving orders to each unit like start at (1,1), move to (1,3) and supress (2,4).

This is something that you (as a huma assess at the beginning of a game and then you stick to that decision until somthing happen to make you reassess. So this level AI can be quite slow since it is called upon rarely. This is the advantage of having a heirarchical system. You could say that you reassess every 5 turns or maybe when you have spotted the enemy or whatever.

So how do you train a NN to do that? Well basically you don't. You train the NN to evaluate each possibility based on the info available. You then get a valuation for each promising possibility and make a random choice based on the valuations. If you win the game then you train the network to increase the value of that strategy under those conditions, if you lose you do the opposite. This is a simplified explaination of reinforcement learning.

A couple of levels down would be the Platoon level AI, which would have received orders from the higher AI. It would receive a higher res map but probably of only a portion of the map, so perhaps still just 5x5. It would have as input known or expected positions of enemies, the current positions of units it is in charge of and its current orders. Based on this it would perhaps choose a formation (2 up, 1 back?) and plot a course for itself, taking into consideration cover, the final objective etc. Each section/squad would have a still higher res but more restricted map and would loosely try to maintain its position in the formation while choosing a route that gives it good cover at its higher resolution.

OK hopefully you get the general idea, but this was just off the top of my head so I could probably go back and pick it apart and come up with something better. The key points are the heirarchical structure and the use of a NN for it's generalisation and reinforcement learning for training the NN.

Just as a possible addition, someone mentioned something about crushing the hopes and dreams of a human opponent. Well I haven't thought too much about these emotions but someone (Vico I think it was) designed a very interesting NN that had an anxiety level.

Basically this worked by increasing the anxiety of the network every time it got negative feedback and reducing it after positive feedback. The anxiety level effected the training rate of the network. So a network that continually got -ve feedback (eg losing the game or losing men) will increasingly try more and more radical solutions to its nightmare. Eventually one of these might actually result in +ve feedback and with the now very high training rate this will receive a lot of reinforcement while at the same time lowering the anxiety, so the AI will blindly follow this "solution" for some time even if it is being -vely reinforced. Sound like going berserk to anyone? Of course we humans have a system like this (which is what Vico based it on) for a reason, when we don't go berserk it actually works very well.

Anyway, human emotions are understood well enough that it isn't impossible to work these into a NN.

Oh well, another day another long post.

[Redwolf]

Originally posted by Bruce70:

The main quality that a NN has that a rule-based system doesn't is it's generalisation ability. While some of you grog's probably know the exact situation in which every unit has and should be used I personally just have a quick look at the stats and then generalise based on the units do know.

Let us forget about the unit question for a moment and assume the game has only one unit, a medium tank.

So that makes the terrain the most important aspect. How would you encode the terrain as input for a neural network. You would have to train it with a big variety of good/bad examples and with an even much larger variety of terrain examples. The crossproduct is overwhelming.

The example you give of visual processing is a very difficult one, arguably as difficult as each aspect of CM. Perhaps you could ask your friend why he didn't just write rules for the system since a rule-based system can handle more complicated problems (like CM) better than a NN. [sarcasm, sorry]

It is also a significantly different type of problem, so it isn't a fair comparison.

It is 12 years ago now and my memory is fuzzy. IIRC his neural net was analysing a surface of some machinery part, which would be observed by a camera and a moving light so that the reflections would walk the surface. The surface would never be even, there would be allowed and disallowed deformings. The company programmed the hell out of a conventional system, but that could only tell deforming were there, not whether they were allowed or not. My friend's neural network based program could do this.

You feed examples of "this is an allowed deforming" and "this is a suspicious deforming", it was dead easy for the user even when parts were changing.

Now, and here we come back to our to our CM application, the key in making this work was not at all int he neural network itself. It was a pretty vanilla one and I think you would even have be able to use a commercial offering.

The key is how do you encode real world data into streams of numbers so that distinctive patterns of numbers reflect differences you care about. This is what he banged his head against for 2 years, and he's a real hotshot programmer.

For a wargame AI, you would have dozends of these streams for which you would have to make a suitable encoding. And afterwards, most probably, you face a showstopper abount of CPU time you would need to actually train a network. Even assuming you can come up with a sufficient number of relevant (in your encoding) examples of "good" and "bad" to train with, which would basically mean you would need to have the CM community plot like 20000 attack approches.

Only when you have a substancial portion of these can you start coding the input cooking, which -based on my friends experience- will keep you busy for years.

All this is for the terrain analysis only.

(I'll comment on the second part of your post later, runnig out of time)

[ July 26, 2002, 11:49 PM: Message edited by: redwolf ]

[Redwolf]

Some remarks on the second half of your posting.

I think it is not (and wasn't mean to) precise enough on what exactly

you feed the NN with and how to come up with all the examples. Let's

leave that aside.

I see difficulties with your approch in several other areas.

Splitting forces. Your seperation of basically doing a high-level

command with a NN feed with a terrain with (much) lower resolution and

then passing rough commands to lower level HQs who will then get a NN

input from finer fine-graded, but local, terrain analysis, avoid the

big CPU hammer of running the whole map will full resolution into a

NN.

First I think that the reduces the CPU usage not enough, but it is

hard to argue about that.

More importantly, this AI would probably do a too even approch,

violating the (military) principle of mass. I think that any

challenging player (flesh'n'blood or computer) must put an emphasis on

minimising secondary efforts and putting the absolute maximum into

"The Fist". I don't see how to solve this problem in your system

without ending up transferring huge numbers of detail decision back up

the command chain to the top-level command. Just as in real life.

But you have limited your high-level HQ to have blurred vision, and

your low-level commanders are short-sighted, they only live from one

terrain cell to the next.

The toughts about anxiety are interesting. Will think about them.

[Bruce70]

At the risk of boring everyone to tears, I will answer some of your objections Redwolf.

So that makes the terrain the most important aspect

I think I would agree with that.

How would you encode the terrain as input for a neural network. You would have to train it with a big variety of good/bad examples and with an even much larger variety of terrain examples

The choice of encoding would be very important, I am not sure what would be best. Some trial and error would be required if a detailed search of the available literature did not uncover anything. At least that is from a developers POV. For myself spatial reasoning is what my PhD is about so naturally I have my own ideas on this.

The simplest way to train a RL NN is to have it play itself in a QB type scenario - but without the graphics of course.

The company programmed the hell out of a conventional system, but that could only tell deforming were there, not whether they were allowed or not. My friend's neural network based program could do this.

Yes I am not surprised that the NN could do better than a rule-based system.

Now, and here we come back to our to our CM application, the key in making this work was not at all int he neural network itself. It was a pretty vanilla one and I think you would even have be able to use a commercial offering.

Yes it was more than likely a BP network or some related algorithm. This algorithm was developed in the early 80's (?), NNs have come a long way since then.

The key is how do you encode real world data into streams of numbers so that distinctive patterns of numbers reflect differences you care about. This is what he banged his head against for 2 years, and he's a real hotshot programmer.

NN programming is easy, that is one of the reasons I find this field rewarding since I myself am an average programmer. As you say the difficulty is in choosing a suitable encoding and there is a certain amount of art (for want of a better word) in that.

you would need to have the CM community plot like 20000 attack approches.

As I said before, have the computer play QBs against itself. The developer doesn't need to come up with good or bad examples, you know if an example is good or bad by who wins. I think you are focusing on the NN too much, you should do some reading on RL (reinforcement learning) in particular have a look at Sutton's "temporal difference learning". RL doesn't even require a NN but it is common to use a NN for the value function especially if the state-space (situational input) is of a continuous nature or prohibitively large (both apply to CM). If the possible actions are of a continuous nature then you do run into some problems and this is the subject of current research. But it is usually possible to design the system so that actions are discreet as I believe is the case here.

First I think that the reduces the CPU usage not enough, but it is hard to argue about that.

The point is that since the high level AI gets used rarely you can put more (CPU) effort into it. It is this part of the solution that most people seem to be complaining about with other AIs.

Not every level of the AI needs to be the way I have explained and that leads to another interesting option. You write a rule-based AI for every level of the code (this doesn't have to be very good) then starting wherever you like (at the highest level probably) you replace that section with your NN/RL code. Once you have trained that level you replace another level and so on. You may even find that at some levels it is easier to keep the rule-based code.

More importantly, this AI would probably do a too even approch,

violating the (military) principle of mass.

I am not sure what you mean, if the principle is valid the AI will find it. But there is no harm in giving the AI a small knowledge base of military principles. There is no need to reinvent the wheel. If there is a SOP that fits a certain situation then you give this procedure a high value before the AI starts training. The AI will be able to change this value assessment based on its own experience but it does save a significant amount of training time and is a common technique.

But you have limited your high-level HQ to have blurred vision, and

your low-level commanders are short-sighted, they only live from one

terrain cell to the next.

It is a feature not a limitation that the high level AI has "blurred" vision. The high level AI does not need to know where every patch of scrub is, as in real life that is a job for subordinates. If every platoon leader started sending radio messages to the battalion commander about the exact placement of trees and shrubs on the battlefield I don't think this would enhance his ability to do his job.

It is a valid point about the short-sighted subordinates though, perhaps it would be better to have a LOD system for terrain input in this case. So the AI has detailed information about the immediate surroundings but only general terrain information about more distant features.

Gotta go, apparently I am not paying enough attention to my wife.

[ July 27, 2002, 03:20 AM: Message edited by: Bruce70 ]