The challenges of developing a good AI to ever more complex games

[ZOOMIE1980]

ORIGINAL: Kitakami

Having actually had to program a learning AI for the simple game of Pente, I have an appreciation for what it takes to program a system that actually learns from its own (and the enemy's) mistakes.

The programming side of it is a large undertaking, and I do not think you could do a generic AI that covers every type of game... it would have to take too much into account. The problem with that is the fact that a specialized AI would, although technically a success, not be an economic success

And to the above you have to add the fact that the knowledge databases would grow, and grow, and grow... the more you play, the bigger they'd get (that's how you store knowledge for the system).

And if you want the system to be efficient, you'd have a server online, where all the registered copies of the game would dump what they have learned from the player(s) that use them, and distribute the knowledge to all the copies by means of AI updates. Otherwise a registered copy would only learn from the local players, and a player with a different style might throw it into a fit.

Doable? Yes. Worth the while of whoever does it? Don't know. But if it ever gets done, count on an industry award, because a good AI is almost a dream that can't be reached... yet.

Yes, economics is the main reason game AI's are still at about the same state they were in the 1980's. There is no economic reason for a game publisher to finance such ventures. Probably going to take a significant OpenSource effort under a GPL license, by techies who have an intrest in this area to ever come up with something useful that could then, in turn, be used by for-profit game developers to ship games with better AI's. And a client-server architecture (even both run ont he same machine) would probably be a mandatory thing in such efforts.

[vorkosigan]

This is the next silver bullet possibly. I think wargame developers, though, are going to eventually have to adobt structured disk assess data management where volatile data resides in a structured disk based system, like an RDBMS. Turn based strategy are not particularly high performance, high throughput designs, but they tend to cart around comparitively larges amounts of data. With something like that you can use

Take a look on HTTR. Just from observing the game behaviour, overall design and developers background (look at Panther Games website) I must admit that those aussie guys have achieved a real breakthrough on the 'Dumb AI front'.

HTTR AI plans. This is, the Computer player (at the tactical/operational level) chooses a set of goals, and lays down an strategy ('sequence of moves') that try to maximize success likelihood while minimizing risks/costs. This might sound like rocket science (it is, just ponder the planning ability of the Mars Rovers which were using these same algorithms). But the algorithms for making this work have been laying around for thirty years.

I think that an on-line learning AI system deployed on a commercial product is non-sense. It is easier/more economical to devise a system that learns but that is trained in the development/beta-testing phase. It is not meant to be a robot free to roam your house - but a robot designed to 'roam' in a virtual, synthetic world were physics and complexity/chaos is controlled by a human ( yeah, brilliant but still human). Suitable learning algorithms for this could be the ones known collectivelly as 'reinforcement learning'.

Still, there could no need at all to 'train' the system. Just take and interview a few chosen, well-respected grognards, profile them and use these 'user profiles' to build the backbone of the AI 'experience'.

But unfortunately, I don't think that applying this technology on the wargaming software industry. Mainly because profit-seeking projects have their own characteristic constraints: time and budget. Defence and space exploration also must battle with this, but the resources at their disposal are several orders of magnitude bigger than usual game development ones.

However, a mixed open source/free software enterprise could do this. First, there is the pioneering spirit ( two guys in a garage can be very dangerous ). And second, it can make profits. Just that one does not try to sell the 'software' (which is a funny idea after all if we look at it objectively), but one sells the artwork, the historic research, the scenarios or the trained computer players...

PS: Sorry for any misspelled word or funny English sentence. I broke my left arm last weekend an I am Spanish :S

[Mr.Frag]

ORIGINAL: vorkosigan

This is the next silver bullet possibly. I think wargame developers, though, are going to eventually have to adobt structured disk assess data management where volatile data resides in a structured disk based system, like an RDBMS. Turn based strategy are not particularly high performance, high throughput designs, but they tend to cart around comparitively larges amounts of data. With something like that you can use

Take a look on HTTR. Just from observing the game behaviour, overall design and developers background (look at Panther Games website) I must admit that those aussie guys have achieved a real breakthrough on the 'Dumb AI front'.

HTTR AI plans. This is, the Computer player (at the tactical/operational level) chooses a set of goals, and lays down an strategy ('sequence of moves') that try to maximize success likelihood while minimizing risks/costs. This might sound like rocket science (it is, just ponder the planning ability of the Mars Rovers which were using these same algorithms). But the algorithms for making this work have been laying around for thirty years.

I think that an on-line learning AI system deployed on a commercial product is non-sense. It is easier/more economical to devise a system that learns but that is trained in the development/beta-testing phase. It is not meant to be a robot free to roam your house - but a robot designed to 'roam' in a virtual, synthetic world were physics and complexity/chaos is controlled by a human ( yeah, brilliant but still human). Suitable learning algorithms for this could be the ones known collectivelly as 'reinforcement learning'.

Still, there could no need at all to 'train' the system. Just take and interview a few chosen, well-respected grognards, profile them and use these 'user profiles' to build the backbone of the AI 'experience'.

But unfortunately, I don't think that applying this technology on the wargaming software industry. Mainly because profit-seeking projects have their own characteristic constraints: time and budget. Defence and space exploration also must battle with this, but the resources at their disposal are several orders of magnitude bigger than usual game development ones.

However, a mixed open source/free software enterprise could do this. First, there is the pioneering spirit ( two guys in a garage can be very dangerous ). And second, it can make profits. Just that one does not try to sell the 'software' (which is a funny idea after all if we look at it objectively), but one sells the artwork, the historic research, the scenarios or the trained computer players...

PS: Sorry for any misspelled word or funny English sentence. I broke my left arm last weekend an I am Spanish :S

Yep, HTTR is great, but you will also note that Dave is quite clear in all his posts that there is a finite limit to how many units he can handle based on horsepower of machines. It's that old "I can do fantastic ai for 1 unit or great ai for 100 units or average ai for 1000 units or poor ai for 10000 units."

I am amazed at what the AI in WitP *can* do considering 12,000 units.

[ZOOMIE1980]

ORIGINAL: vorkosigan

This is the next silver bullet possibly. I think wargame developers, though, are going to eventually have to adobt structured disk assess data management where volatile data resides in a structured disk based system, like an RDBMS. Turn based strategy are not particularly high performance, high throughput designs, but they tend to cart around comparitively larges amounts of data. With something like that you can use

Take a look on HTTR. Just from observing the game behaviour, overall design and developers background (look at Panther Games website) I must admit that those aussie guys have achieved a real breakthrough on the 'Dumb AI front'.

HTTR AI plans. This is, the Computer player (at the tactical/operational level) chooses a set of goals, and lays down an strategy ('sequence of moves') that try to maximize success likelihood while minimizing risks/costs. This might sound like rocket science (it is, just ponder the planning ability of the Mars Rovers which were using these same algorithms). But the algorithms for making this work have been laying around for thirty years.

I think that an on-line learning AI system deployed on a commercial product is non-sense. It is easier/more economical to devise a system that learns but that is trained in the development/beta-testing phase. It is not meant to be a robot free to roam your house - but a robot designed to 'roam' in a virtual, synthetic world were physics and complexity/chaos is controlled by a human ( yeah, brilliant but still human). Suitable learning algorithms for this could be the ones known collectivelly as 'reinforcement learning'.

Still, there could no need at all to 'train' the system. Just take and interview a few chosen, well-respected grognards, profile them and use these 'user profiles' to build the backbone of the AI 'experience'.

But unfortunately, I don't think that applying this technology on the wargaming software industry. Mainly because profit-seeking projects have their own characteristic constraints: time and budget. Defence and space exploration also must battle with this, but the resources at their disposal are several orders of magnitude bigger than usual game development ones.

However, a mixed open source/free software enterprise could do this. First, there is the pioneering spirit ( two guys in a garage can be very dangerous ). And second, it can make profits. Just that one does not try to sell the 'software' (which is a funny idea after all if we look at it objectively), but one sells the artwork, the historic research, the scenarios or the trained computer players...

PS: Sorry for any misspelled word or funny English sentence. I broke my left arm last weekend an I am Spanish :S

Game developers, first, have to get over their tendancy to re-invent every wheel ever invented every time they strike off on a new project. There is a real dirth of third party tools in use in the gaming industry and that is because these guys always feel the need to roll their own. Hell, the few that are slowly moving the disk based management systems are, yet again, mostly rolling their own???? It is a paradigm rut they're stuck in. That "we've always done it that way" nonsense. It's why so many still program their systems in procedural 'C' that the rest of the software development world left behind over a decade ago, and design software and development environments as if they are still writing for old defunct, 640K DOS on 386's.

Like I've said before, the gaming industry as a whole needs a Christianity style reformation. A renneassaince of sorts. Once that happens, then a lot of these kind of ideas might have a chance to be explored. But until then, we are largely going to be stuck with same basic AI's we've got and have had now for almost 20 years....

[vorkosigan]

Yep, HTTR is great, but you will also note that Dave is quite clear in all his posts that there is a finite limit to how many units he can handle based on horsepower of machines. It's that old "I can do fantastic ai for 1 unit or great ai for 100 units or average ai for 1000 units or poor ai for 10000 units."

Hmmm, I think we need to get creative when we talk about the term 'unit'. First, we should take apart the concept of counter ( the physical representation of things on the board i.e. what can move, kill an die) from that of organization.

Now I don't fully have time to ellaborate on this, but I promise to expose my (hopefully) points in next posts.

[ZOOMIE1980]

ORIGINAL: vorkosigan

Yep, HTTR is great, but you will also note that Dave is quite clear in all his posts that there is a finite limit to how many units he can handle based on horsepower of machines. It's that old "I can do fantastic ai for 1 unit or great ai for 100 units or average ai for 1000 units or poor ai for 10000 units."

Hmmm, I think we need to get creative when we talk about the term 'unit'. First, we should take apart the concept of counter ( the physical representation of things on the board i.e. what can move, kill an die) from that of organization.

Now I don't fully have time to ellaborate on this, but I promise to expose my (hopefully) points in next posts.

Sounds like the starting material for a SourceForge project???

[Mr.Frag]

Hmmm, I think we need to get creative when we talk about the term 'unit'. First, we should take apart the concept of counter ( the physical representation of things on the board i.e. what can move, kill an die) from that of organization.

Sure, but really it is quite simple.

A unit is defined as the smallest element capable of independant action.

Anything smaller is simply an element of a unit as it can not act on it's own and does not need to be tracked.

You can destroy elements within the unit which may alter the performance of the unit, but at the ai level, only the unit must be dealt with.

You as a developer choose what defines a unit and this sets the overall tone for the entire game. The lower the unit in the structure, the more tactical the game becomes.

WitP strikes a really weird mix having some level low level tactical units (individual pilots) making it tactical yet on the high end Task Forces or Divisions (operational and strategic). HTTR sits purely at one level and runs the entire game at that level which makes for a much simpler logic problem to soluton. (no critique aimed at either party obviously, both are excellent and I recommend both highly)

[Grotius]

If you'd like to read an interesting discussion of a new massive-wargame-AI project, the AI designer for Matrix's version of "War in Flames" has been posted some of his ideas for that game's AI. That guy, Robert Crandall, says AI is the most "fun" part of a computer wargame project, which is interesting. Here's more:

The AI architecture has not been set yet but it will doubtless be some sort of layered hierarchy of finite state machines within a subsumtive framework. (Don't worry if that is Greek to you - it means a fairly conventional job, thats all). Some of the problems posed towards the middle layer of the AI sound like they would lend themselves to a scripting solution so there might well be a 'playbook' aspect too.

Something that I have not done yet in my games but would be fun to do is to give the the fsm agents a 'memory' of what they have done so far. That would really help with 'maintenance of the objective' issues in the short run, and would open up all kinds of possibilities more generally. Once you have a memory you can start to do all kinds of other things, one of which is simple learning.

Will it be fancy? Nope, not to start but it might actually reduce the complexity of the AI in the long run rather than increase it. Instead of working out all the combinations and permutations for all possible action in code it might become possible to do a simple look up of all ~matching instances in a database of memories and estimate probable outcomes based on what it finds - that sort of thing. That makes me really, really interested in pursuing it!

And this:

It will never have a killer AI, but it should have a sufficiently competent one to teach a newcomer some of the basics and to provide useful filler players in a multiplayer game if desired. Beyond that I cannot really say yet.

AI is the most fun part of any game project and I'm sure that there will be continual development over many years to come in the MWIF AI. At least some of it will be exposed so that interested parties can tweak weightings, etc. For version 1, our goals will be quite modest - honestly, there is no other way to do it!

These posts are on the second page of the thread entitled "AI/No AI" in the WIF forum. See

tm.asp?m=640847

[ZOOMIE1980]

ORIGINAL: Grotius

If you'd like to read an interesting discussion of a new massive-wargame-AI project, the AI designer for Matrix's version of "War in Flames" has been posted some of his ideas for that game's AI. That guy, Robert Crandall, says AI is the most "fun" part of a computer wargame project, which is interesting. Here's more:

The AI architecture has not been set yet but it will doubtless be some sort of layered hierarchy of finite state machines within a subsumtive framework. (Don't worry if that is Greek to you - it means a fairly conventional job, thats all). Some of the problems posed towards the middle layer of the AI sound like they would lend themselves to a scripting solution so there might well be a 'playbook' aspect too.

Something that I have not done yet in my games but would be fun to do is to give the the fsm agents a 'memory' of what they have done so far. That would really help with 'maintenance of the objective' issues in the short run, and would open up all kinds of possibilities more generally. Once you have a memory you can start to do all kinds of other things, one of which is simple learning.

Will it be fancy? Nope, not to start but it might actually reduce the complexity of the AI in the long run rather than increase it. Instead of working out all the combinations and permutations for all possible action in code it might become possible to do a simple look up of all ~matching instances in a database of memories and estimate probable outcomes based on what it finds - that sort of thing. That makes me really, really interested in pursuing it!

And this:

It will never have a killer AI, but it should have a sufficiently competent one to teach a newcomer some of the basics and to provide useful filler players in a multiplayer game if desired. Beyond that I cannot really say yet.

AI is the most fun part of any game project and I'm sure that there will be continual development over many years to come in the MWIF AI. At least some of it will be exposed so that interested parties can tweak weightings, etc. For version 1, our goals will be quite modest - honestly, there is no other way to do it!

These posts are on the second page of the thread entitled "AI/No AI" in the WIF forum. See

tm.asp?m=640847

I would agree wholeheartedly with that assessment. The AI aspect of game development, for me, would be the central focus of anything I would choose to work on. I find that part of a game, from a development perspective, to be, by far, the most compelling aspect of a game project.

And once again, his "memory" take seems taylor made for employing the use of an RDBMS and a client-server architecture.

[Mr.Frag]

I would agree wholeheartedly with that assessment. The AI aspect of game development, for me, would be the central focus of anything I would choose to work on. I find that part of a game, from a development perspective, to be, by far, the most compelling aspect of a game project.

It is *also* the most expensive time consuming portion of any game.

Go find someone to fund you for 2 years while you write your game Zoomie [;)]

[Ron Saueracker]

Yep, sounds like Zoomie is gonna be busy. Get to work, buddy![:D]

[ZOOMIE1980]

ORIGINAL: Ron Saueracker

Yep, sounds like Zoomie is gonna be busy. Get to work, buddy![:D]

But I have 1235 turns to get through yet....................

[Bodhi]

ORIGINAL: ZOOMIE1980
And once again, his "memory" take seems taylor made for employing the use of an RDBMS and a client-server architecture.

What have golf clubs got to do with AI? [&:][:D]

[Mr.Frag]

ORIGINAL: Bodhi

ORIGINAL: ZOOMIE1980
And once again, his "memory" take seems taylor made for employing the use of an RDBMS and a client-server architecture.

What have golf clubs got to do with AI? [&:][:D]

Absolutely nothing at all [:D]

Storage of data has nothing to do with code function at all. Frankly, as long as the data structure is fast, it has no bearing on anything. It could just as simply be stored in XML or as java objects [8|]

[irishman]

How about simply paying Mogami to become a professional player? Pretend there's an AI but secretly e-mail him every turn. Say 1p per turn ? 1000 turns per day? [:D]

[Mike Scholl]

ORIGINAL: Mr.Frag

But it would be nice if you could get it to the point where if it "gets hurt" a couple
of times in an area, it would try to avoid that area while beating down whatever
unit(s) were causing it's pain. If a child can learn to avoid a hot stove, it would
seem that an AI could be programmed to avoid sailing TF after TF into harms way
without taking the slightest action to suppress or eliminate the source of the harm.
It does have access to ALL the information in the game.

Mike, that logic would be completely valid if the AI tracked multiple turns worth of events. It could see that there was a problem "Stove is hot" and remember "I got burned here last time" coupled with a reverse trigger event "stove is cold now". Thats a reactionary system where things become learned based on things going wrong.

I don't think the WitP engine runs as a reactionary system. It seems to be an evaluation type system where it checks each turn to see if a set of conditions exist that would warrant a change "Air Bal = xxx" and chooses to do something else.

To get such a system, the game would have to track trends. That tracking obviously increases the memory and horsepower requirements in an exponential scale. (the farther you track, the more it increases). I doubt very much that type of system (although it would be fantastic) can be done on a PC based platform beyond more then a hundred units or so. WitP has roughly 12,000 ships/planes/ground units.

I'm all for it, but I think we are still years away from the horsepower required.

A reasonable answer, FRAG. So basically the problem is that the "danger reccognition"
loop in the programming isn't sensitive enough as it stands now? And that it doesn't
communicate with the "attack planning sub-routine" well enough to tell it "dangerous
concentration of enemy force here..., do something about it". Still seems as if some
"tweeking" could make it more responsive to the fact that it has placed it's manhood
in a meatgrinder and the crank is being turned every day.

[Mr.Frag]

A reasonable answer, FRAG. So basically the problem is that the "danger reccognition"
loop in the programming isn't sensitive enough as it stands now? And that it doesn't
communicate with the "attack planning sub-routine" well enough to tell it "dangerous
concentration of enemy force here..., do something about it". Still seems as if some
"tweeking" could make it more responsive to the fact that it has placed it's manhood
in a meatgrinder and the crank is being turned every day.

Yep, but there is always a counter balancing risk to these changes. The AI could become so worried about protecting itself that it will no longer come out and play.

It's a balance act between "aggressive and reckless" vs "careful and unmoving"

Both extremes can be bad or good depending on the right time. Where humans have the advantage over all AI's is we can do both at once because we are thinking much longer term.

[Oznoyng]

ORIGINAL: Mr.Frag

ORIGINAL: Bodhi

ORIGINAL: ZOOMIE1980
And once again, his "memory" take seems taylor made for employing the use of an RDBMS and a client-server architecture.

What have golf clubs got to do with AI? [&:][:D]

Absolutely nothing at all [:D]

Storage of data has nothing to do with code function at all. Frankly, as long as the data structure is fast, it has no bearing on anything. It could just as simply be stored in XML or as java objects [8|]

I am suprised Zoomie hasn't nailed you on this one. The value of an RDBMS implementation is in the flexibility that it gives you for manipulation of data. How much space it takes, and even how fast it is are secondary to how quickly you can write the code.

- The best architecture for this kind of game is a pay-per-month game, where *all* data is hosted by the game provider on application servers with an SQL back end. You pays or you no plays.
- No counterfeiting cuz the game is worthless without the servers.
- It would probably run from your web browser - and it will have a better interface because programmers will be able to leverage the web forms capabilities of application servers to produce the interface changes almost as fast as users can request them.
- No OOB/restart issues will exist, because servers can be updated more easily. Fixing a problem in the OOB is an SQL statement.
- You will be able to have people entering turns at the same time, rather than taking turns.
- You will be able to do cooperative development of scenarios. You won't be making a list of changes and sending it to pry, or whoever, you will enter changes directly into the scenario.
- The speed of your machine will matter far less, because the AI isn't running on your machine.
- The AI can be changed on the fly to add capabilities.

BTW, I am quite happy with WitP. I just see alot that could be done with the right architecture.

[Mr.Frag]

ORIGINAL: Oznoyng

ORIGINAL: Mr.Frag

ORIGINAL: Bodhi



What have golf clubs got to do with AI? [&:][:D]

Absolutely nothing at all [:D]

Storage of data has nothing to do with code function at all. Frankly, as long as the data structure is fast, it has no bearing on anything. It could just as simply be stored in XML or as java objects [8|]

I am suprised Zoomie hasn't nailed you on this one. The value of an RDBMS implementation is in the flexibility that it gives you for manipulation of data. How much space it takes, and even how fast it is are secondary to how quickly you can write the code.

- The best architecture for this kind of game is a pay-per-month game, where *all* data is hosted by the game provider on application servers with an SQL back end. You pays or you no plays.
- No counterfeiting cuz the game is worthless without the servers.
- It would probably run from your web browser - and it will have a better interface because programmers will be able to leverage the web forms capabilities of application servers to produce the interface changes almost as fast as users can request them.
- No OOB/restart issues will exist, because servers can be updated more easily. Fixing a problem in the OOB is an SQL statement.
- You will be able to have people entering turns at the same time, rather than taking turns.
- You will be able to do cooperative development of scenarios. You won't be making a list of changes and sending it to pry, or whoever, you will enter changes directly into the scenario.
- The speed of your machine will matter far less, because the AI isn't running on your machine.
- The AI can be changed on the fly to add capabilities.

BTW, I am quite happy with WitP. I just see alot that could be done with the right architecture.

Everything you have mentioned applies to online rpg games, not a single aspect of it has any meaning to a war game where static units with static abilities move around a static map. Online games are *not* time based. Things can change all the time and it makes no difference. On a side note, paying someone else to have a cpu to run your game on costs money *forever*. If you want to pay $20 a month forever to play, thats fine. I'm sure 2by3 would *love* to switch over to subscription fees and just keep milking you for more money each month for a token feature like the online games do. [:D]

In a war game you have a set number of things that you use based on time. The only way to change a unit is to go back in time before the unit was ever used to allow it to be used. Sorry, but that is the very nature of time based games. You can't undo a problem in the past without throwing away everything beyond that point in time (restart).

by the way, anyone who talks about using relational databases to handle a lousy 2 megs of data is a space cadet [8|]

[DrewMatrix]

Let me say something nice about the AI here.

Most games have a very passive AI. The AI in WITP is willing to take some risks, and willing to do something reckless on occasion. That is a big plus.

When it does do something aggressive it tends to do it in force (like with all its CVs in one big group)

Hooray for a non-wuss AI!