Category Archives: Wargames

General Staff Features

General Staff is a direct descendant of the UMS seies which featured a suite of tools that allowed the user to create new maps, armies and scenarios. Our recent survey indicated that 73% of respondents felt that it was either ‘very important’ or ‘somewhat important’ for General Staff to have these abilities, too. Below is a flow chart of the five modules that make up General Staff:

Flow chart of General Staff. From the main screen the user can either create a new map, create a new army, combine a map and two armies into a new scenario or play a previously created scenario. Click to enlarge.

Flow chart of General Staff. From the main screen the user can either create a new map, create a new army, combine a map and two armies into a new scenario or play a previously created scenario. Click to enlarge.

From the Main Menu the user can select:

The Create Map Module

This module provides all the tools that a user needs to create detailed, authentic-looking maps. The are numerous tiles that represent the eight different terrains (field, water, swamp, city, woods, bridge, road, fort). Additionally, the user can sculpt hills and ridges with the AI automatically adding ‘splash contours’. Rivers and roads are added using a Bézier curve tool.

After the map is completed the user can select the amount of ‘dirtying’ (map folds, coffee stains, age stains, etc.) to be added to the map.

The Create Army Module

Armies can be in either an hierarchical format (see below) or a flat format. A flat format is a data structure without layers of commanders. Next week we will be running a user survey to find if you have a preference for hierarchical or flat army unit structures.

Screen shot from UMS II: Nations at War showing a hierarchical army structure. There are four levels of command in this army structure: Army Group, Army, Corps and Division. Click to enlarge.

The original UMS had a flat army structure while UMS II had a hierarchical unit structure.  For both systems an intuitive click and drag interface is provided for quickly creating, editing and saving armies.

Available unit types include: heavy and light infantry, heavy and light cavalry and heavy and light (horse) artillery. Headquarters and courier units are provided for hierarchical army structures.

Create Scenario Module

In the Create Scenario Module a user can combine any two previously created armies with a previously created map to create a new scenario. Mix and match to your heart’s content! The Napoleonic Imperial Guard against the Army of the Potomac’s First Army Corps on the Gettysburg battlefield! The battle of Marengo re-fought with Russian and Austrian troops! Obviously, you can also create historically accurate scenarios, too.

A Wargame 55 Years in the Making (Part 5)

In June, 2009 I successfully defended my thesis and was awarded a doctorate of computer science by the University of Iowa. What followed were some of the most productive years of my professional career. I designed, programmed, project managed and was principal investigator on:

MARS: Military Advanced Real-time Simulator (2009)

OneSAF is the “Semi Automated Forces” wargame / simulator used for training by the US Army. It relies on ‘pucksters’ (see pucksters in this blog) who are usually retired military officers who make all the moves for OPFOR (Opposition Forces), MARS provided an intuitive Graphical User Interface (GUI) for the modification and running of OneSAF scenarios.

Screen capture of the MARS project for the US Army. MARS was a front end to facilitate creating and managing scenarios run on the Army's OneSAF military simulator. Click to enlarge.

Screen capture of the MARS project for the US Army. MARS was a front end to facilitate creating and managing scenarios run on the Army’s OneSAF military simulator. The ‘Magic Bomb’ option is the puckster’s term for ‘magically’ removing a unit from the simulation. Click to enlarge.

CAPTURE: Cognitive and Physiological Testing Urban Research Environment (2010)

While on the surface CAPTURE appears to be a standard ‘shooting gallery’ program it was actually designed to test and store data about how returning veterans saw targets, ‘spiraled in’ on targets and reacted. There were two parts to CAPTURE: the first allowed the tester to set up any particular scenario they wanted (top image, below) and the second part (bottom image, below) was run using a projector, a large screen, an M16 air soft gun with Wii remote and laser mounted to the barrel and an IR camera. CAPTURE was done for the Office of Naval Research (Marines).

Two screens showing the CAPTURE program. The top screen shows the interface for creating target scenarios. The bottom screen is one of the the shooting ranges generated by CAPTURE. Click to enlarge.

Two screens showing the CAPTURE program. The top screen shows the interface for creating target scenarios. The bottom screen is one of the the shooting ranges generated by CAPTURE. Click to enlarge.

NexGEN Behavior Composer (2011)

NexGEN Behavior Composer was another front-end project for OneSAF. Enemy units in OneSAF use scripted AI behavior written in XAML. These AI scripts often contained errors. NexGEN allowed the puckster to select a behavior from a hierarchical tree structure (top image, below) and click and drag it to a composing canvass where a series of behaviors could be joined together (bottom image, below). The artwork for the behaviors was done by my old friend, Ed Isenberg, who has worked with me on games since the ’80s.

Screen shot of NexGEN Behavior Composer which facilitated creating OneSAF behaviors by clicking and dragging behavior icons. Click to enlarge.

Screen shot of NexGEN Behavior Composer which facilitated creating OneSAF behaviors by clicking and dragging behavior icons. This is the hierarchical tree structure of behavior primitives. Click to enlarge.

And example of a OneSAF behavior composed of NexGEN behavior icons. Click to enlarge.

A series of behaviors have been placed together to create a complex behavior (a unit fires, conducts reconnaissance, waits for one minute, moves and then occupies a position). Click to enlarge.

MATE: Machine Analysis of Tactical Environments (2012)

Funded by a DARPA (Defense Advanced Research Project Agency) research grant (W911NF-11-200024) MATE added a new level of battlefield analysis to the TIGER project. Building on the previous nine years of research MATE had the capability of generating a series of ‘predicate statements’ that described the battlefield and then using them to construct a hypothetical syllogism that resulted in a precise Course of Action (COA) for BLUEFOR (US forces). MATE then output this COA as an HTML file and automatically launched a browser to view the COA. MATE was designed to be available to commanders in the field via a small handheld device like a tablet. It was able to perform battlefield analysis in less than 10 seconds.

Consider this real-world situation from the Battle of Marjah:

Given the same data that the commander had in the above video MATE returned this COA (complete with unit paths and ETAs):

MATE's analysis and COA for the Battle of Marjah: a right-flank envelopment maneuver with two infantry platoons while a fixing force of the mortar platoon and a third infantry platoon kept the enemy's attention. Click to enlarge.

MATE’s analysis and COA for the Battle of Marjah: a right-flank envelopment maneuver with two infantry platoons while a fixing force of the mortar platoon and a third infantry platoon kept the enemy’s attention. Click to enlarge.

To see the entire MATE analysis and COA results for the Battle of Marjah click here. (this will load a PDF of MATE’s HTML output on a new tab).


Unfortunately, about the time that I demonstrated MATE to DARPA a series of unfortunate events occurred that were to change my life. The United States Congress passed the Sequestration Transparency Act of 2012. This resulted in a 10% across the board cut in all federal spending. DARPA seemed especially hard hit and they stopped all funding for 4CI (Command, Control, Communications, Computers and Intelligence) research. Only a few years after receiving my doctorate, specifically so I could be the Principal Investigator on government funded 4CI research, I was out of a job.

Without any research funding, and not wanting to relocate I returned to the University of Iowa as a Visiting Assistant Professor teaching Computer Game Design and CS1.  I love teaching. And I am extraordinarily proud of receiving the highest student evaluations in the department of Computer Science but I didn’t have as much strength as I used to have. I found myself out of breath and exhausted after a lecture. And then my kidneys began to inexplicably fail.

In 2013, because of the efforts of superb doctors Kelly Skelly and Joel Gordon at the University of Iowa Hospital, I was diagnosed with a very rare and usually fatal blood disease, AL amyloidosis.  In 2014, thanks to the Affordable Care Act, I was hospitalized for 32 days, my immune system  was purposely destroyed and I received an autologous bone marrow / stem cell transplant. This was followed up by a year of chemotherapy. Being severely immunocompromised I have contracted pneumonia six times in the last two years. Now, against the odds (and I’m a guy that deals with probabilities a lot so I’m being literal) I’ve completely recovered. My kidneys and lungs are permanently damaged but I’m not going to die from this disease. But, it also means I can’t teach anymore, either.

Luckily, I can still sit at a desk and write computer code. General Staff is my return to writing a commercial computer wargame and it will be the first commercial implementation of my tactical AI algorithms that I have been developing since 2003.

I need to produce a game that you grognards want. And, that means next week I will be posting a new gameplay survey to pin down exactly what features you want to see in the new game. As always, please feel free to contact me directly (click here) if you have any questions or comments.

A Wargame 55 Years in the Making (Part 4)

It’s easy to say that you want to create an artificial intelligence that is capable of making human-level tactical decisions but that’s just not how it’s done in academia. First off, the term ‘human-level’ is vague. And then there’s the question of how do you prove your claim? I am indebted to Professor (now Dean) Joe Kearney who proposed the following hypotheses to state my doctoral thesis:

Hypothesis 1:  There is agreement among military experts that tactical situations exhibit certain features (or attributes) and that these features can be used by SMEs (Subject Matter Experts) to group tactical situations by similarity.

Hypothesis 2:  The best match by TIGER (the Tactical Inference Generator  program) of a new scenario to a scenario from its historical database predicts what the experts would choose.

In other words, a preponderance of SMEs will describe a tactical situation in the same way (like ‘Blue has a severely restricted line of retreat’ or ‘Red has anchored flanks’) and a computer program can be written that will describe the same battlefield in the same way as the human experts. And, if TIGER correctly predicts what the SMEs would choose in four out of five tests  (using a one sided Wald test resulted in  p = 0.0001 which is statistically significant) you get a PhD in Computer Science.  By the way, I am also indebted to Dr. Joseph Lang of the Department of Statistics and Actuarial Science at the University of Iowa who calculated the p value.

An example of a tactical description question asked of Subject Matter Experts.

An example of an online survey tactical description question asked of Subject Matter Experts. Image from Sidran’s TIGER: A Tactical Inference Generator. Click to enlarge.

The results of the above survey question: 100% of SMEs agree that RED's left flank is anchored on the Potomac; 79% agree that RED's right flank is anchored on the Antietam. Click to enlarge.

The results of the above survey question: 100% of SMEs agree that RED’s left flank is anchored on the Potomac; 79% agree that RED’s right flank is anchored on the Antietam. Image from Sidran’s TIGER: A Tactical Inference Generator. Click to enlarge.

The descriptors (features or attributes) that were identified by the SMEs included Anchored Flanks, Unanchored Flanks, Restricted Avenues of Attack, Unrestricted Avenues of Attack, Restricted Avenues of Retreat, Unrestricted Avenues of Retreat and Interior Lines. If you are interested in the methodology and algorithms there are links at the end of this post.

Now that the features have been identified (and algorithms written and tested that return a value representing the extent of the attribute) the next step is separating battlefield situations into categories is creating a machine learning classifier program.

There are two kinds of machine learning programs: supervised and unsupervised. Imagine two kinds of fish coming down a conveyor belt with a human being watching this on a TV with two buttons to push. If he pushes the button on the left the fish is classified as, say, ‘tuna’. And if he pushes the button the right the fish is classified as a ‘catfish’. (Why tuna and catfish are coming down this conveyor belt is beyond me, but please stay with the explanation.). In this way the program is taught the difference between a tuna and a catfish (tuna are bigger and longer). This is called supervised learning and is the method used by Netflix and Spotify to select movies or songs that are similar to choices you have previously made. I don’t like supervised systems because they have to be ‘trained’ and, in my opinion, have a tendency to oversimplify classification problems (for example, Netflix movie suggestions are usually awful).

Unsupervised machine learning works differently: there are a number of ‘objects’ that are described with certain ‘attributes’. These objects are presented to the ‘machine’ and the machine separates them into categories based on the likelihood (probability) that they belong together and then displays the results in a hierarchical tree structure. This is how the TIGER program works. The ‘objects’ are battlefield maps and the attributes are things like ‘anchored flanks’ and ‘restricted lines of attack’.

In the image, below, one branch of a tree structure of classified battles (both real and hypothetical) is displayed:

TIGER has classified four battlefield snapshots (Lake Trasimene 217 BC, Antietam 0600 hours, Antietam 1630 hours and a test battlefield submitted to TIGER and the SMEs as being similar. Note how TIGER sees the two Antietam snapshots as 'more similar' and puts them in their own node. Image taken from TIGER: An Unsupervised Machine Learning Tactical Inference Generator. Click to enlarge.

TIGER has classified four battlefield snapshots (Lake Trasimene 217 BC, Antietam 0600 hours, Antietam 1630 hours and a test battlefield submitted to TIGER and the SMEs as being similar. Note how TIGER sees the two Antietam snapshots as ‘more similar’ and puts them in their own node. Image taken from TIGER: An Unsupervised Machine Learning Tactical Inference Generator. Click to enlarge.

The method that TIGER uses to classify battlefields is Gennari, Fisher and Langley’s ClassIT algorithm which is explained in detail in my thesis (link below). Basically, a number of objects are ‘fed’ to the machine (in computer science the terms ‘machine’ and ‘program’ are synonymous) and every time the machine ‘consumes’ an object it asks itself, “does this new object belong in a previously existing category, or a new category, or should I combine two existing categories and add this new object or should I split an existing category and add this new object to one of them? Caveat: just as I explained in the previous blog, computers don’t actually ‘say’ or ‘ask itself’ but it’s easier to explain these processes using those terms. This is unsupervised because there is no human involvement or training. And there is no limit to the number of objects (battlefields) that can be shown to the program. TIGER is constantly learning.

Below is an example blind survey question given to >20 SMEs to validate TIGER’s ability to predict what the majority of SMEs would choose. My good friend, Ralph Sharp, who has worked on art for many of my games did the hypothetical battlefield maps.

An example of the blind survey questions asked of SMEs: is the hypothetical battlefield situation on the top more like the historical battlefield in the middle (Kasserine Pass) or the historical battlefield at the bottom (Gettysburg). Click to enlarge.

An example of the blind survey questions asked of SMEs: is the hypothetical battlefield situation on the top more like the historical battlefield in the middle (Kasserine Pass) or the historical battlefield at the bottom (Gettysburg). Click to enlarge.

The results show a statistically significant number of SMEs are in agreement that the hypothetical battlefield situation most closely resembles Kasserine Pass.

The results from the, above, blind survey question. The SMEs overwhelmingly state that the the battle of Kasserine Pass most resembles the hypothetical battle situation. The TIGER program also chose the 'Kasserine Pass'. Click to enlarge.

The results from the, above, blind survey question. The SMEs overwhelmingly state that the the battle of Kasserine Pass most resembles the hypothetical battle situation. The TIGER program also chose the ‘Kasserine Pass’. Click to enlarge.

Once again this week’s post ran longer than I anticipated. It looks like this story won’t conclude at least until Part 5. It has been said that by the time a PhD dissertation is defended only five people in the world are capable of understanding it. I certainly hope that wasn’t the case with my research. Below is a link to download a PDF of my thesis. Please feel free to contact me directly if I can answer any questions.

Lastly, my good friend Mike Morton, sent me a link to this piece just before my defense:  The “Snake Fight” Portion of Your Thesis Defense. Anybody thinking of getting a PhD should probably read this first (and laugh and then cry).


Papers that were cited in this post with download links:

“Algorithms for Generating Attribute Values for the Classification of Tactical Situations.”

In PDF Format

TIGER: An Unsupervised Machine Learning Tactical Inference Generator.

In PDF Format

 

 

A Wargame 55 Years in the Making (Part 3)

The goal of my doctoral research was to create a suite of algorithms that were capable of making ‘human-level’ tactical and strategic decisions. The first step is designing a number of ‘building block’ algorithms, like the least weighted path algorithm that calculates the fastest route between two points on a battlefield while avoiding enemy fire that we saw in last week’s post. Another important building block is Kruskal’s Minimum Spanning Tree algorithm which allows the computer to ‘see’ lines of units.

I use terms like ‘see’ and ‘think’ to describe actions by a computer program. I am not suggesting that current definitions of these terms would accurately apply to computer software. However, it is simply easier to write that a computer ‘sees’ a line of units or ‘thinks’ that this battlefield situation ‘looks’ similar to previously observed battlefields. What is actually happening is that units are represented as nodes (or vertices) in a a graph and some basic geometry is being applied to the problem. Next week we will use probabilities. But, at the end of the day, it’s just math and computers, of course, don’t actually ‘see’ anything.

Examples of how Kruskal's Minimum Spanning Tree algorithm can be used to separate groups of units into cohesive lines. These figures are taken from, "Implementing the Five Canonical Offensive Maneuvers in a CGF Environment." by Sidran, D. E. & Segre, A. M.

Examples of how Kruskal’s Minimum Spanning Tree algorithm can be used to separate groups of units into cohesive lines. These figures are taken from, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. & Segre, A. M.

When you and I look at a map of a battle we immediately see the opposing lines. We see units supporting each other, interior lines of communication, and lines of advance and retreat. The image, below, shows how the program (in this case, TIGER, the Tactical Inference Generator which was written to demonstrate my doctoral research) ‘sees’ the forces at the battle of Antietam. The thick black line is the ‘MST Spine’. You and I automatically perceive this as the ‘front line’ of the Confederate forces, but this is a visual representation of how TIGER calculates the Confederate front line. Also important is that TIGER perceives REDFOR’s flanks as being anchored (that is to say, BLUE does not have a path to the flanking objective, the tip of the green vector, that does not go through RED Range of Influence, ROI, or Zone of Control).

Figure 1. TIGER screen shot of ‘flanking attribute’ calculations for the battle of Antietam (September 17, 1862, 0600 hours). Note the thick black line that repres ents the MST spine of REDFO R Group 0, the extended vectors th at calculate the Flanking Goal Objective Point and BLUEFOR and REDFOR ROI (red and blue shading). REDFOR (Confederate) has anchored flanks.

TIGER screen shot of ‘flanking attribute’ calculations for the battle of Antietam (September 17, 1862, 0600 hours). Note the thick black line that represents the MST spine of REDFOR Group 0, the extended vector that calculates the Flanking Goal Objective Point and BLUEFOR and REDFOR ROI (red and blue shading). REDFOR (Confederate) has anchored flanks. From, “Algorithms for Generating Attribute Values for the Classification of Tactical Situations,” by Sidran, D. E. & Segre, A. M.

Now that TIGER can see the opposing lines and recognize their flanks we can calculate the routes for implementing the Course of Action (COA) for various offensive maneuvers. U. S. Army Field Manual 3-21 indicates that there are five, and only five, offensive maneuvers. The first is the Penetration Maneuver (note: the algorithms for these and the other maneuvers appear in, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M.) and can be downloaded from ResearchGate and Academia.edu.

The Penetration Maneuver is described in U.S. Army Field Manual 3-21 and as implemented by TIGER. Note how TIGER calculates the weakest point of REDFOR's line. From, "Implementing the Five Canonical Offensive Maneuvers in a CGF Environment." by Sidran, D. E. and

The Penetration Maneuver is described in U.S. Army Field Manual 3-21 and as implemented by TIGER. Note how TIGER calculates the weakest point of REDFOR’s line. From, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M. Click to enlarge.

The next maneuver is the Infiltration Maneuver. Note that to implement the Infiltration Maneuver, BLUEFOR must be able to infiltrate REDFOR’s lines without entering into RED’s ROI:

The Infiltration Maneuver.

The Infiltration Maneuver as described in U.S. Army Field Manual 3-21 and as implemented by TIGER. Note how TIGER reaches the objectives without entering into REDFOR ROI. From, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M. Click to enlarge.

The next maneuver is the Turning Maneuver. Note: in order to ‘turn an enemy’s flanks’ one first must be able to recognize where the flanks of a line are. This is why the earlier building block of the MST Spine is crucial.

The Turning Maneuver as illustrated in U. S. Army Field Manual 3-21 and in TIGER.

The Turning Maneuver as illustrated in U. S. Army Field Manual 3-21 and in TIGER. From, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M. Click to enlarge.

Certainly the most complex offensive maneuver is the Envelopment Maneuver which requires two distinct movements and calculations for the attacking forces: first the attacker must decide which flank (left or right) to go around and then the attacker must designate a portion of his troops as a ‘fixing force’. Think of an envelopment maneuver as similar to the scene in Animal House when Eric “Otter” Stratton (played by Tim Matheson) says to Greg Marmalard (played by James Daughton), “Greg, look at my thumb.” Greg looks at Otter’s left thumb while Otter cold-cocks Marmalard with a roundhouse right. “Gee, you’re dumb,” marvels Otter. In an envelopment maneuver the fixing force is Otter’s left thumb. Its purpose is to hold the attention of the victim while the flanking force (the roundhouse right) sweeps in from ‘out of nowhere’. In the next post I will show a real-world example of an Envelopment Maneuver created by my MATE (Machine Analysis of Tactical Environments) program for DARPA.

The Envelopment Maneuver as shown in U. S. Army Field Manual 3-21 and as implemented in TIGER.

The Envelopment Maneuver as shown in U. S. Army Field Manual 3-21 and as implemented in TIGER. From, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M. Click to enlarge.

Lastly, and obviously the maneuver of last resort, is the Frontal Assault:

The Frontal Assault Maneuver from

The Frontal Assault Maneuver from, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” by Sidran, D. E. and Segre, A. M. Click to enlarge.

All that I’ve done in this post is show some of the things that the TIGER program does. What I haven’t done is show how the algorithms work and that’s because they are described in the papers, below. Obviously, this is a subject that I find pretty interesting, so feel free to ask me questions (you can use the Contact Us page).

It is my intention to incorporate these algorithms into the General Staff wargame. However, I’ve been told by a couple of game publishers that users don’t want to play against a human-level AI. What do you think? If you’ve read this far I would really appreciate it if you would answer the survey below.


Papers that were cited in this post with download links:

“An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps'”

In PDF Format

“Algorithms for Generating Attribute Values for the Classification of Tactical Situations.”

In PDF Format

“Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.”

In PDF Format


 

A Wargame 55 Years in the Making (Part 2)

After The War College I created a couple of non-wargames including Online Mysteries, a massive multiplayer online mystery game that was written for AOL’s WorldPlay. WorldPlay was envisioned to be a 3D online world populated with avatars. It was similar in concept to Second Life but, like a lot of great ideas, was ahead of its time. AOL shut WorldPlay down before most of the games, including Online Mysteries, launched.

Mysteries Unlimited screen shot (Windows) was a massively multiplayer online mystery game created for AOL/WorldPlay (click to enlarge).

Mysteries Unlimited screen shot (Windows) was a massively multiplayer online mystery game created for AOL/WorldPlay (click to enlarge).

By 2000 the game publishing industry  was going through another convulsion of consolidations, buyouts and contractions. Publishers were producing fewer games but the ones that were being created had large teams, long development cycles and massive budgets. The days when an independent developer could pitch a game idea, get an advance and then develop it outside of a publisher’s studio were gone. And the last thing that the big publishers were interested in were wargames.

Over the previous fifteen years I had received inquiries from active duty military and Pentagon project managers about my wargames (known as Commercial Off The Shelf, or COTS, in Pentagon-lingo) and if I would be available to consult on various wargaming projects. Unfortunately, I was lacking a key prerequisite for this: a doctorate. I returned to academia, first to a small local college where I also taught computer game design and in 2003 I was accepted in the computer science PhD program at the University of Iowa (one of the oldest computer science departments in the world).

Before I ever set foot in MacLean Hall (the home of the Department of Computer Science at the University of Iowa) I knew what I would spend the next six years of my life researching and studying: tactical and strategic AI (I would eventually coin the phrase ‘computational military reasoning’ to describe this field).  What I soon discovered was that very little work had ever been done in this research area. What was even more surprising was my discovery that most ‘professional’ military wargames (i.e. wargames used by the US Army, NATO, England, Australia, France, etc.) had absolutely no AI whatsoever. Instead, they employed ‘pucksters’ (usually retired military officers) who made all the moves for OPFOR (Opposition Forces, AKA ‘the enemy’) from another computer in another room.

Pucksters, or humans (usually retired military officers) who make the decisions and moves for enemy (or OPFOR) units during a wargame.

Pucksters are humans (usually retired military officers) who make the decisions and moves for enemy (Opposition Forces = OPFOR) units during a wargame. Note the sign OPFOR & EXCON (Exercise Control) over the puckster’s work station.

To earn a doctorate at an American ‘Research One’ university requires 90 graduate credits (about 30 classes), a GPA > 3.5 (out of 4.0) and passing three major examinations. The first examination on the road to a doctorate is the Qualifying Examination (or Q Exam as everyone calls it). The topic of my Q exam was “An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps’.” This is the area of computer science and graph theory known as ‘least weighted path algorithms’. GPS devices and Map apps use a least weighted path algorithm, except they’re only interested in roads; they don’t consider terrain, slope and other things (that are important to a military unit maneuvering on a battlefield).

Now, if you were to wander into the ivied halls of academic computer science  (like MacLean Hall) and inquire of a tenured faculty member how to calculate the fastest path between two points on a sparse grid they would almost certainly reply to you, “Dijkstra’s algorithm.”  Dr. Dijkstra invented his algorithm in 1956 and it works like this: first calculate the distance between every point on the map and every other point on the map. Then figure out the fastest path. Yeah, it’s that obvious, and painfully slow. In fact, it’s so slow that it isn’t used for GPS or game AI. In computer science we us ‘Big O’ notation to describe how fast (or slow) an algorithm takes to run. Dijkstra’s algorithm runs in O(|V|2). This means that as the number of vertices, or points on the map, (that’s the |V| part) increases, the time it takes for the entire algorithm to complete goes up by the square of the number of vertices. In other words, as the map gets bigger the algorithm gets a lot slower.

Dimdal, and I and most of the gaming world do not use Dijkstra’s algorithm, Instead we use A* (pronounced ‘A Star’) which was designed in 1968 primarily by Nils Nilsson with later improvements by Peter Hart and Bertram Raphael. Below is an example of A* used in General Staff (note that the algorithm doesn’t look at every point on the map, just ones that it thinks are relevant to the problem at hand). A* runs in O(n) time.

A screen shot of A* algorithm running. The green areas are where the algorithm searched for a least weighted path, the brown line is the shortest path (mostly following a road).

A screen shot of A* algorithm running. The green areas are where the algorithm searched for a least weighted path, the brown line is the shortest path (mostly following a road).

Graph showing the difference between Dijkstra's algorithm and the A* algorithm. The blue line that increases rapidly shows that Dijkstra's algorithm gets much slower as the map gets bigger. A* is not affected as much by the size of the map.

Graph showing the difference between Dijkstra’s algorithm and the A* algorithm. The blue line that increases rapidly shows that Dijkstra’s algorithm takes much more time as the map gets bigger. A* (the green line) is not affected as much by the size of the map.

As part of my research into computational military reasoning I made further modifications to A* to take into effect the slope of the terrain (which can affect speed of some units), the range of enemy units (OPFOR ROI, e.g. areas controlled by enemy artillery) and to avoid enemy line of sight (LOS). My MATE (Machine Analysis of Tactical Environments) project used all of these options:

A slide from my presentation to DARPA showing how my modified A* avoids enemy range of weapons.

A slide from my presentation to DARPA showing how my modified A* avoids enemy range of weapons. The likelihood of taking casualties is indicated by the darkness of the red coloring.

While working on General Staff I came up with a new optimization of the A* algorithm which I’ve called EZRoadStar. EZRoadStar first looks at the roadnet and attempts to utilize it for rapid troop movement. Only after ascertaining how far using roads will get it to its goal does the algorithm look for nonroad paths. EZRoadStar is much faster than traditional A*; especially for wargames and military simulations.

An example of the EZRoadStar least weighted path algorithm. What's the fastest way point A to point B (the yellow line)? Taking the road, of course. This algorithm looks at a battlefield like a commander and utilizes the roadnet first before looking at other options. Click to enlarge.

An example of the EZRoadStar least weighted path algorithm. What’s the fastest way from point A to point B (the yellow arrow)? Taking the road, of course. This algorithm looks at a battlefield like a commander and utilizes the roadnet first before looking at other options. Click to enlarge.

Well, this wargame may be 55 years in the making and it looks like describing some of the key things that went into it may take almost as long. Clearly, I’m going to have to continue this story with yet another post. We’ve just barely scratched the surface of my work on wargame AI. The next installment will (hopefully) cover algorithms for ‘the five canonical offensive maneuvers’ (i.e. The Envelopment Maneuver, The Turning Maneuver, Penetration, Infiltration and Frontal Assault. These are the algorithms that are ‘under the hood’ of General Staff. If any of my readers would like to know more about these topics (links to my published papers on the subject or whatever) please drop me a line at Ezra [at] RiverviewAI.com.