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