Why Programming a Campaign Game is Very Hard

[Graymane]

There are a few things that can be done to help AIs perform better. I'm not sure how cost-effective they are in the gaming world where you have limited budgets, people and time, but they are very effective in other areas. You might also have more severe performance criteria (cheaper computers, people that aren't willing to wait around while the AI "thinks", etc).

Hierarchy/Decomposition - Many AIs (game-related or not) are built as one level. The AI is either scripted as a series of IF..THEN..ELSE conditions or a number of scripts are created with some being selected at random. This has the virtual of being economical and simple to program but still gives decent performance. A different approach is to create an AI for each aspect that is important for the problem at hand. For a game, something like a path-finding AI, an LCU AI, an Air AI, a Naval AI, a production AI and then higher level AIs that use those levels lower than themselves. So, you might have an operational AI that is assigned an area, a time and a mission and forces and uses those lower level ones to conduct operations.

Constraints - Time boxing or geographical boxing or other forms of limiting choices is essential for an AI when there are many, many variables. Not sure what all would be involved in a game, but something like an operational area for an operational AI with a given mission and time constraint. By tying this to other constraints like a doctrinal template for conducting an attack or defense, the AI can operate efficiently by reducing noise.

Learning - This one is interesting. If you can identify key variables for certain situations, you can adapt an AI to what it encounters. For example, it could analyze air battles in some fashion (statistically, for example) and/or situationally based on some criteria. It would look at the tendencies of the player it is playing against and try to counter it.

Agent-based Learning - This one is fairly complex, but a completely different approach than what is described above. Above is sort of a "top-down" view of the world. It assumes you can derive meaningful rules from some subset of the variables to drive decisions. What if you don't know the rules or which variables are important? What if you can derive behaviors though? "Avoid danger", "find food", "explore", etc. If you can come up with some behaviors and situations and rules for which behaviors you want to see in those situations, various kinds of agents can "learn" after a fashion. This has been used in modelling traffic flows and rush hour modelling, for example.

[JWE]

Why is programming a campaign game very hard?

a) because nobody in the world can do it. And if you think you can, you are an instant billionare and have won the Nobel Prize in mathematics for the next five years;

b) because even if you could, not many people would get it, and even those who do would complain about extraneous, ultra useless, logistics, clickfests; and

c) sounds great, but I only got 2 minutes to do the shrimp and crawfish for the Jambalaya, and I been here way too long.

[LoBaron]

ORIGINAL: fcharton
This is where programming a wargaming-AI differs from programming a chess AI. I would try and use something like Bayes inference here : basically, you start considering the situation as 'totally random' (within some prior knowledge you were given, like the map, game rules, perhaps enemy OOB at start), and incorporate into it all the things you learn (as posteriori knowledge). This makes the situation "less random", and the few certitudes you have on the current situation help you (the AI) decide what to do next. In other words, to perform on wargames like this one, where incomplete information is common, the AI decision process has to be statistical, and not analytic.

This is yet another reason why I think a dedicated AI could do wonders : the human brain is bad at statistics (just consider the number of statistical paradoxes).

Thanks for the detailed response fcharton!

What you wrote above is where I think this discussion leads to, and we are again stuck with the same problem.

An AI capabe of doing this or something similar (randomness + a posteriori knowledge) requires the ability to

- extract a specific frame of information based on the requirements of the specific situation - which suggests a complex flexible base decision process on how to choose the frame
- pull information from a huge/ever increasing memory storage that incorporates everything dubbed as a posteriori knowledge (that means not one specific dataset but again an ever increasing number
of specific frames containing multiple datapoints with relation to each other, to enable the AI to work with this knowledge at all - without this you could skip the a posteriori knowledge part as a whole
and just create a static dataset at the start)
- the ability to come to a limited decision set using this data, without creating non-sensical results (where we are back at
And everything has to be kept reasonable--anything not sanity checked will drift into insanity. )
which suggests an additional layer of control AI to compare actions against results.

As, like herwin mentioned at the beginning,

Campaign games involve hundreds or thousands of turns, each involving millions of sequential steps. The end of each turn involves large numbers of rounding operations to convert floating point numbers to integers that represent the game state at the end of the turn. If each of those operations introduces 1% error, playing a hundred turns inflates that error to the point that all numbers are meaningless.

the AI has to be able to perform what I wrote above for the situation described in the quote, the only way this is leading to is an
AI which is not as, but a multitude as complex as the game itself, and requires a multitude of processing power and memory storage.

[Reconvet]

Really interesting thread. I've been pondering every now and then why so few strategy games have a decent AI. Can it really be that hard to code leadership basics as taught in staff courses?

English is a foreign language to me and apart from some macros and excel-programming I've had no coding practice in the last 25 years, but I'll give it a shot to lay out how I'd define the basic capabilities an AI should get:

a) Situation analysis
Even a non-cheating AI should be capable of gaining a minimal situational awareness. Own forces available, infos on enemy forces, distinguishing between important/neglectable map locations/regions, listing and interpreting enemy activities, distinguishing active fronts from quiet ones, recognizing regions offering opportunities or being threatened due to force balance, applying force composition templates for specific tasks.

b) Define Strategy
Based on repeated/rolling situation analysis: define, prioritize and adapt goals/targets/missions, in general (theatre-wide) and for different front regions, which implies the use of sub-AI's (forming a hierarchical command structure) for each front region and possibly individual missions. Use free resources for new missions or for reenforcing struggling missions. Switch stances according to threat levels.

c) Management of Operations
Distribution of resources according to mission requirements. Use templates for force compositions. All AI's constantly reevaluate their situation (every front region AI has to do it's own situation analysis with it's own resources), ask for reeinforcements or release unneeded resources according to the state of their mission and enemy activities, and adapt their operational stance (build up and prepare before offensives, halt offensives to wait for reeinforcements, switch to defense when hitting a wall or running into a counteroffensive, etc).
Keep record of the level of combat success and adapt own resource investment (redefine action templates - for example reduce ground unit allocation for attacks in china if attacks succeed below a 3:1 ratio, etc).

d) Evaluation of enemy behaviour and adapting to it
Recognize enemy behaviour patterns and changes in enemy behaviour. Sun Tsu delivers the basics how to react/adapt.

I'm running out of time, and this post has grown too long already, but these are the main points every strategy game AI should try to deliver, and most AI's in this sector (imho) suffer from a terrible situation analysis, leading to total AI failure.


Just one thing more:
I just tested (and trashed again...) another Paradox-game, Hearts of Iron III (discount-bought, and I won't throw any money after them anymore). But inspite of all it's faults (and utter failure in several game aspects) the approach of letting the player set goals for individual HQ's on different levels (theatre/army group/army/army/corps) and then let this specific HQ-AI use it's attached assets to work towards it's goal (defending/conquering a targetted map location) seems very promising to me. HoI3-Theatre-AI's can make requests for more troops/panes if they think they can't do their assigned job with the assets they have. Paradox once again was either unwilling or incompetent to implement a really useful AI, but they did take a step in the right direction.

[mike scholl 1]

ORIGINAL: JWE

Why is programming a campaign game very hard?

a) because nobody in the world can do it. And if you think you can, you are an instant billionare and have won the Nobel Prize in mathematics for the next five years;

b) because even if you could, not many people would get it, and even those who do would complain about extraneous, ultra useless, logistics, clickfests; and

c) sounds great, but I only got 2 minutes to do the shrimp and crawfish for the Jambalaya, and I been here way too long.

You left out "d)". Most designers seem to think "AI" stands for "Animated Ignorance". That it's purpose is to give the player the IMPRESSION that their non-human opponant is DOING something..., even if most of what it's doing is rediculous. Very few rise to the level of AE in trying to make the AI into a reasonably rational opponant with goals and purpose.

[herwin]

ORIGINAL: JWE

Why is programming a campaign game very hard?

a) because nobody in the world can do it. And if you think you can, you are an instant billionare and have won the Nobel Prize in mathematics for the next five years;

b) because even if you could, not many people would get it, and even those who do would complain about extraneous, ultra useless, logistics, clickfests; and

c) sounds great, but I only got 2 minutes to do the shrimp and crawfish for the Jambalaya, and I been here way too long.

Think about what a program would look like if it worked like John Von Neumann thought brains worked. Incredible numbers of inputs, but very simple operations.

[herwin]

I'm back in the UK, and I'm completely beat, but I want to put something together later in the week that describes my vision of an alternative way to build intelligent systems. Just a straw-dog to kick around.

Something to remember is that your average human makes sense of the world with a collection of about 30,000 concepts. That's not a big number for a computer to manage. The operations they apply to that collection are simple. Most of the intelligence involves the number of other concepts or sensory inputs that feeds into each concept.

[fcharton]

ORIGINAL: mike scholl 1
Most designers seem to think "AI" stands for "Animated Ignorance". That it's purpose is to give the player the IMPRESSION that their non-human opponant is DOING something...

I think this is a bit unfair on the designers... (and besides, this could be said of a number of players of the same games, doing random stuff, not following any plan, and trying to post rationalize the results). Programmers try to develop serious AI, but it is a very complex topic, where very little is published or shared, and where budgets are low.

I tend to think that programming an AI is the same kind of effort as designing a compiler. If you try to attack it from scratch, you are bound to fail. Yet, after many years (decades) or research by lots of people (computers used to cost millions, and investment in compiler theory was worthwhile), a very general theory was developped, and tools were created to solve specific problems in this filed (regular expressions, parsers...)

Unfortunately for games, working on AIs is not cost effective. Games are cheap, often have short shelf lives, and developping a networked, or PBEM, mode is very easy, and sometimes extremely profitable (eg WoW).

It is a "dammned if you..." situation : developping AI from scratch is too much of an effort to be cost effective, and since no one does it (because it is not cost effective) there is no "common knowledge" to capitalize upon, and foster faster development...


Besides, giving the player the impression that the computer is acting purposedly is what AI programming is all about. Computers don't think, no matter how you program them... The goal of an improved AI is just to provide players with a better challenge, and one that "feels real".

Francois


PS *** a small and unrelated comment ***
AE, due to its turn system is a game that could allow for an "independent AI" (ie something developped apart from the game). Basically, an AI for AE would take a PWS save file, open it "in Tracker fashion", modify it, and save it as played. When this new turn file is opened, the turn would play..

Such an external AI would suffer from not knowing the game internals, but it means that, given "tracker like" NDA and stuff, AE is a good platform for such a projet.

[crsutton]

ORIGINAL: JWE

Why is programming a campaign game very hard?

a) because nobody in the world can do it. And if you think you can, you are an instant billionare and have won the Nobel Prize in mathematics for the next five years;

b) because even if you could, not many people would get it, and even those who do would complain about extraneous, ultra useless, logistics, clickfests; and

c) sounds great, but I only got 2 minutes to do the shrimp and crawfish for the Jambalaya, and I been here way too long.

Funny you should bring this up. I actually did win the Nobel Prize in 1979. For my Jambalaya. You can look that up......

[Chickenboy]

@ crsutton: In reviewing the Nobel awards for the past 50 years, I only encountered your Nobel awards for A. 'Most improved' Allied player and B. Tantric amorous activities. Did I miss it? [&:] [:'(]

[mike scholl 1]

ORIGINAL: fcharton

ORIGINAL: mike scholl 1
Most designers seem to think "AI" stands for "Animated Ignorance". That it's purpose is to give the player the IMPRESSION that their non-human opponant is DOING something...

I think this is a bit unfair on the designers... (and besides, this could be said of a number of players of the same games, doing random stuff, not following any plan, and trying to post rationalize the results). Programmers try to develop serious AI, but it is a very complex topic, where very little is published or shared, and where budgets are low.

Besides, giving the player the impression that the computer is acting purposedly is what AI programming is all about. Computers don't think, no matter how you program them... The goal of an improved AI is just to provide players with a better challenge, and one that "feels real".

Francois

I don't think it's "unfair" at all, given some of the "advertising blurbs" attached to the release of new games. "Improved" and "intuitive" AI are favorite phrases in these things..., and in 75% of them total lies. Thanks to the hard work of a couple members of the AE team, the "Admiral's Edition" actually did provide an improved challange to AI-only players, which proved that SOMETHING could be done to do a better job of AI creation. And given the complexity of AE over your average "Tiller Game" and the like, it also proves that the designers are often lazy.

"The goal of an improved AI is just to provide players with a better challenge, and one that "feels real"." I agree with this statement totally. It SHOULD be the goal of every designer. Unfortunately it seldom seems to be more than that "advertising blurb" I mentioned above. Ask any hard-core military gamer how many titles sit on his shelf gathering dust because after one play it became obvious just how to beat the AI? No matter how much "hype" the AI was given.

[decaro]

ORIGINAL: herwin

East rather than West ...

Herman Wouk wrote that both IJ and the Nazis made the same mistake in going East.

[Shark7]

ORIGINAL: LoBaron

I think this is one of the major difficulties when developing an AI.

The brain narrows down to a flexible decision point through checks on experiences and thousands of comparisions pulled from a high capacity
memory with the ability to abstract those memories.

It lacks the speed and accuracy but is far more independent and flexible on decision making compared to a process involving
a multitude of partly predefined decision steps.

anything not sanity checked will drift into insanity

Absolutely. Without the knowledge about that tendency about 50% of the present SF literature
would not exist. [;)]

Actually a better way of seeing it is that while a computer is capable of coming to a decision based on a number of variables, it is not capable of coming to variable conclusions.

That is the strength that the human mind has over an AI. An AI is only capable of coming to the conclusions it is programmed to come to. Take 100 computers with the same code and same variables, and they will come to the same comclusion...even with the addition of a randomizer, they will still fall into a predictable range. Take 100 humans and present them with a problem, and you will likely come to 100 different methods of arriving at a solution.

Add to that the human mind is capable of 'thinking outside the box'. An AI is very limited to the box it has defined in its code.

AIs may be able to crunch a bunch of numbers and do it a lot faster than you or I, but you and I have the advantage of creativity. [;)]

[Pascal_slith]

ORIGINAL: PaxMondo

ORIGINAL: herwin

John von Neumann, one of the inventors of Game Theory,

One of the people on my Top 10 list ... Brilliant man who thought through so many things. His Theory of Games and Economic Behavior sits right up Front and Center on my book shelf ... adorned with many "stickies" and dog eared pages ....

Available here: http://www.archive.org/details/theoryof ... d030098mbp

[Pascal_slith]

ORIGINAL: herwin

For a number to make sense in the game, someone had to deliberately program code to do that. There are too many significant numbers for us to reasonably expect that. I'm finally beginning to appreciate that it's just a game, and it does what it does. The historian in me is sad, but that's the way it is.

Are there not two distinct arguments at work here?

If your purpose is only to play against a computer AI, I understand your conclusion.

However, if your purpose is to play against a human opponent and use the computer to 'simulate', or a better term, abstract decisions made at levels lower than the player's direct control level (along with being an aid to administrating the simulation), why would a well-programmed campaign game not be an achievable objective? And thus, why would it not be a reasonable construct within which to generate some plausible historical outcomes?

Most of the points you and others have made in the many threads over the years have been about the plausibility of outcomes of sub-events within the game (or essentially whether the sub-event has been modeled in the best manner). Understandably, the cumulation of implausible sub-event outcomes can lead to implausible end-game results. But in human vs human play at least we do not have the AI problem, which seems intractable with the current state of software and hardware.

[LoBaron]

ORIGINAL: Shark7
Actually a better way of seeing it is that while a computer is capable of coming to a decision based on a number of variables, it is not capable of coming to variable conclusions.

That is the strength that the human mind has over an AI. An AI is only capable of coming to the conclusions it is programmed to come to. Take 100 computers with the same code and same variables, and they will come to the same comclusion...even with the addition of a randomizer, they will still fall into a predictable range. Take 100 humans and present them with a problem, and you will likely come to 100 different methods of arriving at a solution.

Add to that the human mind is capable of 'thinking outside the box'. An AI is very limited to the box it has defined in its code.

AIs may be able to crunch a bunch of numbers and do it a lot faster than you or I, but you and I have the advantage of creativity. [;)]

100 Humans presented with a problem may yield 100 differet methods of arriving at a solution. But theres a simple underlying
reason:
Those humans have 100 different brains, none of them operates the same on a biochemical level, and additionaly they have
100 different sets of, as fcharton said, a posteriori knowledge gathered through different experiences made in their
lifetime.

Comparing this to 100 identical AIs who access an identical dataset is comparing apples to oranges.
A comparision on that level only is valid as long as you compare the capabilities and differences
of one human brain to a single AI. And there the above conclusions would not be possible.

Edit: the a posteriori approach is very intriguing, just because of what was written above. It would
obviousely result in different behaviour of 2 AIs, even if they are identical in their base structure
because they access different datasets.

The complex problem is how to bring an AI to identify data needed to adress a specific task if the dataset
is not present from the beginning. So how do you enable an AI to both, create and categorize new datasets,
and successfully use the available data in a way it makes sense?

[herwin]

After flying from California to England through eight time zones and then sleeping twelve hours, I'm still a bit zonked out. Perhaps that's a good state to be in if I'm to explain what I'm about to non-specialists.

I'm a computational neuroscientist--I try to model how the brain works. I specialise in hearing, but I've always have had a more general interest in how the brain produces behavior, especially planned behavior. To study that question takes a lot of specialised training--computer science, cognitive science, physics, chemistry, biology, neuroscience, psychology, statistics and mathematics--but no more time or brains than many other specialities. It's just a form of expertise, and a lot of people are experts at about the same level in their own fields.

I currently teach in England, but I expect to return to America permanently in a couple of years. I talked to a lot of American researchers this summer, and it seems clear to me that the UK is no longer competitive in neuroscience. The available training is too weak, and research funding has become minimal. So rather than focussing my work on computational hearing, it's time for me to plan further ahead. I want to build a simulation of biological intelligence that behaves like a smart animal. Such a thing would have applications in a lot of areas--speech understanding, autonomous vehicles, and computer games in particular. During the summer I came up with some ideas.

The human brain has between two billion and twenty billion neurons, and ten thousand times as many synapses. Neurons are the active cells in the brain, and synapses are the connections they use to communicate. Modelling that in a computer will be barely feasible in the next ten years, but we won't know how to *program* that model to do anything useful. There is enough known about how the brain works to suspect a model that big isn't required. Your average person uses about thirty thousand concepts to make sense of the world, each of which involves about a half million neurons working together, spread over ten or so regions of the brain. John von Neumann thought the big difference between computers and brains was that computers used a very few inputs at a time and millions of steps to do anything, while brains used many, many inputs at a time and perhaps ten steps to do everything. So if I could come up with some way to program thirty thousand concepts, each with about ten steps, and using thousands to millions of inputs for each, I might possibly model human intelligence.

Walt Freeman has been working on an idea for forty years that extends work done by a famous polymer expert named Aharon Katzir Katchalsky. Katchalsky was killed by terrorists at the Ben Gurion International Airport in 1972 coming home from a conference where he had presented his preliminary ideas, and very few people have taken them anywhere since. (His younger brother became President of Israel in 1973.) Katchalsky suggested brain cells work in cooperative assemblies, not individually, and the assemblies interact both in parallel and in sequence. This idea overcomes the biological noise of neurons and begins to explain how von Neumann's ideas might work.

Freeman has also shown that the brain switches randomly between two phases about forty times a second. One of these phases is 'gaseous', while the other is more liquid, and the alternation is seeded by local changes to the gain of the system.

Gain greater than one is an increasing rate of spiking, while gain less than one is a decreasing rate of spiking. The average game is equal to one, meaning the average rate of spiking is close to constant. Epileptic fits are triggered, BTW, when the gain becomes significantly greater than one. We can think of the brain as experiencing about forty frames a second.

So think of a 'cell assembly' as a collection of ten or more local assemblies, each with about forty thousand neurons. Each local assembly shares neurons with other assemblies, so that concepts have overlap. Each local assembly consists of four sub-assemblies. two excitatory and two inhibitory, that interact to form oscillators, each oscillating about forty times a second. The total number of cell assemblies is greater than thirty thousand because there's a lot of subconscious housekeeping to be done.

Since the subassemblies have about ten thousand neurons, they can be treated statistically, and that's what Katchalsky proposed. Some of the subassemblies form 'blackboards' in various parts of the brain, like the amygdala and hippocampus. Most do specialised but simple tasks. Almost all have large numbers of inputs and outputs. For example, the cerebellum behind the brainstem seems to be specialised to propagate state into the future. About half works with motor actions, but the remaining half seems to be more generalised. Plans involve this sort of propagation. Time is measured and job step timing is controlled by specialised sub-assemblies in the hippocampus.

Cell assemblies come and go. A new cell assembly is learned during sleep. In sleep, experiences are replayed at about twenty times real-time. These experiences include what was sensed, what actions were taken, and the payoffs experienced, and useful cell assemblies come together in hebbian learning driven by the payoffs.

So my idea for a biological AI is one of these models, trained during 'sleep' based on its experiences. The training produces the program. To build such a model, I'm thinking of adapting something called 'Gibbs Sampling'. The model is represented by the states of about a hundred thousand cell assemblies, linked together by causal chains. Each causal chain describes how a given cell assembly evolves based implicitly on the states of other cell assemblies and of the external world. Plans consist of a sequence of moves linked together by job step timing. Certain 'motor' cell assemblies then describe how the model acts. The model program learns what plans work, depending on the state of the game.

Questions?

[tocaff]

[&:]

So technology is just beginning to scratch at the surface of how the brain works and applying it to computing?

It's very interesting but I suspect I'll be long gone before the types of breakthroughs required will occur.

[mdiehl]

That's one way to go. I always wondered if an agent based model with a few simple rules for each agent (ships in a TF, planes in a section) might produce some very interesting and realistic combat resolution results. But it's been decades since I wrote code and nothing at all like the stuff you're writing about.

[herwin]

ORIGINAL: mdiehl

That's one way to go. I always wondered if an agent based model with a few simple rules for each agent (ships in a TF, planes in a section) might produce some very interesting and realistic combat resolution results. But it's been decades since I wrote code and nothing at all like the stuff you're writing about.

I'd like my agents to emerge from the training and not have to be programmed in.