Battle AI Dev Diary

[TosaInu]

[Nobunaga]

I have just received a warning for this thrad... my initial intentions was to help CA...

things is I am being flamed for nothing really, most (even all) here dont have a clue about what I am saying...

[regor]

Are you implying that TW is non-deterministic

I'm not implying anything. If you've played any of the titles and know the definition, this should be glaringly obvious. For example, run a custom battle with two identical units on a completely level battlefield. Mark down the winner and the respective losses.
Now do that ten times. Does the same unit always win? Are their casualties always the same?

and dosent have boundaries nor rules

I said well-defined. There is a difference between a rigorous mathematical definition, as opposed to, say, the definition of a word in a dictionary.
In chess, a knight can move two spaces forward, and one to the side. Always.
If another piece is standing in that space, it can be taken. Always.
In a TW battle a unit of knights can beat a weak unit of spearmen head-on. Sometimes. If they charge the spearmen in the back, it's almost a certainty. A charge to the side is trickier to predict. What about charges at a 45° angle? 25°? 1,222123°? Furthermore, are they fighting on flat terrain, or a slope? Did one unit have to run to get to the engagement and is now tired?
There is no simple rule you can 'teach' the AI, so that it can use it and always win, even in this, the simplest 1v1 scenario.
As for boundaries, well, just look at a screenshot of a battle when the two battle lines meet. I think it's as far as you can get from an 8 by 8 grid. And that's basically just melee infantry.

and what do you mean by non-linear
Do you know what determinism is

I assure you I do, although you'll have to take my word for it I'm afraid. But just so there's no confusion, we can consult Wikipedia. They have a pretty extensive article on the subject. Most of it is on the philosophical concept, but I present you this:

Many mathematical models are deterministic. This is true of most models involving differential equations (notably, those measuring rate of change over time). Mathematical models that are not deterministic because they involve randomness are called stochastic. Because of sensitive dependence on initial conditions, some deterministic models may appear to behave non-deterministically; in such cases, a deterministic interpretation of the model may not be useful due to numerical instability and a finite amount of precision in measurement. Such considerations can motivate the consideration of a stochastic model when the underlying system is accurately modeled in the abstract by deterministic equations.

[pevergreen]

I have just received a warning for this thrad... my initial intentions was to help CA...

things is I am being flamed for nothing really, most (even all) here dont have a clue about what I am saying...

1. Yes, your initial intent was good, however it descended into something that wasnt. You recieved a warning point, I presume, for your language and overall behaviour. I had asked TosaInu to do what he thought right in terms of trimming the thread down, because I lack the power to.

2. Although not everyone knows what you are talking about, you shouldnt really take the assumption that they do. I can mostly follow along with all this, not everyone is a person of experience in this community, I am a high school student. I dont know Diddily-Squat about programming an AI.

I would appreciate if all talk of what has happened ends here. It goes much nicer like that, dont you think?



edit:

Spoiler Alert, click show to read: 

in addition, if you feel the warning was not warranted, please contact the person who issued it, explaining why you dont think it was deserved.

[Nobunaga]

I'm not implying anything. If you've played any of the titles and know the definition, this should be glaringly obvious. For example, run a custom battle with two identical units on a completely level battlefield. Mark down the winner and the respective losses.
Now do that ten times. Does the same unit always win? Are their casualties always the same?

regor determinosom and non-determinosim do not mean non-randomness and randomness in algorithmic/complexity theory they mean a very different thing... Still randomness is not a factor in developing AI since u always take the expected outcome...

I said well-defined. There is a difference between a rigorous mathematical definition, as opposed to, say, the definition of a word in a dictionary.
In chess, a knight can move two spaces forward, and one to the side. Always.
If another piece is standing in that space, it can be taken. Always.
In a TW battle a unit of knights can beat a weak unit of spearmen head-on. Sometimes. If they charge the spearmen in the back, it's almost a certainty. A charge to the side is trickier to predict. What about charges at a 45° angle? 25°? 1,222123°? Furthermore, are they fighting on flat terrain, or a slope? Did one unit have to run to get to the engagement and is now tired?
There is no simple rule you can 'teach' the AI, so that it can use it and always win, even in this, the simplest 1v1 scenario.
As for boundaries, well, just look at a screenshot of a battle when the two battle lines meet. I think it's as far as you can get from an 8 by 8 grid. And that's basically just melee infantry.

You are talking about factors that affect battles outcome... so what? Still TW has well defined boundaries and rules. Actually if u read I said this before:

I am not over simplifying the issue here, modifying chess algorithms so that they work with TW is alot of work. I am just saying that it works / worth looking at since the two problems have very similar nature. I am aware of the big differences such as terrain, unit orientation, unit speeds, morale, ... and other stuff

[Juggernaut]

Since you seem to have a much better understanding of AI programming then anybody at CA, maybe you can offer CA to lend a hand in AI programming?

[Nobunaga]

Juggernaut I dont think that I have a better AI understanding than everyone in CA... I just suggested an Idea and defended it constructively....

[Cheetah]

Jack, thanks for the info.

May I ask one thing? Could you post up the basic priorities for the AI that you are looking for? I know it could be a hornet's nest and that you might not have the permission to give out "strategic" details, but still it would be very interesting and important to know at least just the basics. For example: are you looking for army cohesion, deployment, handling of highground, etc?

many thanks,
Cheetah aka. Lional of Cornwall

ps. I can give my priority list if it is of any interest.

[fenir]

When I was at University, (many years ago now), we made a small checker program.
Then we got ambitous, and made a chess one.


Then we had this neat idea.......turn the chess program into fighting men. So they can battle one another.


Well from our experiance, it fell over. The time, the lack of our experiance. et cetera....

Just the mssive complexities involved.


Chess Vs TW individual combat?


TW Hands down with out a bink.




Sincerely

fenir

[TosaInu]

Hello,

It won't hurt when others checked their post too: Nobunaga got an edit for replying in kind. Opinions I don't care about really. But play the ball, not the man.

[SwordsMaster]

Now, a chess AI that calculates its bargaining position using an algorithm similar to the chess grading system would not be a bad idea. For the diplomatic engine I mean. This would be the AI that decides when to fight, when to surrender, when to accept or decline offers, etc. If it could evaluate its position as if it was about to make a move in a game of chess - ultimate goal (checkmate) being the victory conditions - I would like to play that AI.

[seireikhaan]

Hmm, this is interesting. I might consider getting ETW.

[woad&fangs]

CA, Thanks for the info.

[ArtistofWarfare]

Now, a chess AI that calculates its bargaining position using an algorithm similar to the chess grading system would not be a bad idea. For the diplomatic engine I mean. This would be the AI that decides when to fight, when to surrender, when to accept or decline offers, etc. If it could evaluate its position as if it was about to make a move in a game of chess - ultimate goal (checkmate) being the victory conditions - I would like to play that AI.

I'm going to drop my 2 pennies into this hat quickly...

The bottom line is that I understand the way rationing of resources/time works in development today and I understand all too well the term "cost effective". That said, it WOULD be cost effective to spend the time and money on an AI system that operates in the manner discussed in this thread.

Let's face it- AI is #1. Everything else in this genre walks behind AI almost like a bridesmate. AI leads the charge.

I believe that getting a system in place that focuses on goals, and then calculates the best approach (using variables such as diplomacy, when to attack/not to attack, building/recruiting, deep long term planning etc) would be an investment...a long term investment for CA.

Every single company in this industry is desperately seeking something innovative and cutting edge to implement into their games to wow the strategy community and get people excited. There is nothing that would get people more absorbed into the franchise for Empires and anything else you throw at them in the future, than an AI system that operates in this manner.

Let me make this clear- To ANY group of gamer you are targeting: AI is #1. This notion that there is a group of gamers who are more concerned about graphics than gameplay, is entirely overblown. There are simply some gamers who are more concerned with graphics than others. That said, this group would still be entirely intrigued by an AI system like the one we're discussing.

Look at it this way- Once you get the graphical standard up to a certain level, it's a very small percentage of the userbase who will ever even see that graphical standard...due to the hardware that is required to display/run it appropriately. We're past the point where the majority of gamers are fooled by video footage and cinematic clips during the preview phase of the game. Virtually no gamer will include this footage in their expectation of how the end product will look/play. So let's be honest- an overabundance of time spent in this department- is simply wasted...just utterly, wasted.

Now when we're talking about shifting some of those resources into the AI engine we're discussing- the entirety of your userbase is a) included...even @ this phase. When they hear about the revolutionary AI engine, their first thought is not "well, my pc certainly won't take advantage of this" (as they will think when they hear about graphical enhancements). There thoughts will be entirely devoted to how exciting this sounds and to contributing to discussions like the one that is taking place in this thread.

So with the AI being the #1 priority you're a) including the entirety of the userbase in your efforts and resources b) clearly aligning your vision (the dev) and goals with the userbase's vision/goals and c) putting time and resources into the ONLY thing you can in order to actually separate your franchise from all of the other strategy franchises that exist. Let's face it- there are several games out there with bleeding edge visuals. Total War is not the graphical benchmark in gaming...nor should it be. Total War should be the AI benchmark in gaming...with "arguably" the top 3 visuals in the industry. This would work much better than "Total War has (still) visuals that are arguably in the top 3 industry wide...and has AI that is equally as flawed as AI in every other franchise".

In my opinion...any other approach is point blank: A mistake. Any argument in favor of visuals over AI- a flawed one. From a business perspective, as well as a quality perspective...focusing your efforts in the direction laid out here is by far your best bet. Focusing on visuals is just spinning your tires in the mud. It's doing nothing to drive sales and it's doing nothing to separate your franchise from "all of the others".

Let's see where we go from here...but this thread is great...and I hope it's taken into consideration during these crucial phases of Empire development.

[JeromeGrasdyke]

actually i gave alot of thought about TW battle field AI in general. It shouldnt be that hard to implement!!!!!!!!

One can view the battlefield as a nxm grid(matrix) (every unit exist in a matrix cell)... now the problem is very much similar to developing chess AI, the major differences are:

1-grid size (bigger grid here)
2-units function differently, thus the evaluating function should be different...
3-chess is turn based while TW is real time but this shouldnt be a problem since we want to find the best move for a given state of the matrix/grid...

Now AI literature is filled with "Chess Algorithms" mainly heuristics which is fine really... so just adopt any and customiz it in order to count for differences above

The designers just pointed me at this thread, and although I'm a little late in replying, I thought I'd try and give you guys a little insight into the kinds of problems that a Total War ai faces, compared to a chess AI.

First of all, let's consider what is a unit. Total war units are not chess pieces, they are collections of fully animated 3D men. Each man has an individual position, but what then is the position of a unit? The men can be spread over a large area, in one close detachment or even in several, some of them might be in a building or on a bridge... so where is the "unit"? What should it's "move" be? Any TW AI has to deal with these things as best it can, and it's not something you can design around without removing the concept of units made of collections of men (obviously a non-starter).

Second, let's consider what is position. The Total War battlemaps are not grids, they're continually variant planes, with a resolution down to about 0.0001 m. So determining when you're in striking distance is not as simple as, "am I adjacent". It's about range-to-contact, which carries with it a travel time... and the travel time is dependent on the terrain type, and on the ground slope, and on the unit type, and on the unit's current organisation. Working out exact positions and a 'tree' of future moves and board-states in the style of a chess program is nigh-on impossible, because the number of possible moves is just too big... the combinatorial explosion would eat up all available memory after looking ahead less than a seconds.

Third, let's consider what happens when a unit attacks. In chess, a unit takes another unit instantly on attack. In Total War, well, the unit may win, or it may loose. That's dependent not only on stats, but on all sorts of complex factors such as individual soldier facing, precise soldier distribution, ground slope, a semi-random number element and many other things. It's sufficiently complex that even though it is deterministic, the result is not 100% foreseeable without actually running the simulation, which we obviously don't have the computational power to do... even the AI does not know 100% for sure which unit will win when 2 units clash (although it makes a pretty good guess). This hugely complicates the assessment of your move tree.

But hey, no one ever said it was going to be easy ;)

I feel that we're on the right track with the approach we've adopted with this generation of Total War AI. We've taken the best code we had available as a starting point. It already solved many of the above issues, and we've added to that several cutting edge techniques to increase its awareness of time and make it better at handling a large variety of goals. We've added a dedicated AI programmer, and also adjusted our working process, as Jack already mentioned, giving us a methodology to sharpen and refine the AI until it squeaks.

The ETW AI not yet done - not by a long shot - but I think it already shows a lot of promise ;)

[rajpoot]

Very interesting all this info. I never knew there was so much to it. Thanks.

[Nobunaga]

Hello JeromeGrasdyke,

First of all thanks for the reply. I dont want to be stuborn, and maybe modifying chess AI to fit TW is not a good idea, Yet i dont see why...

First of all, let's consider what is a unit. Total war units are not chess pieces, they are collections of fully animated 3D men

It doesnt matter if they are animated or not, or if they are 3d or 2d, chess AI doesnt change when peices are 3d or animated.

Each man has an individual position, but what then is the position of a unit? The men can be spread over a large area, in one close detachment or even in several, some of them might be in a building or on a bridge...

Who said in TW a unit should take only one position in the grid. Each unit may take several positions. This is different than chess as I said alot of modificaiotns should be made.

Second, let's consider what is position. The Total War battlemaps are not grids, they're continually variant planes,

But they can be abstracted as grids or special grids where each cell in the grid have a height attribute...

because the number of possible moves is just too big... the combinatorial explosion would eat up all available memory after looking ahead less than a seconds

Yeah it will be huge if we consider all possible moves. But the same case also applies to chess. Thing is we will not consider all possible moves just good moves. What strikes me is that movement in chess have much bigger stratetgic impact than that in TW.

Third, let's consider what happens when a unit attacks. In chess, a unit takes another unit instantly on attack. In Total War, well, the unit may win, or it may loose. That's dependent not only on stats, but on all sorts of complex factors such as individual soldier facing, precise soldier distribution, ground slope, a semi-random number element and many other things. It's sufficiently complex that even though it is deterministic, the result is not 100% foreseeable without actually running the simulation, which we obviously don't have the computational power to do... even the AI does not know 100% for sure which unit will win when 2 units clash (although it makes a pretty good guess). This hugely complicates the assessment of your move tree

Yeah the outcome of two units attacking depends on many factors but it should be easy to guess the expected winner of the engagment. A cell in the grid can contain several units. Am not after perfect AI good gueses are fine. This shouldnt affect the size of the movement tree.

But hey, no one ever said it was going to be easy

AI is tough work no doub about that.

Theoreticaly a search tree based approach will work. Their are many factors to consider yet ultimately it will work. It always does (theoreticaly) yet many times it is not needed (FPS/fighting games for instance).

Thing is the two problems (chess and TW) are very similar (1v1 at least). We have two oposite teams, each team has a set of units (the number of units in the set doesnt increase over time as opposed to other RTS games). The units are postioned on a grid. For a player to win he have to destroy a subset of his opponent units.

The way I see it the biggest possible problem is that chess is turnbased while TW is real time. So a search tree approach may prove disastrous in turn of run time. Then again if well optimized it may work I dunno...

thanks for your time Jerome...

[Martok]

Spoiler Alert, click show to read: 

The designers just pointed me at this thread, and although I'm a little late in replying, I thought I'd try and give you guys a little insight into the kinds of problems that a Total War ai faces, compared to a chess AI.

First of all, let's consider what is a unit. Total war units are not chess pieces, they are collections of fully animated 3D men. Each man has an individual position, but what then is the position of a unit? The men can be spread over a large area, in one close detachment or even in several, some of them might be in a building or on a bridge... so where is the "unit"? What should it's "move" be? Any TW AI has to deal with these things as best it can, and it's not something you can design around without removing the concept of units made of collections of men (obviously a non-starter).

Second, let's consider what is position. The Total War battlemaps are not grids, they're continually variant planes, with a resolution down to about 0.0001 m. So determining when you're in striking distance is not as simple as, "am I adjacent". It's about range-to-contact, which carries with it a travel time... and the travel time is dependent on the terrain type, and on the ground slope, and on the unit type, and on the unit's current organisation. Working out exact positions and a 'tree' of future moves and board-states in the style of a chess program is nigh-on impossible, because the number of possible moves is just too big... the combinatorial explosion would eat up all available memory after looking ahead less than a seconds.

Third, let's consider what happens when a unit attacks. In chess, a unit takes another unit instantly on attack. In Total War, well, the unit may win, or it may loose. That's dependent not only on stats, but on all sorts of complex factors such as individual soldier facing, precise soldier distribution, ground slope, a semi-random number element and many other things. It's sufficiently complex that even though it is deterministic, the result is not 100% foreseeable without actually running the simulation, which we obviously don't have the computational power to do... even the AI does not know 100% for sure which unit will win when 2 units clash (although it makes a pretty good guess). This hugely complicates the assessment of your move tree.

But hey, no one ever said it was going to be easy ;)

I feel that we're on the right track with the approach we've adopted with this generation of Total War AI. We've taken the best code we had available as a starting point. It already solved many of the above issues, and we've added to that several cutting edge techniques to increase its awareness of time and make it better at handling a large variety of goals. We've added a dedicated AI programmer, and also adjusted our working process, as Jack already mentioned, giving us a methodology to sharpen and refine the AI until it squeaks.

The ETW AI not yet done - not by a long shot - but I think it already shows a lot of promise ;)

Appreciate you taking the time to reply in detail, JeromeGrasdyke.


If I could ask a slightly off-topic question: Do you have a different AI programmer for naval battles? And if so, are both programmers using the same basic code, or are they completely separate?

[JeromeGrasdyke]

If I could ask a slightly off-topic question: Do you have a different AI programmer for naval battles? And if so, are both programmers using the same basic code, or are they completely separate?

I can't go too deeply into our staffing arrangements, but we've got dedicated AI programmers for both battlefield and campaign, who are assisted by various other people in special areas. The battlefield ai is also used for naval battles, since they share an awful lot of common functionality ;)

Theoreticaly a search tree based approach will work. Their are many factors to consider yet ultimately it will work. It always does (theoreticaly) yet many times it is not needed (FPS/fighting games for instance).

Theoretically, perhaps it might ultimately be made to work, after some drastic changes to the game. But "theoretically" is not good enough. It needs to be practically possible given today's cpu and memory constraints, and programmable by mere mortals, and within a timespan measured in man-months. It really is not a feasible approach for this style of game.

[SwordsMaster]

According to your description Nobunaga, chess and ice hockey are also almost identical...

[Nobunaga]

Please elaborate.

plus AIs for sport games like soccer, hokey, .... is very good just play winning eleven on hardest setting.

[SwordsMaster]

two oposite teams, each team has a set of units (the number of units in the set doesnt increase over time as opposed to other RTS games). The units are postioned on a grid. For a player to win he have to destroy a subset of his opponent units.

Isn't that almost like ice hockey?

[Martok]

I can't go too deeply into our staffing arrangements, but we've got dedicated AI programmers for both battlefield and campaign, who are assisted by various other people in special areas.

Good to know, man. Thanks.

The battlefield ai is also used for naval battles, since they share an awful lot of common functionality ;)

I'd sort of guessed as much, but I didn't want to assume. I'd think programming the naval AI would be even more complex, though, since it must factor in not only the ships fighting each other, but the men crewing them as well.

Gah! My brain hurts just thinking about it, and I'm not even a coder.

[TosaInu]

It needs to be practically possible given today's cpu and memory constraints, and programmable by mere mortals, and within a timespan measured in man-months. It really is not a feasible approach for this style of game.

Hello JeromeGrasdyke,

That may be a point. A chess AI or even a smart modified chess AI will be used by thousands of units and that in real-time. Maybe a smart mortal could program and debug it in a week, but will our computer ever resolve one minute of battle?

[Tamur]

I respectfully suggest an exciting activity for anyone who thinks it's possible to make a real-time decision-tree, neural net, or other "higher-level" AI for the battle map.

Create a simple version of a TW battlefield, without dealing with graphics at all. You can cheat, and create a discrete multi-dimensional terrain map, simplified down to elevation, terrain type, and weather conditions. Create two competing units of 1 man each, with specific base statistics such as movement speed, attack statistics, range-to-contact for primary and secondary weapons, etc. Basically, create a stripped-down skeleton simple enough for a test.

Now implement your AI. Make sure it is taking into account every known (line-of-sight knowledge) attribute of the terrain map, as well as every known attribute of the competing unit, including the competing unit's projected trajectory. Make up whatever decision rules you like.

Write XY locations and health to the console. I think you'll find it a bugger but not insurmountable.

Now, increase unit size to ten men, each with locations and trajectories of their own on this discrete map surface. Feel free to apply your decision rules universally for simplicity, but change your code so that, not only does the unit make decisions, but each individual man makes movement and attack decisions, taking into account his own unit's orders, known local terrain information, and the location and projected trajectory of individual men in the competing unit.

I don't suggest this sarcastically or with malignant intent. I tried it back when RTW came out and locked up my system six times in a row when expanding to 10v10. It's very difficult stuff to deal with. I can't imagine giving 100 men to each unit and putting 40 units on the map...

[TosaInu]

Hello Tamur,

I don't think I'll ever complete 1v1.

Did you scale up from 1v1 to 10v10 immediately or did you try 2v2 and so on and monitor the resources required for that too?

[Tamur]

I tried jumping right to 10v10 thinking it was no problem, so after trying to solve the lockups I changed to 4v4, and it ran until the first of the two men came within ranged distance of each other, then started really grinding. I know one of them got a shot off and a hit because one of the men's health points dropped, but it became so slow that I had to abandon the run, and never got back to it due to busy-ness.

Not a very thorough test, and no optimisation. I'd be very interested to compare implementation notes with anyone who actually does take this on. I'm guessing that I could have achieved a smooth 2v2 battle (ha, what an achievement!)

Will have to look for that code, but that's going back a ways...

[TosaInu]

Wow, that's quick.

Optimising 2v2 may be a challenge already. Perhaps there's another odd thing going on, which is not directly related to it being scaled up? Each soldier suddenly got a friend too.

[Tamur]

Perhaps there's another odd thing going on, which is not directly related to it being scaled up

Yes, the fact that it ran fine until the attack contact made me think that the attack/retreat rules I had created were flawed, creating an infinite "indecisive" state. This makes me want to get back there and figure out what was going wrong.

[Swoosh So]

So what all this techno babble narrows down to is that theres a disagreement on whether or not chess movement is more complex than totalwars? yet ca could easily make chess movement with no errors yet in totalwar there are errors? I think that tells its own story.