Newgroup: comp.ai.games
From: andrew@cs.uct.ac.za (Andrew Luppnow)
Date: Fri, 2 Dec 1994 10:10:50 +0200 (SAT)
This document proposes an approach to the problem of
designing the AI routines for intelligent computer wargame
opponents. It is hoped that the scheme will allow the
efficient, or at least feasible, implementation of opponents
which are capable of formulating strategy, rather than
behaving predictably according to fixed sets of simple rules.
In the text below, "DMS" is an abbreviation for "decision-
making-system". I use the term very loosely to denote any
programming subsystem which accepts, as input, a "situation"
and which generates, as output, a "response". The DMS may
be a simple neural network, a collection of hard-coded
rules, a set of fuzzy logic rules, a simple lookup table,
or whatever you want it to be! It's most important feature
is that it must be SIMPLE and TRACTABLE - in particular, it
must accept input from a small, finite set of possible
inputs and generate output which belongs in a similarly
small, finite set of possible outputs.
Some time ago I asked myself how a programmer might begin to
implement the AI of a wargame which requires the computer
opponent to develop a sensible military strategy. I
eventually realized that simply feeding a SINGLE decision-
making system with information concerning the position and
status of each friendly and enemy soldier is hopelessly
inefficient - it would be akin to presenting a general with
such information and expecting him to dictate the movement
of each soldier!
But in reality a general doesn't make that type of decision,
and neither does he receive information about the precise
location of each soldier on the battlefield. Instead, he
receives _strategic_ information from his commanders, makes
strategic decisions and presents the chosen strategy to the
commanders. The commanders, in turn, receive _tactical_
information and make tactical decisions based on (1) that
information and (2) the strategy provided by the general.
And so the process continues until, at the very bottom level,
each soldier receives precise orders about what he and his
immediate comrades are expected to accomplish.
The important point is that the whole process can be envisaged
in terms of several 'levels'. Each level receives information
>from the level immediately below it, 'summarises' or
'generalises' that information and presents the result to
the level immediately above it. In return, it receives a set
of objectives from the level above it and uses (1) this set
of objectives and (2) the information from the lower level
to compute a more precise set of objectives. This latter
set of objectives then becomes the 'input from above' of the
next lower level, and so on. In summary: information filters
UP through the levels, becoming progressively more general,
while commands and objectives filter DOWN through the levels,
becoming progressively more detailed and precise.
I decided that this paradigm might represent a good conceptual
model for the implementation of the AI procedures in a
complex strategy-based game: a "tree of DMS's" can be used to
mimic the chain of command in a military hierarchy.
Specifically, one might use one or more small, relatively simple
DMS's for each level. The inputs for a DMS of level 'k' would
be the outputs of a level (k+1) DMS and the information
obtained by 'summarising' level (k-1) information. The outputs
of the level k DMS would, in turn, serve as inputs for one or
more level (k-1) DMS's. Outputs of the level zero DMS's would
be used to update the battlefield.
"Top brass" - fewer,
MORE GENERAL options
allow lookahead and
Level 3 ^ o "what-if reasoning."
/|\ / \
Level 2 / | \ o o
| /|\ |\
Level 1 | o o o o o
\ | / /| | | | |\
Level 0 \|/ o o o o o o o Individual soldiers -
V many options, but
decision-making is
As information simple and doesn't
filters UP the attempt "lookahead",
tree, it becomes "what-if reasoning",
more general. As etc.
objectives filter
DOWN the tree,
they become more
specific.
The main advantage of this scheme is that it allows the "higher
levels" of the hierarchy to formulate strategy, without being
overwhelmed by the immense and intractably large number of
possibilities which the computer AI would have to consider if
it possessed only information about individual soldiers.
Indeed, at the topmost level, decisions would involve rather
abstract options such as
- "direct all military activity towards seizing territory X",
or
- "conduct wars of attrition in territories X, Y, and Z",
or
- "buy time - stick to diplomacy for the time being",
or
- "avoid direct military engagement - concentrate on disrupting
enemy supply routes",
etc.
Under these circumstances, it would be feasible for the computer
to attempt a certain amount of "lookahead", or to consider
"what-if" scenarios - something which would be out of the
question if options were presented in terms of the actions of
individual soldiers.
At the time of writing this, I haven't yet had the opportunity
to explore an implementation of these ideas in a working game,
but if anybody DOES enjoy some practical success with these
ideas, I'd be interested in hearing from him/her!
--- Andrew LuppnowAddendum: Mark Everson is using some of these ideas in his game, The Clash of Civilizations[1].