Citation
LG hypergames for real-world defense systems

Material Information

Title:
LG hypergames for real-world defense systems
Creator:
Umanskiy, Oleg Y
Publication Date:
Language:
English
Physical Description:
95 leaves : ; 28 cm

Subjects

Subjects / Keywords:
War games -- Mathematical models ( lcsh )
War games -- Computer simulation ( lcsh )
Computer war games ( lcsh )
Computer war games ( fast )
War games -- Computer simulation ( fast )
War games -- Mathematical models ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 93-95).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Oleg Y. Umanskiy.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
49630746 ( OCLC )
ocm49630746
Classification:
LD1190.E52 2001m .U52 ( lcc )

Full Text
LG HYPERGAMES FOR
REAL-WORLD DEFENSE SYSTEMS
Oleg Y. Umanskiy
B.S., University of Colorado, 2000
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
by
2001


2001 by Oleg Y. Umanskiy
All rights reserved.


This thesis for the Master of Science
degree by
Oleg Y. Umanskiy
has been approved
by
Dianne Kumar
Date


Umanskiy, Oleg Y. (M.S., Computer Science)
LG Hypergames for Real-World Defense Systems
Thesis Directed by Professor Boris Stilman
ABSTRACT
The subject of this thesis is application of the Linguistic Geometry (LG) approach to
real-world Defense Systems. Due to their nature, these problems usually need to be
modeled employing large scale, multi-dimensional games, with totally concurrent
movement of a large number of various game agents. Such complex systems are not
tractable by conventional methods due to the exponential growth of search trees. LG
techniques provide a way to decompose these systems into hierarchies of dynamic
subsystems by employing a Hierarchy of Formal Languages. LG approach
dramatically reduces the complexity of the problems and allows for satisfactory
solutions to be found.
The class of problems that can be addressed by these methods is formally defined as
abstract board games (ABGs). Mapping real-world Defense Systems to ABGs is of
particular interest due to the inherent variety of complex behavior. Introduction of
hypergames further extends this approach by modeling simultaneous tightly
interconnected systems using inter-linking mappings (ILMs). In addition, the
software framework concepts presented in this thesis demonstrate how such
representations and LG tools can be implemented. Consequently, Linguistic
Geometry approach employing hypergames is a viable method for modeling and
constructing strategies for real-world Defense Systems.
IV


ACKNOWLEDGEMENT
I would like to thank my thesis advisor Professor Boris Stilman for guidance in my
scientific endeavors. Also, I would like to thank the committee members Professors
Altman, Cios, and Kumar for their assistance and participation. This thesis is based
on the extensive R&D conducted at STILMAN Advanced Strategies (STILMAN). I
would like to use this opportunity to thank STILMANs management for allowing me
to use some of their proprietary information and software in my M.S. thesis research.


CONTENTS
Figures...........................................................viii
Tables..............................................................ix
Chapter
1. Introduction.....................................................1
1.1. Games for Real-World Defense Systems............................1
1.2. Current Gaming Approaches.......................................2
1.3. Imitating Human Approach........................................4
1.4. Linguistic Geometry Hypergame Approach..........................5
2. Linguistic Geometry Approach to Complex Systems..................7
2.1. Abstract Board Games............................................7
2.2. Hierarchy of Formal Languages..................................13
2.2.1. Language ofTrajectories......................................13
2.2.2. Language of Zones............................................21
2.3. LG Strategies..................................................28
2.4. LG Areas of Applicability......................................28
3. ABGs for Real-World Problems....................................30
3.1. Discretization of Continuous Systems...........................30
3.2. Spatial Discretization.........................................31
3.2.1. 2D Game Boards...............................................31
3.2.1.1. Rectangular Grids..........................................32
3.2.1.2. Hexagonal Grids............................................33
3.2.1.3. Phase Spaces...............................................34
3.2.2. 3D Game Boards...............................................35
3.2.3. Spherical Boards.............................................36
3.3. Temporal Discretization......................................38
3.4. Game Agents....................................................39
3.4.1. Movement.....................................................39
3.4.2. Attack.......................................................40
3.4.3. Miscellaneous Behavior.......................................42
4. LG Hypergames...................................................46
4.1. Motivation.....................................................46
4.2. From ABGs to Hypergames........................................47
4.3. Common Inter-Linking Mappings..................................49
vi


4.4. Benefits of Hypergames...................................50
5. LG Hypergame Framework Specifications......................52
5.1. Conceptual Modules.......................................53
5.2. Software Framework.......................................54
5.3. Using the Framework......................................58
6. Future Work................................................60
7. Conclusion.................................................61
Appendix
A. LG Hypergame Framework Classes.............................62
Bibliography..................................................92
vii


FIGURES
Figure
1.1 Comparison of searches for the same processing time.......................5
2.1 Hierarchy of Formal Languages in LG.......................................7
2.2 TRANSITION^,x,y).........................................................9
2.3 Bundle of trajectories..................................................14
2.4 Interpretation of the algorithm for next* for the grammar Gt(1).........16
2.5 Values of MAPgg^........................................................17
2.6 Values of MAP36p........................................................17
2.7 SUM...................................................................18
2.8 ST! (88)................................................................18
2.9 ST!(78).................................................................19
2.10 ST2(88)................................................................19
2.11 ST 1(68)...............................................................19
2.12 ST3(88)................................................................19
2.13 STi(57)................................................................20
2.14 ST4(88)................................................................20
2.15 ST}(47)................................................................20
2.16ST5(88).................................................................20
2.17 LG zone for TC system with strikes.....................................22
2.18 Various types of LG zones..............................................24
3.1 Concentric circles on rectangular grid...................................33
3.2 Hexagonal grid enumeration schemes......................................34
3.3 Directions with respect to a hex grid...................................35
3.4 3D cell: hexagonal prism................................................36
3.5 Reachability based on turning radius....................................40
3.6 Strikability with obstacles.............................................41
3.7 Bundles of shortest trajectories........................................43
3.8 Incomplete/false information............................................45
5.1 Conceptual framework.....................................................53
5.2 LG Hypergame classes framework..........................................55
vm


TABLES
Table
2.1 ABG definition................................................................8
2.2 ABG definition for the game of chess.........................................11
2.3 ABG definition for combat simulations........................................12
2.4 Grammar of shortest trajectories GtO)........................................15
2.5 Grammar of Zones Gz..........................................................26
2.6 LG areas of applicability....................................................29
IX


1. Introduction
1.1. Games for Real-World Defense Systems
When thinking about modem or future military operations, the game metaphor comes
to mind right away. Indeed, the aerospace, together with the ground and seas, may be
viewed as a gigantic three-dimensional game board. The groups of ships, aircraft, and
tanks performing a single task may be viewed as friendly pieces, whereas the enemy
manned and unmanned vehicles together with the stationary ground/sea-based targets
may be viewed as the opponents pieces. The mission commanders on various levels
have a place in this picture as game players. Generalizing this picture, we may
envision several concurrent interconnected games of various kinds: military
(including Navy Ops), logistics, economic, political, etc. In order for this
representation to be useful for real-world Defense Systems, we need efficient
algorithms finding the best game strategies.
A game strategy describes behavior in terms of moves. A move represents the
smallest activity of pieces discemable from the game point of view. It may include
physical motion of pieces as well as their actions such as employment of weapons,
refueling, or leadership change (in a political game). A move can be associated with a
time interval. Depending on the task level (tactical, operational, or strategic) the
interval could be measured in seconds, minutes, hours, or days. A strategy may offer
a significant look ahead so that various intended or unintended consequences of
immediate actions could be seen.
A significant characteristic of Defense Systems is developing game strategies that do
not exclude a human commander out of the loop. Indeed, whatever problems would
be solved by future military operations, they are eventually human problems and, as
such, they may not be completely solvable by a machine. Instead of replacing the
operator, the goal of game strategies is to help the mission commanders and
individual combatants to conduct and monitor the operations with less effort and with
greater chance of success.
Without an ability to find winning strategies, games and computer simulations would
serve mostly as displays of the situation, rather than models from which solutions
could be derived. The purpose of Linguistic Geometry hypergame approach,
presented in this thesis, is to find such strategies.
1


1.2. Current Gaming Approaches
To be successful in providing solutions to defense-related projects, we have to
overcome two major technical barriers. The first barrier is related to adequate
representation of an active intelligent adversary capable of asymmetric responses.
The second barrier is the so-called curse of dimension, which makes all the
theoretical constructions impractical. Both barriers have been attacked in the past.
The only theoretical approach that allows introduction of the full-scale intelligent
adversary is the gaming approach (Von Neumann and Morgenstem, 1947).
Game-based approaches have frequently been applied to military command and
control (C2). The games used by many game-based approaches are continuous and
discrete, strategic and extensive.
Continuous games are usually described mathematically in the form of pursuit-
evasion differential games. The classic approach based on the conventional theory of
differential games (Isaacs, 1965) is insufficient, especially in case of dynamic, multi-
agent models (Lirov, Rodin et al, 1988; Garcia-Ortiz et al., 1993). It is well known
that there exist a small number of differential games for which exact analytical
solutions are available. There are a few more differential games for which numerical
solutions can be computed in a reasonable amount of time, albeit under rather
restrictive conditions. However, each of these games must be one-to-one, which is
very far from the real world combat scenarios. They are also of the zero-sum type
which does not allow the enemy to have goals other than diametrically opposing to
those of the friend. Other difficulties arise from the requirements of the 3D modeling,
limitation of the lifetime of the agents, or simultaneous participation of the
heterogeneous agents such as on-surface and aerospace vehicles.
Discrete strategic games were introduced and investigated by (Von Neumann and
Morgenstem, 1947; Osbom and Rubinstein, 1994) half a century ago and later
developed by multiple followers. This approach allows analyzing full game strategies,
representing entire games. It does not allow breaking a game into separate moves and
comparing them. Only full strategies, the entire courses of behavior of players can be
compared. Each player chooses his/her plan of action once and for all and is not
informed about of the plan chosen by another player. This significant limitation
makes this approach inadequate for real world C2 problems.
2


For both types of games, discrete and differential, advanced theoretical results have
been obtained. However, these advanced theories lack scalability.
Discrete extensive games specify the possible orders of events; each player can
consider his/her plan of action not only at the beginning of the game but also
whenever he/she has to make a decision (Osborn and Rubinstein, 1994). Extended
games are usually represented as trees, which include every alternative move of every
strategy of every player. Application of this class of games to real world problems
requires discretization of the domain, which can be done with various levels of
granularity. In addition, in the real world problems, moves of all the pieces (aircraft,
tanks) and players (Red and Blue) are concurrent, and this can be represented within
extensive (not strategic) games. Thus, the extended games would allow us to
adequately represent numerous problem domains including military C2. However, the
classic game theory considers real extensive games (like chess) trivial for rational
players because an algorithm exists that can be used to solve the game (Osborn and
Rubinstein, 1994). This algorithm defines a pair of strategies, one for each player,
that leads to an equilibrium outcome: a player who follows his/her strategy can be
sure that the outcome will be at least as good as the equilibrium no matter what
strategy the other player uses. Classic theory of extensive games is not interested in
the actual tractability of this algorithm, which makes it irrelevant to our project.
Practical gaming approaches try to solve games by searching through the game tree.
The main difficulty for any practical gaming approach is scalability, i.e., the curse of
dimension. Even for a small-scale combat, an extensive game would be represented
by a game tree of astronomic size, which makes this game intractable employing
conventional approaches.
Consider, for example, a small concurrent game with 10 pieces total so that each can
make 10 distinct moves at a time. If the game lasts for at least 50 moves (not unusual
for battlefield examples), the size of the game tree would be about (1010)50 = 10500
nodes. To be more specific, the JEC (JFACC Experiment Commander) Game for
Suppression of Enemy Air Defenses developed for Joint Force Air Component
Commander (Lee at al., 2001) includes 30 mobile pieces with 18 moves each, while
the game lasts 70 moves.
No computer can search such trees in a lifetime. Even the most presently promising
search algorithms on the game trees, those that utilize alpha-beta pruning, would
result in insufficient search reduction. Even in the best case, the number of moves to
be searched employing alpha-beta algorithms grows exponentially with the power of
this exponent divided by two with respect to the original game tree (Knuth and
Moore, 1975). In the above example the reduced tree would have 10250 nodes, which
is just as impossible to search as the unreduced tree. Moreover, the alpha-beta
3


pruning method is applicable to sequential alternating games only (Blue-Red-Blue-
...) with one-entity-at-a-time movement, whereas most of the real world games,
including military operations are concurrent. For the games with concurrent actions
the number of moves to be searched explodes more dramatically than for the
sequential games. This is because all the possible combinations of moves for different
pieces can be included in one concurrent move. With conventional non-LG
approaches, the question of practical solvability of extensive concurrent games could
not even be raised.
1.3. Imitating Human Approach
The computers can compute several orders of magnitude faster than humans.
However, there is wide variety of real-world complex systems for which a human
expert can outperform any computing system. This is due to the fact that people apply
different methods to problem solving than traditional computing methods. Since the
main strength of computers is fast computation, it seems natural to take advantage of
it by computing and considering every possible combination of moves in the system.
However, as stated above, even for fairly simple real-world problems, exponential
explosion of combinations prevents any perceivable computer from searching them to
a necessary depth in reasonable amount of time. The human approach is to avoid
searching all possible combinations. Instead, a human expert only considers one or
two possible moves for a position. Since the branching factor is small, the depth of
the variations considered can be considerably larger. Therefore, a slower human
can consider strategy much further ahead than a faster computer, due to ignoring
most of the possibilities as not beneficial.
4


Figure 1.1 Comparison of searches for the same processing time
One of the most important skills that a human expert in a particular field possesses is
an ability to break the problem into sub-problems. These smaller sub-problems can be
solved and the solutions reconstituted into a solution for the original problems. While
original problem may have been intractable, sub-problems may be solvable due to
smaller dimension. There are several difficulties with emulating this human expert
behavior. First, the system must be broken into sub-systems. For real-world problems,
this decomposition usually cannot produce completely independent sub-systems.
Therefore, solving smaller sub-problems must take into account the effects of the
partial interactions with the other sub-problems (thus hindering the benefit of
dimension reduction). Consequently, the goal is to produce decompositions with the
least dependence between parts. On the other hand, the decomposition should
produce sub-systems such that their solutions can be reconstructed into approximately
optimal solution for the entire system. Another issue is to determine which parts of
the state changes during a state transition. We should avoid recomputing the entire
system state; therefore, we need to be able to determine effectively what must change.
There is no general solution due to interconnection between facts in the particular
problem.
This process of decomposition usually can be performed by an expert in the particular
field; however, this expertise is not easily transferable into a different problem
domain. We may have heuristics, which allow us to successfully decompose a
particular problem. However, a new problem must be carefully studied and previous
experience is usually not readily applicable. We do not yet posses the full ability to
formally describe the principles of human heuristics, which produced a successful
hierarchy for a particular problem, and then transfer that knowledge to a different
problem domain. Another goal of formalizing human heuristic knowledge is to pass
the knowledge of experts in one field, to a field where less expertise is available so
far (new problem domains).
1.4. Linguistic Geometry Hypergame Approach
Linguistic Geometry (LG) is an approach to construction of formal mathematical
models for knowledge representation and reasoning about large-scale multiagent
systems. A wide variety of real-world systems can be modeled as abstract board
games (ABGs). LG dramatically reduces the size of the search trees, thus making the
problems computationally tractable. LG provides a formalization and abstraction of
search heuristics of advanced experts. The formalized expert strategies yield efficient
algorithms for problem settings whose dimensions may be significantly greater than
the ones for which the experts developed their strategies. Moreover, these formal
5


strategies allow solving problems from different problem domains far beyond the
areas envisioned by the experts. Since both the theory of formal languages, as well as
certain geometric structures over the abstract board, are used to formalize the
heuristics, this approach was named Linguistic Geometry (Stilman, 2000a).
While originally LG was developed by formalizing chess-playing expertise of grand
masters, it has since been expanded to a wide range of problem domains, such as real-
world Defense Systems. One of the fascinating aspects is that methods developed for
an 8x8, 2-demensional board game with alternating piece movement, have been
transferred over to real-world, large scale, multi-dimensional games, with totally
concurrent movement of various game agents.
One of the extensions of the theory presented in this thesis is introduction of
hypergames a system of interconnected ABGs. This approach helps overcome some
of the inherent difficulties of the real-world Defense Systems, such as representing
the system using a discrete model. In addition, hypergames allow modeling of related
Defense Systems for maintaining inter-game effects.
A thorough discussion of the Linguistic Geometry theory is presented in (Stilman,
2000a). Chapter 2 of this thesis presents the foundations and the main principles of
this theory, while the subsequent chapters demonstrate how this theory can be
expanded and adapted to complex real-world Defense Systems. Chapter 3
demonstrates the process of mapping such systems to abstract board games (class of
systems that LG is designed to solve). Chapter 4 expands this approach to
hypergames, which allow better representation of real-world systems, as well as
solving more complex problems. Chapter 5 presents specifications of a thorough
software framework for implementing and solving such systems using LG
hypergames.
6


2. Linguistic Geometry Approach to Complex Systems
The purpose of Linguistic Geometry is to develop a formal approach to a certain class
of multiagent systems that involves breaking down a system into a hierarchy of
dynamic subsystems. The methods of LG are formalized as a Hierarchy of Formal
Languages used to solve certain classes of problems. The languages in the hierarchy
are used to generate hierarchy of structures: trajectories, zones, translations, searches,
etc. The class of problems that is addressed by these techniques is formally defined as
Complex Systems or abstract board games. The LG method generates a tree of
translations which is a string in the Language of Translations. In order to do so
several strings of the Language of Zones or Webs are generated. In turn, those strings
contain strings of the Language of Trajectories. Together, the hierarchy creates
decomposition of dynamic subsystems, which is used to solve the problem. (Stilman,
2000a).
2.1. Abstract Board Games
Before the Hierarchy of Formal Languages at the heart of LG can be applied to a
problem, it needs to be represented as an abstract board game. This provides
formalization for a large class of problem domains. As a result, LG methods can be
easily and directly applied to any system that can be represented in this form. The
formal definition of ABGs is shown below. Following this definition, two examples
Figure 2.1 Hierarchy of Formal Languages in LG
7


are presented to demonstrate the relationship between an ABG and a problem it
represents.
Abstract board game is the following eight-tuple:
< X, P, Rp, SPACE, val, Sj, St, TR>
Table 2.1 ABG definition
x = {Xi} A finite set of points, locations of elements
p=(Pi) A finite set of elements, P is a union of two disjoint subsets Pi and P2 called the opposing sides
Rp(x, y) A set of binary relations of reachability in X (x and y are from X, p is from P);
Val A function on P with positive integer values describing the values of elements
SPACE The state space. A state S e SPACE consists of the list of formulas, which employ a partial function of placement ON:P-X and additional parameters. The value ON(p) = x means that element p occupies location x at state S. Thus, to describe function ON at state S, we write equalities ON(p) = x for all elements p, which are present at S. We use the same symbol ON for each such partial function, though the interpretation of ON may be different at different states. Every state S from SPACE is described by a list of formulas {ON(pj) = x*} in the language of the first order predicate calculus, which matches with each relation a certain Well-Formed Formula (WFF).
Sj and St The sets of start and target states. Thus, each state from S, and St is described by a certain list of WFF (ON(pj) = x*}. St is a union of three disjoint subsets St', St2, and St3. St1, St2 are the subsets of target states for the opposing sides Pi and P2, respectively. St3 is the subset of target draw states.
TR A set of transitions, TRANSITION^, x, y), of the System from one state to another (Fig. 2.2). These transitions are described in terms of the lists of WFF (to be removed from and added to the description of the state) and a list of WFF of applicability of the transition. These three lists for state S e SPACE are as follows Applicability list: (ON(p) = x) n Rp(x,y); Remove list: ON(p) = x;
8


Figure 2.2 TRANSITION^,y)
Note, that this generic definition can be expanded for a particular class of Complex
Systems. Additional parameters of a state may be added. In addition to the data
described above, a state of an alternating Complex System includes a binary function
MT(S) e {1, 2}, a move turn to distinguish between the states when player 1 or 2 is
allowed to move. A state of a Complex System with variable speed includes function
of speed sp. Other information may be included based on system requirements.
The transitions TR above may also be more complex. Transitions may be of several
types. A simple move transition occurs when element p moves from x to y without
removing an opposing element. In this case, point y is not occupied by an opposing
element. A remove transition occurs if element p moves from x to y and does
remove an opposing element q, i.e., OPPOSE(p, q) holds. For alternating serial
systems, the opposing element q has to be at location y before the move of p has
commenced. In this case, the Applicability list and the Remove list include
additional formula ON(q) = y. For concurrent systems, this is not necessary: element
q may arrive at y simultaneously with p and be removed. These transitions are
governed by the reachability relationship Rp(x, y).
Further constraints can be imposed on the members of TR. In case of an alternating
Complex System (see, definition of SPACE above), if the move turn MT(S) = i, then
only elements p from Pj (from Pj or P2, respectively) can participate in the transition.
9


Additional constraints may be introduced based on a particular class of system (e.g.
systems in which no two game pieces can occupy the same location).
For real-world systems (especially Defense Systems), another type of transitions is
common a strike transition. For this class of systems, another element is
introduced into the eight-tuple above binary relations of strikability Strkp(x,y),
which is analogous to relations of reachability. Strike transition occurs when an
opposing element q is removed at a location different from y. This reflects a common
situation, where a piece can destroy an opposing piece located at a different position
on the board by shooting. In this case, Remove List may include additional formulas
ON(qi) = zi, ON(q2)=Z2, etc for all locations Zj that are considered strikable from
location y (i.e. Strkp(y,z;) holds true). Chapter 3 contains more information on
mapping real-world Defense Systems to ABGs.
In a Complex System, the goal of each side is to reach either one of its winning states
(a state in subsets St' or St2, respectively), or, if impossible, a draw state from St3. The
problem of the optimal operation of the System is considered as a problem of search
for a sequence of transitions leading from the Start State of Si to a target state of St
assuming that each side makes only the best moves, i.e., such moves (transitions) that
could lead the Complex System to the respective subset of target states. To solve a
Complex System means to find a strategy (an algorithm to select moves) for one side,
if it exists, that guarantees that the proper subset of target states, St, St, or St, will be
reached assuming that the other side makes arbitrary moves.
As mentioned above, a wide range of classes of complex systems is possible. These
can be categorized into 3 general classes: Alternating Serial, Alternating Concurrent,
and Totally Concurrent systems. In Alternating Serial (AS) systems, the opposing
sides alternate turns and only one element at a time can be moved. In Alternating
Concurrent (AC) systems, the opposing sides alternate turns; however, all, some, or
none of the current players elements can be moved simultaneously. In a Totally
Concurrent (TC) systems, players do not alternate and all, some, or none of the pieces
of both sides can be moved simultaneously. It is important to note, that in general the
level of difficulty increases from AS to AC to TC due to the need to consider all
possible combinations of moves. For instance, consider a game of 5 pieces against 5
opposing pieces, where each piece can make any one of 10 moves. Then, AS
branching factor is 10, AC branching factor is 105, and TC branching factor is
105+5=10 . Due to the nature of real-world Defense Systems, they usually need to be
modeled as Totally Concurrent systems.
10


To further illustrate, the relationship between a problem and an ABG, two examples
are presented below outlining the definitions of the eight-tuple for game of chess and
generic combat simulation.
Table 2.2 ABG definition for the game of chess
X = {xj} 64 squares on the chess board
P = (Pi) White and black pieces
Rp(x, y) Reachability is defined by the rules of chess. I.e. Rp(x,y) is true if and only if a piece p is allowed to move from x to y according to the rules of chess. For example, if p is a king, Rp(x,y) is true iff y is one of the immediate neighbors of x on the chess board.
Val Val{p) is the value of a piece. E.g. Fa/(Pawn)=l, Fu/(B)=3, Fa/(K)=500, etc.
SPACE ON(p)=x, iff piece p stands on square x MT(S)=White or Black active player
Sj and St Sj is the traditional chess start state or an arbitrary position that is to be analyzed. St' and St2 are sets of all checkmate positions for the corresponding side. St3 is the set of all draw positions.
TR TRANSITION^, x, y) represents moving piece p from square x to y. If opposing piece is present at y, capture is implied. Since chess is an Alternating Serial system, only one piece of the active player can be moved at a time (with exception of castling). In addition, chess is a Complex System with blocked beams and destinations, which means that some moves may be prohibited due to presence of another piece either at the target location y, or on the beam from location x to location y. Pawn promotion is also a transition which removes ON(p)=x, and substitutes ON(p)=y, where x is the row before last, y immediately ahead in the top row, and p is promoted piece.
As the reader can see there are certain discrepancies from a general Complex Systems
present several pieces are prevented from occupying the same location (system with
blocked beams and destinations), pawns can be promoted, etc. Such differences can
be easily incorporated into a special class of Complex Systems. Similarly, for other
problem domains, apparent discrepancies from a general abstract board game can be
easily accommodated.
11


Table 2.3 ABG definition for combat simulations
X = {xj} 2D or 3D grid of the area of operations. Could be a simple 2D rectangular grid for land operations, or a complex 3D packing of aerospace, including orbit positions of satellites.
II Sets of resource of the opposing sides, where each element can represent individual or groups of airplanes, tanks, ships, infantry, satellites, etc.
Rp(x, y) Reachability is defined by the movement capabilities of different types of elements present. Ships can move on grid points corresponding to water only. Satellites can only move to a point further along its orbit. The maximum speed of a particular element defines how far it can move in one step.
Val Val(p) can be defined by the abilities of the element (more powerful element has a higher value), as well as by the value of the element to the operation (an airstrip that must be protected can have a higher value).
SPACE ON(p)=x, iff element p is at location x (at particular coordinates on the surface of Earth, volume of aerospace, or position in orbit depending on set X).
Sj and St S, is arbitrary position that is to be analyzed e.g. positions of the resources before the conflict. St is a set of target states based on mission objective e.g. certain targets destroyed (or defended).
TR TRANSITION^, x, y) represents element p moving from location x to y (on land, sea, air, etc). In addition to move transitions, strike transitions are needed to reflect long- distance shooting for objects Due to the nature of real world, these are Totally Concurrent systems any combination of pieces from both sides can move simultaneously during a single time step. Also, transitions may include a game piece producing a new element, changing into a new element, splitting into several elements to reflect events such as firing missile, dropping paratroopers, re-loading expended ammunition, splitting into smaller combat units, etc.
Real-world Defense Systems are the focus of this thesis. Although they exhibit more
complex behavior than traditional board games, they are fully susceptible to LG
techniques. A detailed presentation of ABGs for this problem domain is presented in
Chapter 3.
12


2.2. Hierarchy of Formal Languages
As mentioned above, LG methods are formalized as a Hierarchy of Formal
Languages Language of Trajectories, Language of Zones, Language of Translations,
and Languages of Searches. This formal hierarchy is presented in (Stilman, 2000a)
employing declarative (non-constructive) definitions, followed by introduction of
generating grammars for these languages. Since the subject of this thesis is extension
and application of LG to hypergames for Read-World Defense Systems, this section
is not intended to duplicate that presentation of the LG theory. The purpose of this
section is to show the direction of the LG methods and allow the reader to follow
further discussions in the subsequent chapters. Languages of Trajectories and Zones
are introduced informally and constructively through their generating grammars. The
generating grammars used by LG theory are the so-called controlled grammars, which
are very flexible tools for producing strings of symbols with parameters. The
definitions are followed with simplified examples to demonstrate application of these
grammars (on a chess-like ABG).
2.2.1. Language of Trajectories
The lowest level in the LG Hierarchy of Formal Languages is the Language of
Trajectories. The strings of this language represent a path or route of a game piece
from one location to the next. In general the strings are of the following form:
t0 = a(x)a(x,)...a(x/),
which represents a trajectory for some piece peP from location xeX to location x/eX
of length /. Informally, it is simply a string of symbols a with parameters, where
each parameter is a location of the ABG. The main property of this string is that it is a
valid path for piece p from x to x/. This implies that every point X; is reachable in one
step from previous location x;.i, i.e. Rp(xi,Xj+i)=True for all i = 0,1,_,/-l. Usually,
there is more than one trajectory between any two locations. A set of trajectories for
the element p from location x to location y of length / is called a bundle of
trajectories of length /, and can be denoted by tp(x,y,/). An example, using a chess-
like board, is shown below. The game piece p in the example has a reachability
relation analogous to a chess King, while shaded locations are considered
unreachable. Locations are represented by two numbers (xy).
13


8
7
6
5
4
3
2
1
Trajectories for piece p from (88) to (36) of length 5 are as follows:
to=fl(88)fl(78)a(68)fl(57)a(47)a(36),
t,=a(88)a(78)a(68)a(58)a(47)a(36).
A bundle of trajectories for p from (88) to (36) of length 5:
tp(88,36,5)={to,ti} (Note, that there are no other trajectories of length 5).
Next, the controlled grammar Gt(1) that generates shortest trajectories is presented and
demonstrated on the above example. This is the most basic type of trajectories. A
variety of other trajectory grammars are possible. For instance, admissible
trajectories of degree k represent trajectories consisting of k segments, each of which
is a shortest trajectory. Detailed definitions, proofs of correctness, and discussions on
more advanced types of trajectory grammars can be found in (Stilman, 2000a).
1 2 3 4 5 6 7 8
Figure 2.3 Bundle of trajectories
14


Table 2.4 Grammar of shortest trajectories GtW
L 0 Kernel, 7t£ n FT Fp
1 Qi S(x,y,l) -> A(x,y,f) two 0
2/ Qi A(x,y,f) -> a(x) A(nexti (x,/), y,./(/)) two 3
3 03 ^(x,y,0 -> a(y) 0 0
Vf = W
VN = {S,A}
VPR
Pred={Qi,Qi,Q^},
0l(x> y,l)~ (MAPx p(y) = /) (0 < / < n)
02(0= (/ >1)
Q3 = T
Var= {x, y, /}
F = Fcon 'uFvar,
Fcon = {f, next\,...,nextn} (n = |X|),
Fvar= {x0,y0,/0,p}
E- Z+uXuP
Parm: S ->Var, A->Var, a -+Jx}
L= {1,3} u two, two={ 2j, 22,, 2n}
At the beginning of derivation:
x = xQ, y = y0, / = /0, xQ from X, y0 from X, lQ from Z+, p from P.
nexti is defined as follows:
D(nextj) = XxZfxX2xZfxP
SUM = {v | v from X, MAPxo p(v) + MAPyo p(v) = /0},
STk(x) = {v | v from X, MAPxp(v) = k>,
MOVE/(x) is an intersection of the following sets:
STj(x), ST/0./+1(x0) and SUM.
if
MOVE/(x) = {m\, m2, ,mr} 0
then
nextjix, l) = mf for i <$ and
nextt{x, l) = mr for r else
nextj{x, l) = x.
endif
15


There are several points that require clarification before an example is shown. First is
the definition of the MAPXjP(y) function. MAPx,p(y) is equal to k, such that y is
reachable from x in k steps, but not reachable in k-1. For instance, MAPXiP(y)=l for
all points y such that Rp(x,y)=True; MAPXiP(y)=2 if there is a point z such that
Rp(x,z)=True and Rp(z,y)=True; and so forth.
Second necessary clarification is that the number of productions in this grammar is
not 3 as it seems at first glance. Rather, there are several productions 2j (the set two).
This number is limited by the size of set X; however, it can vary at different steps in
the generation process. There is one production 2j for every different value for the
function next\.
The function nexti is the heart of this grammar. Function nexti returns the i**1 member
of the set MOVEi(x) which contains all possible locations for the next step in the
trajectory. This set is determined as an intersection of three sets: STi(x), St/o_/+i(x0)
and SUM. The set SUM is a set of all points v such that MAPXO p(v) + MAPy0 p(v)
= /0, i.e. the set of all points such that the distance from the beginning of the
trajectory to this point added to the distance from this point to the end of the
trajectory is equal to the total length of the trajectory. It can be easily shown that this
is a set of all the points on all the shortest paths of length lo from xo to yo. This set is
shown as the long ellipse in the figure below.
Figure 2.4 Interpretation of the algorithm for nexti for the grammar Gt(1)
To illustrate the meaning of the other two sets, consider a situation where the first k-1
points of the trajectory have been constructed (xo, xlv. ,,Xk.i), and we are interested in
finding all possible points v for the k1*1 step. Clearly v belongs to the set SUM. Since
the point v has to be on the k*11 location along the shortest path, the distance from xq to
16


v has to be equal to k. Therefore, v is in the set STk(xo)={v | MAPXo p(v) = k} (shown
as the rectangle in the magnified view on the right side of the figure above).
Furthermore, point v is reached on the k01 step from location Xu; as a result, v has to
be reachable from Xk-i in one step. I.e. v is in the set STi(xn)={v | MAPXk.,5p(v) = 1}
(shown as the small circle in the magnified view). In the example above, MOVE
contains two elements. This implies that at the k*11 step, the generation can branch into
two separate trajectories by applying either production 2i or 22.
To demonstrate how the controlled grammar Gt(1) actually generates shortest
trajectories, it has been applied to the situation in Fig. 2.3 in a step-by-step fashion.
The start symbol is S(x,y,l) = S(88,36,5). We start with production 1, and follow to
production 2i out of set two. Since Qi=True (MAPggp(36) = 5), we took the branch
corresponding to Ft in the first production:
S(88,36,5) !=> A(88,36,5) 2i=> a(88)A(ex/,(88,5),36,f(5)).
At this point we need to compute the parameters using function f and nexti. The first
function is trivial: f(5)=5-l=4, which means that the remainder of the trajectory needs
to be of length 4. To compute next;, we need to construct the set MOVE by
computing 3 different sets mentioned above. Let us compute MAPXo p(v) and
MAPyo>p(v), i.e. MAPgg p(v) and MAP3gjp(v). These maps are necessary for
construction of set SUM and ST*.
8
7
6
5
4
3
2
1
Figure 2.5 Values of MAPgg ^
7 6 5 4 3 2 1 0
7 6 5 4 3 1
7 6 5 !i 3 2 2
7 6 6 3 3 3
7 7 7 4 4 4
8 8 8 5 5 5
9 9 8 7 6 6 6 6
10 9 8 7 7 7 7 7
1 2 3 4 5 6 7 8
2 2 2 2 2 3 4 5
2 1 1 1 2 5
2 1 0 ii 3 4 5
2 1 1 4 4 5
2 2 2 5 5 5
3 3 3 6 6 6
4 4 4 4 5 6 7 7
5 5 5 5 5 7 7 8
1 2 3 4 5 6 7 8
8
7
6
5
4
3
2
1
Figure 2.6 Values of MAPj^p
Now, we can compute the set SUM as a set of all points v on the board such that
MAPgg p(v)+MAP36 p(v)=5. In order to complete construction of the set MOVE, we
need 2 more sets: STi(x), ST/0_/+i(x0), i.e. STj(88) and ST5_5+j(88) (in this case
17


they are identical). Note, that the same set SUM is used on every step of the
generation. However, the other two sets that form MOVE do change.
Figure 2.7 SUM
Figure 2.8 STj(88)
From the above figures, it is easy to see that the set MOVE={78}. As a result, there is
only one value of function nextj= 78 and there is only one production in the set two -
2\. Therefore: a(88)A(nex/;(88,5),36,f(5)) = a(88)A(78,36,4). We can continue the
derivation by applying rule 2; again:
a(88)A(78,36,4) 2i=> a(88)a(78)A(ex/z,{78,4),36,f(4)).
At this step the set MOVE is found as intersection of sets SUM (same as above), and
STi(78) and STj_4+j(88) (Figures 2.9 and 2.10). As on the previous step, this set
contains only one value: MOVE={68}. As a result there is only one value of next]
and only one rule 2\. Therefore a(88)a(78)A(ex//(78,4),36,f(4)) can be rewritten as
a(88)a(78)A(68,36,3) and derivation continued as before:
a(88)a(78)A(68,36,3) 2i=> fl(88)a(78)a(68)A(/iexf,{68,3),36,f(3)).
Next, the sets STj(68) and STj_3+i(88) (Figures 2.11 and 2.12) need to be
computed. However, this time the intersection of the 3 sets form the set MOVE with
more than one element: MOVE={57,58}. Therefore, the function next can take on
two different values. This means that at this step the shortest trajectory can go two
different ways. By applying production 2\ or 22 we can achieve the following
derivations:
a(88)o(78)A(68,36,3) 2i=> a(88)a(78)a(68)A(57,36,2), or
a(88)a(78)A(68,36,3) 22=> a(88)a(78)a(68)A(58,36,2).
18


In practice, the generation has to branch every time when the set MOVE contains
more than one element. The total number of shortest trajectories in the bundle is
multiplied every time such condition is encountered. In this case there will be at least
two shortest trajectories generated. For this demonstration, let us pick the first of
these trajectories and proceed with the generation.
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8
Figure 2.10 ST2(88)
8
7
6
5
4
3
2
1
Figure 2.11 ST^) Figure 2.12 ST3(88)






1 2 3 4 5 6 7 8
The next iteration of applying the rule 2j produces the following expansion:
a(88)cr(78)fl(68)A(57,36,2) 2>=> a(88)a(78)a(68)a(57)A(next,{57,2),36,f(2)).
19


The set MOVE={47} (Figures 2.13 and 2.14), therefore
a(88)a(78)a(68)a(57)A(next,{57,2),36,f(2))= The next application of rule 2\ produces the following expansion, where nextj=36,
since MOVE={36} (Figures 2.15 and 2.16):
a(88)a(78)a(68)a(57)A(47,36,1) 2i=>
a(88)a(78)a(68)a(57)a(47)A(nejcf,{47,1 ),36,f( 1)) =
a(88)fl(78)fl(68)fl(57)(47)A(36,36,0).
8
7
6
5
4
3
2
1
20


At this point, production 2j can no longer be applied due to the fact that
Q2=(/>l)=(0>l)=False. Therefore, rule 3 from Ff of rule 2\ is applied. There are no
more non-terminal symbols present and generation is complete:
a(88)a(78)fl(68)a(57)a(47)A(36,36,0) 3=> a(88)a(78)a(68)a(57)(47)a(36).
The second trajectory that is generated by choosing a(88)a(78)a(68)A(58,36,2) on the
4th step (instead of a(88)a(78)a(68)A(58,36,2)) is fl(88)a(78)a(68)a(58)a(47)a(36).
Therefore the entire bundle of shortest trajectories for piece p from location 88 to 36
is trajectories is tp(88,36,5)={to,ti} (Figure 2.3), where
to=fl(88)fl(78)fl(68)a(57)a(47)fl(36),
ti=a(88)a(78)a(68)a(58)a(47)a(36).
Note, that this grammar is completely universal with respect to the problem domain.
It will produce the shortest trajectories for any system for which the set of locations X
and reachability relation Rp(x,y) is defined. Other grammars can be applied in similar
fashion to generate longer trajectories, such as admissible trajectories of order k. This
demonstrates the general method of employing controlled grammars to generate
strings of languages in the LG Hierarchy of Formal Languages.
2.2.2. Language of Zones
The next level in the LG Hierarchy of Formal Languages is the Language of Zones.
The strings of this language represent a network or a set of interconnected
trajectories. One of these trajectories is known as the main trajectory, and the others
are negation trajectories. Intuitively, the main trajectory represents a path that the
main piece needs to take to accomplish a certain goal. The 1st negation trajectories
represent paths for the opposing pieces that can disrupt the main piece from arriving
at its destination. The purpose of k1*1 negation trajectories is to prevent trajectory of k-
1 negation from accomplishing their interception. Full formal definitions of zones and
supporting concepts can be found in (Stilman, 2000a).
Consider the zone shown in Figure 2.17 for a Totally Concurrent Complex System
with strikes (zero-time moves that destroy another object). The main goal within the
zone is for the Gray Bomber po to destroy the Black Tank qo. To accomplish this goal
the Gray Bomber needs to move along trajectory a(l)n(2)n(3)a(4). This brings it
within the strike range of the target which can be destroyed by the strike 4>5. The
zone also contains two Black elements that are capable of destroying piece po before
it reaches its target q0 namely, qi and qi with 1st negation trajectories a(6)a(7)a(&)
21


and a(9)a(10)a(l 1) respectively. However, during the construction of the zone,
Language of Zones also generates 2nd negation trajectory for the Gray Plane pi which
allows it to intercept the Black Plane q2 and therefore, stop q2 from intercepting the
Gray Bomber a(12)a(l 3)a( 14). At the next level, the generation is able to employ
Black Plane q3, which was not able to intercept the Gray Bomber due to time
constraint. However, a 3rd negation trajectory can be constructed for q3 to stop pi
from intercepting q2, so that q2 can intercept po to protect qo. Finally, a 4th negation
trajectory is added seeing as Gray Plane p2 can assist the Gray side by destroying q3
and canceling the chain of events above.
f.,
Figure 2.17 LG zone for TC system with strikes
An LG zone has several constraints. The first constraint is that every trajectory
represents a valid path for the ABG (generated by LG Language of Trajectories). The
second major constraint is that the zone timing is maintained. This timing constraint is
necessary to insure that the interception is actually possible to insure that the
interceptor arrives in time to destroy the target. In general, the length of any negation
trajectory t must be less than or equal to the number of moves that the acting piece on
the trajectory negated by t has to make for reaching the target location of t. The zone
is strict if the length of t is not only limited by the above number but is strictly equal
to it. Strict zones correspond to Complex Systems where a game element cannot
22


wait for its target to arrive at the location of intercept, e.g. fighter plane may not be
able to hover in the air waiting for the bomber to come within range. In the zone
above, the length of the 1st negation trajectory of qi is equal to 2, which is equal to the
number of steps po has to make to arrive at the intercept location (3). Likewise, the
length of the 4nd negation trajectory of p2 is 1, which is equal to the number of steps
for q3 from (15) to (16). Different Complex System may require modification of the
timing constraints. For instance, in chess the length of a 2nd negation trajectory cannot
exceed 1 due to the Alternating Serial nature of the game.
As with the language of trajectories, there is usually not a single zone, but rather a
bundle of zones. Consider that the trajectory for the main piece to the target is usually
a bundle of trajectories with the same source and target. As a result, there is usually a
bundle of zones with each of those trajectories as the main trajectory. The same
principle holds for the negation trajectories.
When LG strategy is derived from the zones, either individual zones or the entire
bundles are analyzed. The important aspect of the zones is that they describe
relationships between the pieces in the Complex System at the same time providing
information on how to exploit these relationships. For instance, if the above zone
were generated within a game we would know immediately that Black Side would
win because there is an intercept trajectory with no counter-intercept trajectories
possible. Moreover, we can see exactly how the Black Forces must behave to
accomplish this protection. For instance, the plane qi is clearly the most important
element. The Gray side can also see how support fighters can attempt to increase
Gray Bombers chances by counter-interception. Even though qi will be able to shoot
at po, the rest of the zone may still be important if the destruction is probabilistic
(rather than unconditional as in chess). The bundle of zones shows exactly how
interception and counter-interception is possible. The analysis becomes more
complex when zones with different goals are present and are interconnected. In
Defense Systems more than one target may be given and available resources must be
distributed between different tasks. However, analysis of zones may provide a
strategy, which uses same resource for several tasks (i.e. in several zones)
simultaneously. This is usually done by the tree evaluation procedure which favors
moves that allow involvement in several zones. In addition to attack zones described
above, other zones are possible, such as block/relocation, domination, retreat, and
unblock zones (Figure 2.18). Block/relocation zones differ from attack zone in that
the main piece is not attempting to destroy a target, but rather just move to the given
endpoint. The opposite side is attempting to block this relocation. The domination
zone is essentially a relocation zone to the endpoint that allows the main piece to
provide domination of another game piece. Retreat and unblock zones have the goal
of moving the main element so as to save it or clear the path for another piece. Other
23


similar networks may be used for a decomposition of Complex Systems for a variety
of problem domains.
24


The previous section presented formalization of trajectories as a string of symbols in
the Language of Trajectories. Similarly, a zone introduced above can be represented
as strings in the Language of Zones using the relation of trajectory connection. Two
trajectories are considered connected, if the endpoint of the first trajectory coincides
with an intermediate point of the second trajectory. In general zones are represented
in the following form:
Z = t(po,to,To) t(pi,ti,Tj) ... t(pn,tn,Tn)
where t is a terminal symbol, p;s are game pieces from the set P, tjs are trajectories
from the Language of Trajectories for the corresponding pieces, and ifs are non-
negative integer time bounds on the corresponding trajectories. The first symbol,
t(p0,to,To) corresponds to the main trajectory of the zone, while t(pi,ti,Ti)...t(pn,tn,Tn)
are the negation trajectories. The time bound x; for t; represents the notion of time
constraints presented above, which insure that the negation trajectories can intercept
on time. Intuitively, Xi is the number of game moves that the piece pi has to intercept
its target trajectory. The particular way Xj is calculated depends on the class of the
Complex Systems and the level of negation. The Grammar of Zones computes these
values automatically during derivation of a particular zone. The zone from Figure
2.17 can be represented in the following way:
Z = *(Po (1 )(2)a(3)a(4)a(5), 4) t(q i, a(6)a(7)a(8)a(3), 3)
t{ca, (9)fl(10)fl(l l)a(3), 3) ph a(12)a(13)a(14)a(l 1), 3)
f(q3, a( 15)a( 16)a( 13), 2) The concept of zones has been thoroughly presented above. The controlled Grammar
of Zones Gz that generates such zones for a given Complex System is presented in
Table 2.5. Since the method of application of such control grammars is presented in
the previous section, an example of applying Gz is not shown. Such examples as well
as declarative definitions of the Languages of Networks and Zones, related concepts
(e.g. trajectory connections and x time constraints) can be found in (Stilman, 2000a).
Productions 1 and 2; generate the main trajectory. Productions 3 and 4j are used to
generate the 1st negation trajectories, while production 5 provides a way to switch to
higher negation. Subsequently, combination of productions 3, 4j, and 5 is used to
generate trajectories of all higher levels of negation. The generation is terminated
using production 6 when no more trajectories of higher level of negation exist
(predicate Q5 is False). The main intricacies of this grammar are generation of
connection points and maintaining time bounds on the negation trajectories to each of
those points.
25


Table 2.5 Grammar of Zones Gz
L 0 Kernel, n£ (2 e X) tt(2 e X) Ff Fp
1 01 S(u, v, w) - A(u, v, w) two 0
2/ 02 ^(m, v, w) -> /(/i,(u), /0+l) A((0, 0, 0), g(/i/(u),w), zero) TIME{z) = DISI\z,hj(u)) 3 0
3 03 A(u, v, w) > A(f(u, v), v, w) NEXTTIME(z) = initiu. NEXITIME(z)) four 5
4j 04 A(u, v, w) > t(hj(u), TIME(y))) A(u, v, g(hj{u), w)) NEXITIME(z) = ALPHAiz, hj{u), TIME(y)-l+\) 3 3
5 05 A(u, v, w) > /1((0,0, 0), w, zero) TIME(z) = NEXTTIME(z) 3 6
6 06 A(u, v, w) £ 0 0
vT = £ II
VPR
Pred = {Qi, Q2, Q2, Q4,
01 O') = (ON(p0) = x) A(MAPx po(y) (3q ((ON(q) = y) a(OPPOSE(p0, q))))
Q2(u)=T
0300 = (x*0)v£y*n)
0400 = (3p ((ON(p) = x) a (/ > 0) a (x *x0) a (x *y0)) a
((_,OPPOSE(p0, p) a (MAPx>p(y) = 1)) v
(OPPOSE(p0, p) a (MAPx>p(y) £ /)))
Q$(w) = (w*zero)
Qe=T
Var= {x, y, /, % 0, v2,vn, wj, w2,..., wn};
for the sake of brevity: u = (x, y, /), v = (vj, V2,vn),
w= (wq, w2,..., wn), zero = (0, 0,..., 0);
Con = {x0,y0,/0,p0};
Func = Fcon vjFvar,
Fcon = {/x/y//, - >£n> hbh2 >AM-
h{, h2,..., hM, DIST, init, ALPHA),
f~ (fxfyfl) 8 = (8x\ £x2> >£xn)
M = |Lt/o(S)| is the number of trajectories in l/(S);
Fvar= {x0,y0,/0,p0, TIME, NEXTTIME}
E = Z+u XuPu L^(S) is the subject domain;
Parm: S-*Yar, A-*1u,v,w), />{p,r, 9)\
L ={1,3,5,6} 26


Table 2.5 (Cont.)
D(init) = XxXxZ+xZf
init(u,r)
2n, if u = (0,0,0),
r, if u (0,0,0).
D(/) = (X x X x Z+ U {0, 0, 0}) x Z+n
J(x + l,y,/), if((x ^ n) a(/> 0))v((y= n) a(/<0))
/(. v) |(1, y+1, 77M£{y + l)xvy+1), if (x = n)v((/<0)A(y*n)).
D(DIST) = X x P x Lt/o(S).
Let t0 e Lt/o(S), t0 = a(z0)a(z1)...a(zm), t0 tp0(z0, zm, m);
If ((zm = y0) a (p = p0) a (3 k (1 < k < m) a (x = zfc))) v
(((zm Yo) v (p p0)) a (3 k (1 < k < m 1) a (x = zfc)))
then DIST\x, p0, t0) = k+1
else DIST(x, p0, t0) = 2n.
D(ALPHA) = X x P x Lt/o(S) x Z+
max (NEXTTIME
ALPHA (x,p0,t0,k) =
k,
NEXTTIME (x),
(x),k), if (DIST (x,Po,t0) 2n)
a (NEXTTIME (x)*2n);
if DIST (x,p0,t0) 2n)
a (NEXTTIME (x) = 2n);
if DIST (x,p0,tc) = 2n).
D(gT) = P x Lt/o(S) x Z+n, r e X.
, * if£MS2Tr,p0,t0)<2a
&(Po.to,w) if D/S7(r,p0,t0) = 2a
D (hf3) = X xX x Z+;
If TRACKS,, =0
Po
Let TRACKSpo = {Po} x (u L[Gt(2)(x, y, k, p0)];
l then h (u) = e
else TRACKS Po = {(p0, t,),(p0, t2),..., (p0,tb)}, (b < M) and
[(Po.L). if
h() =
(Po.tb), if i>b.
D(hj) = X x X x Z+; Let TRACKSp = {p} x (vj L[Gt(2)(x, y, k, p)];
l If TRACKSp = 0 then A/() = e
else TRACKS p = {(p,,t, ),(p,,t2),...,(pm,tm)}, (m UPm.tm). If i>m.
Trajectories tj should not be embedded (as sub-trajectories) in the trajectories of the same negation.
At the beginning of generation:
u = (xo> yo- *o) w = zero- v = zero- xo e X, yQ 6 X, /0eZf, p0 e P,
TIME(z) = 2n, NEXTTIME(z) = 2n for all z from X.
27


2.3. LG Strategies
There are two methods that can be used to apply the Hierarchy of Formal Languages
to construct strategies. The first, more traditional approach is to construct search trees
employing the Languages of Translations and Searches using the generating tools
presented above. By following this technique, reduced search trees can be generated
of sizes significantly smaller than those of Alpha-Beta search. The second approach is
to construct a solution without any search at all. The construction of strategies is
achieved by decomposition of the State Space in the form of the State Space Chart,
which is based on the expansion of the terminal sets. Neither of these approaches is
presented here, as both of them are discussed in detail in (Stilman, 2000a), and a full
understanding of strategy construction is not essential for the reader to follow further
discussions in the subsequent chapters. It is sufficient to mention that these methods
make significant use of Languages of Zones and Trajectories presented in previous
sections.
2.4. LG Areas of Applicability
Although LG was developed by formalizing chess-playing expertise, these methods
are applicable to a wide range of other problem domains. One such area is Defense
Systems, which encompasses a number of topics such as Wargaming, Information
Warfare, Unmanned Aerial Vehicles control, Effect Based Operations and many
others. Problems from this domain are the focus of this thesis. The other areas that
Linguistic Geometry methods can be applied to are Interactive Entertainment,
Network Security and Data Routing, and Transportation. A partial list of such topics
is shown in Table 2.6. A number of researchers, such as (Turek, 1997) and (Skhisov,
1997), have already applied LG tools to some of these areas, while other areas are yet
to be examined.
28


Table 2.6 LG areas of applicability
Defense and Aerospace Global Command and Control Software Wargaming (Symmetric and Asymmetric) Information Warfare, Cyberwar Unmanned Aerial Vehicles Missile Defense Systems Satellite Command and Control Operations Effect Based Operations
Interactive Entertainment Internet Optimized Multi-player Strategic Games Educational Tools for strategic thinking and training Software Tools for professional sports
Network Security and Data Routing Strategic Defense of Networks Efficient Routing of Data Packets Global Virus Protection Security Against Hacking.
Transportation Intelligent Transportation Systems Emergency Vehicle Routing Aircraft Collision Avoidance GPS-enabled Traffic Advisor
29


3. ABGs for Real-World Problems
In order to solve the problem using mathematical tools, the first requirement is to
model the problem in the form that can be solved using those tools. In the case of
Linguistic Geometry such form is an abstract board game. Initial development of LG
was based on chess games, so unsurprisingly, chess and similar board games can be
easily modeled as ABGs. However, those games are simple. One main reason is that
these games are well defined there is usually an accepted set of rules, set of possible
game elements on a specific board, and standard goals. Another reason is that the
majority of these games are Alternating Serial one player can only move one piece
at a time. Chess is played on an 8x8 board with 64 cells and 32 game pieces where
one piece is moved per game turn. The game is further restricted by conditions of
blocked destinations and beams no two elements can occupy the same cells and
most elements cannot jump over other elements. The complexity of the game also
decreases over time as captures occur. Shogi (Japanese Chess) is a harder chess
variant. It is played on a 9x9 board with 81 cells and 40 game pieces most of which
can be promoted. Moreover, the number of pieces generally does not reduce over
time due to drops a captured enemy piece can be placed back on the board as a
friendly piece. Probably the largest chess variant is Tai Shogi. This game is played on
a 25x25 board with 625 cells and 354 game pieces of 101 distinct piece types. The set
of piece types is wide with incredible variety of movement patterns and capabilities.
Some pieces are allowed to make more than one move per game turn, while other
have such powerful reachabilities that on an empty board they can reach any board
location in one step (they can move as a bishop in one direction for any distance, then
make a 90 degree turn and continue moving). Still, only one piece per game turn can
be moved.
3.1. Discretization of Continuous Systems
However complex, most board games were designed as over-simplifications of real
life problem so that they can be played by people. This implies reasonably simple
boards, movement patterns, and, of course, Alternating Serial discrete game format
(imagine playing a Totally Concurrent game before invention of computers). As a
result, the games are already well structured. On the other hand, the real world is not.
In general, real problems are not discrete either in space or in time there is no
inherent discretization into board cells or time increment. Furthermore, everything
happens at once. Even after questionably successful discretization, the games remain
30


concurrent. Note, that even large AS games have significantly lower branching
factors than smaller TC games. For instance, an AS game with 400 game pieces each
of which can make 5 distinct moves has the branching factor of (400/2)*5=1000,
whereas a TC game with only 5 game pieces and the same number of moves per
game piece has the branching factor equal to 55=3125. Furthermore, real world
problem do not have a well-defined set of rules. The majority of rules that are defined
are of course continuous, such as those based on the law of physics for motion.
The first part of solving these types of problems is to adequately model the situation
in discrete format. As mentioned above, for LG these models are described as ABGs,
which can be represented as 8-tuples < X, P, Rp, SPACE, val, Sp Sp TR>. This 8-
tuple can be expanded based on the particular system, such as adding strikability
relationship for long distance shooting. The first 3 elements of this 8-tuple are the
most important and potentially difficult to define X, P, and Rp. Once operational
board, the set of pieces, and the capabilities of these pieces are defined, the remaining
game elements are easier to specify. One of the choices about the Complex System
representation of real-world Defense Systems is unfortunately clear the model has
to be Totally Concurrent, so that at least within our discretization everything can
happen at once. Serial games are not well suited for this problem domain.
3.2. Spatial Discretization
An issue that requires more consideration, yet usually must be answered first is
discretization of space into members of set X. For Defense Systems, this implies
breaking down operational district into a reasonable representation as a game board.
One of the major concerns is the size of the discretized unit. If each cell is very large
we cannot model real situation very closely. On the other hand, if each cell is very
small, the number of cells very large thus increasing computational burden. A good
case is for the size of the cell to represent the minimum transition in one time step
that the slowest moving game agent can make. Therefore, one of our goals at the
modeling stage is to find a near-optimal cell size.
3.2.1. 2D Game Boards
There is no single solution for best discretization; rather different problems yield
themselves to different representations. In general several cases can be considered.
Perhaps the simplest case is a problem that can be considered 2-dimensional. Such
problem can include various land or sea operations, as well as some air operations,
which do not loose much generality when the 3rd dimension is dropped. For instance,
31


for land combat with air elements, that can provide fire support and transportation of
troops and resources, a 2-dimensional board may be a good choice. Whereas, air
operations where elevation data is crucial may require more detail than 2D board can
provide. A lot of the terrain properties can still be reflected within the 2D structure by
storing properties of each cell (such as elevation above ground level and terrain type).
This data can be used to make reachability relationships for game pieces more
realistic. For instance, a land unit moving through a forest to a location at higher
elevation can move through less cells in one game turn, compared to moving on level
ground.
3.2.1.1. Rectangular Grids
Within the class of 2D boards, we still need to break down this continuous planar
structure into a set of locations. One of the traditional approaches is rectangular
discretization (usually into square regions). The obvious benefit is that it is a familiar
to most people and can be easily represented as a matrix in the computer. However,
very often this method is not sufficient. The reason is that many objects that we may
need to model for Defense System have natural motion patters (as opposed to
patterns such as Knights in the game of chess). Very often this implies uniformity of
motion in all directions i.e. the piece can move a certain distance (based on its
speed) in any direction. For instance, an army division can move north just as easy as
south-west (assuming identical terrain). Rectangular decomposition does not allow
for very accurate modeling of such cases (see Figure 3.1.). As you can see, when we
attempt to draw circles of radius 1 or 2, the results do not appear circular. One way to
judge the quality of these representations is to calculate the ratio of the range in the
distances to the cells on the circle to their average (the optimal ratio is 0). For radius
1 this ratio is equal to 0.34314, while for radius 2 it is 0.35629. As can be seen from
the Figure 3.1, as the radius increases, we can attempt better representation of circles
similar to a circle being drawn on a rasterized computer screen. However, one of our
concerns is with the size of cells. If the slowest moving agent in the game can move
within 4 cells in one time step, we may be using discretization that is too detailed and
wasting computational efforts.
32


zr
vVV
- .:As
!i
*

V-*

#|
Figure 3.1 Concentric circles on rectangular grid
3.2.1.2. Hexagonal Grids
An alternative approach for discretization of 2-dimensional space is to use a
hexagonal grid. While this method is less familiar than using a rectangular grid, it is
not new and should still be familiar to most people as it has been used in many games
and simulations. Another concern with this approach is storing the data in the
inherently linear computer memory. Several hexagon enumeration schemes exist such
as those shown in Figure 3.2. The choice of a particular scheme depends on the
particular application demands (for instance, the left scheme provides an easier way
to cover a rectangular region). However, the main benefit of hexagon grids is that
every cell is exactly the same distance from all of its neighbor cells. Therefore, the
ratio of the range in the distances to their average is 0. Of course, for circles of larger
radius, the hexagonal approximation is not as perfect. For instance, for radius of 2 the
ratio is equal to 0.14359. As in the rectangular case, as the resolution increases the
approximation of the circle becomes better. Since it is computationally more efficient
to use the most coarse sufficient resolution, hexagonal grid can better represent
reachability relations for pieces that can move equal distances in any direction.
33


Figure 3.2 Hexagonal grid enumeration schemes
3.2.1.3. Phase Spaces
There is one more issue we need to consider with regard to 2D boards for Defense
Systems. An army division may be able to move north and south-west the same
distance (e.g. 5 miles) over a given time period (e.g. 2 hours). However, consider a
situation where a jet is flying north 500 miles per hour. If we have to use time
increment of 0.5 minute and cell size of 2 miles (due to specific problem
requirements), we may need to account for the fact that the plane cannot suddenly
turn around. What this implies is that instead of a circular reachability relationship,
we may need to use a movement pattern that more resembles a sector of a circle with
a certain arc. However, the orientation of this sector depends on the direction of the
velocity vector on the previous move. At first glance the definition of ABGs and
generating grammars do not allow us to keep track of such extra information during
trajectory generation. In fact, this can be easily incorporated in the board design by
extending the 2D board into Phase Space. For instance, let us use a hexagonal 2D grid
and discretize direction dimension into 6 values 0 thru 5. 6 directions is a natural
choice for hexagonal grids, although any number can be used based on the
application. Every 2D cell (x,y) becomes 6 different cells (x,y,d), where direction
d={0,l,2,3,4,5} (Figure 3.3). This allows us to model the current direction of the
piece as the cell on which it is located. Furthermore, the reachabilities (and therefore
trajectories) are considered from current cell (xi,yi,di) to destination cell (X2,y2,d2).
This allows us to account for situations described above. For instance, consider
reachability relationship shown in Figure 3.3. If piece p is at location (x,y) with
velocity vector 0 (N) and wants to move to location (x,y+2), we can only arrive there
with velocity vector 0 (N). This implies that Rp((x,y,0),(x,y+2,d))=True only for d=0.
On the other hand Rp((x,y,0),(x,y-l,d))=False for any d, since we can not fly directly
back. Clearly, if this piece needs to reverse its direction of flight it has to do so over
34


several moves gradually changing its direction (xi,yi,0)-> (X2,y2,5) (x3,y3,4)->
(x4,y4,3).
Figure 3.3 Directions with respect to a hex grid
Phase space allows us to model real-world situations with a lot more precision than a
simple 2D grid. The same method can be extended into other types of basic boards
(such as 3D), as well as other types of phase dimensions (e.g. fuel or acceleration).
However, increasing the number of phase dimensions and the level of their
discretization increases the board size. Total size of the board becomes: |X|=|2D
Space|x|Phase Dimensionl|x|Phase Dimension2|x...x|Phase DimensionN|. For a 2D
board of 1,000 cells with 6 possible directions and 3 values of acceleration, the board
size becomes 18,000. As with the size of 2D cells, one of the goals is to use the
minimum number of phase dimensions with the most coarse discretization levels that
can represent the world in sufficient detail.
3.2.2. 3D Game Boards
While 2D boards may be sufficient for some problem, a much higher level of
precision can be achieved with 3-dimensional discretizations. For some Defense
Systems this extra degree of realism is essential. One such area is air operations. As
mentioned above, some problems with air units in it can be approximated with a 2D
game; however, that is not always the case. Consider a scenario, where a group of
airplanes is flying through a mountainous area with surface to air defenses. A 3D
representation will allow us to handle complex behavior such as flying through the
canyons to stay out of line of sight of surface radars. Furthermore, the reachability
relationships for cells at higher altitudes may allow faster flight than low above
ground level. Some weapons can only be fired from aircraft at targets that are within a
certain cone of attack, so that the plane has to adjust its position before strike. If we
attempt to model these types of games with a 2D ABG, any position above a given
cell will have identical properties. While we can model one of the aspects mentioned
above (such as canyons by noting ground level at every 2D cell), we cannot model all
of the potential different behaviors over that cell. Using a 3D model we can
35


distinguish and plan our strategy to take advantage of such effects as flying through
this location at 100ft above ground level to avoid radar, moving to attack altitude, or
accelerating to burst speed at 20,000 ft and keep track of line-of-sight visibilities at
all times.
Several approaches can be used to model 3-dimensional space. One way is to use a
dense packing of space by certain shapes (usually approximating spheres). The goal
of such packing is to achieve an effect similar to hexagonal grids on a plane every
cell is located equal distance away from all of its neighbors. Such discretizations are
usually complex and counterintuitive for most people. More importantly, they are
unnecessary and often not appropriate for real-world Defense Systems. The reason is
that in real life 2 horizontal directions are very similar, while altitude is quite
different. The aircraft may be able to move at 500 miles per hour in any direction at
any given altitude; however, it is usually only able to change altitude at the rate of
about 20 miles per hour. For the same reason, it is also common to use a different
scale in the horizontal and vertical dimensions. Since motion in vertical direction is so
different from horizontal directions, it makes more sense to model 3D boards as a
stack of 2D boards. If the 2D board is discretized as a rectangular grid, a 3D cell is a
cube or a rectangular prism. Hexagonal 2D discretization produces hexagonal 3D
prisms (Figure 3.4). Each of the cells represents a chunk of 3D space and stores the
properties of the section of space contained in that region, such as air, water, ground,
etc. The reachability relationships are then designed to conform to the properties of
game elements an airplane can only move through cells with air, while a ground
unit can only exist in an air cell immediately above a ground cell. Furthermore,
similarly to 2D games, the concept of Phase Space can also be extended into 3D
games, thus making them 4D (or higher).
Figure 3.4 3D cell: hexagonal prism
3.2.3. Spherical Boards
So far, all of the discretizations have only dealt with either 2- or 3-dimensional areas
above a planar surface. We have assumed that the 2D grid is covering a uniform
portion of a flat surface. However, the Earth is not flat. Plan approximations assumed
above work well for relatively small area. On the other hand, some Defense Systems
may require an operational district that is large enough to notice the curvature. Others
36


may require considering the entire surface of Earth as the operational district. In this
case, we have to discretize the entire surface of a sphere (for large, yet not full-Earth
models, we can use subsets of full spherical mappings). There are two general classes
of approaches to this problem. The first is to map the surface of a sphere onto a plane
and then discretize this planar representation. The second approach is to discretize the
surface of the sphere directly. The main difficulty of both methods is maintaining
uniformity of cells. As mentioned in the previous section, an important property is for
the distances between neighboring cells to be uniform. We would also like each cell
to be of approximately equal area and shape. A comprehensive survey of Discrete
Global Grids can be found in (Sahr and White, 1998).
Consider the first approach. The first step in this approach is to map the surface of the
sphere onto a planar structure with as little distortions of distances, areas, and shapes
as possible. This problem has been studied extensively by researchers in the area of
map projections. Unfortunately, there is no projection, which maintains distances,
areas, and shapes. There are projections that may be able to maintain some of the
properties (e.g. equal area projections); however, there is no projection that is
equidistant in all directions. As a result, we may have cells, which are not spaced
uniformly on the sphere. One of the better projections is the Snyder equal area
projection onto a polyhedral globe (Snyder, 1992). The second step of this method is
to discretize the planar structure into 2-dimensional cells. The cells can be of any
shape; however, as for 2D boards, hexagons have some of the most desired
properties. The difficulty of this step is usually due to the shape of the planar structure
used. For instance, consider projections onto a polyhedral globe. These structures
consist of several planar faces that can be triangles, squares, pentagons, hexagons,
etc. Each of these faces then needs to be broken down into cells. However, if we
attempt to discretize a pentagon as a tiling of hexagons, we will encounter problems
along the edges and at the comers. The easiest shape to discretize is either a square
(which usually has large projection distortions), or a triangle. Furthermore, there is
usually a tradeoff between the quality of the first and second steps. Snyder equal area
projection onto an icosahedron (20 triangular faces) has much higher distance
distortions than a projection onto a truncated icosahedron (20 hexagonal and 12
pentagonal faces). On the other hand, the icosahedron is easy to discretize
consistently into hexagons with no edge problems, while pentagons and hexagons do
not allow for such a consistent discretization. One of the better approaches of this
type is presented in (Carr, 1997).
The second approach consists of discretizing the surface of the sphere directly. One
common method is to start by approximating the sphere as polyhedron (usually a
platonic solid). Then each face is broken down into several smaller parts to construct
a more complex polyhedron. By such successive subdivision, a sphere is
37


approximated by a polyhedron with a very large number of faces. The key element of
this process is the subdivision of the face to produce a number of smaller faces. At
each subdivision, some new vertices are produced which need to be projected back to
the sphere creating the new polyhedral structure. This process is somewhat similar to
the map projections mentioned above. The difficulty lies in creating the new vertices
so that the distances between neighboring vertices remain fairly close. The final cells
are created from this collection of small faces. Either a cell can incorporate the area
covered by 1 or more faces, or a cell may be centered on a vertex and contain points
that are closest to it. This approach with an extra optimization step was presented in
(Heikes and Randall, 1995a, 1995b). The grid may not exhibit all desired properties
(such as equal distances and areas); however, it can be used as a starting state for a
dynamic optimization technique based on the requirements for the grid. The cells are
adjusted slightly to maximize the optimization criteria.
3.3. Temporal Discretization
Another important part of ABG modeling is temporal discretization. As mentioned
above real-world Defense Systems generally have to be modeled employing Totally
Concurrent Complex Systems; however, the time step may be varied and usually
depends on the particular application. Temporal and Spatial discretizations are very
closely interconnected. In the Section 3.2 we presented the idea of compromise: the
cell must be small enough to be able to represent necessary level of detail, yet large
enough so that the computations are not overwhelming. However, this spatial
parameter is subject to the time step used. Consider representing a vehicle moving at
1 mile per minute. If we use a time increment of 1 minute, we may want to use 1 -mile
cells. On the other hand, this spatial scale may not be sufficient due to the nature of
the terrain. If we decrease the size of the grid to 14 mile per cell, we have a choice of
decreasing the time scale to 30 or 15 seconds (so that the reachability is 2 or 1
cell/tum) or maintaining the spatial scale (using 4 cells/tum reachability). Conversely,
if there are other events happening more frequently in the game, we may need the
time step of 30 seconds per turn, which can require a change in the spatial scale. As
the reader can see there is a very tight interconnection between temporal and spatial
discretization. However, the time step may be affected by factors other than just
relationship between cell size and agent speeds. There may be additional non-
movement events affecting the time scale, such as weapon effects and sensor updates.
38


3.4. Game Agents
Another issue that must be considered early on in the modeling stage is the set of
game pieces. For a Defense Systems this set may include buildings, bunkers, infantry
units, tanks, airplanes, missiles, satellites, and more. The choice of representations for
movable agents in the simulation goes hand in hand with defining the operation
district. As mentioned in the previous sections, one of the qualities of a good board is
that the size of the cells reflects the velocity of the game pieces. The agents in real-
world Defense Systems are real objects with continuous properties. As always,
discretization creates some approximations. There are several main properties of a
game agent for Defense Systems that need to be defined movement, attack, and
miscellaneous abilities.
3.4.1. Movement
The movement pattern is defined as a reachability relationship on the game board. As
a result, the ability to represent certain patterns is subject to our choice of spatial (and
temporal) discretization. Conversely, the choice of the board must reflect the
movement patterns that we need to implement. Consider a case where we need to
model jet planes moving at 20 miles per minute and cargo planes moving at 6 miles
per minute using a time step of 1 minute. If we use a cell size of 1 mile, the level of
detail is higher than necessary. On the other hand if the cell size is 6 miles, then the
speed of the jet can only be represented as 3 or 4 cells i.e. 18 or 24 miles. A more
appropriate choice might be 5 miles/cell, so that the jet has a reachability of 4
cells/tum and the cargo plane 1 cell/tum. For a particular problem, an expert in the
problem domain must be consulted to determine the minimum precision necessary to
represent the real world (e.g. 18 or 24 miles may not be an appropriate approximation
for the jet, but 5 miles per minute may be acceptable instead of 6 for the cargo plane).
Furthermore, consider a scenario with jet airplanes moving at 1,200 mph and cargo
ships moving at 20 mph. The size of the cell cannot be smaller than (20 mph x
TimeStep), so that the move of a ship can be represented. However, this produces a
reachability relationship for a jet of 60 cells per game turn. This corresponds to more
than 10,000 possible moves from any location, for a full circular reachability even on
a 2D map. If such computational burden is too large, these 2 types of pieces cannot be
represented on the same board. Chapter 4 presents the hypergame approach to deal
with such situations.
39


In addition, the movement of real objects is affected by other physical factors such
as gravity and inertia. For 3D boards we need to define reachability relationship to
include vertical motion as well as horizontal based on their parameters. A plane may
be able to descent faster than to ascent. This may be reflected by considering cells one
level above and two levels bellow current position reachable in one time step.
Furthermore, inertia may prevent the plane from turning 180 in one game turn. In
this case, a Phase Board may be necessary and the reachability can be defined based
on physical properties of the agents such as minimum turning radius (Figure 3.5).
Similar properties may include higher speed at higher altitudes for airplanes and
different reachabilities over different terrain types (such as amphibious vehicles).
Another property of movement for real objects is fuel limitations. However, this
property may not always need to be modeled. For instance, a truck with period of
operation that is less than 5 hours can be assumed to have unlimited fuel; while, a
missile in the same period can not be in flight for the entire duration. Moreover, some
game elements, such as an airplane in flight, may not remain on the same location for
2 consecutive game turns (Rp(x,x)=False). This may impose certain restrictions on the
generation of trajectories and zone timing principles. For instance, in an LG zone a
piece can arrive at the attack location at any time before the target piece reaches it.
However, if a piece cannot hover or stay in one place, the trajectories must match up
exactly both pieces must arrive at exactly the same time. This implies that more
complex LG trajectories must be generated.
Figure 3.5 Reachability based on turning radius
3.4.2. Attack
Another important property of agents in Defense Systems is the ability to attack. In
chess and similar board games, a piece is captured when an opposing piece moves to
40


the same location. Unfortunately, it is not always quite so simple in the real world. A
piece may be destroyed from a remote cell; or when a piece moves to a location
occupied by the opposing piece, it may be the first piece that ends up being destroyed.
The first aspect of attacks is the strikability relationship. In Section 2.1, we defined
which cells can be attacked by a given piece from a given location. These
relationships can depend both on the type of the game agent and the type of the
weapon used. Thus, an airplane with bombs and air-to-air missile can have two
different relations of strikability. The first relation may include all cells directly
bellow current position, while the second one includes all cells within the cone of
attack. Some of these strikabilities may be more complex than other. For instance,
consider a plane that can fire a missile at any target within 10 cells and the cone of
attack of 60 in the horizontal direction and 10 in the vertical direction relative to
its current velocity vector. To compute this relationship we first need to find all cells
in the specified cone within the range. However, we still need to take into account
line-of-sight requirement by checking for obstacles and removing any locations
behind them from the set of strikable locations (Figure 3.6). In addition to
strikabilities, attacks in Defense Systems may need to be modeled as creation of a
new game piece. Consider an aircraft firing a sub-sonic cruise missile at a target 100
miles away. In this case, it may take several game turns for the missile to reach its
destination. During this time it should exist physically within the game as a game
piece so that other objects can interact with it (e.g. intercept it). Regardless of whether
the weapon is modeled as a strikability relationship or generated piece, the weapon
load is usually very limited and must be considered during strategy generation.
Complex properties such as reloading at friendly stockpiles may also need to be
modeled.
Figure 3.6 Strikability with obstacles
41


The second aspect of attacks for real-world Defense Systems is that not every attack
results in destruction one, several, or none of the pieces involved in the attack may
be destroyed. If one object shoots another, the second object may be able to shoot
back at the same time (if allowed by the strikability) since the game is Totally
Concurrent. More complex cases may include more than two pieces shooting at each
other. However, the outcome of any single attack is usually probabilistic there is a
Probability of Kill (PK) that determines the outcome. This probability depends on the
type of weapon and the type of target. Other factors may affect this probability, such
as position of the target relative to the attacker (consider firing at the plane in flight or
on the airstrip). In simulations, a pseudo-random number is usually generated and
compared to the PK to determine the outcome. The importance of PK lies in the
analysis of the situation. In LG this analysis is performed by dynamic decomposition
using the Hierarchy of Formal Languages. Consider the zone in Figure 2.17. If all
PKs are equal to 1 (unconditional destruction), the Black side will be able to destroy
the Gray bomber p0, and q2 and q3 are not necessary. However, if PK for each plane is
equal to 0.5, the red side may be able to get through. The probabilities of kill can be
incorporated at the zone analysis level to determine best possible behavior. For some
Defense Systems applications Probabilities of Damage (PDs) have to be used instead
of Probabilities of Kill. The main difference lies in that the result of an attack is not
destruction of a piece, but rather incurred damage. Each piece has an associated status
value that can be thought of as its health. When a game agent attacks another agent
a random value is compared to the corresponding PD value. If the outcome is
damage, the status value is decremented by the amount of damage associated with
that weapon type. Alternatively, the amount of damage can be modeled as a random
number between 0 and PD. When the status of the element drops below a certain
threshold, it is considered destroyed. As with PKs, PD values must be considered at
the zone analysis level.
3.4.3. Miscellaneous Behavior
In addition to simple movements and attacks described above, real-world Defense
Systems may require a very wide range of miscellaneous behavior. One of the
common constraints comes from the inaccuracies of spatial discretization. Consider
rectangular and hexagonal 2D boards with relationships of reachabilities of one cell in
every direction. Any path for a piece in this framework will be jagged similar to a
straight line being drawn on a rasterized display. A path on a discrete board is
considered to pass through the centers of cells; as a result even the shortest trajectory
is not a straight line but a collection of several trajectories with a number of turns
(Figure 3.7). Clearly, the trajectories on the outside of the bundle look like they are
42


longer, while some of the internal trajectories are extremely jagged (a turn on every
step). For some applications this may not be an important issue. This is especially true
if the model is used for higher level planning while another system handles low level
control (e.g. through hypergame). However, sometimes these zigzag trajectories have
to be dealt with. One way such problems can be reduced is through Trajectory and
Move Evaluation Function, which is a standard component of LG. Quality of
individual moves and trajectories is constantly evaluated based on parameters such as
participation in multiple zones at once and avoiding interception. We can easily
incorporate other criteria into this evaluation in particular smoothness and deviation
from true shortest direction. This allows us to discard trajectories that would not be
considered reasonable by human experts, while still evaluating entire bundles in case
the unusual trajectories prove useful. The exact parameters of this evaluation depend
on the problem domain.
Figure 3.7 Bundles of shortest trajectories
Another aspect of real-world Defense Systems is that they may combine long periods
of inactivity with conflict stages. Consider an aircraft group flying to the target 100
miles distant. The first 50 miles may be completely uneventful, yet we still have to
consider them as the opponent may appear even then. Then, there may be a short
period of combat (e.g. with outer ring of defenses), followed by another stretch of
inactivity until the next level of defenses or target is reached. The fight at the target
will then be followed by the group returning back to base. The flight back still needs
to be modeled since there may be more conflicts. This presents the case of soft
(inactive) and hard (active) stages. Most of the standard games contain only active
stages because soft periods are considered too simple. While soft phases are easier to
handle, a complete model for a Defense System has to include both due to their
interconnection. Proper strategy at the inactive stage may increase the chances of
success during combat. Consider the above scenario when we know only the location
of the target, but not the composition or location of the enemy defense. The strike
group must fly to the target together and in a formation that provides the maximum
43


variability of responses when the enemy is discovered. For instance, such a mission
may be flown with bomber in the tail of the group, while fighter aircraft and
electronic countermeasure aircraft are leading the package. Such extra level of
complex behavior has to be defined by the human experts in the field and then
introduced into the strategy generation algorithms. In this case, extra level of expert
defined behavior and standard LG methods are employed together by the LG strategy
generation approach to find the best course of actions in both soft and hard stages.
Another example of expert defined behavior that can be used at combat stage is
commitment of resources to a threat. When a package is attacked by one enemy plane
it may not make sense to send all defenses to intercept it and leave the bomber
unprotected.
Incomplete or false information is another non-standard aspect of real-world Defense
Systems. Note, that some of the extra expert principles above are most useful in the
presence of incomplete information. If everything is known about the enemy, such
advice may not be needed. For instance, when the group is attacked by one enemy
aircraft, but we know that there are another 3 on the way, standard LG methods can
be used. On the contrary, if we do not know that there may be more aircraft, the
correct action for LG is to send everyone against the plane that is visible. There are
two general directions of handling incomplete information. First is to use visibility
flags for each piece. Under certain conditions (e.g. distance to target, line of sight,
etc) a piece can become visible. Then LG ability to update strategy on every step
together with expert principles can be used. This takes advantage of the natural
properties of LG methods, which include dynamic decomposition and updating of
strategies as the game situation changes. This way, while the information is
unavailable expert defined behavior can be used as described above. However, as
soon as the new game agents become visible they are automatically and immediately
incorporated into LG zones and included in the strategy. The second approach to
incomplete information is to solve this issue more thoroughly by introducing several
worldviews. The real state of the system is reflected in the True Worldview. In
addition to this true state, each player has its own worldview Playerl Worldview
and Player2 Worldview. Each of these worldviews contains correct information about
its players elements; however, the information about the other player may be
incomplete or false. This allows for a significant advantage over simple visibility
model, as it allows for a player to have some inaccurate data. This may reflect a
situation where an object was visible before, but has moved out of line-of-sight. In
this case, the opposing player does know of the existence of that agent, although not
its exact position. Conversely, inaccurate data may be due to a decoy an element
that is seen by the opposing player as an object of a different type. The strategy is
planned based on the available information. As the information becomes more
accurate and complete, the strategy is constantly updated as in the visibility model.
44


This method can also be expanded from purely reactive approach to a proactive one.
While 2 different worldviews allow us to react to incomplete, outdated, and decoy
data, it does not provide a way to plan for the enemys reaction to it. For instance, we
can launch a decoy, yet in our worldview we see it as a decoy since we have accurate
information about our forces. Therefore, a strategy based on our worldview will not
account for the enemy considering the decoy as a more important object. To allow for
this consideration, we can provide an extra worldview within each players
worldview. Thus, each player has its own worldview with a nested worldview, which
reflects what this player thinks the other player can see (Figure 3.8). This allows a
player to develop strategies with intentional disinformation taking into account
enemys reaction to the false data.
Settings
Filtered LG P2 Moves and
Filtered Discrepancies
LG P1 Moves
True Worldview^
P1 pieces
P2 pieces
- - X
Environment yj
**
J
LG P2 Moves
Filtered LG P1 Moves and
Filtered Discrepancies
Settings
Figure 3.8 Incomplete/false information
45


4. LG Hypergames
The previous chapter provides a comprehensive survey on modeling real-world
Defense Systems employing LG abstract board games approach. A wide range of
conditions and properties can be represented. However, there are still some
limitations in the representation of systems as ABGs. This chapter presents
hypergame approach for modeling an even wider range of increasingly complex real
life problems. First, several issues are presented to motivate this approach. Then,
hypergames are defined and explained. Several critical aspects are elaborated for
clarification. In conclusion, the benefit of this approach is presented by showing how
the more complex systems can be modeled using this method.
4.1. Motivation
Consider the following military scenario. The Red side has decided to invade a
particular island nation X. The Blue side has political obligation to protect X from
external military actions. To accomplish the invasion, the Red side is establishing
supply bridges by air cargo planes and cargo ships. The transport operation is
protected by fighter aircrafts and navy battleships. The resources being transferred
include ground troops, airplanes, and support equipment (e.g. ammunition, fuel, field
equipment). The Blue side plans to engage airplanes based on aircraft carriers, which
must be moved to the area of operations, as well as submarines. In addition, resources
are also to be transferred by air from remote Blue bases to the island to insure
prolonged and continuous defense. The Blue side can also use certain ground and air
elements of the nation X. Satellite based surveillance and weaponry is available, as
well.
This is a very large-scale campaign of several closely interconnected smaller tactical
operations. The entire scenario covers a large portion of the Earth surface due to
remote supply routes. On the other hand, some of the tactical components take place
over areas of the island, which may be only 100 miles across, and require high level
of detail for accurate planning. The duration of individual tactical maneuvers differs
from 30 minutes for some air missions to 12 or more hours for supply transport
bridges. The entire campaign may last several days. The resources involved in the
game range from ground troops to ships and submarines to cargo and fighter planes to
satellites. This represents distribution of speeds from 3 miles per hour to 30 miles per
hour to 1,200 miles per hour to 17,000 miles an hour. Compared to aircraft, the navy
46


elements are 40 times slower, while ground troops are 400 times slower. The types of
individual missions may include air, navy, and ground combat, resource
transportation, and surveillance. There may also be potential effects on politics and
economy. The total number of units involved may be on the order of thousands, while
some missions only require dozens. However, even though the tasks are so widely
varied there is a tight coupling between individual missions. If resource transfer is
interrupted by an enemys combat units, the outcome of another combat mission may
be affected due to lack of necessary supplies. Similarly, a combat operation that
cannot be won may be saved by launching a different operation earlier to cut enemys
resuply chain. All of the missions can be influenced by satellite surveillance.
There are several difficulties of representing such a complex campaign as an abstract
board game. Some operations require representation of the entire planet Earth, yet
high level of detail is required for others. This implies that a very large high-
resolution board is needed. However, the majority of that representation will be
wasted since high level of detail is only needed in specific areas. The game agents
include objects with speeds that differ by the factor of 20 or 200 (even disregarding
the satellites). Representing such wide range of motion patterns on the same board
requires very large reachabilities. The time scales necessary to handle different
missions are also extremely varied. Air combat missions may require 30-second
intervals, while the movement of ground units within this time step is negligible. In
addition, the entire campaign involves thousands of agents out of which only a
small portion is used for any one given mission. Yet, we cannot consider one task at a
time, as they are very closely interconnected. These are just some of the issues, which
motivate the development and application of the hypergame method.
4.2. From ABGs to Hypergames
There is a natural decomposition for such complex systems as the one described
above. This is due to the way human experts in the field approach planning of such
campaigns. The goals are broken down into sub goals, creating tasks and supporting
sub-tasks necessary for each higher-level task. It is natural to model the situation in
the similar manner by modeling each of the tasks as a game. However, as for any
real-world problem, this decomposition usually does not produce completely
independent sub-systems. Therefore, each individual game may not be solved by
itself in isolation. Effects of the interactions with the other sub-problems must be
taken into account. Attempting to solve separate games may produce ineffective,
incomplete, or incorrect solutions. LG hypergames are introduced for the ability to
handle these types of complex systems. A hypergame is a collection of several inter-
linked concurrent abstract board games. It may include a number of different types of
47


ABGs (military, resource allocation, transport, political, economical) with different
boards of various Spatial and Temporal resolutions. A move in one of these ABGs
may change the state of the rest of the ABG included in the hypergame. Intuitively, a
hypergame is a collection of smaller sub-games that are synchronized in time and
space as well as through game agents. Formally, a hypergame consists of a set of
abstract board games (ABGs) and a set of inter-linking mappings (ILMs) for
maintaining inter-connection between them. ILMs map state space from each of the
sub-games to all other sub-games. These state space mappings may include
transformation of locations, time, game pieces, and any additional data.
The closeness of connections created by these mappings can also vary. Subsystems
can be either connected serially corresponding to cause-and-effect relationships, or
concurrently to simulate interweaved effects. The serial interconnections occur for
two systems when the outcome of the first system affects the second system. For
instance, the result of resource resuply mission (mission 1) affects the outcome of a
combat mission (mission2) that requires these resources. In this case, the first mission
takes place before the second mission. However, at the end of the supply mission, the
game objects from game 1 (resources), are transferred to the second game through an
inter-linking mapping of game agents. The outcome of the combat mission is
therefore dependent on whether or not those resources were received and introduced
into game 2 or destroyed and lost in game 1. The second type of interconnection
allows for even closer concurrent interweaved coupling between systems. For
instance, consider a navy battle and an air battle occurring simultaneously. Due to the
difference in spatial and temporal scales and the speed of the objects, these conflicts
may be represented as different games. However, the airplanes must be present in the
navy game just as ships must be present in the air game. In this case, ILM is linking
the representations of the same objects in two or more simultaneous games. These
objects must be synchronized in space and time, so that a movement of a ship on the
navy game is immediately reflected in the air game and a destruction of a ship by an
aircraft in the air game is reflected in the navy game. This is clearly a more difficult
type of interconnections due to a high degree of coupling and requirement for
constant synchronization.
Another important property of hypergames is a possibility for dynamic generation of
new games. For a given collection of ABGs, ILMs can provide the necessary
interconnections. However, this collection may not be fully known in advance. In this
case, it is desirable to have sub-games generated when the need arises. Consider a
navy aircraft carrier battle group relocating to the site of conflict and encountering
enemy air patrol. Since in real-world Defense System such information may not be
available ahead of time, there may be no air combat game set up over the necessary
region. We can resolve this skirmish in the navy game; however, such resolution will
48


not provide very accurate solutions due to lack of sufficient detail. To handle such
situations effectively and precisely, there must be a possibility for a new game of
necessary type to be created and linked to the existing games with ILMs. Such
generation of sub-games can be event triggered and represented as another item in the
set of transitions in the ABG similar to movement or shooting. A shooting transition
uses a precondition target is within weapon range of a game agent to change the
state of the system by removing the target. Similarly, a sub-game generation
transition can use a precondition a game object is present that requires a different
sub-game. In this case, when an enemy plane appears in the navy ABG (from a
different game through an ILM), a new subgame is created automatically.
Another benefit of hypergames is a possibility for using ILM for sharing information
other than just game state data. In particular, strategy information may be inter-linked
as well. Consider the previous example of the simultaneous navy and air combat
games. Standard ILMs insure that both games can see and interact with all of the
present objects including the ones that are controlled by the other game. The strategy
is then generated within each of the sub-games separately based on this complete data
set. However, the strategies are planned independently from each other. Introducing
ILM for strategy information, such as LG zones and trajectories, allows for
cooperative planning. For instance, let us assume that the enemy force consists of 3
ships out of which the air patrol can only destroy 2 in the available time. If the
friendly battle ships can destroy only one specific enemy ship, this information is
essential for the air game to decided which 2 enemy elements to destroy. A strategy
ILM allows for an interchange of zones between the two games. Therefore each game
has information on both zones, which can be combined into a hyper-zone. A strategy
generated based on this hyper-zone can then be used a global hyper strategy for both
sub-games.
4.3. Common Inter-Linking Mappings
As mentioned above, there are several types of inter-linking mappings. The ILMs
needed for a given problem domain depend on the particular problem specifications.
However, there are several types that are needed for most Defense Systems
hypergames spatial, temporal, agent, and strategy ILMs. Spatial ILM is used to
translate between locations of different ABGs. Note, that this is not necessarily a one-
to-one relationship several cells from high-resolution board may be mapped to the
same location on the low-resolution board. The mapping can also be between boards
of different types. For instance, a satellite may be represented on a board of orbiting
positions, yet it may need to be mapped to a location on a 2D board. In such cases the
translation is based on the particular systems needs (e.g. it can be mapped to a cell
49


over which it is currently located). Furthermore, some locations may be impossible to
map onto another games board. The content of such locations is then not inter-linked
between these games.
Temporal ILM is another common type of mappings, which is used to synchronize
the games in time. Different sub-games may have different time steps and may start at
different times. As a result we need to insure that the data is updated in all of the
inter-linked games at the correct turns. For instance, if an air game uses 30 second
intervals and a navy game uses 4 minute intervals, then the positions of ships in the
air game must be updated every 8 game turns, while positions of airplanes are
updated in the navy game on every turn. Spatial and temporal ILMs may be used
together to achieve more continuous synchronization. If the board of the air game
uses resolution 8 times higher than in the ship game, then a ship moving one cell in
the ship game actually moves 8 cells in the air game. With more accurate spatial and
temporal ILMs, we can avoid the ship jumping 8 cells every 8 game turns in the air
game by moving it more smoothly one cell per turn.
Agent ILM takes advantage of the previous two ILMs to synchronize the game pieces
between sub-games. Spatial ILM is used to link the objects location to the right
locations on all of the linked game boards, while temporal ILM insures that the
locations are updated on the correct game turns. Agent ILMs usually contain filtering
so that only the necessary objects are inter-linked. In addition, miscellaneous game
piece data may be interchanged such as weapons load, fuel, and health status.
Finally, even the type of the object may be changed or the object may be replaced by
other objects (e.g. supply ship arriving at the destination in the resource game, may be
transferred over to the combat game as the actual supplies transferred several
aircraft, tanks, etc). The other common type of ILM strategy ILM has already
been presented in the previous section. The particular information being exchanged
depends on the particular problem domain and amount of details required. For
instance, instead of inter-linking actual zones, only a summary or analysis can be
transferred.
4.4. Benefits of Hypergames
The major benefit of using hypergames is the ability to handle very complex tightly
interconnected systems. Consider the campaign presented in Section 4.1. Each of the
sub-tasks can be represented as a separate ABG Red navy bridge, Red air bridge,
Blue air bridge, Disruption of Red navy bridge navy combat, Disruption of Red
navy bridge air combat, Disruption of Red air bridge, island ground combat, island
air support, satellite reconnaissance, etc. Additional sub-games may also be generated
50


as needed. Each of the individual ABGs can use the type of spatial and temporal
discretization that is most suited for the game. Spatial discretizations may include 2D,
3D, Full Spherical, and Orbital boards of different resolutions, while the best time
step is selected based on the size of cells and objects to be represented. Some of the
games may be present through the entire campaign, whereas others are only active for
the duration of a particular mission. Whenever several especially different types of
objects need to be represented within the same mission (such as ships and airplanes),
the game can be split into two or more inter-linked sub-games of the most appropriate
spatial and temporal scales. Appropriate agent ILMs can insure that only the
necessary objects are present in each of the ABGs thus maintaining computational
complexity of individual games at the appropriate level. All through this
decomposition, required interconnections between sub-games can be maintained
using inter-linking mappings within a single global hypergame. Therefore, both serial
and concurrent interweaved effects can be observed and used to generate cooperative
strategies that can be combined to form the global strategy.
51


5. LG Hypergame Framework Specifications
This chapter presents the design of a skeleton framework for a generic software
system implementing LG hypergame for simulation and strategy generation for
Defense Systems. Note that this is not an implementation of such framework for a
particular problem domain. Rather this is a generic design of such framework that can
be adapted and implemented for a specific system. The framework is represented as a
collection of C++ style classes. This representation was chosen due to the wide
recognition of this language as a de-facto standard. Since the majority of the software
designers are familiar with this language, an implementation in any particular
language can be constructed using this presentation as the basis. Furthermore,
widespread understanding of C++ constructs makes it a choice superior to any
pseudo-code, as there is no need to describe particular pseudo-code conventions used.
This design takes advantage of such common computer language concepts as classes,
inheritance, and virtual functions. If an implementation of such framework is desired
in a language without such facilities, certain design changes may be required.
There are several issues that have influenced the format of this framework. Most
applications today are created for systems with highly developed Graphical User
Interfaces (GUI). The usual approach to implementation of such systems is to use
event driven processing, rather than more traditional linear procedural design. As a
result, the framework presented provides functionality to perform experiments in such
environments. Another common trend is to use multi-threaded applications;
consequently the framework allows for both single- and multi-threaded
implementations. However, it should be noted that a multi-threaded application
running on a single processing system might not provide a good performance due to
highly computation intensive nature of this problem. Single threaded event based
approach may provide a better performance due to the entire processor being devoted
to either GUI or strategy computation. On the other hand, most of the LG algorithms
are highly parallel, so an implementation of this framework for a multiple-processor
system can take advantage of this fact.
Another issue pertains to using this framework for hypergames rather than singular
ABGs. Two design alternatives exist implementing multiple games within a single
application or using multiple applications with communication protocols for
interconnections. Each of these approaches has benefits and disadvantages. Single
application allows for easier communication between sub-games using standard
function calls. The games can share common data in memory. All of the games can
52


also be represented in the single application window. On the other hand, for large
scale hypergames, single application containing all of them may not be able to run on
a single machine and there is no inherent way to distribute the computational load
between several computers. A multi-application design allows distribution of a
hypergame over several computers thus increasing performance and the amount of
sub-games that can be handled simultaneously. However, this design requires
implementation of communication protocols in order to achieve interconnection
between games. In addition, due to the overhead of individual applications, less
simultaneous sub-games may be ran on a single computer than with a single
application approach. Due to importance of networks in Defense Systems and in the
modem computing industry, we believe that an approach based on multiple
applications communicating via a common protocol (such as TCP/IP) provides a
more flexible solution.
5.1. Conceptual Modules
The first part of the design is to separate a system for modeling LG hypergame
applications into Conceptual Modules. The software framework for actual
implementations of such systems is presented in the following section. Note, that
there is a correspondence between modules in this section and object classes in the
next.
LG-KERNEL
->LG-ABG
LG-STRATEGY
^MAP-ENGINE
-^TRAJECTORY-GENERATOR
-^ZONE-GENERATOR
^STRATEGY-CONSTRUCTOR
LG-HYPERGAME
LG-W ORLD VIE W
->LG-DOMAIN
LG-INTERFACE
LG-ADAPTER
LG-INTEGRATOR__________________
Figure 5.1 Conceptual framework
The core of the framework is LG-KERNEL, which represented the majority of the
ABG, hypergame, and LG Hierarchy of Language method of problem decomposition.
The other 3 high level modules are LG-INTERFACE, LG-ADAPTER, and LG-
53


INTEGRATOR. LG-INTERFACE is the visualization unit, which is necessary for
any simulation system. Note, that it is desirable to have graphical methods separate
from the core module for higher portability. The framework in the next section
follows the same principle. LG-ADAPTER and LG-INTEGRATOR modules are
introduced to allow other software components to be added respectively above or
below the LG software. Thus, LG-INTEGRATOR can be used conceptually to access
data from a 3rd party database and transform it to the LG format. Similarly, LG-
ADAPTOR can be used to accept requests (e.g. for strategies) from higher-level
software.
LG-FRAMEWORK module can be decomposed into LG-ABG, LG-STRATEGY,
LG-HYPERGAME, LG-WORLD VIEW, and LG-DOMAIN. LG-ABG and LG-
HYPERGAME modules reflect representation of ABGs and hypergames
respectively. LG-WORLD VIEW corresponds to employing several separate
Worldviews to handle incomplete and false information into the system. The purpose
of LG-DOMAIN is to adapt the general methods to the particular application domain
(e.g. air force or navy operations). The core of LG methods is collectively represented
as LG-STRATEGY with sub modules for map, trajectory, zone, and strategy
generation.
5.2. Software Framework
This section contains the diagram for the software framework that can be used to
represent and solve LG hypergame systems. The pseudo header files for these classes
can be found in the appendix. One of the major design objectives of this framework is
to allow for definition of base classes and subsequent expansion into a concrete
application for a specific problem domain. Thus most of the objects are dynamic to
take advantage of potential inheritance and virtual functions. Two nonstandard
constructs are used in the framework class CString for representation of strings, and
CTemplateList for representation of lists of elements of type
element_type\ Both of these classes can be easily implemented in any language.
Figure 5.2 shows the class interaction diagram for this framework. Note, that solid
arrow represents ownership, while dashed lines reflect inheritance.
54


f CDownData'j f CLG Hyper ^ pCListeningSo'j f CUpData 'j
l Socket J l SubGame J l cket J l Socket )
5
CLGSpace
CLGStrategy\
Empty j\
CLGStrategy'V1
Simple J
CLG Board
CLG Piece
CLG Player
CLGHyperGameMaster
CLGGameMaster
CLGInterface
CLG Master
CLGStrategy
( CLGStrategy
GUI

CLGMove
LG
A r CLGMove v Combo "j C CLGMove A f CLGMove A J l PieceMove J lPieceRemovey
J
fCLGMultiZone') Bundle CLGZone > Bundle J ( CLGTraiectorvj__j Bundle J * r \ CLG Mao v J
i i >
CA>-Btr Bis^ Figure 5.2 LG Hypergame classes framework
Class CLGGameMaster is the heart of the framework as it contains all of the other
objects as well as the methods for driving and controlling the simulation. This class
corresponds to the LG-ABG and LG-WORLDVIEW conceptual modules. The
GameMaster contains the board (CLGBoard), the set of game pieces (a list of
CLGPiece), player objects (vector of CLGPlayer), interface object (CLGInterface),
LG Master (CLGMaster), and a list of moves performed so far (a list of CLGMove).
Each of these classes is elaborated below. CLGGameMaster also contains methods
for controlling the simulation. These functions include initialization and simulation
update functions. The most important method of this class is PlayerMoveDone, which
is called by the player strategies to pass the moves for the respective players.
The simulation proceeds as follows. After the GameMaster is initialized, it creates all
other objects in CLGGameMaster::Initialize and CLGGameMaster::
InitializeCreateMainObjects. Then initial position of the game agents is loaded using
CLGGameMaster::LoadPiecePositions. At this point the simulation is ready to begin.
The first players strategys method CLGStrategy::StartYourTum should be called to
55


initiate the calculation of the current move. Based on the type of the strategy class the
appropriate virtual function is accessed. The way the move is generated depends on
the strategy class used. When the move is ready, the strategy can submit it to the
GameMaster by calling CLGGameMaster::PlayerMoveDone. Note, that due to the
design of CLGMove, a collection of concurrent moves can be considered as a single
complex move. Therefore, when move is used in the context of this framework, a
complex move is usually implied. PlayerMoveDone method checks whether both
players have submitted moves. Since this is only the first players move, it should be
stored in myMovesList, and CLGStrategy::StartYourTum called for the second
player. The second players strategy also calls CLGGameMaster:: PlayerMoveDone
to submit its move. However, this time the function can detect that both players have
submitted their moves and CLGGameMaster:: PlayerMoveDone_LastPlayer can be
called. Since this framework simulates Totally Concurrent games, the moves from
both players are executed together at the same time. Additional helper functions such
as CLGGameMaster:: AfterMoveUpdates may be called for additional processing
(such as creating shooting actions based on relative positions of game pieces). At this
point the system has advanced to the next turn and the above procedure is repeated.
As noted above, the way the move is generated depends on the strategy class used.
For CLGStrategyGUI, requests for information are made using
CLGInterface::RequestPiece() or CLGInterface::RequestTargetLocation(). When the
user specifies this information, CLGInterface uses callback functions in
CLGStrategyGUI to return the information respectively CLGStrategyGUI::
PieceSelected and CLGStrategyGUI::SpaceSelected (this is done for even-based GUI
system). Since Totally Concurrent system is simulated, the player can specify several
moves, which will be executed simultaneously. When all desired moves have been
passed to the strategy, CLGStrategyGUI::MoveDone call back function should be
called. At this point the strategy contains all the necessary moves and it can submit
them to the GameMaster by calling CLGGameMaster:: PlayerMoveDone. On the
other hand, CLGStrategySimple can read the moves from an input file based on the
current move number, while CLGStrategyEmpty submits empty moves (dummy
strategy).
The behavior of the CLGStrategyLG is the most complex. When StartYourTum
method is called, this strategy performs the dynamic decomposition employing LG
Hierarchy of Formal Languages. First, LoadGoals function should be called to load
the target information. Then AnalyzeGoals and GenerateZonesForGoals are called to
create an LG MultiZone Bundle, which is a collection of LG zone bundles. As
presented in Chapter 2, each zone bundle is a collection of TrajectoryBundles, which
produce a decomposition for this system. The zones and trajectories are generated
using CLGMaster class which contains methods for generating all of the require LG
56


Languages (maps, trajectories, and zones). The method MakeMultiMoveByZone is
then called to calculate moves for each of the players elements by calling
ChooseBestMove for each of the pieces. This function analyzes LG zones to calculate
the most desirable move. When all of these moves are calculated they should be
passed to the GameMaster using PlayerMoveDone method. Note, that classes
CLGStrategyLG, CLGMaster, CLGMultiZoneBundle, CLGZoneBundle,
CLGTrajectoryBundle, and CLGMap correspond to the LG-STRATEGY conceptual
module.
Most of the system representation (LG-ABG and LG-WORLDVIEW) is contained
within 3 variables in the GameMaster myBoard, myPieceList, and myPlayers. The
board is an object of type CLGBoard which is an enumerated set of objects
CLGSpace. Each space can have certain properties such as its composition or terrain
type. The way the spaces are arranged and stored together to form the board is
application-specific. All of the LG methods, such as trajectory generation, should be
designed so that they can work for any board, which can enumerate its location. This
way the same algorithm will work for a 3D board as for a spherical board. The list of
pieces contains all of the game agents in the game. Each element is stored as an
object of type CLGPiece that contains properties such as location, ID, type, player,
and other domain specific data. Moreover, this class contains its reachability and
strikability relationships both forward and reverse which are required for
generation of maps and trajectories. For Defense Systems with probabilities of kill
(Section 3.4.2), ProbOfKill method can be used to determine the PK against a given
enemy object and which weapon should be used to achieve it. As with CLGBoard, a
particular implementation should attempt to maintain this interface for any derived
class, so that any LG generation algorithms can be reused. The players are
represented as objects of type CLGPlayer within the GameMaster. Each player object
contains its name and the strategy object (of any type derived from CLGStrategy),
which is used to generate, moves for this player.
Another member of CLGGameMaster is an object of type CLGInterface
(corresponding to the LG-INTERFACE conceptual module). All of the user
interaction should be restricted to this class to allow for better portability. For
instance, when an application is to be transferred to a different windowing system
only Interface class should be affected. CLGInterface may contain a wide range of
methods for visualization (displaying moves, strikes, and zones) and user input
(requesting information such as moves for CLGStrategyGUI). The remaining member
of CLGGameMaster is the list of moves. Each list element contains one full game
move that consists of one move for each player. However, each of the players moves
can also be a complex move and contain several individual moves within. This
flexibility can be achieved by using a base class CLGMove with a virtual function
57


ExecuteMove. Then several concrete classes can be derived from it such as
CLGMovePieceMove and CLGMovePieceRemove. When ExecuteMove virtual
function is called on these classes, a piece is, respectively, either moved to a different
position or removed from the board. In addition CLGMoveCombo class is derived
which contains a list of CLGMove objects. The overridden ExecuteMove function
calls ExecuteMove on each of the sub-moves. Note, that each of these sub-moves can
also be a CLGMoveCombo. This approach allows for maximum flexibility for a
Totally Concurrent system as all moves can be easily stored together and executed
simultaneously.
There is one more complex class in the framework CLGHyperGameMaster which
is derived from CLGMaster to allow hypergames to be represented. Any hypergame
application can be both a sub-game in another game and a host for more sub-games.
Therefore, methods for establishing communications to the host game (based on its
network address) and accepting connection requests from lower sub-games are
required. A CUpDataSocket is used for connecting to the higher-level game, while
CListeningSocket is used to monitor for connection requests from lower levels. When
a new sub-game connects, it is added to the list of sub-games of type
CLGHyperSubGame and a CDownDataSocket is created. Note, that the framework
does not specify any information for the socket classes, as they must be based on the
communication protocols used. Each sub-game object may contain any necessary
domain specific data. The rest of CLGHyperGameMaster and CLGHyperSubGame
contain methods and data for temporal and agent synchronization (spatial linking is
considered a part of agent synchronization). Temporal synchronization is maintained
by sending time ticks from the host down to all clients. If the current tick is equal to
the time corresponding to the next move, the client computes and executes the move.
Otherwise, the tick should simply be re-transmitted to its sub-games. When all sub-
games have confirmed the tick, the confirmation is sent back to the host. The client
should send a Timing Request to its host to insure that the time ticks generated
include the ones required for the particular game. The agent update functions are
responsible for performing conversion (agent ILM) between pieces of the lower and
higher level games.
5.3. Using the Framework
The framework presented in the previous section can be used directly to create LG
ABG or hypergame systems by implementing the demonstrated interface in the
desired language on a particular problem domain. However, it may be beneficial to
initially create a set of base classes containing only the essential functionality.
Implementations for the particular problem domains can be then created more
58


efficiently by deriving specific classes from the base set. If inheritance and virtual
functions are used correctly, the common class interfaces can be used to create
generic code. For instance, LG algorithms for generating maps, trajectories, zones, as
well as for analyzing these structures, should be developed so that they can be used
by any application using a board class derived from CLGBoard and piece classes
derived from CLGPiece.
59


6. Future Work
Linguistic Geometry provides a formal approach to decomposition of multiagent
systems into a hierarchy of dynamic subsystems. The methods of Linguistic
Geometry are formalized as a Hierarchy of Formal Languages. The generating
grammars for these languages can be used to construct a variety of structures that
assist in analyzing the problem trajectories, zones, translations, and searches. This
approach can be applied to any system that can be represented as an abstract board
game. However, this class can be expanded by introducing hypergames (Chapter 4).
While hypergames and their applications have been presented, there is still a need to
formalize and define generating grammars for such systems. As mentioned above,
one of the benefits of inter-linking mappings is to allow for interchange of strategy
information between sub-games. In this way, two interconnected zones can be
combined into a hyper-zone a zone that spans more than one game. One of the goals
of the LG approach is to provide a unified mathematical formalization of such
techniques. Thus, an important undertaking would be to define the controlled
grammars for hyper-zones and hyper-trajectories and incorporate them into the
overall LG Hierarchy of Formal Languages. Moreover, additional experiments may
be needed to further refine and generalize these methods.
The design of a skeleton framework for a generic software system employing LG
hypergame ABG design for simulation and strategy generation for Defense Systems
has been presented (Chapter 5). However, it may be advantageous to develop an
implementation of this framework as a collection of LG Foundation Classes in a
particular language for a particular system. While a particular implementation may
not be suitable for all uses due to differences in programming languages and
computer platforms, a generic implementation may be attempted for demonstration
purposes. Furthermore, the choice of a popular platform may provide a wider
acceptance of this foundation library. The main requirement for this task would be to
maintain a high level of abstraction and to provide for a wide range of expansion
through inheritance. The major drawback for such an approach is that a particular
system can be better optimized than a generic implementation. As a result, if
performance is an important criterion, applications derived from these foundation
classes may need to override and optimize some critical algorithms.
60


7. Conclusion
Real-world Defense Systems form an exceptionally difficult problem domain. The natural
approach is to use a game-based approach to solve them. At first glance, this task seems
simple the area of operations can be represented as a gigantic board while various
aircraft, ships, and vehicles are considered the game pieces. However, numerous
difficulties are inherent in such a conversion. Various approaches to overcome some of
these obstacles have been presented. Following this method, real-world Defense Systems
can be converted to abstract board games. By introducing hypergames, the range of
systems that can be modeled is expended even further.
However, these systems remain complex even after conversion to ABG or hypergame
formats. The difficulty is partly due to their size. In contrast to the board games played on
boards with tens of cells, real-world problems usually require the boards of tens of
thousands of cells or more. In addition, a large number of game agents with a wide variety
of behaviors is needed. Finally, these systems are Totally Concurrent by their nature all
elements can move and act at the same time. As a result, conventional approaches do not
provide practical solutions for such problems.
Linguistic Geometry approach provides a way to decompose these systems into
hierarchies of dynamic subsystems by employing a Hierarchy of Formal Languages.
This approach dramatically reduces the complexity of the problems and allows for
satisfactory solutions to be found. Introduction of hypergames further extends this
approach by modeling simultaneous tightly interconnected systems. Inter-linking
mappings, which maintain the coupling between sub-games, insure the inter-game
effects are maintained. They allow for the events of one game to affect the progress of
another game. Finally, LG game strategies can be developed in a way that takes
advantage of such interconnections. Furthermore, the software framework concepts
presented in this thesis demonstrate how such representations of real-world Defense
Systems can be implemented. By following this approach a wide range of particularly
difficult problems can be modeled and analyzed in practice.
My contribution to Linguistic Geometry covers theory and applications. I developed
techniques for effective control of ABGs within hypergames. My research also
allowed to bridge the gap between the theoretical advancements and practical
applications to the area of Defense Systems. In Chapter 3,1 have presented a
comprehensive and detailed study of methods for modeling such complex systems as
ABG so that they can be approached by LG methods. Various difficulties and
61


techniques to overcome them are described in depth. In Chapter 4, this study is taken
a step further by introduction of hypergames. Practical applications of hypergames to
real-world Defense Systems are thoroughly examined and analyzed. Finally, a
flexible framework presented in Chapter 5 shows how these principles can be
implemented in software applications.
LG-FRAME WORK was developed at STILMAN Advanced Strategies. I was
involved in the development of this framework and applications based on this
framework at STILMAN Advanced Strategies. Current implementations include JEC
(JFACC Experiment Commander) for Defense Advanced Research Projects Agency
Joint Force Air Component Commander, LG-EBO (LG for Effect Based Operations),
and LG-PROTECTOR (LG for Cruise Missile Defense).
62


APPENDIX A
LG Hypergame Framework Classes
CLGBoard.h
iifndef _CLGBOARD_H_
idefine _CLGBOARD_H_
include "CLGSpace.h"
idefine DIST_INF 32000
class CLGBoard
{//This class represents the board as
//enumeration of spaces CLGSpace
public:
//The content of this class depends on
//the details of the board for this problem
CLGBoard();
virtual ~CLGBoard();
//The two functions below provide the common
//interface to any board type by requiring
//for an enumeration scheme to exist
//Returns the space at location 'location'
virtual CLGSpace *GetSpace(long location);
//Returns the number of locations on the board
virtual long GetTotalSize(void);
iendif
63


CLGGameMaster.h
#ifndef _CLGGAMEMASTER_H
#define CLGGAMEMASTER H
include
include
include
include
include
include
include
include
include
include
include
"CLGBoard.h"
"CLGPiece.h"
"CTemplateList.h"
"CLGInterface.h"
"CLGPlayer.h"
"CLGStrategyGUI.h"
"CLGStrategySimple.h"
"CLGStrategyEmpty.h"
"CLGMove.h"
"CLGMaster.h"
"CLGMoveCombo.h"
class CLGGameMaster
{//this class is the heart of the framework as it
//contains all of the other objects as well as
//the methods for driving and controlling the simulation.
public:
CLGGameMaster();
virtual -CLGGameMaster();
//Initializes the simulation system
virtual int Initialize(int maxplayers,...);
//Creates all necessary objects for particular ABG
virtual int InitializeCreateMainObjects(void);
//Resets the simulation for a different run
//name can be used as to specify input file/directory
//with initial conditions
virtual int Reset(CString name);
//Loads/Saves position of the game agents
virtual int LoadPiecesPositions(void);
virtual int SavePiecesPositions(void);
//Adds/Removes a game agent to/from the system
virtual int AddPiece(CLGPiece *newpiece);
virtual int RemovePiece(CLGPiece *oldpiece);
//This function is to be called by players'
//strategy to submit their moves for the current
//turn. This function should accumulate these
//moves to create the Totally Concurrent move
virtual int PlayerMoveDone(CLGMove *move);
64


//This function should be called from PlayerMoveDone
//after all players have submited their moves for the
//game turn. These moves should be executed and any
//additional processing done (such as shooting)
virtual int PlayerMoveDone_LastPlayer();
//These functions should perform and additional
//processing that is needed before or after moves
//for the particular problem domain (such as shooting)
//They are to be executed from the above function
virtual int PreMoveUpdates(void);
virtual int AfterMoveUpdates(void);
virtual int AfterMoveUpdates_Shooting(void);
//Helper Function to find a game piece by
//piecelD, as they are used to uniquely identify
//each game agent
virtual CLGPiece *FindPiecebyID(int piecelD);
//For DefenseSystems such functions may be needed
//to determine if the particular agent can stay in
//place or has to remain moving (e.g. airplane)
//It may also be of interest to determine if this
//piece is at a base (e.g. airport)
//Other similar methods may be needed based on the
//problem domain
virtual int CanStaylnPosition(CLGPiece *piece);
virtual int PieceAtBase(CLGPiece *piece);
//Helper functions to access all of the game objects
//Contained in the GameMaster
CLGBoard *GetBoard();
CTemplateList *GetPieceList();
CLGPlayer *GetCurrentPlayer();
int GetCurrentPlayerlndex() ;
CLGPlayer *GetPlayer(int index);
CLGInterface *GetInterface(void);
CLGMaster *GetLGMaster(void);
protected:
//GameMaster contains all of the game
CLGBoard *myBoard;
CTemplateList myPieceList;
CLGInterface *mylnterface;
CLGPlayer **myPlayers;
CTemplateList myMovesList;
CLGMaster *myLGMaster;
objects
//game board
//list of game pieces
//interface module
//vector of players
//stack of moves
//LG tools object
//Status of the system
65


int currentPlayer;
int numOfPlayers;
CLGMoveCombo *currentMultiMove;
int currentMove;
CString gamename;
//Additional information may be needed
//on the specific problem requirements
};
//A single instance of GameMaster should
//and used throughout the application
extern CLGGameMaster *GameMaster;
#endif
//active player
//number of players
//complex TC move
//current move
//simulation name
based
be declared
66


CLGHyperGameMaster.h
iifndef _CLGHYPERGAMEMASTER_H_
#define _CLGHYPERGAMEMASTER_H_
#include "CLGGameMaster.h"
class CListeningSocket;
class CUpDataSocket;
class CDownDataSocket;
class CLGHyperSubGame;
class CLGHyperGameMessage;
struct timing_request
{//Descrbies timing information for a subgame
double timeStart; //time the game was initiated
double timeStep; //frequency of time ticks
};
class CLGHyperGameMaster : public CLGGameMaster
{//This class is defined as an extension of CLGGameMaster
//to allow for hypergames to be modeled
//This class provides methods to communicated with a host
//game and to a number of child sub-games.
public:
CLGHyperGameMaster() ;
virtual -CLGHyperGameMaster();
//Initialization of HyperGameMaster requires network
//information for the host game (if any), and for listening
//to incoming sub-games (if this is a host)
virtual int Initialize(CString host_ip,UINT host_port,UINT
listen_port,
int maxplayers,...);
//This function must be overriden from CLGGameMaster
//so that at the end of the turn the data is synchronized
//with other games both up and down the chains,
virtual int PlayerMoveDone_LastPlayer();
//These functions provide functionallity to connect
//to a host game at give network address; and to listen for
//and accept (or remove) connections from new sub-games,
virtual int ConnectToHostHyperGame(CString server_address,UINT
server_port);
virtual int ListenForHyperSubGames(UINT server_port);
virtual int AcceptNewSubGame(void);
virtual int RemoveSubGame(CLGHyperSubGame *psubgame);
//This function provides a call back for socket classes
67


//to be called when a message from a host game is recieved
virtual void ReceiveHostHyperGameMessage(CLGHyperGameMessage
*info);
//These functions can be called based on messages from sub
//games to add or remove a timing request
virtual void TimingRequestAdd(double start,double step);
virtual void TimingRequestCancel(double start,double step);
//These functions provide Temporal and Agent (Spatial implied)
//synchronisation with sub-games. They must take into account
//the current TimingRequest information as well as any
//necessary agent filters and postion conversion for this game
virtual void SendTimeTickToClients(double time);
virtual void SendAgentUpdateToClients(void);
virtual void UpdateAgentsFromClient(CLGHyperSubGame *psubgame);
public:
//socket&info to listen for new sub-games
CListeningSocket *listeningSocket;
UINT listenPort;
//socket&info for communication with the host game
CUpDataSocket *uplinkSocket;
CString hostIP;
UINT hostPort;
//Lists of existing subgames,
CTemplateList CTemplateList
CString myGameName;
double timeStart;
double timeStep;
double timeLastReceived;
double timeLastAcknowledged;
double timeLastReceivedPending
int amClient;
int amHost;
and their timing requests
> myHyperSubGames;
timingRequests;
//the name of this game
//this game's timing
//requirements.
//status of the timing
//synchronisation
//true if this is a sub-game
//true if can host sub-games
//Additional information may be needed based
//on the specific problem requirements
};
////////////////////////////////////////////////////////////////////
II III
68


class CLGHyperSubGame //rpublic CObject
{//Class that stores necessary data for maintaining
//connection and synchronisation with a sub-game
public:
//Name of the game
CString name;
//socket for communcations with this sub-game
CDownDataSocket *downlinkSocket;
//Timing requirements and current status
double timeStart;
double timeStep;
double timeLastSent;
double timeLastAcknowledged;
public:
CLGHyperSubGame(CString newname);
virtual -CLGHyperSubGame();
virtual void Close();
//A callback function to be called by the socket class
//when a message from this sub-games arrives
void Receive(CLGHyperGameMessage *message);
//This method should perform Agent synchronization
//with this subgame
void SendAgentUpdate(void);
////////////////////////////////////////////////////////////////////
/////
class CLGHyperGameMessage
{//A class to encapsulate messages that can be send between
//games within a hypergame
enum MESSAGEJTYPE {TEXT_MESSAGE = 0, TIME_MESSAGE = 1,
NAME_MESSAGE =2, TIMINGREQUESTADD_MESSAGE=3,
TIMINGREQUESTCANCEL_MESSAGE=4,
CLIENTDISC0NNECTING_MESSAGE=5};
public:
int type;
//addition message data
};
//Socket classes to handle communcation downstream,
//upstream, and listening for incoming connections
69


//Implementation depends on the networking
//libraries available
class CUpDataSocket
{
} ;
class CDownDataSocket
{
class CListeningSocket
{
#endif
70


CLGInterface.h
#ifndef _CLGINTERFACE_H_
#define _CLGINTERFACE_H_
include "CLGPiece.h"
include "CTemplateList.h"
include "CLGZoneBundle.h"
class CLGInterface
{//This class encapsulate any visualization or
//input routines. It should serve as a layer between
//other framework classes and the windowing system used
//for better portability
public:
CLGInterface ();
virtual ~CLGInterface();
//These functions should provide any necessary vizualization
//such as update of displays after a move, removing/adding
//a game agent to a display, showing weapon fire, etc
virtual void UpdateAllViews(void);
virtual void RemovePiece(CLGPiece *piece,int sound=0);
virtual void AddPiece(CLGPiece *piece);
virtual void ShowShot(CLGPiece *piecel,CLGPiece *piece2,int
weap,int sound=l);
//These functions should be used by GUI Strategies
//to request input from the player a piece, or a location,
//as well as to check results&status of the request
virtual void RequestClear();
virtual void RequestPiece();
virtual void RequestTargetLocation(CLGPiece *piece);
virtual CLGPiece *GetActivePiece(void);
virtual int GetRequest(void);
//This method may be implemented to provide a choice of
//strategies&names for players during initalisation
//E.g. GUI, LG, Empty, Simple strategies
virtual void SelectStrategy(CString Splayername,int &stratnum);
//Allows for a game object to be selected as a 'camera'
//piece. So that the visualization modules will follow
//this piece in the display windows
virtual CLGPiece *GetCameraPiece(void);
virtual void SetCameraPiece(CLGPiece *piece);
//Allows for an LG Multi Zone Bundle to be selected
//and accessed in the intrface, so that visualization
//modules can display these zones.
71


virtual CLGMultiZoneBundle *GetMultiZoneForDisplay(void);
virtual void SetMultiZoneForDisplay(CLGMultiZoneBundle *mzbundl)
//Provides a way to ask for the name of the simulation
//when it is restarted, so that initial conditions can
//be loaded based on this name
virtual int Selectlnit(CString previous,CString Snewname);
//Provides capabilities to log any necessary information
//from anywhere in the framework. This log can be displayed
//or saved to file
virtual void AddToLog(CString addstr);
virtual void ClearLog(void);
virtual CString GetLog(void);
//Provides a way to set the title for the display,
//as well as set status parameters (e.g. to be
//displayed on the status bar of the window
virtual void SetStatusDisplay(int i,CString str);
virtual void SetTitle(CString newtitle);
//Provides a generic input function based on prompt
virtual double InputDouble(CString prompt);
//additional input/visualization functions may be needed
//based on problem domain
protected:
//Any necessary variable for storying information
//that may be specified using the methods above
CLGPiece *activePiece; //active piece (for GUI strategies)
int strategyNeeds; //request from GUI strategy
CLGPiece *cameraPiece; //current camera piece
CLGMultiZoneBundle *multizoneForDisplay; //zones
CString LogString; //Log
};
iendif
72


CLGMap.h
#ifndef _CLGMAP_H_
#define _CLGMAP_H_
class CLGMap
{//This class encapsulates an LG MAP object
public:
CLGMap();
virtual -CLGMap();
//Resets the map object to the necessary size
virtual int Reset(long newsize);
public: long size; int *MAP; }; #endif //total size of the MAP //Vector of values of MAP function //for every board location
73


CLGMaster.h
#ifndef _CLGMASTER_H_
#define _CLGMASTER_H_
#include "CLGBoard.h"
#include "CLGPiece.h"
#include "CTemplateList.h"
class CLGMap;
class CLGTrajectoryBundle;
class CLGMultiZoneBundle;
class CLGZoneBundle;
class CLGMaster
{//This class contains a collection of LG tools,
//such as generating algorithms for MAPs, Trajectories,
//Zones, and their analysis
public:
CLGMaster ();
virtual -CLGMaster();
//Any necessary initalization or clean up can be performed
virtual void Initialize(void);
virtual void CleanUp(void);
//Generates a map of given type for a given piece and start
location
virtual void GenerateMap(CLGPiece *piece, long startloc,CLGMap
*lgmap,int type,int strike_type);
//Generates a trajectory of a given type for a given piece, start,
and
//end locations. The strike type can be specified for games with
//strikabilities
virtual void GenerateTrajectoryBundle(CLGPiece *piece, long
startloc, long endloc,CLGTrajectoryBundle *trjbndl,int type,int
strike_type);
//Generates a zone of a given type for a given piece, start, and
//end locations. A target piece can be specified for zones such as
//attack or protect zones
virtual void GenerateZoneBundle(CLGPiece *piece,long startloc,long
endloc,CLGZoneBundle *zonebndl,int type,CLGPiece *targetpiece=NULL);
//May contain necessary zone analysis based on the problem domain
virtual void AnalyzeZoneBundle(CLGZoneBundle *zonebndl);
//Additional generation/analysis methods may be needed based
//on the specific problem domain.
74


protected:
//Generation and analysis may be influenced by some parameters
//based on specific application requirements
double *params;
int num_of_lg_params;
} ;
//Different map, trajectory, zone types may enumerated
#define MAPTYPE_FORWARD 0
#define MAPTYPE_BACKWARD 1
#define MAPTYPE_FORWARD_ATTACK 2
#define TRJTYPE_MOVE 0
define TRJTYPE ATTACK 1
//LG Parameter such as maximum negation level, or
//trajectory horizones may be used
define PARAM_MAX_NEG_LEV 0
define PARAM_MAXTRJHORIZ 1
endif
75


CLGMove.h
iifndef _CLGMOVE_H_
#define _CLGMOVE_H_
#define MOVETYPE_NULL 0
class CLGMove
{//This is a base class for all moves to be used
//within the framework,
public:
CLGMove();
virtual -CLGMove(){};
//Every derived class must override these two
//methods. They either perform the move, or take
//it back. The action performed depends on the
//move type
virtual void ExecuteMove(void){};
virtual void UndoMove(void){);
public:
int classtype; //stores the type of the move
};
#endif
76


CLGMoveCombo.h
# i fnde f _CLGMOVECOMBO_H_
#define _CLGMOVECOMBO_H_
include "CLGMove.h"
include "CTemplateList.h"
include "CLGPiece.h"
class CLGMoveCombo : public CLGMove
{//This move class is derived from CLGMove
//and is used to store complex multi-move
//i.e. moves that consist of several other
//moves
public:
CLGMoveCombo();
virtual -CLGMoveCombo() ;
//these methods execute or take back all of
//moves contained in this move by calling
//ExectueMove or UndoMove of each of those
//sub-moves
virtual void ExecuteMove(void);
virtual void UndoMove(void);
//This method adds another move to the list
//of moves contained in this object
void AddMove(CLGMove move);
protected:
//Stores the sub-moves contained in this object
CTemplateList myMovesList;
};
define MOVETYPE COMBO 1
endif
77


CLGMovePieceMove.h
#ifndef _CLGMOVEPIECEMOVE_H_
#define _CLGMOVEPIECEMOVE_H_
#include "CLGMove.h"
include "CLGPiece.h"
class CLGMovePieceMove : public CLGMove
{//This move class is derived from CLGMove
//to represent a move where a piece moves
//from one location to another
public:
//the move is initialized with the start and
//destination locations
CLGMovePieceMove(CLGPiece *piece,long start,long end)
virtual 'CLGMovePieceMove();
//Execute changes the location of piece to 'end'
virtual void ExecuteMove(void);
//Undo changes the location of piece to 'start'
virtual void UndoMove(void);
//Returns the piece,start, and end locations
//for this move
CLGPiece *getPiece();
long getStartLocation() ;
long getEndLocation();
protected:
CLGPiece *myPiece; //piece moving
long startLocation;//initial location
long endLocation; //target location
} ;
define MOVETYPE_PIECEMOVE 2
endif
78


CLGMovePieceRemove.h
#ifndef _CLGMOVEPIECEREMOVE_H_
#define _CLGMOVEPIECEREMOVE_H_
tinclude "CLGMove.h"
#include "CLGPiece.h"
class CLGMovePieceRemove : public CLGMove
{//This move class is derived from CLGMove
//to encapsulate a game move, when a piece
//is removed (destroyed)
public:
//the move is initialized with the piece
//to be removed
CLGMovePieceRemove(CLGPiece *piece);
virtual 'CLGMovePieceRemove();
//Exectue removes this piece from GameMaster's
//list of active pieces
virtual void ExecuteMove(void);
//Unto places the move back into GameMaster's
//list of active pieces
virtual void UndoMove(void);
protected:
CLGPiece *myPiece; //the piece to be removed
} ;
#define MOVETYPE_PIECEREMOVE 3
#endif
79


CLGPiece.h
#ifndef _CLGPIECE_H_
#define _CLGPIECE_H_
#include "CLGBoard.h"
class CLGPiece
{//This class encapsulates the properties of a game agent
public:
//The piece is initialized with it's properties, such as
//player it belongs to, it's type, ID, etc
CLGPiece(int newplayer,int newtype,CString newstrlD,...);
virtual -CLGPiece();
//These methods provide access to this piece's reachability
//relationship (and reverse reachability relationship)
//by either enumerating all locations reachable from
//a given location, or by checking if end location is
//reachable from startloc
virtual long ReachableEnum(long startloc,int num);
virtual int IsReachable(long startloc,long endloc);
virtual long ReachableFromEnum(long startloc,int num);
virtual int IsReachableFrom(long startloc,long endloc);
//These methods provide access to this piece's strikability
//relationship (and reverse strikability relationship)
//by either enumerating all locations strikable from
//a given location, or by checking if end location is
//strikable from startloc
virtual long StrikableEnumflong startloc,int num,int
strike_matrix);
virtual int IsStrikable(long startloc,long endloc,int
strike_matrix);
virtual long StrikableFromEnum(long startloc,int num);
virtual int IsStrikableFrom(long startloc,long endloc);
//This function returns the PK against the target piece,
//and the type of weapon that should be used to achieve it
virtual double ProbOfKill(CLGPiece *targetpiece, int &best_weapon);
public:
//Various piece properties can be stored
int player; //player it belongs to
int type; //piece type
CString strlD; //piece ID
long location; //current location
int weapons; //vector of weapon loads
80


//Any additional data necessary for the specific
//problem domain.
};
#endif
81


CLGPlayer.h
#ifndef _CLGPLAYER_H_
#define _CLGPLAYER_H_
include "CLGStrategy.h"
class CLGPlayer
{//This class contains any necessary information
//about the player
public:
CLGPlayer();
virtual -CLGPlayer();
//Access function to the player's name
void SetPlayerName(CString newname);
CString GetPlayerName(void);
//Access function to the player's strategy
void SetStrategy(CLGStrategy *newStrategy);
CLGStrategy *GetStrategy(void);
protected:
//player's name
CString name;
//player's strategy may be anything derived
//from CLGStrategy
CLGStrategy *myStrategy;
} ;
#endif
82


CLGSpace.h
#ifndef _CLGSPACE_H_
Idefine _CLGSPACE_H_
class CLGSpace
{//Contains any neccessary information about
//a space(location) on the game board
public:
CLGSpace();
//The space can be initialized with its type
CLGSpace(int newtype);
virtual -CLGSpace();
public:
int type; //the type of the space
//any other data needed for the specific
//problem domain
} ;
#endif
83


CLGStrategy.h
#ifndef _CLGSTRATEGY_H_
#define _CLGSTRATEGY_H_
class CLGStrategy
{//Base class for any player strategies
public:
CLGStrategy(int player,int type);
virtual -CLGStrategy();
//This method should be called by the framework
//at the begining of the game to initialize the
//strategy
virtual void Initialize(void);
//Returns the type of the strategy
virtual int GetTypeO;
//This method should be called by the framework
//to tell the strategy to generate a move
//Once, the move is done it should be submited
//to the GameMaster
virtual void StartYourTurn(void);
protected:
//the player that the strategy belongs to
int myPlayer;
//the type of the strategy
int myType;
#endif
84


CLGStratefiyEmpty.h
ifndef _CLGSTRATEGYEMPTY_H_
idefine _CLGSTRATEGYEMPTY_H_
include "CLGStrategy.h"
define LG_STRATEGY_EMPTY 3
class CLGStrategyEmpty : public CLGStrategy
{//Derived strategy that does not produce moves
public:
CLGStrategyEmpty(int player);
virtual -CLGStrategyEmpty();
//This method should be overriden, to
//submit empty moves to the game master
void StartYourTurn(void);
protected:
};
endif
85


CLGStrategyGUI.h
#ifndef _CLGSTRATEGYGUI_H
Idefine _CLGSTRATEGYGUI_H
Iinclude "CLGStrategy.h"
#include "CLGPiece.h"
iinclude "CLGMoveCombo.h"
idefine LG STRATEGY GUI 0
class CLGStrategyGUI : public CLGStrategy
{//derived strategy that uses user input to produce moves
public:
CLGStrategyGUI(int player);
virtual 'CLGStrategyGUI();
//this method should be overriden, to send input
//requests to the interface
void virtual StartYourTurn(void);
//Callback methods should be provided to accept
//requested data from the interface
void virtual SpaceSelected(long location);
void virtual PieceSelected(CLGPiece *piece);
void virtual MoveDone(void);
protected:
CLGMoveCombo *movecombo;
CLGPiece *activePiece;
};
//contains the complex move
//piece that was last selected
//by the user
lendif
86


CLGStrategyLG.h
ifndef _CLGSTRATEGYLG_H_
define _CLGSTRATEGYLG_H_
include "CLGStrategy.h"
include "CLGPiece.h"
include "CTemplateList.h"
include "CLGMoveCombo.h"
define LG_STRATEGY_LG 2
class CLGMap;
class CLGTrajectoryBundle;
class CLGMultiZoneBundle;
class CLGZoneBundle;
class CLGStrategyLG : public CLGStrategy
{//Overriden strategy that uses LG approach to
//generate moves
public:
CLGStrategyLG(int player);
virtual ~CLGStrategyLG();
//Any necessary initialization should be performed
virtual void Initialize(void);
//This method uses functions below to calculate
//moves using LG strategy generation methods
virtual void StartYourTurn(void);
protected:
//These function may be used to load and analyze game goals
virtual void LoadGoals(void);
virtual int AnalyzeGoals(void);
//This function may be used to generate all needed zones
//based on the game goals
virtual int GenerateZonesForGoals(CLGMultiZoneBundle
*&zonebndlptr);
//This function may be called to generate the full
//multimove (moves for each agent) based on the multizone
virtual CLGMoveCombo *MakeMultiMoveByZone(CLGMultiZoneBundle
*multizonebndl);
//This function may be used to generate the best move for a
//particular game agent based on the zones in the game
virtual void ChooseBestMove(CLGPiece *piecefCLGMultiZoneBundle
*multizonebndl, long Snewloc);
87


protected:
int currentMove; //the index of the current move
//Goal and strategy data needed for the particular
//system
};
#endif
88


CLGStrategySimple.h
ifndef _CLGSTRATEGYSIMPLE_H_
#define _CLGSTRATEGYSIMPLE_H_
include "CLGStrategy.h"
define LG_STRATEGY_SIMPLE 1
class CLGStrategySimple : public CLGStrategy
{//Overriden strategy that produces moves
//by loading them from a script file
public:
CLGStrategySimple(int player);
virtual -CLGStrategySimple();
//This method should be overriden to read in
//move data from the file and generate moves
//for player's pieces based on that data
virtual void StartYourTurn(void);
protected:
//current move can be used to access the right
//moves from the file
int currentMove;
};
endif
89


CLGTrajectoryBundle.h
#ifndef _CLGTRAJECTORYBUNDLE_H
#define CLGTRAJECTORYBUNDLE H
include "CLGBoard.h"
include "CLGPiece.h"
include "CTemplateList.h"
class CLGTrajectoryBundle
{//This class encapsulates a bundle of LG Trajectories
//In a way that is most suited for the problem domain
public:
CLGTraj ectoryBundle();
virtual -CLGTrajectoryBundle();
//The bundle can be reset to the necessary length
virtual int Reset(int newlength);
//Statistics can be calculated for the trajectory
//bundles number of nodes, memory use, etc
virtual long Stat_Nodes(void);
virtual long Stat_Mem(void);
public:
//Trajectory data
long startloc;
long endloc;
long numoftrajectories;
int length;
CLGPiece *piece;
int negationlevel;
//initial location
//target location
//number of trajectories in the
//bundle
//length of trajectories
//piece that the trajectory is for
//level of negation within a zone
//specific trajectory data for a problem domain
};
endif
90


CLGZoneBundle.h
#ifndef _CLGZONEBUNDLE_H_
idefine _CLGZONEBUNDLE_H_
#include "CLGTraj ectoryBundle.h"
#include "CTemplateList.h"
class CLGZoneBundle
{//This class encapsulates a bundle of LG Zones
public:
CLGZoneBundle();
virtual 'CLGZoneBundle();
//Removes all data from the zone
virtual int Reset();
//Statistics number of trajectory bundles,
//memory use, etc
virtual long Stat_TrajectoryBundles();
virtual long Stat_Mem();
public:
//the list of LG Trajectory bundles in this zone
//bundle
CTemplateList trjBundles;
//The main piece of th zones
CLGPiece *mainpiece;
//The target piece of the zones
CLGPiece *targetpiece;
//The type of the zones
int type;
//Any data needed for the problem domain
};
class CLGMultiZoneBundle
{//This class encapsulates a collection of different
//LG Zone bundles
public:
CLGMultiZoneBundle();
virtual 'CLGMultiZoneBundle();
//Removes all data from this object
91