Author Archives: EzraSidran

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 3)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’ 2)Thank you Dennis Beranek for introducing me to the concept of ‘reasonableness test’. See http://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   [ + ]

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. Thank you Dennis Beranek for introducing me to the concept of ‘reasonableness test’. See http://general-staff.com/schwerpunkt/ for explanation
3. Yes, somebody has built one and you can see what Turing described here: https://www.youtube.com/watch?v=E3keLeMwfHY
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.

Mea Culpa, Mea Maxima Culpa

I just recently discovered that the email contact form on this web site was not properly forwarding emails to me. I feel awful about this. I’ve always taken great pride in personally answering every letter or email written to me – going back to the days of dot-matrix printers and postage stamps – and, literally, hundreds of people wrote to me and never heard back.

To clarify: if you responded to a post with a comment, I did get an automated message for those and did respond immediately. Only queries using the contact form page on this site did not forward emails to me.

Pretty much all that I’ve been doing for the last three days is writing emails (occasionally taking a break to walk the dog and feed the other animals here). I apologize for having to send out some form letters but the important thing is that you now all have my personal email address. In fact, if you go to the ‘Contact’ page on this site you’ll find my personal email address. Is this a good idea? No. I definitely do not encourage people to post their email addresses on line because you will get spammed. But, I guess, this will be my penance. Mea culpa, me maxima culpa!

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)http://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   [ + ]

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

What’s Taking So Long?

This is what a brilliant game publisher looks like: Marten Davies. I was looking for a photo of Marten from the ’80s and I found this 2019 photo (credit: University of Texas). This is exactly what he looked like in ’87. He hasn’t aged a day.

Marten Davies, my first publisher and still a close friend, was painfully accurate when he said, “Take any time estimate that Ezra gives you and multiply it by three.” Now, in my defense, Marten probably said that because I had a contractual obligation to deliver UMS: The Universal Military Simulator in some insanely short period of time like six months and I actually delivered it in eighteen. To my credit I delivered a #1 game (Europe and US). To Marten’s credit, he was very easy to work with and it remains the best experience of my career. The bottom line was that Marten knew that I needed more time to make a better game and he made sure I got it.

So, what’s the hold-up? Well, that would be me, again.

Specifically, it’s the AI.  As many of you know, I’ve been working on AI for wargames for a long time and I was hoping to turn General Staff into a showcase for my work. Some of this has been accomplished 1) Antietam & AI . These are the algorithms that I’ve written about in my doctoral thesis and in various published papers.

The MATE2)Machine Analysis of Tactical Environments, see http://riverviewai.com/ set of tactical AI routines built upwards from low level routines; like 3D Line of Sight (3DLOS) 3) http://general-staff.com/tag/3d-line-of-sight/ , Range of Influence (ROI), and least weighted path algorithms 4) http://general-staff.com/tag/least-weighted-path-algorithm/ to battlefield analysis 5) Algorithms for Generating Attribute Values for the Classification of Tactical Situations.: http://riverviewai.com/papers/Algorithms-Tactical_Class.pdf , to selection of objectives 6) http://general-staff.com/antietam-ai/ , and the implementation of offensive maneuvers 7) Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.:http://riverviewai.com/papers/ImplementingManeuvers.pdf to achieve those objectives.

So, given a list of objectives the AI can implement a tactical plan (Course of Action, or COA); but the AI doesn’t have any comprehension of the greater strategic picture. For example, MATE’s analysis of Gettysburg is that Blue8)MATE always labels the attacker as blue (Confederates) should not attack because Red (Union) has interior lines, a superior defensive position, and greater troop strength.

MATE representation of Gettysburg: Confederates (blue), Union (red). MATE screen shot. Click to enlarge,

MATE output analysis of Gettysburg. Confederates (BLUEFOR) should not attack because REDFOR (Union) has interior lines, a superior defensive position, and greater troop strength.

But, what the AI doesn’t understand is that the Confederates were desperate for a victory on Union soil which required them to attack at Gettysburg.

Screen capture of the Battle of Little Bighorn in the General Staff Scenario Editor. Click to enlarge.

Or consider the tactical positions at the battle of the Little Bighorn (above). My goal is to write a human-level tactical AI and, clearly, the historical attack (splitting forces) by Blue (7th Cavalry) against the far superior Red (Native American) forces was very ill advised (perhaps calling into question the definition of ‘human-level tactical AI’).

After a lot of thought I realized that I needed to create an AI Editor program. You use the Army Editor to create armies for the General Staff Wargaming System, the Map Editor to create maps, the Scenario Editor to place armies on the map and now you use the AI Editor to quickly and easily select strategies for an army. For example:

Screen shot of the General Staff AI Editor being used to program AI strategies for the Union forces at Antietam. Click on a battle group and select strategies from the drop down menus. Click to enlarge.

The AI Editor is very easy to use. You just load a scenario (created in the Scenario Editor, of course) tell the AI to separate the units on the field into battle groups (this creates unique groups based on proximity rather than the Order of Battle hierarchy) and then select strategies from the drop down menus. It’s important to note that these units won’t follow the direct paths between objectives; those are just there to show the order of Objectives. The MATE AI algorithms will be engaged to actually move units on the battlefield and implement tactical maneuvers like envelopment and turning attacks. Also, note the AI Editor creates one set of strategies that the AI will follow, if so instructed, when you actually play a simulation. You will also have the  option to let the Machine Learning algorithms select strategies as well though these may not follow historical strategies.

It took less than a minute to set up Custer’s strategy at Little Bighorn:

Screen shot from the General Staff AI Editor showing Custer’s historical strategy at Little Bighorn. Click to enlarge.

With the creation of the AI Editor the last piece is in place for the General Staff Wargaming System. We now have nine battlefield maps with more on the way (we’re hoping to ship the finished game with about 20 battlefield maps) and fifteen armies (we hope to have about sixty when we’re finished). We’re now registered with Steam and are getting our ‘store’ set up. We will be using Steam for player vs. player games. With a bit of luck we’re hoping to start player vs. player testing in about sixty days.

As always, please feel free to contact me directly with questions, comments or complaints. I’m sorry for the delay, but we’re creating something that hasn’t been done before and that always takes a bit longer.

References   [ + ]

1. Antietam & AI
2. Machine Analysis of Tactical Environments, see http://riverviewai.com/
3. http://general-staff.com/tag/3d-line-of-sight/
4. http://general-staff.com/tag/least-weighted-path-algorithm/
5. Algorithms for Generating Attribute Values for the Classification of Tactical Situations.: http://riverviewai.com/papers/Algorithms-Tactical_Class.pdf
6. http://general-staff.com/antietam-ai/
7. Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.:http://riverviewai.com/papers/ImplementingManeuvers.pdf
8. MATE always labels the attacker as blue

Antietam & AI

MATE AI selected Objectives for Blue, 3D Line of Sight (3DLOS) and Range of Influence (ROI) displayed for the Antietam: Dawn General Staff scenario. Screen shot from General Staff Sand Box. Click to enlarge.

The author walking across Burnside’s Bridge in 1966 (age 12).

I have been thinking about creating an artificial intelligence (AI) that could make good tactical decisions for the battle of Antietam (September 17, 1862, Sharpsburg, Maryland) for over fifty years. At the time there was little thought of computers playing wargames.1)However, it is important to note that Arthur Samuel had begun research in 1959 into a computer program that could play checkers. See. “Samuel, Arthur L. (1959). “Some Studies in Machine Learning Using the Game of Checkers”. IBM Journal of Research and Development.” What I was envisioning was a board wargame with some sort of look-up tables and coffee grinder slide rules that properly configured (not sure how, actually) would display what we now call a Course of Action (COA), or a set of tactical orders. I didn’t get too far on that project but I did create an Antietam board wargame when I was 13 though it was hardly capable of solitaire play.

The Antietam scenario from The War College (1992). This featured 128 pre-rendered 3D views generated from USGS Digital Elevation Model Maps.

In 1992 I created my first wargame with an Antietam scenario: The War College (above). It used a scripted AI that isn’t worth talking about. However, in 2003 when I began my doctoral research into tactical AI I had the firm goal in my mind of creating software that could ‘understand‘ the battle of Antietam.

TIGER Analysis of the battle of Antietam showing Range of Influence of both armies, battle lines and RED’s avenue of retreat. TIGER screen shot. Appears in doctoral thesis, “TIGER: A Machine Learning Tactical Inference Generator,” University of Iowa 2009

The TIGER program met that goal (the definition of ‘understand’ being: performing a tactical analysis that is statistically indistinguishable from a tactical analysis performed by 25 subject matter experts; e.g.. active duty command officers, professors of tactics at military institutes, etc.).

In the above screen shot we get a snapshot of how TIGER sees the battlefield. The darker the color the greater the firepower that one side or the other can train on that area. Also shown in the above screen shot is that RED has a very restricted Avenue of Retreat; the entire Confederate army would have to get across the Potomac using only one ford (that’s the red line tracing the road net to the Potomac).  Note how overlapping ROIs cancel each other out. In my research I discovered that ROIs are very important for determining how battles are described. For example, some terms to describe tactical positions include:

  • Restricted Avenue of Attack
  • Restricted Avenue of Retreat
  • Anchored Flanks
  • Unanchored Flanks
  • Interior Lines
  • No Interior Lines

A Predicate Statement list generated by MATE for the battle of Antietam.

Between the time that I received my doctorate in computer science for this research and the time I became a Principal Investigator for DARPA on this project the name changed from TIGER to MATE (Machine Analysis of Tactical Environments) because DARPA already had a project named TIGER. MATE expanded on the TIGER AI research and added the concept of Predicate Statements. Each statement is a fact ascertained by the AI about the tactical situation on that battlefield. The most important statements appear in bold.

The key facts about the tactical situation at Antietam that MATE recognized were:

  • REDFOR’s flanks are anchored. There’s no point in attempting to turn the Confederate flanks because it can’t be done.
  • REDFOR has interior lines. Interior lines are in important tactical advantage. It allows Red to quickly shift troops from one side of the battlefield to the other while the attacker, Blue, has a much greater distance to travel.
  • REDFOR’s avenue of retreat is severely restricted. If Blue can capture the area that Red must traverse in a retreat, the entire Red army could be captured if defeated. Lee certainly was aware of this during the battle.
  • BLUEFOR’s avenue of attack is not restricted. Even though the Blue forces had two bridges (Middle Bridge and Burnside’s Bridge) before them, MATE determined that Blue had the option of a wide maneuver to the north and then west to attack Red (see below screen shot):

MATE analysis shows that Blue units are not restricted to just the two bridge crossings to attack Red. MATE screen shot.

  • BLUEFOR has the superior force. The Union army was certainly larger in men and materiel at Antietam.
  • BLUEFOR is attacking across level ground. Blue is not looking at storming a ridge like at the battle of Fredericksburg.

MATE AI selects these objectives for Blue’s attack. General Staff Sand Box screen shot. Click to enlarge.

We now come to General Staff which uses the MATE AI. General Staff clearly has a much higher resolution than the original TIGER program (1155 x 805 terrain / elevation data points versus 102 x 66, or approximately 138 times the resolution / detail). In the above screen shot the AI has selected five Objectives for Blue. I’ve added the concept of a ‘battle group’ – units that share a contiguous battle line – which in this case works out as one or two corps. Each battle group has been assigned an objective. How each battle group achieves its objective is determined by research that I did earlier on offensive tactical maneuvers 2)See, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” link to paper.

As always, I appreciate comments and questions. Please feel free to email me directly with either.

References   [ + ]

1. However, it is important to note that Arthur Samuel had begun research in 1959 into a computer program that could play checkers. See. “Samuel, Arthur L. (1959). “Some Studies in Machine Learning Using the Game of Checkers”. IBM Journal of Research and Development.”
2. See, “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.” link to paper.