Why Programming a Campaign Game is Very Hard

[herwin]

John von Neumann, one of the inventors of Game Theory, discussed this in his 1956 book, the Computer and the Brain. He was considering the difference between biological intelligence and the computer and pointed out that while brains could get by with low accuracy, computers needed very accurate floating point and integer representations. Brains generate their outputs in a small number of steps, using very large numbers of inputs, so round-off error was not a problem for them. On the other hand, computer codes generate their outputs using hundreds or thousands of sequential steps, each of which has to be very exact or else round-off and other arithmetic error quickly overwhelms data with noise.

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 implication is that programming a campaign game without some mechanism to keep the numbers meaningful is an impossible task. A couple hundred turns into the campaign, the numbers have drifted into noise unless we do something to keep them historically reasonable on a turn-by-turn basis. And everything has to be kept reasonable--anything not sanity checked will drift into insanity.

[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. [;)]

[herwin]

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. [;)]

Right. A biological AI relies on the thing modelled being lawful and causal--to make sense. Numbers in a computer are just numbers--there's nothing forcing them to make sense.

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

[mdiehl]

Harry Erwin, that initial post of yours was very, very interesting. A breath of fresh air. Thanks for that.

[fcharton]

Hi Harry,

I think you have to make a difference between two extreme forms of "error": bias and noise. Over time, biases accumulate, like a ship following an incorrect bearing. Noise, on the contrary will tend to cancel out (a bit like someone driving a car, steering left and right, and remaining on the road). In presence of noise, the laws of statistics even tell us that the more turns you have, the less noise you get.

In reality, you have both bias and noise.To perform "long term", an process must be low on bias, and avoid amplifying noise as it runs.

This is true for the human brain as well. Creating and reinforcing biases is exactly what deception and PsyOps are about (and probably a good definition of madness, too). Also, I suspect most of the "cyclic" theories of warfare (OODA and the like) use the fact that a shorter/faster decision process allows for better cancellation of noise.

As for computers, the whole point, which was not understood in Von Neumann's time, is that some (not all) laws of mathematics do not hold in presence of error. Some simple calculations will amplify errors, and some formulae will not behave nicely when dealt with approximately. Fortunately, there are methods around this. In fact, this is pretty much the subject matter of applied mathematics.

The brain probably does this naturally. Machines can do it as well, but the maths behind it are a little more involved than high school stuff.

Francois

[herwin]

ORIGINAL: fcharton

Hi Harry,

I think you have to make a difference between two extreme forms of "error": bias and noise. Over time, biases accumulate, like a ship following an incorrect bearing. Noise, on the contrary will tend to cancel out (a bit like someone driving a car, steering left and right, and remaining on the road). In presence of noise, the laws of statistics even tell us that the more turns you have, the less noise you get.

In reality, you have both bias and noise.To perform "long term", an process must be low on bias, and avoid amplifying noise as it runs.

This is true for the human brain as well. Creating and reinforcing biases is exactly what deception and PsyOps are about (and probably a good definition of madness, too). Also, I suspect most of the "cyclic" theories of warfare (OODA and the like) use the fact that a shorter/faster decision process allows for better cancellation of noise.

As for computers, the whole point, which was not understood in Von Neumann's time, is that some (not all) laws of mathematics do not hold in presence of error. Some simple calculations will amplify errors, and some formulae will not behave nicely when dealt with approximately. Fortunately, there are methods around this. In fact, this is pretty much the subject matter of applied mathematics.

The brain probably does this naturally. Machines can do it as well, but the maths behind it are a little more involved than high school stuff.

Francois

I always read your posts carefully.

A lot of my coursework in computational science was numerical analysis, and you're very right. The brain doesn't get hung up with these issues because it relies on the universe being lawful and the laws being simple. Gibbs sampling models that, and that's the idea I'm exploring in my current research.

Meanwhile I've been convinced by von Neumann's argument that trying to replicate history in WitP-AE is a fool's errand, and I'm just going to have fun from here out. [:)]

[tocaff]

..."I'm just going to have fun from here out."

Well isn't having fun what gaming is all about? If we don't enjoy playing a game for, whatever reason, we stop and find something else to amuse ourselves with.

[LoBaron]

ORIGINAL: herwin
--there's nothing forcing them to make sense.

How could you implement an aequivalent to the human basic instincts into an AI? Major question IMHO.

[vettim89]

The human brain on the cellular level has systems of incredible complexity. At the point where neural cells communicate with each other there are bichemical sytems for intecellular communication but also have numerous modulating chemicals that affect how the cells interact. Therefore there is a set of checks and balances in place not at the conscious level nor at the subconscious level but at the cellular level. The human brain has systems in place to filter out inpulses that fall beyond the expected levels at the most rudimentary level. Computers at this time have no way to have this level of system control.

Even Big Blue with its ability to beat World Grandmasters at chess does so with a matrix consisting of only 64 possible locations for 32 possible pieces. Those 32 possible pieces are further limited as to how they can move. So a computer far beyond the capabilites of your average PC can master a games with far fewer possible moves than the most basic of war games. My point being that computer processing is no where near the point where it would need to be to truly challenge a human mind at a more complex game. Unforunately, many programmers, realizing this conundrum, use AI cheats to compensate for the sortfall (even in AE)

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

[fcharton]

ORIGINAL: vettim89
So a computer far beyond the capabilites of your average PC can master a games with far fewer possible moves than the most basic of war games. My point being that computer processing is no where near the point where it would need to be to truly challenge a human mind at a more complex game.

Number of possible moves is only relevant if one attempts to find a brute force solution. This is desirable for games like chess, where the rules are simple enough to warrant searchable solution spaces, and where the importance of tactics make detailed calculations a necessity.

Wargames, like AE, are not the same. Granted, there are lots of parameters, but their effects tend to average out, and you don't need to micromanage every detail to be efficient (the engine does a good job at handling all this).

In my opinion, the complexity of the game system actually makes it possible to devise a very good AI. Since the engine works as a "black box", and is very complex, players learn the ropes very slowly, and seldom bother to try to achieve perfect management of their turn (because the game is so large). On the other hand, the AI designer knows the inner working of the engine, and the AI is not afraid to tackle lots of boring calculations.

I think a better AI could be developped by analysing the game system (mathematically or statistically), and deriving "best practices" (maybe computationally intensive), that could be programmed into the AI, making its tactical decisions almost perfect. Understanding the inner working of the system could also help the AI better evaluate a global position, which would go a long way towards a better strategic insight. And then, scripts could do the rest (there are not so many possible overall strategies).

Such an AI would probably not be perfect, but I believe it would beat most newbies and give a lot of trouble to seasoned players. Just think of the number of times you've discovered something very important in the game you didn't know, and the advantage the AI could derive from knowing all that...

But then, programming such an AI would probably be as difficult as programming the game, and imply quite a bit of specialized knowledge (including statistics and game theory). Knowing that most good players play PBEM, I think it is just not worth the effort.

Francois

[dorjun driver]

Scenario 666: Weizenbaum vs Minsky!

[zzodr]

One thing i've learnt from computer games: Computers cheat.
But I can always reload my save game. [;)]

[zzodr]

One thing i've learnt from computer games: Computers cheat.
But I can always reload my save game. [;)]

[dorjun driver]

Well put.

[LoBaron]

ORIGINAL: fcharton
In my opinion, the complexity of the game system actually makes it possible to devise a very good AI. Since the engine works as a "black box", and is very complex, players learn the ropes very slowly, and seldom bother to try to achieve perfect management of their turn (because the game is so large). On the other hand, the AI designer knows the inner working of the engine, and the AI is not afraid to tackle lots of boring calculations.

I think a better AI could be developped by analysing the game system (mathematically or statistically), and deriving "best practices" (maybe computationally intensive), that could be programmed into the AI, making its tactical decisions almost perfect. Understanding the inner working of the system could also help the AI better evaluate a global position, which would go a long way towards a better strategic insight. And then, scripts could do the rest (there are not so many possible overall strategies).

Such an AI would probably not be perfect, but I believe it would beat most newbies and give a lot of trouble to seasoned players. Just think of the number of times you've discovered something very important in the game you didn't know, and the advantage the AI could derive from knowing all that...

But then, programming such an AI would probably be as difficult as programming the game, and imply quite a bit of specialized knowledge (including statistics and game theory). Knowing that most good players play PBEM, I think it is just not worth the effort.

Francois

The problem faced by an AI is that it needs to rely on information present, not absent.
As long as an AI has sifficient data on a certain situation it probably is able to handle threat assessment
better than the human brain. But the basic ingredients of laying traps or creating deception is based
on interpreting or creating loads of non values. I wonder how an AI would be able to compete here.

Even if an AI is able to create the perfect tactical setup for a specific situation based on a broad spectrum
of available data, this setup might be far from perfect taking absence of/irrelevant/purposefully incorrect
data into account. What could enable an AI to cope with this?

[alesha93]

The other challenge will always be how to enable the AI to model irrational human behavior. Part of the fun of playing against humans is that they are sometimes/often irrational in their behavior. That irrational play or randomness is sometimes just that or is often part of a tactical setup in order to force their opponent to do something even more irrational in response (thus gaining a tactical or strategic advantage for the person who moved first).

The AI is going to behave logically - that's why it's so hard to beat a PC program at chess. With enough interaction human players will almost always figure out these logical processes and determine methods to get around them and defeat them. I think we are a long way away from having an AI that can truly compete with the human mind; however, it will be fascinating to watch as the AI improves as its logical behavior becomes more difficult to recognize and/or a degree or randomness or irrational behavior is introduced.

[fcharton]

Hi LoBaron,

re deception, keep in mind that it is irrelevant whether the AI really plans traps, or creates deception. What counts is that the human opponent feels he's been trapped, or deceived. Whereas complex PsyOps are probably out of reach, many aspects of deception can be programmed. This includes :

- prepping for a likely target to deceive enemy SigInt
- while planning an offensive, create a number of decoys, for other likely targets. If the human detect the decoys first, the impression of deception will be perfect.
- adding some randomness to reaction : say, once an airfield is bombed, instead of rushing the fighters in, allow for some random delay
- adding some randomness to TF paths (possibility to double back at times, and all that).

Once again, it is a lot of work, but most of the deception schemes I see in AAR seem quite amenable to programming.

Even if an AI is able to create the perfect tactical setup for a specific situation based on a broad spectrum
of available data, this setup might be far from perfect taking absence of/irrelevant/purposefully incorrect
data into account. What could enable an AI to cope with this?

A very good point. 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).


@oreskovich: this is an important point. A reason why lots of AI fail is that they become predictable. A good AI need to randomize its actions: instead of selecting and implementing one "best move", you select several good moves, and draw one at random...

Francois

[herwin]

I'm on my trip back to the UK. Last night I was thinking about how I would design an approach to WitP that would lend itself to AI and not go off the rails due to the problem with noise growing over hundreds of moves.

The first thing that struck me was use a strategic segment once a quarter. For example, Japan made three strategic decisions prior to going to war:

1. South instead of North. That caused the resources for the southern strategy to be released and the necessary ground forces were released from a restricted command to the Southern Army. French Indochina became Japanese-controlled. It also gave the Allies the option of embargoing Japan, cutting off resource and oil movement from the DEI to Japan.
2. Take on America rather than only the Commonwealth and the DEI. That brought forward the start of war between America and Japan probably by a quarter. There may have been effects on warship production and a release of fuel to the navy.
3. East rather than West. That added six months to the end of the war and increased American naval production.

Other decisions were about what ships to build, whether to escort commerce or prepare for the great battle, whether to concentrate on naval air or naval surface forces, etc.

PPs become much less important if this is done.