Battle AI Dev Diary

[SenseiTW]

Hi guys,

In advance of our forthcoming AI video development diary, we have posted a new blog detailing part in the Battle AI development process. Head over to www.totalwarblog.com (http://blogs.sega.com/totalwar/2008/06/24/empire-total-war-ai-diary/#more-60) to check it out!

Thanks,

Mark O'Connell
(aka SenseiTW)

[Wandarah]

Nice one! Cheers Big Ears!

Edit: Cripes, old Lusted has done alright for himself innit. I may not steal his prize pig now.

[Jack Lusted]

Edit: Cripes, old Lusted has done alright for himself innit. I may not steal his prize pig now.

'Git yer hands off ma pig!

:laugh4:

(not quite sure what you're referring to, but the farmer accent seemed appropriate in repsonse)

I'll try and answer as many additional questions you guys have as I can.

[Mailman653]

'Git yer hands off ma pig!

:laugh4:

(not quite sure what you're referring to, but the farmer accent seemed appropriate in repsonse)


http://www.freeiconsweb.com/Freeicons/Farms_Icons_set/pig.png

[Martok]

Appreciate the info, CA! ~:cheers:

It's certainly no secret that AI in games like these are an issue near & dear to many of us, so I'm glad to see you guys talking about it with us. Looking forward to the video blog. :2thumbsup:

[Odin]

Is jack lusted the same lusted who created the lands to conquer mods? If it is I can speak directly to the quality of that mod and its playability. If it is him thats a solid plus for empires if he is developing the AI

[pevergreen]

They are one and the same!

It's a comfort to many of us that we have a former patron helping build our next game!

[Odin]

They are one and the same!

It's a comfort to many of us that we have a former patron helping build our next game!

yeah hes a good guy and fellow patron but his work on LTC was pretty good. Like the rest of us I have played plenty of games with plenty of mods and LTC for MTWII corrected all outstanding issues and basically upgraded the vanilla game without dramatic change to interface.

I still wont change my position on gaming companies in general and the consumers duty to hold them to account with there purchase but when you take a position like I have you have to be able to make concessions.

Lusted is a fine modder, I have used his product and I hold them in the highest regard, anyone on the fence about empires should take note of his participation in the process.

[Rhyfelwyr]

Nice to see something on the AI! :2thumbsup:

[Nobunaga]

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

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 :juggle2:

[PBI]

Then again, the purpose of the AI is not to resoundingly thump the player in every battle; I suspect programming it to do that wouldn't be that hard. The aim of the AI is to lose to the player in an interesting and challenging way. I suspect the difficulty comes more in getting the AI to behave more like a human player than in getting it to win every time; aren't chess programs generally designed to calculate every possible move and thus beat the human player through sheer number crunching?

Good to see something out on the AI BTW, nothing wrong with nice shots of naval combat but it is nice to see that CA is taking something which is a big issue for many players seriously. :beam:

[Jack Lusted]

Nobunaga, real time is a huge difference over turn based. Chess AI's can take tens of seconds to minutes to make decisions, AI in TW games have to make decisions in miliseconds in real time in a battlefield that contains hugely more variables than a chess board. It's not as simple you think.

And at it's most simplest the TW AI doe do some things similar to chess AIs, but there is a huge amount of difference between chess and the TW battles in terms of number of variables and in predicting how the battle will progress.

Making an AI that plays well and provides a challenge in the battles of the TW series is tough, but we're putting a lot of effort into it and Empire's battle AI is looking promising.

[Colonel Flambard]

Nobunaga, real time is a huge difference over turn based. Chess AI's can take tens of seconds to minutes to make decisions, AI in TW games have to make decisions in miliseconds in real time in a battlefield that contains hugely more variables than a chess board. It's not as simple you think.

And at it's most simplest the TW AI doe do some things similar to chess AIs, but there is a huge amount of difference between chess and the TW battles in terms of number of variables and in predicting how the battle will progress.

Making an AI that plays well and provides a challenge in the battles of the TW series is tough, but we're putting a lot of effort into it and Empire's battle AI is looking promising.


Brilliant news Jack, keep plugging away CA. :beam:

[Nobunaga]

Nobunaga, real time is a huge difference over turn based. Chess AI's can take tens of seconds to minutes to make decisions, AI in TW games have to make decisions in miliseconds in real time in a battlefield that contains hugely more variables than a chess board. It's not as simple you think.


Yeah it takes minutes to play near optimal (or optimal moves) but if we are interested in "good" moves it takes like milliseconds. Moreover unit movement in TW is not as complex as unit movement in chess.




And at it's most simplest the TW AI doe do some things similar to chess AIs, but there is a huge amount of difference between chess and the TW battles in terms of number of variables and in predicting how the battle will progress.


yeah as i said:


units function differently, thus the evaluating function should be different...

All we need is a different evaluation function, this can be easily done in polynomial time so...


Making an AI that plays well and provides a challenge in the battles of the TW series is tough, but we're putting a lot of effort into it and Empire's battle AI is looking promising.

I surely hope so...thanks for the reply Jack

[Jack Lusted]

Yeah it takes minutes to play near optimal (or optimal moves) but if we are interested in "good" moves it takes like milliseconds. Moreover unit movement in TW is not as complex as unit movement in chess.

It's the other way round, unit movement is more complex in TW than in chess, where each piece can only move in a limited way to a limited number of squares each turn, whereas in TW it can move to a vast number of different places at different speeds, and that is also affected by terrain etc. It is hugely complex to predict where units will move to.

[Nobunaga]

It's the other way round, unit movement is more complex in TW than in chess


Not really I'll elaborate. First I think movement in TW is more complex than that in checkers but less complex than that in chess.



each piece can only move in a limited way to a limited number of squares each turn, whereas in TW it can move to a vast number of different places at different speeds


It depends on how you model the problem and your branching strategy. In the branching tree, the time difference between a node and its children should correspond to some constant time period "T". So per branch a unit can either:
-not move
-or move to a location reachable in period T

so the number of squares a unit can move to per branch depends on its speed and T i.e. it is not unlimited.

[Jack Lusted]

It depends on how you model the problem and your branching strategy. In the branching tree, the time difference between a node and its children should correspond to some constant time period "T". So per branch a unit can either:
-not move
-or move as much to a location reachable in period T

so the number of squares a unit can move to per branch depends on its speed and T i.e. it is not unlimited.

Even then you can only do that for very short predictions of where a unit can move to. We do have code in Empire that predicts where units will go to, but it's use is limited because of the difficulty in predicting where a unit will go given the vast amount of different possible places each unit can move to if the period of time being predicted isn't very short, and over short periods of time it's only so much use. So we can give the AI some predictive abilities, but not much because if you try to predictions for long periods of time the huge amount of variables involved basically means it's useless.

The AI does react to enemy units based on position relative to it's own, and makes limited use of time planning to predict enemy unit positions. But time planning is limited, and more emphasis is placed on other factors to get the AI to react and play well. In sea battles the time planner is used more due to the slower turning rate of ships complared to land units and so it is easier to predict where ships will be going.

[Nobunaga]

Even then you can only do that for very short predictions of where a unit can move to. We do have code in Empire that predicts where units will go to, but it's use is limited because of the difficulty in predicting where a unit will go given the vast amount of different possible places each unit can move to if the period of time being predicted isn't very short, and over short periods of time it's only so much use. So we can give the AI some predictive abilities, but not much because if you try to predictions for long periods of time the huge amount of variables involved basically means it's useless.

Ok. When I say:


In the branching tree, the time difference between a node and its children should correspond to some constant time period "T"

I mean that the time difference between a node and its child is T. Then the difference between a node and its grandchild is 2T. And the difference between the node and the child of its grandchild is 3T and so on...So the time covered will correspond to the tree depth, which can be as large as u want it to be.


So we can give the AI some predictive abilities, but not much because if you try to predictions for long periods of time the huge amount of variables involved basically means it's useless.

Now I know that doing exhaustive search (brute force search) will take too much time/space. But heuristics(and greedy choices) should be used at certain points of the tree.

Again this is the same as chess! You don't need to search every possible move, you only go through the moves that make sense (based on some criteria). Again AI literature is filled with "Chess Algorithms" and and our problem is very similar so why not adopt similar strategies/search techniques!


The AI does react to enemy units based on position relative to it's own, and makes limited use of time planning to predict enemy unit positions. But time planning is limited, and more emphasis is placed on other factors to get the AI to react and play well. In sea battles the time planner is used more due to the slower turning rate of ships complared to land units and so it is easier to predict where ships will be going.

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

[Jack Lusted]

I mean that the time difference between a node and its child is T. Then the difference between a node and its grandchild is 2T. And the difference between the node and the child of its grandchild is 3T and so on...So the time covered will correspond to the tree depth, which can be as large as u want it to be.

Still doesn't change the fact that the number of possible branches is vast, and as such hugely limits the value of predicting how things will go beyond very short periods of time. We use other methods as a result which provide a better AI.


Now I know that doing exhaustive search (brute force search) will take too much time/space. But heuristics(and greedy choices) should be used at certain points of the tree.

Again this is the same as chess! You don't need to search every possible move, you only go through the moves that make sense (based on some criteria). Again AI literature is filled with "Chess Algorithms" and and our problem is very similar so why not adopt similar strategies/search techniques!

Because it is better to use techniques designed around the way the TW series works. TW at it's most simplest might seem similar to chess, but the huge amount of differences make that meaningless in terms of programming AI.


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

They are not similar enough to justify that kind of work when creating an AI specially designed for TW will result in a much better AI in the long run.

And for an example of a very simple game with a similar problem to TW in terms of number of possible moves, take a look at this page. And TW is far, far, far more complex than Go.

http://www.aihorizon.com/essays/goai/intro.htm

But basically in summary, TW is very complex. It might at it's most simplest bear some relation to chess, but not enough to use modified chess AI algorithms because it's not worth it. We are instead making an AI tailored to the somewhat unique nature of TW battles and an AI which we are hoping will provide a good challenge to players.

Be under no illusions, TW is a very complex game to make AI for, it's not easy or simple. But we are putting in a lot of effort to make sure the Empire AI will be good, and things are looking promising.

[Nobunaga]

Still doesn't change the fact that the number of possible branches is vast, and as such hugely limits the value of predicting how things will go beyond very short periods of time. We use other methods as a result which provide a better AI.

what i said:


You don't need to search every possible move, you only go through the moves that make sense (based on some criteria).





Because it is better to use techniques designed around the way the TW series works. TW at it's most simplest might seem similar to chess, but the huge amount of differences make that meaningless in terms of programming AI.


what i said:


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



GO is more complex than chess. TW is NOT (it has more rules but it doesnt have the strategic depth of chess). It is somewhere between checkers and chess.

The concept of chess and TW are very similar. We have a set of units on a grid (The number of units dont increase unlike other RTS games). Each unit occupies a position in the grid. The goal is to destroy a subset of your opponent units. (the king in chess and all the units in TW).

Moreover movement of units in chess is much more complex strategically than that in TW. I am sure any mp vet that plays chess can verify that. This is why TW mp 1v1 have little strategic depth. You see mp vets playing 4v4 games not 1v1... thing is u cant do much with 16 units...

Things like morale,attack bonuses,terrain, and these stuff shouldn't be a very big issue algorithmically...

[Jack Lusted]

what i said:


You don't need to search every possible move, you only go through the moves that make sense (based on some criteria).


But this is the AI trying to predict the humans moves, you only make it consider the moves that make the most sense and you make it very easily exploitable.


what i said:


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

But they are not very similar as I have said, I know you maintain that they are, but they aren't.


GO is more complex than chess. TW is NOT (it has more rules but it doesnt have the strategic depth of chess). It is somewhere between checkers and chess.

It is more complex in terms of movement, so you get the same problem as in GO with trying to predict the future moves of the player.


The concept of chess and TW are very similar. We have a set of units on a grid (The number of units dont increase unlike other RTS games). Each unit occupies a position in the grid. The goal is to destroy a subset of your opponent units. (the king in chess and all the units in TW).

There is no grid in TW, just the position of units on the battlefield, so talk of grids is irrelevant.

And as I've said the very basic concep of TW and chess is simple, but beyond that the differences are vast and make comparisons impossible.


Moreover movement of units in chess is much more complex strategically than that in TW..

Doesn't change the fact that the possible movements each unit can make is vastly bigger than the possible movements of each chess piece.


Things like morale,attack bonuses,terrain, and these stuff shouldn't be a very big issue algorithmically...

But they all have a huge impact on how a unit v unit fight might go, or on how a unit moves or what it should do.

Nobunaga, your main point seems to be that TW and chess are very similar, when they just aren't. I know you keep on making this point, but it's just not true. AI in TW has to deal with an almost freeform battlefield with the possible terrain and units possibly random from battle to battle, it's a complex problem.

The battle AI in Empire is programmed in a way that best deals with the complexity of the TW battles and allows the AI to plan and react accordingly. We're working hard to make an AI that reacts and plans well and that will be a challenge. Now I'm leaving this thread as I've made my point and answered your's and I hav to get back to work.

[Nobunaga]

But this is the AI trying to predict the humans moves, you only make it consider the moves that make the most sense and you make it very easily exploitable.

No it wont be exploitable, since we are considering all movements that make sense... And even if it wasn't perfect/optimal it will be good.


It is more complex in terms of movement, so you get the same problem as in GO with trying to predict the future moves of the player.

It is not more complex in term of movement. Actually it is alot simpler since all units move the same but with different speeds. We discussed this before. Programmaticly you don't take the possible positions the unit can reach during the whole game. But you take the positions a unit can reach in a small time period.

(Example: In chess a horse can reach any position, but when branching u take the positions the horse can reach in one turn! replace the turn with a time period for TW)


There is no grid in TW, just the position of units on the battlefield, so talk of grids is irrelevant.

I thought we agreed above that their is a grid :dizzy2:. I assure u their is a grid, how else do you think map is represented programmaticly? It is always represented by a 2D (or higher sometimes) matrix.


Doesn't change the fact that the possible movements each unit can make is vastly bigger than the possible movements of each chess piece.

It is not. It is much more simpler. I talked about this in the beginning of this post.


But they all have a huge impact on how a unit v unit fight might go, or on how a unit moves or what it should do.

They have impact but nothing that cant be adjusted...as i said:


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

Thanks for your time Jack...

[Jack Lusted]

Okay one last post.


No it wont be exploitable, since we are considering all movements that make sense... And even if it wasn't perfect/optimal it will be good.

But if the AI is judging the players mvoes, how can you be certain the player will do moves that make sense?


It is not more complex in term of movement. Actually it is alot simpler since all units move the same but with different speeds. We discussed this before. Programmaticly you don't take the possible positions the unit can reach during the whole game. But you take the positions a unit can reach in a small time period.

But units can reach vastly more positions than in chess over a limited period of time because in chess there are only a few squares you can move to in a turn.


I thought we agreed above that their is a grid . I assure u their is a grid, how else do you think map is represented programmaticly? It is always represented by a 2D (or higher sometimes) matrix.

There is no grid in the sense your talking about in regards to AI. Nor will there be one as it makes no sense to divide the battlefield into a grid when we can just take the units position.

And for the record, the battle AI programmer has made chess AI's and has been working on game AI's for over 8 years and he says there is no point comparing chess AI to TW AI as the 2 are just too different.

[Nobunaga]

But if the AI is judging the players mvoes, how can you be certain the player will do moves that make sense?

Because moves that dont make sense are bad moves that which will probably be game costing. Am not saying that the AI will be perfect even chess AIs found in the market are not perfect (i.e. they dont always choose optimal moves, doing an optimal chess AI is very computationally time/space consuming).


But units can reach vastly more positions than in chess over a limited period of time because in chess there are only a few squares you can move to in a turn.

Yeah but you should only choose the moves that make sense or that succeed a certain criteria. One can always use heuristics/greedy choices. Here is one way to solve this:

We develop some function (call it F) that evaluates the current grid, now this should not be hard, and again I am not after exact scoring, but one that is good most of the times. We decide a threshold k for the maximum number children a node can have. If a node can branch to more than k children we only branch on the k children that give the highest scores in F.


There is no grid in the sense your talking about in regards to AI. Nor will there be one as it makes no sense to divide the battlefield into a grid when we can just take the units position.

But nothing prevent us from having one...


And for the record, the battle AI programmer has made chess AI's and has been working on game AI's for over 8 years and he says there is no point comparing chess AI to TW AI as the 2 are just too different.

i may be wrong, but why is it that different? i would love to hear his explanation, cause as i said:


The concept of chess and TW are very similar. We have a set of units on a grid (The number of units dont increase unlike other RTS games). Each unit occupies a position in the grid. The goal is to destroy a subset of your opponent units. (the king in chess and all the units in TW).

[Jack Lusted]

Because moves that dont make sense are bad moves that which will probably be game costing. Am not saying that the AI will be perfect even chess AIs found in the market are not perfect (i.e. they dont always choose optimal moves, doing an optimal chess AI is very computationally time/space consuming).

Doesn't stop the player from making those moves, and if the AI is expecting the player to play a certain way the player could play looking like they are playingt hat way, and then completely change tactic to exploit the AI reacting based on expecting the player to play a certain way.


Yeah but you should only choose the moves that make sense or that succeed a certain criteria. One can always use heuristics/greedy choices. Here is one way to solve this:

See above. We need to make an AI that can react and play well in any situation, which is especialy true given the huge variation in battles possible in TW.


But nothing prevent us from having one...

There's no point though as what would a grid bring to the Ai that knowing the position of a unit already does.


i may be wrong, but why is it that different? i would love to hear his explanation, cause as i said:

The explanations I've given in this thread are from him, and like I've said, TW is hugely more complex than chess despite your claims otherwise.

[Nobunaga]

Doesn't stop the player from making those moves, and if the AI is expecting the player to play a certain way the player could play looking like they are playingt hat way, and then completely change tactic to exploit the AI reacting based on expecting the player to play a certain way.

yeah but when the player change his tactics the AI should adjust its play...!? Each tree should be reconstructed periodically, or by triggers caused by moves the player make. So when the player changes his movement, the AI will adjust.

The same goes for chess, u cant fool the AI, if u did stupid moves u r heavily punished, u cant do stupid moves to fool the AI, then change your tactics since the AI will adjust...


There's no point though as what would a grid bring to the Ai that knowing the position of a unit already does.

now this really make no sense. isnt the position represented by the coordinates (x,y or x,y,z), so yeah their is a grid.


p.s. the current battle AI for TW can be exploited in countless ways....

[Jack Lusted]

yeah but when the player change his tactics the AI should adjust its play...!?

And it does currently without using much of a predictive system as a predictive system over any period of time larger than a few seconds could be wildly inaccurate given how different a units position could be over longer periods, so by then it's too late. So we instead use other methods to get the A to react well instead of using an extensive predictive system that would eat up a lot of processing time for not much benefit given how much things can change over anything larger than very short periods of time.


now this really make no sense. isnt the position represented by the coordinates (x,y or x,y,z), so yeah their is a grid.

Well I supose in that sense yes there is a grid, but it's not really termed as such as that is a units position on the battlefield.

[Nobunaga]

yeah but when the player change his tactics the AI should adjust its play...!?

And it does currently...


I sure hope it does...cause it didn't in previous TW titles...

thanks for your time jack...

[rajpoot]

Wow!!
As long as we're at it, making things clearer, can it now be disclosed if we have the choice of fighting sea-land battle combined? As in ships attacking a fort? :beam:

[CBR]

It should be pretty obvious that Total War (and most wargames) are a lot more complex than chess:

-A simple ordered movement system that allows only one piece to be moved at a time
-All pieces have same combat strength
-No time consideration when taking out opponent units
-No terrain differences
-No fatigue
-No morale
-No ranged attacks
-No hidden units and restricted camera
-Always the same "army" and deployment
-Units taking up half the playing board

And all that has to be done in real time. Understanding such complexity takes lots of playing experience which is why back in MTW days a CA dev team got wiped out when playing against a MP community team. Whereas chess is simple to learn but difficult to master, Total War is also difficult to learn before you even have a chance at mastering it.

In my 6 year MP experience I would say only a minority of players showed they had really learned the game. The rest just went through the basics and some even did what they could to remove some of the complexity through map choice or having "enough" money.

So no wonder that it is difficult to make a really good AI that really use all the elements of the battle engine.


CBR

[Nobunaga]

CBR u didnt read everything i wrote? do u have any programming experience? and y do u think that more rules implies more complicated AI????

[Kataki]

Jack you've spent more time than I would have trying to explain this :P ROFL

And nob, how does more rules NOT translate into more complex AI? In chess the moves that can be made are limited to one piece at a time, in a very strict manner of movement for each piece. In TW on the other hand every unit moves in real time anywhere they want to.

Only thing i can hope is that the battle AI will better recognize the entire army rather than seemingly concentrating on individual units. IMO anyway seems like the battle AI considers each unit its own army and doesn't really try to stay as a whole. Also be nice if the AI would use historical battle tactics for each army, or at least general formations.

[Nobunaga]

kat read the whole thread before posting... while it is easy to get misleaded and think that more rules imply more complex AI this is NOT the case...i'll give an example to show that AI is not affected by the number of rules (the example is trivial but it is sufficient):

suppose their is a game that is exactly the same as TW, but it has a unit that can't be routed and can't die call this game TW2, moreover in battles vs the AI the AI can pick his army. Now TW2 have trivial AI, the AI should just get this unit and do nothing and it will never lose. U see TW2 has the same number of rules as TW but doing optimal AI for TW2 is trivial...



In chess the moves that can be made are limited to one piece at a time, in a very strict manner of movement for each piece. In TW on the other hand every unit moves in real time anywhere they want to.

I have answered this several times i said:


It is not more complex in term of movement. Actually it is alot simpler since all units move the same but with different speeds. We discussed this before. Programmaticly you don't take the possible positions the unit can reach during the whole game. But you take the positions a unit can reach in a small time period.

plz read the whole thread before posting and u should have the minimum algorithmic knowledge to be order to disscuss...

[Kalle]

Mastering total war as a player is a lot easier then mastering chess as a player.

What requires most effort in creating good ai I would guess is an entirely diffrent matter and totalwar I think would require much more effort. And no, I do not need permission to take part in the debate or advanced programming or mathematics skills to make this guess and yet I think im not far off from target.

It took a few months of almost entire dedication to become a force to be reckoned with in totalwar mp in mtw and mtw-vi, it took roughly the same time for the clan (FF) that i was part of to become a clan that could fight the older clans successfully. Chess on the other hand I played for a lot longer and I prolly would never become a master at even if i played my entire life.

And ai, really is it the most important? For me most important is human vs human play. Balance, good nice factions with some unique flavor but not to much that it unbalances, smooth mp-functions for communicating and so on. (Remember buttons t and y in multiplayer?? :yes:) Manouver and tactics made more important then the kind of weapon a unit uses in melee allthough that should also matter of course.

Many of the best mp vets hugely enjoyed 1 on 1. Winning one on one in cwb in mtw / mtw-vi was a daunting and very exciting task and yes you could indeed do lots of things with 16 units.

Kalle

[Martok]

And ai, really is it the most important?
In short, yes it is. More Total War fans play the SP campaign than fight MP battles, so having a reasonably competent AI tends to be fairly crucial to the singleplayer experience. Hence, why this particular dev diary is of such keen interest to many of us. ~:)

[Kalle]

I know more players play sp yes :yes:

I only want them to remember the multiplayer aspect also :2thumbsup:

But im sure you havent forgotten mp? lusted?? :)

[Geoffrey S]

A comment earlier has made me wonder. A chess AI can indeed take as long is likes to plot a good-to-perfect move, something obviously impossible in a fluid real-time tactical game. However, is it feasible or even useful to have an AI in something like the TW series issue orders every 10-15 seconds, using the time in between to plot the best moves for the next 'interval'? Perhaps different length intervals based on the scale - overall army tactics, unit cohesion, and individual unit behaviour.

But I'm no programmer, and must confess having not a clue about how these things work.

[Nobunaga]

Geoffrey doing the perfect move may take million of years (literally). Yet doing a good move can take milliseconds...

[CBR]

CBR u didnt read everything i wrote? do u have any programming experience? and y do u think that more rules implies more complicated AI????

No I dont have any AI programming experience. My limited experience (if relevant at all) are rules for pen and paper RPG's and strategy games. The more parameters one adds the more rules are needed to clarify its use. If you add an ability that the player can use but make no rules for the AI then it will not use it and become weak and predictable.

In RTW the AI is horrible at managing fatigue. One easy plan is to deploy on top of a large hill and watch the AI do its usual uphill deathmarch which makes its exhausted when finally attacking you. I suspect fatigue is not part of AI calculations at all. It will be complex to program the AI to handle fatigue because the AI will have to think of the enemy army too and not just its own fatigue level: sometimes it is good to keep on going although exhausted if the enemy is exhausted too.

A chess program do not have to consider hidden enemy units and potiential hiding spots. A TW AI will have to have some way of dealing with that, maneuvering whole army to avoid such spots or use cav for recon, or it will fall to hidden units most of the times. Then add the ability for the AI to use hidden units too. How is that not gonna be complex?

You say movement is easier because units move at the same time but armies can be split up and used in groups and one can have reserves. Would chess be easier if one could move two or more pieces every turn? And what if you didnt have to move any pieces at all? That would mean more outcomes to calculate and not less.


CBR

[Nobunaga]

No I dont have any AI programming experience. My limited experience (if relevant at all) are rules for pen and paper RPG's and strategy games. The more parameters one adds the more rules are needed to clarify its use. If you add an ability that the player can use but make no rules for the AI then it will not use it and become weak and predictable.


more rules may imply more programming needed for the rules but not always more complex AI...

read:

kat read the whole thread before posting... while it is easy to get misleaded and think that more rules imply more complex AI this is NOT the case...i'll give an example to show that AI is not affected by the number of rules (the example is trivial but it is sufficient):

suppose their is a game that is exactly the same as TW, but it has a unit that can't be routed and can't die call this game TW2, moreover in battles vs the AI the AI can pick his army. Now TW2 have trivial AI, the AI should just get this unit and do nothing and it will never lose. U see TW2 has the same number of rules as TW but doing optimal AI for TW2 is trivial...



A chess program do not have to consider hidden enemy units and potiential hiding spots. A TW AI will have to have some way of dealing with that, maneuvering whole army to avoid such spots or use cav for recon, or it will fall to hidden units most of the times. Then add the ability for the AI to use hidden units too. How is that not gonna be complex?

as i said:


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

one direct solution to this maybe that the AI will cheat and the "Fog of war" option doesnt apply to the AI.


You say movement is easier because units move at the same time but armies can be split up and used in groups and one can have reserves. Would chess be easier if one could move two or more pieces every turn? And what if you didnt have to move any pieces at all? That would mean more outcomes to calculate and not less.


you dont have a clue about what I am talking about... I am saying movement is easier becaouse all units move in the same way but at different speeds... just read man:


It is not more complex in term of movement. Actually it is alot simpler since all units move the same but with different speeds. We discussed this before. Programmaticly you don't take the possible positions the unit can reach during the whole game. But you take the positions a unit can reach in a small time period.

btw are u sugesting that movement in TW has more statetgic implications than in chess :wall::wall:

[Ituralde]

Great Develop Blog, really interesting to read. I think it's good to see that the AI progression is checked and adjusted at a regular basis. I'm really looking forward to see it in action! :2thumbsup:

I considered writing something in response to Nobunaga, but then decided not to waste my time. I'm confident you're on the right track to improving the TW AI.

[Nobunaga]

omg Ituralde i am sure you have a great idea on what we were talking about....and I am sure that CA is on the right track just as they were in RTW and MTW2... actually the AI in the TW series was always great just ask mp guys what they think about the AI and they will tell you it is unexploitable/unbeatable...

[CBR]

Ok in the same way then. But it is still an AI handling 20 units or more, if more than one army is involved, and all has to be done in real time.

Since some pieces can move across the whole board in chess and the loss of one piece (the king) will mean a lost game, I'd say each move in chess has more strategic implications. But that does not say anything about how complex it is for the AI to calculate the move.


CBR

[SwordsMaster]

Nobunaga, You've been told repeatedly that the AI will not be a chess AI. It is being developed specifically for the game. If anything you should be happy some generic algorithm is not being used, and a whole new engine is being developed.

What is your obsession with a chess engine anyway? Let it go, the developers are obviously not interested, and I fully trust their intelligence to have considered their options before they spent thousands to develop the game.

[Nobunaga]

i really dont care about TW AI. CA can do whatever it wants with the TW series I dont give a crap...This was something I thought about at certain times and I still think it may work....I really hope that ETW will be a great game but if it didnt there is always starcraft2. Judjing from CA history my expectation are very low this time...CA should change its marketing tricks and all the hype it does cause it is becoming boring and obvious... they never anounce real game content or things that matter....they are always releasing games that are in beta state and they never balance mp...


What am saying is just my opinion, for me the game have greatly detoriated over time. Then again sales are good for CA...so good for them... I really dont give a crap...this is just a silly game...

[Colonel Flambard]

really dont care about TW AI. CA can do whatever it wants with the TW series I dont give a crap...

You know he has lost the argument. Looking forward to the new AI CA, however you choose to make it.

[Wandarah]

If only we could somehow transpose Nob's towering intellect into the AI for ETW. Surely then, we would have a challenging opponent!

I just read it, and I feel more challenged already.

[Nobunaga]

very constructive replies guys thank u :bow:

and flam please enlight me and elaborate on what u said:


You know he has lost the argument

[Nobunaga]

I'd say each move in chess has more strategic implications. But that does not say anything about how complex it is for the AI to calculate the move.

CBR the AI should study these startetgic implications so that he can make a good move. So the higher the startetgic implications the more complex the AI will be...

[Csargo]

i really dont care about TW AI. CA can do whatever it wants with the TW series I dont give a crap...This was something I thought about at certain times and I still think it may work....I really hope that ETW will be a great game but if it didnt there is always starcraft2. Judjing from CA history my expectation are very low this time...CA should change its marketing tricks and all the hype it does cause it is becoming boring and obvious... they never anounce real game content or things that matter....they are always releasing games that are in beta state and they never balance mp...


What am saying is just my opinion, for me the game have greatly detoriated over time. Then again sales are good for CA...so good for them... I really dont give a crap...this is just a silly game...

You can say whatever you want, but really deep down we all know you give a crap.

[pevergreen]

We also all know that particular line of discussion is not going anywhere good. I suggest an end to it?

[hoom]

there is always starcraft2Dude, Blizzard can't even work out how to make AI that gets 12 individual units to go to the place you asked without about half of them getting confused & taking the long way around or blundering into Siege Cannon range :wall:
TW AI has to work with loosely ordered groups totalling several thousand individuals on a vastly more complex map than any that Starcraft can provide & with many more factors to take into account (morale/fatigue & the various other combat attributes plus trying to approximate historically accurate army formations & reacting to the players moves).

Even Starcraft AI is going to be far more complex than any Chess AI but the Starcraft game rules are ridiculously more simple than TW.


Lusted/CA:
One thing I'd really like to see is for the possibility of both human & AI in-battle ambushes to actually work again.

In the grand old days of Shogun the AI would setup ambushes & players could get away with them sometimes too.
There was a big morale hit for being surprised by units suddenly appearing out of hiding, particularly if it was on flanks/to the rear.

Later TW AI seems to immediately recognise even a single unit being hidden & immediately heads for it with superior numbers :(

I think a part of it is that RTW engine has unlimited battle LoS, where in STW, a unit hidden behind a hill was invisible until you had LoS.
Quite often I'd even crest a hill only to find most of the AI army suddenly charging from short range (with related morale hit!)

[Colonel Flambard]

and flam please enlight me and elaborate on what u said:

Nobby, by saying that you don't give a crap anyway is a defeatist attitude. People with a defeatist attitude are usually the ones who have lost the argument. By using that tone it says that you cannot think of anything else to say to put forward your point of view. You could have a valid point, I would not know about alogorithms, but since facing strong opposition your argument has fallen apart.

[Divinus Arma]

Dude.

Jack Lusted just posted more in this thread than I ever seen a CA staffer post in any thread. And every word had to do with the AI.

What a treat!

[Geoffrey S]

Indeed, an interesting read.

[regor]

A game of chess and a TW battle are nothing alike. One is a deterministic system, with well defined boundaries and rules, while the other (although firmly grounded in a discrete world of the digital computer) is essentially non-linear. While you can argue witch is more complex (a moot point IMO, since the two really require two separate definitions of complexity), it wouldn't be productive to try and solve the problems present in the latter with the techniques used in the former.

I can agree with you that the current AI is, well, unintelligent. But if you cannot appreciate what it can do, given the complexity it deals with, you really don't know much about AI programming. I think most people here can, if only by sizing up he competition. The main complaint levied against the AI is not that it is down right broken, but that it has not progressed much over the years. Hopefully, this blog is a sign that Empires will address this.

[Nobunaga]

A game of chess and a TW battle are nothing alike. One is a deterministic system, with well defined boundaries and rules, while the other (although firmly grounded in a discrete world of the digital computer) is essentially non-linear.

Are you implying that TW is non-deterministic :laugh4: and dosent have boundaries nor rules :laugh4: :laugh4: and what do you mean by non-linear :laugh4:
Do you know what determinism is :inquisitive:

[PBI]

Nobunaga, have you considered perhaps making a mod in which you could implement your ideas for the AI? Whether your idea is a good one or not (I honestly have no idea), I think it's clear that the CA devs aren't convinced, so maybe a proof of concept would be useful to show the idea works? Isn't that more or less what Lusted did with his Lands to Conquer mod?

It's a shame this thread seems to have got rather bitter in tone, I think we should remember that Nobunaga was merely suggesting an idea to improve the game, which I don't think anyone would argue is a bad thing.

[Nobunaga]

The AI in TW cant be moded. Yet I can do a proof fo concept in an independent applicaton...

[Kommodus]

Thanks for the update CA! I am really looking forward to this game, since I've been wanting a game that models combat from this era for a long time. Many have tried, of course, but all have fallen short - either they tried too hard to be "realistic" and lost sight of the idea that a game should be fun, or they included too many game-ey elements to be truly immersive. As a fan of the TW series, I thank you guys for your hard work and wish you success in making this game's AI truly challenging! :bow:

And don't worry. Some of us really are programmers, and understand that creating the AI for a game like this presents a unique and difficult challenge. We know better than to take seriously the ramblings of certain ignorant self-satisfied know-it-alls. ~:rolleyes: ~;)

[TosaInu]

:campfire:

[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?



:laugh4: and dosent have boundaries nor rules :laugh4: :laugh4:

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 :laugh4:
Do you know what determinism is :inquisitive:

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?

:balloon2:

edit: 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. :medievalcheers:

[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!!!!!!!!:furious3:

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 :juggle2:

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]

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. :bow:


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. :2thumbsup:



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. :dizzy2:

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

[Tamur]

Well...

Let's put it this way: writing a battle AI for chess is very simple in comparison to TW, because:

Chess has a flat rectangular board with 64 square tiles. TW "boards" are thousands of times larger, are made up of no tiles, and contain terrain, elevation, and weather information.
Chess units are individual pieces. TW units are made up of multiple individuals.
Chess units kill instantly with any valid attack move. TW units can be counter-attacked.
Chess takes no account of factors that TW does, such as morale, fatigue, etc.
The moves available to a chess unit are very limited in scope, and executed instantly. The moves available to TW units are hugely more varied and executed over real-time.
A Chess AI can use its turn to formulate a strategy. In TW there are no turns, so strategy must be created on the fly.

I'm sure there are other factors, but these are a few of the basics.

I'm entirely open to the possibility that a TW battle AI could be written which outperforms CA's. After TosaInu's posts earlier this week I dug around and found the start of my coding project, and am trying it myself using a stripped-down knowledge-base approach.

However, in my experience, it's a very, very difficult proposition. Chess is so nicely packaged for computation in comparison.