Category Archives: Artificial Intelligence

Layers: Why a Military Simulation Is Like a Parfait

Detailed military simulations and wargames are made up of layers1)Here is the obligatory link to Shrek and the layers, onions and parfait bit. by necessity. Layers keep simulation designers and users from being overwhelmed by oceans of data. In General Staff every scenario (battle) is made up of these layers (some are optional):

The Background Image. Ironically named because even though it’s underneath all the other layers it’s makes up most of what the user sees of the battlefield. However, the background image contains no data that is actually used by the computer; it is completely ‘eye candy’ for the user. That said, us humans get most of our data from looking at this map (we can make sense of the hills, roads, forests, rivers, etc.). But that’s not how computer vision works (see below).

The Background Image for the Antietam scenarios. Click to enlarge.

This map came from the Library of Congress (here). The Library of Congress is a great place to get royalty-free battlefield maps from American history. Personally, it’s exactly these old maps that inspired me to create General Staff. There is, however, one problem: these old maps are just not ‘GPS accurate’. That is to say, even though the General Staff Map Editor allows the user to directly import Google Maps elevation data, it won’t align properly with maps made over a hundred years ago without GPS data. That means the scenario designer will have to enter the elevation data by hand and not import it from satellite data.

The Terrain Layer. This layer is a visual display of what the computer ‘sees’ of the terrain: forests, water, fences, hedges, walls, swamp, mud, field, city, road, river, fortification, buildings (seven kinds), fords, and bridges.

The terrain layer for Antietam. Click to enlarge.

The Terrain Drawing tab (right). This is one of the tabs in the General Staff Map Editor (click here to go to the online Wiki for more detailed information). Click on the desired terrain type and then draw with either the mouse or a digitizing tablet and pen. I have absolutely no drawing abilities, but I’ve watched actual artists create a map using a digitizing tablet and pen in about 30 minutes. If you’re drawing a river, the harder you press with the digital pen the wider the river gets.

There are three ways you can input water and roads in the Map Editor: mouse, digitizing tablet and XAML code. For me, because I have very limited drawing abilities, I find using XAML code the easiest (below):

The Road Net Layer (optional). This image (below) was created in a paint program (PhotoShop, though any paint program that you’re comfortable with will work just fine). It was then imported into Inkscape (free download here) and exported as XAML.

The road net at Antietam. Click to enlarge.

The Water Layer (optional). Like the Road Net image (above) this was created in a paint program (PhotoShop). It was then imported into Inkscape (free download here) and exported as XAML.

Antietam water map. Click to enlarge.

The Elevation Layer. There are four ways to input elevation in the General Staff Map Editor: you can draw with the mouse, use a digitizing tablet and pen, input elevation data directly using Google Earth and directly importing a BMP image.

Antietam height map. Click to enlarge.

The Slope Layer. This layer shows the extrapolation of slopes from the elevation layer (above). Combined with the Background, and Elevation layer it can produce a dramatic 3D effect. See Trenton, below.

The Slope Layer for Antietam. Click to enlarge.

Blending Multiple Layers. This is a blend of the Background, Elevation, Terrain and Slope layers. The user can set the blend values (see screen shot from the Map Editor, right).

 

Antietam with background, elevation, slope and terrain blended. Click to enlarge.

The Places and Victory Points Layer. This layer allows you to set certain locations as Victory Points or Placenames. A Placename is a descriptive text placed on the map that has no importance to the simulation; e.g. labeling the Potomac River (below).

The Victory Point and Placenames Layer. Click to enlarge

The Units Layer. This is a visual representation of the current simulation state showing unit locations. This information may be filtered by Fog of War (FoW) and what units can observe other units (both friend and foe) using 3D LOS (see below):

The Units layer for Antietam. Note: reinforcements are displayed on this layer even though they won’t enter the scenario until later. This screen shot was taken from the Scenario Editor. Click to enlarge.

The Fog of War Layer. This layer is a visual representation of what can be observed from any point on the battlefield; in this case, the 3D LOS view from the Pry House (McClellan’s Headquarters at Antietam).

Antietam with complete Fog of War displayed for McClellan’s HQ at the Pry House. Click to enlarge.

The AI Layer. This layer is a visual representation of the output of a number of AI algorithms including Range of Influence (ROI), battle groups, and flank units. This is how the AI ‘sees’ the battlefield.

The AI Layer displays Red and Blue Range of Influence. Click to enlarge.

Trenton. I recently began working on a Trenton scenario. One of the best places to begin a search for a contemporary map of an American battle is the US Library of Congress. That is where I found the extraordinary campaign map for Trenton published in 1777.

From the US Library of Congress (published 1777, London). Click on the map to go to source.

From the above original map, Ed Kuhrt created an elevation or height map (see above) in PhotoShop. From that Elevation Layer we extrapolated the slopes and displayed them using an algorithm created by Andy O’Neill. When blended together the result is striking:

Screen shot of the Trenton map in the General Staff Map Editor. Note how the blending of the slope layer with the elevation and original background create a 3D effect. Click to enlarge.

References

References
↑1 Here is the obligatory link to Shrek and the layers, onions and parfait bit.

The State of the Game

Grant’s Overland campaign that began at the Wilderness and ended at Petersburg. It can be argued that Grant did not win one battle but, clearly, achieved a great strategic victory. This was the beginning of the end for Lee’s Army of Northern Virginia and the beginning of the end of the American Civil War. Map by Hal Jespersen (www.posix.com/CW), found on Wikipedia. Click to enlarge.

I had just sat down to write this blog when a derecho,1)Ironically, the first person to use the Spanish word “derecho” to describe this type of storm was Gustavus D. Hinrichs, a German immigrant who settled in my hometown of Davenport in 1861. with wind speeds that peaked at 117 mph, flattened much of Iowa and dropped a hundred year old maple tree on my ’98 mustang. We also lost power and internet for a week. I spent much of that time reading old favorites including Horace Porter’s Campaigning with Grant. Porter, who served on Grant’s staff during 1864-5, provides a first person account of many extraordinary events from the start of the Overland Campaign to Lee’s surrender at Appomattox. Admittedly, the 19th century prose does get a bit flowery at times, but the he was actually there when it happened aspect of this memoir makes it invaluable.

I was struck by this passage from the beginning of the campaign and how it felt like what I wanted to write about to explain where we are on completing General Staff:

“[Grant] said,… “The only time I ever feel impatient is when I give an order for an important movement of troops in the presence of the enemy, and am waiting for them to reach their destination. Then the minutes seem like hours.” – Campaigning with Grant

At this point Grant was now General in Chief, commander of all U. S. armies including the Army of the Potomac. Orders had been issued and every U. S. army was to be on the march at this very moment and there was nothing more that Grant could do. Grant was confident that his plan would ultimately be successful. If we look at the map of the Overland campaign (above) we see that Grant wanted to fight Lee in the open. If that was not possible he would move by his left and Lee would have to respond. Eventually, Lee would be forced to entrench around Richmond and Petersburg and Grant would trap him. It was like a chess master looking sixteen plies ahead: there was nothing Lee could do, his defeat was inevitable.

There are two programmers coding General Staff:  Andy O’Neill is working on the actual game from my design documents and me (I’m working on AI).  Andy specializes in Microsoft Windows Presentation Foundation (WPF) development of business applications. General Staff is a wargaming system that utilizes multiple interlocking programs (like Microsoft Office) so it is logical to use Microsoft WPF for development. Andy is literally a  Microsoft gold medal developer. Andy also specializes in the Model-View-View Model (MVVM) development technique. This is a method commonly used in Microsoft business applications.  Despite repeated efforts to learn MVVM I confess that I am just an old coder, set in my ways, and I can’t get it. While Andy and I both write in the C# programming language, it’s best if I do not muck about with Andy’s code. What I do is write AI routines in C# and Andy imports them into his code.

In early July or late June Andy, who lives and works in Liverpool, England, fell very ill with an undefined infection. He became very dizzy and nauseous and was unable to write any code for over a month. Andy reports that he is now, “sort of…nearly…better.”

And this is why I felt like Grant on May 2, 1865: there wasn’t anything I can do to move the game forward. I’m working on the AI Engine and researching battles, maps and OOBs but that’s it. And then we lost power and the internet for a week.

My wife says that when I can’t work I get, “very testy.” Grant, however, outwardly was imperturbed. This is how Porter describes him this day:

General Grant Whittling Again – Civil War Reenactor Kenneth Serfass portraying Lt. General Ulysses S. Grant whittling at the site of Grant’s headquarters knoll at the Battle of the Wilderness. 150th Anniversary of the Battle of the Wilderness, 1864-2014

“… most of the day he sat upon the stump of a tree, or on the ground, with his back leaning against a tree. The thread gloves2)It is assumed that Mrs. Grant gave him the gloves. Grant wore them out whittling and never wore them again. remained on his hands, a lighted cigar was in his mouth almost constantly, and his penknife was kept in active use whittling sticks. He would pick up one small twig after another, and sometimes holding the small end away from him would rapidly shave it down to a point, at other times he would turn the point toward him and work on it as if sharpening a lead-pencil, then he would girdle it, cut it in two, throw it away, and begin on another.” – Campaigning with Grant

So, in summation, almost nothing has been done in the last six weeks to move development of the actual game (what we call the Game Engine application) forward. For this I can only sincerely apologize and repeat what you know: there’s only two of us coding it and when the lead coder falls ill everything stops.

What’s Going on with the Scenario Editor?

There are three stand alone programs that create data files used by the General Staff Game Engine: The Army Editor, the Map Editor and the Scenario Editor. The first two have long been available to early backers. What’s holding up the release of the Scenario Editor?

The Scenario Editor is actually done, and has been completed for some time. I use it to create the scenarios that you’ve seen and that I use to test the AI:

Screen shot of Antietam with battle groups, range of influence and objectives displayed. Click to enlarge.

So, why haven’t we released it? Because as we (that is to say, Andy) works on the Game Engine we discover that we need to make changes in the data files. For example, I left out the time it takes for a unit to change formations. To correct this, we need to add that value to the scenario data files and that, in turn, means a change to the Scenario Editor, itself. And, even worse, it means that previously created scenario files are no longer compatible and have to be redone. Andy, specifically, said he didn’t want to make the Scenario Editor available to early backers for this very reason: you could lose your earlier work.

So, in conclusion, again please allow me to apologize for these delays. There will inevitably be more delays before General Staff is completed. But, like Grant at the beginning of the Overland campaign, I am supremely confident in our inevitable success. Grant famously said at this time, “I propose to fight it out on this line if it takes all summer.”  It actually took all summer, fall, winter and next spring before Lee surrendered. But the ultimate success of the campaign was never in doubt.

And, as always, please feel free to email me directly at Ezra [at] RiverviewAI.com.

References

References
↑1 Ironically, the first person to use the Spanish word “derecho” to describe this type of storm was Gustavus D. Hinrichs, a German immigrant who settled in my hometown of Davenport in 1861.
↑2 It is assumed that Mrs. Grant gave him the gloves. Grant wore them out whittling and never wore them again.

Feeding the Machine

The famous Turing Machine1)It was first described in Turing’s, “On Computing Machines with an Application to the Entscheidungsproblem,” in 1937 which can be downloaded here: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf. Also a very good book on the subject is Charles Petzold’s, “The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine.” was a thought experiment and, until recently did not physically exist 2)Yes, somebody has built one and you can see what Turing described here: https://www.youtube.com/watch?v=E3keLeMwfHY . When computer scientists talk about machines we don’t mean the, “lumps of silicon that we use to heat our offices,” (thanks Mike Morton for this wonderful quote), but, rather, we mean the software programs that actually do the computing. When we talk about Machine Learning we don’t think that the physical hardware actually learns anything. This is because, as Alan Turing demonstrated in the above paper, the software functions as a virtual machine; albeit, much more efficiently than creating a contraption with pens, gears, rotors and an infinitely long paper strip.

When I talk about, “feeding the machine,” I mean giving the program (the AI for General Staff is called MATE: Machine Analysis of Tactical Environments and the initial research was funded by DARPA) more data to learn from. Yesterday, the subject at machine learning school was Quatre Bras.

Screen shot of the General Staff AI Editor after analysis of Quatre Bras and calculating the flanking Schwerpunkt or point of attack (blue square).  Click to enlarge.

The MATE tactical AI algorithms produce a plan of attack around a geographic point on the battlefield that has been calculated and tagged as the Schwerpunkt, or point where maximum effort is to be applied. In the above (Quatre Bras) scenario the point of attack is the extreme left flank of the Anglo-Allied (Red) army. I apply the ‘reasonableness test’ 3)Thank you Dennis Beranek for introducing me to the concept of ‘reasonableness test’. See https://www.general-staff.com/schwerpunkt/ for explanation and think, “Yes, this looks like a very reasonable plan of attack – a flanking maneuver on the opponent’s unanchored left flank – and, in fact, is a better plan than what Marhshal Ney actually executed.

It would be good at this point to step back and talk about the differences in ‘supervised’ and ‘unsupervised’ machine learning and how they work.

Supervised machine learning employs training methods. A classic example of supervised learning is the Netflix (or any other TV app’s) movie recommendations. You’re the trainer. Every time you pick a movie you train the system to your likes and dislikes. I don’t know if Netflix’s, or any of the others, use a weighting for how long (what percentage watched over total length of show) watched but that would be a good metric to add in, too. Anyway, that’s how those suggestions get flashed up on the screen: “Because you watched Das Boot you’ll love The Sound of Music!”  Well, yeah, they both got swastikas in them, so… 4)Part of the problem with Netflix’s system is that they hire out of work scriptwriters to tag each movie with a number of descriptive phrases. Correctly categorizing movies is more complex than this.

Supervised machine learning uses templates and reinforcement. The more the user picks this thing the more the user gets this thing. MATE is unsupervised machine learning. It doesn’t care how often a user does something, it cares about always making an optimal decision within an environment that it can compare to previously observed situations. Furthermore, MATE is a series of algorithms that I wrote and that I adjust after seeing how they react to new scenarios. For example, in the above Quatre Bras scenario, MATE originally suggested an attack on Red’s right-flank. This recommendation was probably influenced by the isolated Red infantry unit (1st Netherlands Brigade) in the Bois de Bossu woods.  After seeing this I added a series of hierarchical priorities with, “a flank attack in a woods (or swamp) is not as optimal as an attack on an exposed flank with clear terrain,” as a higher importance than pouncing on an isolated unit.  And so I, the designer, learn and MATE learns.

My main concern is that MATE must be able to ‘take care of itself’ out there, ‘in the wild’, and make optimal decisions when presented with previously unseen tactical situations. This is not writing an AI for a specific battle. This is a general purpose AI and it is much more difficult to write than a battle specific AI. One of the key aspects of the General Staff Wargaming System is that users can create new armies, maps and scenarios. MATE must make good decisions in unusual circumstances.

Previously, I have shown MATE’s analysis of 1st Bull Run and Antietam. Below is the battle of Little Bighorn in the General Staff AI Editor:

The battle of Little Bighorn in the General Staff AI Editor. Normally the MATE AI would decline to attack. However, when ordered to attack, this is MATE’s optimal plan. Click to enlarge.

I would like to expose MATE to at least thirty different tactical situations before releasing the General Staff Wargame. This is a slow process. Thanks to Glenn Frank Drover of Forbidden Games, Inc. for donating the superb Quatre Bras map. He also gave us maps for Ligny and Waterloo which will be the next two scenarios submitted to MATE. We still have a way to go to get up to thirty. If anybody is interested in helping to create more scenarios please contact me directly.

References

References
↑1 It was first described in Turing’s, “On Computing Machines with an Application to the Entscheidungsproblem,” in 1937 which can be downloaded here: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf. Also a very good book on the subject is Charles Petzold’s, “The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine.”
↑2 Yes, somebody has built one and you can see what Turing described here: https://www.youtube.com/watch?v=E3keLeMwfHY
↑3 Thank you Dennis Beranek for introducing me to the concept of ‘reasonableness test’. See https://www.general-staff.com/schwerpunkt/ for explanation
↑4 Part of the problem with Netflix’s system is that they hire out of work scriptwriters to tag each movie with a number of descriptive phrases. Correctly categorizing movies is more complex than this.

Schwerpunkt

I first encountered the German word Schwerpunkt in Major General F. W. von Mellenthin’s Panzer Battles many years ago. The word has a number of definitions but, for our purposes, we’ll use, “the point of maximum effort;” or the point where we should hit the enemy’s lines with all our strength. For von Mellenthin it was the point where his panzers would smash through the Allied lines in the 1940 Western Front blitzkrieg.

Many years later, when I was working on my doctoral research on tactical AI, I realized that calculating the Schwerpunkt was crucial for any offensive algorithm (it’s also a good thing to know your weak points when planning a defense). On every battlefield there is at least one Schwerpunkt but calculating that point first involves numerous algorithms to analyze the terrain, elevation, unit positions, 3D Line of Sight (3DLOS) and range of influence (ROI) of these units.

TIGER1)Tactical Inference GEneratoR was the program created from my doctoral research that performed battlefield analysis. Later, with a DARPA grant, it was expanded into MATE 2)Machine Analysis of Tactical Environments. One problem, that was discussed in my last blog post, was that after analysis MATE would come to the conclusion that some forces should not attack in specific situations (for example, Lee at Gettysburg). However, for General Staff,  we need an AI that will attack when we want it to.

My solution was to create the General Staff AI Editor (this may be rolled into the General Staff Scenario Editor for convenience) which allows the scenario designer to specify objectives for each army’s battle groups.

Screen shot of Antietam with battle groups, range of influence and objectives displayed. Blue indicates areas within Blue forces Range of Influence (ROI); meaning that their weapons can fire on these locations. The darker the color the more firepower they can concentrate at that location. The same is displayed for Red forces. Note that areas under both Red and Blue ROI cancel each other out (based on accuracy and firepower). Click to enlarge.

This output is just for debugging and won’t be displayed during the actual game but you can see how MATE made it’s decision to place the Schwerpunkt for Blue Battle Group #1. MATE starts by making a series of statements. These are  similar to predicates used in predicate logic but every statement is known to be true. MATE then constructs hypothetical syllogisms by combining these statements. In the series, below, MATE identifies the opposing force that must be dealt with to achieve its assigned objective, does strength analysis of the two opposing forces, determines if the defender has anchored or unanchored flanks, calculates the slope of the attack, etc., and then calculates the Schwerpunkt after analyzing the enemy’s flank positions, supporting forces and if the attacker has an unrestricted avenue of attack.

Screen shot of the output from the General Staff AI Editor showing the analysis for Blue Battle Group #1 at Antietam. The top section, “Statements about the tactical situation,” are the results of MATE algorithms that analyze unit positions, strengths, 3D Line of Sight, etc. The bottom section, “Tactical Analysis,” are conclusions drawn from the above statements. Click to enlarge.

The Schwerpunkt for Blue Battle Group #1 is displayed on the map as a blue square.

Screen shot from the General Staff AI Editor showing the location of Blue Battle Group #1s schwerpunkt (marked by a blue square). Click to enlarge.

I have written before 3)https://www.general-staff.com/antietam-ai/ about the American Civil War battle of Antietam and I frequently use it as a ‘baseline’ for my AI work. This is because I am very familiar with the battlefield having walked it numerous times, as well as having studied it in depth. So, I know the area that MATE has indicated where Blue Battle Group #1 (Union I and XII corps) should concentrate their attack: west of the West Woods at J. R. Jones’ Confederate Division’s exposed left flank.

The original caption, “Photograph shows four Union soldiers looking at dead Confederate soldiers on Miller Farm, looking toward the west woods on September 19, 1862.” From the US Library of Congress. Click to enlarge.

Many years ago I had an accountant who would apply what he called, ‘the Reasonable Test’, to Profit & Loss statements. He would look at the P&L statement and ask out loud, “does this look reasonable?” Is this a reasonable number for income? Is this a reasonable number of expenses? So, I ask, “is this a reasonable place for the Union I Corps to attack at Antietam?” And, I have to conclude, yes, it is. I can’t mathematically prove that this is the best place to attack; but I think it’s pretty good. In general, MATE will always attempt to outflank enemy positions and, I think, this is a very solid approach to offensive tactics. Indeed, I’m reminded of Wellington’s comments about Napoleon’s tactics at Waterloo, “Never did I see such a pounding match. Both were what the boxers call gluttons. Napoleon did not manoeuvre at all. He just moved forward in the old style, in columns, and was driven off in the old style.” 4)“Wellington: The Years of the Sword,” p, 488 Longford, Elizabeth For MATE, pounding is a last resort. This is the case at Burnside’s Bridge:

MATE analysis for Blue Battle Group #4 (Union IX Corps) at Antietam. Note that MATE recognizes the choke point (Burnside’s Bridge) and orders up an artillery barrage before the assault. Click to enlarge.

In the Tactical Analysis section (above) look at statement #8: “Blue Battle Group #4 has a severely restricted Avenue of Attack (Bridge).” MATE recognizes that there is no way to maneuver around to the objective (Snavely’s Ford is not on this battle map so there really isn’t any other option except over the bridge). Frontal Assault is MATE’s maneuver of last resort. Consequently, MATE first orders up the artillery to positions within distance (> 50% accuracy as set in the General Staff Army Editor for these units) and with a clear Line of Sight (3DLOS) of the target. MATE will order the artillery to bombard enemy forces that control the bridge for an hour before ordering an infantry assault).

Let’s look at MATE’s analysis of First Bull Run:

Screen shot from the General Staff AI Editor showing objective set for Union forces at the battle of First Bull Run. The Union Schwerpunkt is the blue square to the west of the Confederate left flank. Click to enlarge.

Here Blue Battle Group #2 (Heeintzelman’s and Hunter’s Union divisions) are assigned the objective of capturing the Henry House Hill (historically accurate). MATE set’s their Schwerpunkt to the west of the Confederate left flank. This is very close to Union commander McDowell’s original strategy. Again, MATE will attempt to outflank strong positions rather than attack them directly. MATE is not a pounder.

MATE’s analysis for the Union’s right flank: they have an unrestricted Avenue of Attack and Red’s left flank is unanchored. Click to enlarge.

MATE recognizes that the Confederate’s left flank is unanchored and is a perfect target for an envelopment maneuver and places the Schwerpunkt at the end of Red’s line appropriately.

I still have work to do on MATE’s ability to construct defensive lines and that will be the next thing to add to the AI. But, as you can see, great progress has been made. I believe that the MATE tactical AI is unique and I know that there is nothing similar even among the wargames used by US and NATO allies. As always, please feel free to contact me directly if you have any questions or comments.

References

References
↑1 Tactical Inference GEneratoR
↑2 Machine Analysis of Tactical Environments
↑3 https://www.general-staff.com/antietam-ai/
↑4 “Wellington: The Years of the Sword,” p, 488 Longford, Elizabeth