• # Hierarchial AI

Artificial Intelligence

<%Topic="Hierarchal AI"%> Courtesy of Amit Patel

Newsgroup: comp.ai.games
From: andrew@cs.uct.ac.za (Andrew Luppnow)
Date: Fri, 2 Dec 1994 10:10:50 +0200 (SAT)

This document proposes an approach to the problem of designing the AI routines for intelligent computer wargame opponents. It is hoped that the scheme will allow the efficient, or at least feasible, implementation of opponents which are capable of formulating strategy, rather than behaving predictably according to fixed sets of simple rules.

In the text below, "DMS" is an abbreviation for "decision-making-system". I use the term very loosely to denote any programming subsystem which accepts, as input, a "situation" and which generates, as output, a "response". The DMS may be a simple neural network, a collection of hard-coded rules, a set of fuzzy logic rules, a simple lookup table, or whatever you want it to be! It's most important feature is that it must be SIMPLE and TRACTABLE - in particular, it must accept input from a small, finite set of possible inputs and generate output which belongs in a similarly small, finite set of possible outputs.

Some time ago I asked myself how a programmer might begin to implement the AI of a wargame which requires the computer opponent to develop a sensible military strategy. I eventually realized that simply feeding a SINGLE decision-making system with information concerning the position and status of each friendly and enemy soldier is hopelessly inefficient - it would be akin to presenting a general with such information and expecting him to dictate the movement of each soldier!

But in reality a general doesn't make that type of decision, and neither does he receive information about the precise location of each soldier on the battlefield. Instead, he receives strategic information from his commanders, makes strategic decisions and presents the chosen strategy to the commanders. The commanders, in turn, receive tactical information and make tactical decisions based on (1) that information and (2) the strategy provided by the general.

And so the process continues until, at the very bottom level, each soldier receives precise orders about what he and his immediate comrades are expected to accomplish.

The important point is that the whole process can be envisaged in terms of several 'levels'. Each level receives information from the level immediately below it, 'summarises' or 'generalises' that information and presents the result to the level immediately above it. In return, it receives a set of objectives from the level above it and uses (1) this set of objectives and (2) the information from the lower level to compute a more precise set of objectives. This latter set of objectives then becomes the 'input from above' of the next lower level, and so on. In summary: information filters UP through the levels, becoming progressively more general, while commands and objectives filter DOWN through the levels, becoming progressively more detailed and precise.

I decided that this paradigm might represent a good conceptual model for the implementation of the AI procedures in a complex strategy-based game: a "tree of DMS's" can be used to mimic the chain of command in a military hierarchy. Specifically, one might use one or more small, relatively simple DMS's for each level. The inputs for a DMS of level 'k' would be the outputs of a level (k+1) DMS and the information obtained by 'summarising' level (k-1) information. The outputs of the level k DMS would, in turn, serve as inputs for one or more level (k-1) DMS's. Outputs of the level zero DMS's would be used to update the battlefield.

  "Top brass" - fewer, MORE GENERAL options allow lookahead and Level 3 ^ o "what-if reasoning." /|\ / \ Level 2 / | \ o o | /|\ |\ Level 1 | o o o o o \ | / /| | | | |\ Level 0 \|/ o o o o o o o Individual soldiers - V many options, but decision-making is As information simple and doesn't filters UP the attempt "lookahead", tree, it becomes "what-if reasoning", more general. As etc. objectives filter DOWN the tree, they become more specific. 

The main advantage of this scheme is that it allows the "higher levels" of the hierarchy to formulate strategy, without being overwhelmed by the immense and intractably large number of possibilities which the computer AI would have to consider if it possessed only information about individual soldiers. Indeed, at the topmost level, decisions would involve rather abstract options such as

• "direct all military activity towards seizing territory X", or
• "conduct wars of attrition in territories X, Y, and Z", or
• "buy time - stick to diplomacy for the time being", or
• "avoid direct military engagement - concentrate on disrupting enemy supply routes",
• etc.

Under these circumstances, it would be feasible for the computer to attempt a certain amount of "lookahead", or to consider "what-if" scenarios - something which would be out of the question if options were presented in terms of the actions of individual soldiers.

At the time of writing this, I haven't yet had the opportunity to explore an implementation of these ideas in a working game, but if anybody DOES enjoy some practical success with these ideas, I'd be interested in hearing from him/her!

--- Andrew Luppnow

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• 0
• 23
• 0
• 1
• 0

• 9
• 9
• 11
• 11
• 23
• ### Similar Content

• I'm writing a little game for visual deficient people, but I'm having a hard time getting the mouse position. Let me explain :
I need to know where in the table the mouse cursor is, without having a click, and then I want to play a sound. That sound would be different for every position. Any thoughts? Thanks, in advance!
e.g., when the mouse is on the 1st box would be played the audio "a1", when it's on the 2nd box, "a2", and so on.
I tried with:
mouse_x, mouse_y = get_Position() if mouse_x and mouse_y == map[x][y] then if map[x][y] == 0.1 then Audio:play() But it makes a loop and the sound keeps playing forever!
• By Alin N.
Hello there,

Let's say I am looking into designing a game similar to Guitar hero for mobile.
If a player plays niche songs from obscure bands, what is the best way to register his highscore on a global server?
I'm interested in resource efficiency and response times.

Thanks!

• Hi guys,
I've got a little problem which is irritating me as there must be a simple solution but Google isn't necessarily being my friend right now.
In my new game, I've got a set of projectiles for which I need to check for collisions with typically rectangular shapes (but which aren't axis aligned). My general approach is to create an axis aligned bounding box for both the projectile's movement and the target object. If there's a match on the broad phase, then I want to check whether the projectile collides with any of the edges of the collision and then report the first collision (i.e. if the projectile would have gone through multiple lines then I want to know the first collision so I can display the explosion animation in the right place).
I represent my shapes as a series of line segments (there's a future question about colliding with semi-circles and circles, but that's later). Can anyone 'refresh my memory' on being able to test for the interaction of line segments?
Thanks
Steve
• By congard
Hello! When I implemented SSR I encountered the problem of artifacts.
Screenshots here
Code:
#version 330 core uniform sampler2D normalMap; // in world space uniform sampler2D colorMap; uniform sampler2D reflectionStrengthMap; uniform sampler2D positionMap; // in world space uniform mat4 projection, view; uniform vec3 cameraPosition; in vec2 texCoord; layout (location = 0) out vec4 fragColor; void main() { mat4 vp = projection * view; vec3 position = texture(positionMap, texCoord).xyz; vec3 normal = texture(normalMap, texCoord).xyz; vec4 coords; vec3 viewDir = normalize(position - cameraPosition); vec3 reflected = reflect(viewDir, normal); float L = 0.5; vec3 newPos; for (int i = 0; i < 10; i++) { newPos = position + reflected * L; coords = vp * vec4(newPos, 1.0); coords.xy = 0.5 + 0.5 * coords.xy / coords.w; newPos = texture(positionMap, coords.xy).xyz; L = length(position - newPos); } float fresnel = 0.0 + 2.8 * pow(1 + dot(viewDir, normal), 4); L = clamp(L * 0.1, 0, 1); float error = (1 - L); vec3 color = texture(colorMap, coords.xy).xyz; fragColor = mix(texture(colorMap, texCoord), vec4(color, 1.0), texture(reflectionStrengthMap, texCoord).r); } I will be grateful for help!
×