Category Archives: Algorithm

Fixing a Major Mistake

Steam Update

Darin Jones has been working on the Steam side. He created the Installer and is working on setting up Player versus Player (PvP) leveraging Steam’s built-in features. While this has been a steep learning curve, Darin has made some significant progress:

Screen shot of Steam Player vs. Player invitation for General Staff: Black Powder. This is not a Play by Email (PBEM) system, rather it uses Steam’s internal messaging system

Darin is also setting up a ‘Workshop’ area where you can upload scenarios, armies and maps that you create and want to use in a PvP game.

What’s Next

Our goal remains to get General Staff: Black Powder into beta-testing (that’s you guys playing with it) as soon as possible. We want to use the Steam PvP method, above, as the vehicle for testing. I’m grateful for the emails that I’ve received that are encouraging me to not rush General Staff: Black Powder out before it’s ready and to deliver a solid game (see also, Gabe Newall on why game delays are OK: ‘Late is just for a little while. Suck is forever.’).

As always, please feel free to contact me directly at Ezra[at]RiverviewAI.com.

References[+]

References
↑1	Full disclosure: I wouldn’t say ‘screwed up’. If you want to get an undergraduate’s attention use the ‘f word’.
↑2	MonoGame is a community supported version of Microsoft’s XNA which was created specifically for making cross-platform games. Microsoft stopped all support for XNA in April 2014. Previously, I had used XNA for some work that I had done for the US Army and the Department of Defense and thought it had great potential for creating computer wargames and simulations.

The Friction of War

12 Replies

The delay in the transmittal of orders from headquarters and staff is one example of the Friction of War. Note the calculated time for couriers to arrive displayed in the Subordinate Orders list on the left of the screen. The red lines are the routes that couriers from General HQ to Corps HQ to individual units will take. General Staff: Black Powder screen shot. Click to enlarge.

Carl von Clausewitz, in has seminal work, On War, (Book 1, Chapter 7) originated the phrase, “Friction of War”:

Carl von Clausewitz painted by Karl Wilhelm Wach. Credit Wikipedia.

“Friction is the only conception which, in a general way, corresponds to that which distinguishes real war from war on paper. The military machine, the army and all belonging to it, is in fact simple; and appears, on this account, easy to manage. But let us reflect that no part of it is in one piece, that it is composed entirely of individuals, each of which keeps up its own friction in all directions.”

I knew that if General Staff: Black Powder were to be an accurate simulation, and not just ‘war on paper’, that the friction of war would have to be calculated into the command / orders chain. One part of this – the distance the couriers will travel from one headquarters to the next to deliver their orders and the time it takes to travel this distance – can be calculated with reasonable certainty (I’m using the rate of 10.5 kilometers per hour for a horseman, I’m not an expert but this seemed reasonable, and it’s easy to change if somebody has a more accurate value).

Another example of friction of war is factored into the delaying of the arrival of orders is Leadership Value:

In this example, the Imperial couriers will travel over 4.3 kilometers, taking 24 minutes, to deliver their orders. Also, note the cost of the combined Leadership Values. Because Napoleon and Vandamme have very high Leadership Values little additional delay is added. General Staff: Black Powder screen shot. Click to enlarge.

You can specify at what time the order is to be executed (in this case 6:15), however you can not set a time earlier than when the couriers would arrive. This allows for coordination of attacks across units. General Staff: Black Powder screen shot. Click to enlarge.

The other value – and it is arbitrarily set – is the cost of ineptitude, incompetence, lack of motivation, and sloppy staff work. In the above scenario (Ligny) Napoleon’s Leadership is set at 93%:

The slider adjusts Napoleon’s Leadership Value which effects the delay in issuing orders. General Staff: Black Powder Army Editor screen shot. Click to enlarge.

I understand that Napoleon may have been feeling a bit under the weather during the Hundred Days Campaign. You can set his Leadership Value to anything you want in the Army Editor (above).

Major General George B. McClellan’s Leadership Value can be changed in the Army Editor. Click to enlarge.

Did I set McClellan’s Leadership Value too low? He was amazingly incompetent. Note below:

The combination of McClellan’s and Burnside’s extremely low Leadership Values adds an additional 29 minutes to the transmittal of orders. The blue lines trace the route that couriers would travel from McClellan’s headquarters to Burnside’s headquarters and then to each division and battery. General Staff: Black Powder screen shot. Click to enlarge.

The combination of McClellan’s and Ambrose Burnside’s Leadership Values results in almost a half hour delay in transmittal of the orders (remember after receipt of the orders, Burnside has to send couriers to his divisional and battery commanders, too and their Leadership Values effects the delay before their unit executes the order). After factoring the time it would take for a horseman to travel the distance between McClellan’s headquarters to Burnside’s headquarters (14 minutes) the earliest that a unit could be expected to respond to the original order from General Headquarters would be forty-one minutes later (and, in reality, a bit after that because of that unit’s Leadership Value).

The path of the couriers from McClellan’s headquarters, to Burnside’s Headquarters and then out to the divisions and batteries. General Staff: Black Powder screen shot. Click to enlarge.

I have spent some time at Antietam and studied it at length and this delay of about three-quarters of an hour between the time McClellan wanted to issue an order and the men of Burnside’s IX Corps moved out seems if anything, too optimistic of a timetable. In fact, as I write this, I think I need to increase the penalty for poor Leadership Value. McClellan and Burnside couldn’t possibly have got units moving in less than an hour.

As I have begun playtesting General Staff: Black Powder I found the delay between issuing orders and wanting to see something move now was a bit disconcerting. It shouldn’t have been. I’ve read enough military history to know that battlefield orders were often transmitted the night before and moving units around during the battle could be a risky proposition. Some armies, however, were less afflicted with these problems than others, and that I would attribute to ‘leadership value’ which also encompasses the army’s general staff.

If you don’t want to use General Staff: Black Powder as a simulation that inserts a calculated delay between orders and execution, and would rather just move units instantly, there is ‘Game Mode’:

The Select Mode screen in General Staff: Black Powder. The user chooses between ‘game’ and ‘simulation’ with differences in rules and unit icons. Click to enlarge.

Game Mode has the same maps but uses simpler icons and rules. I originally envisioned Game Mode as a way of introducing wargaming to a new generation (I wanted to write it for the XBox). Anyway, it’s included with General Staff: Black Powder.

Lastly, I know everybody is waiting for news about when can I get my hands on the game?!!?!! My friend, Damien, wasn’t able to work on finishing it using Unity so I’m finishing it up using MonoGame. As you can see I’m pretty far along and I think I will be playing the first ‘actual game’ (that is a simulation from start to finish) within the next couple of weeks; maybe sooner. After that, probably at least another month of fixing bugs, but then I’m hoping to set up a Beta download for all the early backers via Steam. We have a space on Steam but I haven’t even begun to build it out. Obviously, I’m just one guy, I’m working as fast as I can, but I think this is all good news. Also, I’m working on a video to show everything off.

As always, if you have any questions or comments, please feel free to contact me directly.

Schwerpunkt: Calculating the Optimal Point of Attack

19 Replies

MATE’s analysis of Blue (Union) position at Antietam. NB: Unable to outflank Red’s position, MATE has calculated the Schwerpunkt, or optimal point of attack on Red’s lines. Click to enlarge.

The holy grail of military science is an algorithm that calculates the optimal point of attack upon an enemy’s lines. In German, the word is Schwerpunkt and is commonly translated as “the point of maximum effort.” I have written extensively about Schwerpunkt previously in this blog, in academic papers and in my doctoral thesis.

MATE (Machine Analysis of Tactical Environments 2.0, the AI behind General Staff: Black Powder) is now able to calculate Schwerpunkt to a new, substantially greater, degree of accuracy. There are a number of reasons why this is now possible, but the primary cause must be the ability to analyze the battlefield in 3D and to accurately map where every unit on the map can project its force. Indeed, for many years now I have looked at the problem of computational military reasoning (AI for tactical situations) as a force projection problem.

Below, is a visual representation of the total force projection of all units at Gettysburg, Day 3 (July 3, 1863 0600 hours):

Visual representation of the total force projection (Range of Influence, or ROI) for all units at Gettysburg Day 3. Note: normalization and alpha values affect color output. Also, note how the terrain (woods, depressions, hills) shape the projection of force. Also, all projections are independent of unit facing. Click to enlarge.

If we ask MATE to determine the Schwerpunkt for the Confederates in the above situation, it responds with:

MATE’s selection (labeled OBJECTIVE) for Red Schwerpunkt. Click to enlarge.

And adds the following commentary (edited for brevity, the numbers are the Premise Statement ID#s. This is basically a logic trace of MATE’s thinking):

8|∴ The enemy does not need to capture more Victory Points.
9|∴ The enemy will be on the defensive.
...
22|The enemy's flanks are anchored.
23|[9] + [22] ∴ Frontal assault is the only remaining option.
...
25|COA: Battle Group #1 (Mixed) assigned objective Weak Point Calculated by ROI coords: 551,232
...
33|Red Battle Group #1 is opposed by Blue Battle Group #6
34|Red Battlegroup # 1's strength = 21,663
35|Blue Battlegroup # 6's strength = 13,635
36|Red Battlegroup # 1 has a numerical advantage of 8,028. Red has a 1.59 / 1 advantage over Blue Battle Group #6.
37|Distance to objective is 1,029.86 meters.
38|The maximum slope along the line of attack will be on an upward slope of 3.64%.
39|The attacking avenue of approach will be in enemy ROI for 541.18 meters.
40|The greatest enemy ROI along the avenue of approach is: 1,276.00 .
41|There is an unrestricted avenue of attack.

In other words, MATE has found a path to its objective that encounters the least amount of enemy projection of force. MATE would much prefer to flank the enemy position but it has calculated that this is impossible (#22, above).

ROI (Range of Influence) is calculated using values set up for each unit in the General Staff Army Editor and running a 3D Bresenham line algorithm to ensure that there is direct Line of Sight (LOS) to that point.

Screen shot of the General Staff Army Editor showing the interface for entering values for a typical artillery unit. Note that the accuracy curve is user editable (there are also default curves for various common weapons). Click to enlarge.

It is because every unit has an accuracy curve attached to it we can exactly map out the overlapping fields of fire (see above) and we can precisely calculate how long each attacking unit will be under fire and its intensity. That is how MATE chooses the optimal attack point: the path where its troops will be under the least amount of fire.

When MATE is presented with a tactical problem it first determines what it needs to do to win; is it on the offense or defense? On the offense, MATE will next check to find the enemy’s open flank and, if there is one, are there any crucial choke points on the flanking route? If MATE is unable to ‘fix and flank’ the enemy, and it has determined that it must be on the offensive, MATE then calculates Schwerpunkt (above). With this new Schwerpunkt algorithm the last big piece of the offensive AI puzzle is in place. Ironically, much of MATE’s defensive calculations involve first figuring out how to attack itself and then countering what it determines are its own optimal moves against itself (see this blog).

As always, please feel free to contact me directly with comments or questions.

A Human-Level Intelligence at Gettysburg, Day 3

1 Reply

Screenshot of MATE analysis of Gettysburg, Day 3 from the Red (Confederate) position. Click to enlarge.,

General Lee, at Gettysburg, said: “the enemy have the advantage of us in a shorter and inside line and we are too much extended.” – quoted by Major General Isaac Trimble.¹⁾Isaac Trimble, Southern Historical Society Papers, Vol. 26, Richmond, Virginia: Reverend J. William Jones, D.D., MATE, the AI behind General Staff, came to the exact same conclusion:

A portion of MATE’s analysis of Red’s position at Gettysburg, Day 3. Here MATE recognizes that Red has exterior lines and the enemy has a decided advantage.

I have been porting TIGER ²⁾Tactical Inference GenERator, the AI behind my doctoral thesis and my DARPA sponsored research from C++ to C# and integrating it into the General Staff: Black Powder wargaming system. I have been doing this via the method of first creating a scenario typifying a specific attribute (exterior lines, exposed flanks, choke points, etc.) and then porting the actual code over and feeding it the scenario for analysis. Gettysburg, Day 3, is the canonical example of exterior and interior lines.

92.9% of Subject Matter Experts agree! The Union (Blue) lines at Gettysburg, Day 3, exhibit the attribute of being Interior Lines. Interior lines are good. Exterior lines are bad. From author’s doctoral thesis.

So, first a significant number of Subject Matter Experts (combat commanders, tactics instructors at military academies, etc.,) agree that there is an attribute called ‘Interior Lines’ and that it is exhibited by the Union (Blue) forces at Gettysburg, Day 3. We then create an algorithm that can detect such an attribute and convert it from C++ code to C# code (and substantially rewrite and improve said algorithm in the process) . We then create a Gettysburg, Day 3 scenario using the General Staff Army Editor, the General Staff Map Editor and the General Staff Scenario Editor and feed the scenario³⁾In Computer Science lingo programs are machines that consume data / tokens to MATE, the General Staff: Black Powder AI. These are the results:

MATE analysis text output (with author’s commentary) of Gettysburg, Day 3, from the Red (Confederate) position. Click to enlarge.

The first time that I presented the Gettysburg, Day 3 scenario as Red to MATE it refused to attack. The enemy has interior lines (1.4, or 40% greater is pretty significant value), you’re attacking uphill (slope > 7%), your attacking units are under enemy ROI (mostly batteries of 12 lb. Napoleon canon shooting explosive shot and then canister and then double-shotted canister) for over a kilometer. Attacking is not a good idea. To get MATE to attack I had to go back to the Map Editor and create a number of new Victory Points; specifically the places where significant roads (Emmitsburg Road, Cashtown Road, Baltimore Pike, etc.) enter the map. Then I went in to the Scenario Editor and assigned appropriate values and current ‘ownership’. Saved it all and fed it back to MATE and the, above, is what I got.

The only way for MATE to win (as Red) is to attack large Victory Point areas (Cemetery Hill and Cemetery Ridge) and hope to destroy significant numbers of Blue (Union) forces along the way to meet the victory conditions set in the Scenario Editor:

Gettysburg, Day 3 Victory Conditions. Screenshot General Staff Scenario Editor.

Anybody who has built a wargame scenario (and I suspect there are more than a few among the readers of this blog) know the drill of going back to edit the OOBs, starting positions, victory conditions, etc. I would just like to say it’s pretty painless using the General Staff Wargaming System. The various editors all integrate seamlessly like Microsoft Office products (they were written in Microsoft WPF by Andy O’Neill who is a Microsoft Gold Developer).

But, the real question that this raises is: why did Lee attack on Gettysburg, Day 3? Blue (the Union) not only had interior lines, an elevated position, but they also had anchored flanks (see #22 above). MATE is running out of options at this point. If you look at the top screenshot you will see yellow numbers in yellow circles. These represent MATE’s three ‘weakest points’ in Blue’s line and it’s not much.

So why did Lee attack?

James Longstreet’s From Manassas to Appomattox states absolutely that

All that I could ask was that the policy of the campaign [Lee’s invasion of the north] should be one of defensive tactics, that we should work so as to force the enemy to attack us, in such good position as we might find in his own country, so well adapted to that purpose, – which might assure us of a grand triumph. To this he readily assented as an important and material adjunct to his general plan. [p. 331]

So, Longstreet, in his autobiography, is saying that Lee agreed that at some point in Pennsylvania, the Army of Northern Virginia would find a good solid defensive position and let Hooker (they didn’t yet know that Meade was the new commander of the Army of the Potomac) smash his army to pieces upon it. James McPherson in, To Conquer a Peace: Lee’s Goals in the Gettysburg Campaign writes:

“In a conversation with General Isaac Trimble on June 27, when most of the Army of Northern Virginia was at Chambersburg, Pa., and when Lee believed the enemy was still south of the Potomac, he told Trimble: “When they hear where we are, they will make forced marches…probably through Frederick, broken down with hunger and hard marching, strung out on a long line and much demoralized, when they come into Pennsylvania. I shall throw an overwhelming force on their advance, crush it, follow up the success, drive one corps back on another, and by successive repulses and surprises, before they can concentrate, create a panic and virtually destroy the army.” Then “the war will be over and we shall achieve the recognition of our independence.”

The argument is that Lee, on the morning of July 3, 1863, found himself in a terrible strategic situation with very few options. It was imperative that Lee must, “destroy the [enemy] army;” nothing less than a great triumph in enemy territory would do. In Lee’s only official report of the battle of Gettysburg, written on July 31, 1863 he states:

The enemy was driven through Gettysburg with heavy loss, including about 5,000 prisoners and several pieces of artillery. He retired to a high range of hills south and east of the town. The attack was not pressed that afternoon, the enemy’s force being unknown, and it being considered advisable to await the arrival of the rest of our troops. Orders were sent back to hasten their march, and, in the meantime, every effort was made to ascertain the numbers and position of the enemy, and find the most favorable point of attack. It had not been intended to fight a general battle at such a distance from our base, unless attacked by the enemy, but, finding ourselves unexpectedly confronted by the Federal Army, it became a matter of difficulty to withdraw through the mountains with our large trains. At the same time, the country was unfavorable for collecting supplies while in the presence of the enemy’s main body, as he was enabled to restrain our foraging parties by occupying the passes of the mountains with regular and local troops. A battle thus became in a measure, unavoidable. Encouraged by the successful issue of the engagement of the first day, and in view of the valuable results that would ensue from the defeat of the army of General Meade, it was thought advisable to renew the attack. . . .

Lee was in for a penny and in for a pound. This was not the defensive battle of Longstreet’s choosing. This was now Lee desperately trying to, “throw an overwhelming force on their advance, crush it, follow up the success, drive one corps back on another, and by successive repulses and surprises, before they can concentrate, create a panic and virtually destroy the army,” but now the enemy had, “retired to a high range of hills south and east of the town.” The Union had flipped Longstreet’s strategy 180 degrees and it was they who had, “force[d] the enemy to attack [them], in such good position as [they] might find.”

I will create some other Gettysburg scenarios including ones with the Union and Confederate cavalry available. While not historical, it might make for some interesting gameplay and Human-Level AI decisions.

As always, please feel free to contact me directly with comments.

References[+]

References
↑1	Isaac Trimble, Southern Historical Society Papers, Vol. 26, Richmond, Virginia: Reverend J. William Jones, D.D.,
↑2	Tactical Inference GenERator
↑3	In Computer Science lingo programs are machines that consume data / tokens

A Human-Level Intelligence at Quatre Bras

17 Replies

Quatre Bras, June 16, 1815. Click to enlarge

Napoleon has humbugged me, by God!” Lord Wellington swore. “He has gained twenty-four hours’ march on me!” ¹⁾David Chandler, Waterloo: The Hundred Days, Macmillan Publishing Co., Inc. New York 1980, p. 85 And, indeed, he had.

The Armée du Nord, racing north on the roadnet from Paris to Brussels, now occupied the crucial strategic ‘central position’ between the Anglo-Allied army under Wellington assembling at Quatre Bras in the west, and the Prussian army under Blücher at Ligny in the east. Napoleon, outnumbered by the combined forces of Wellington and Blücher only had one realistic option: destroy his opponent’s armies separately before they could combine and destroy him.

Napoleon divided the Armée du Nord into two wings (the left commanded by Marshal Ney and the right by the Emperor, himself). The Imperial Guard would serve as the strategic reserve. In our previous blog, we showed the MATE (Machine Analysis of Tactical Environments) artificial intelligence analysis of the battle of Ligny.

The starting positions of the Armée du Nord (Blue) and the Anglo-Allied Army (Red) at the battle of Quatre Bras. Screen shot from General Staff: Black Powder. Click to enlarge.

The positions in the above screen shot come from the West Point Atlas of the Napoleonic Wars and Chandler’s Waterloo: The Hundred Days. I’ve ordered Mike Robinson’s The Battle of Quatre Bras, 1815 (which is very highly regarded) but it’s coming from Europe and will be a while before it arrives. I’ll update the positions accordingly when it arrives.

Today MATE is going to show off a new trick that it learned.

MATE AI analysis of Blue’s position. General Staff screen shot. Click to enlarge.

Text output and author’s commentary of MATE’s analysis of Blue’s position at the battle of Quatre Bras.

The salient points of MATE’s analysis of Blue (Ney’s) position at the battle of Quatre Bras are:

Red (Wellington) has an open flank (in fact, both of Red’s flanks are exposed but MATE has calculated a left flanking maneuver is shorter than a right flanking maneuver)
Blue has a reserve cavalry division (Line #25 in the text output above, Battle Group #3, Pire’s 2nd Cavalry Division) that is in position to spearhead the left flanking maneuver ahead of
Battle Group #1 (the 6th Division commanded by Prince Jerome) which will follow as the main strike force of the left flanking maneuver (Line #23)
Battle Groups #0 and #2 (Reilles and Foy’s divisions) will be the fixing force attacking Gémioncourt in the classic envelopment maneuver (see below):
Battle Group #4 (Kellerman’s reserve cavalry division) will snatch the important crossroads at Thyle.

In other words, Battle Groups #3 and #1 will be the Enveloping Force and Battle Groups #0 and #2 will be the Fixing Force as illustrated in the above graphic from the U. S. Army Field Manual 3-21. Algorithms for implementing this maneuver (an early version of MATE) first appear in my paper, Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.

And MATE’s new trick? It’s in line #25, above. If there is a Battle Group that is composed entirely of cavalry and horse artillery, and it is close enough, it will be used as the spearhead for the flanking maneuver.

MATE’s analysis of Ligny. Screen shot from General Staff AI Editor. Click to enlarge.

But, in this situation (Ligny, above) MATE has calculated that Battle Group #1 will get to the crucial Choke Point (labeled in black, above) before the reserve cavalry Battle Group #4 will arrive and would create a tremendous bottleneck at the very choke point that MATE wants to quickly capture. Consequently, the cavalry has been left in reserve.

Mini MATE FAQ

Can MATE read and analyze any battle map from history?

No. MATE is integrated into the General Staff Wargaming System. MATE can only ‘understand’ Order of Battle (OOB) tables created in the General Staff Army Editor, maps created in the General Staff Map Editor and scenarios created in the General Staff Scenario Editor.

What is meant by a ‘human-level’ artificial intelligence?

Perhaps you have heard of the famous Turing Test (from Alan Turing’s Computing Machinery and Intelligence). In it he describes, “The Imitation Game,” where a computer is in one room behind a closed door, and a human is another room behind a closed door. A third person, the ‘interrogator’, can only ask questions via a teletype (an ancient I/O device consisting of a keyboard and a printer) and must determine in which room the computer is and in which room is the human. In Turing’s original paper the interrogator would ask questions of the two subjects such as, “Please write me a sonnet on the subject of the Forth Bridge,” and, “Add 34957 to 70764.” Currently, no Artificial Intelligence (AI) could pass such a test; the subject area is far too broad. However, it has been my thesis, that an AI could pass such a test if the subject area is restricted to a narrow field of human endeavor, such as commanding units on a battlefield. If, in the above Turing test, the computer in one room was replaced with MATE, the human in the other room was replaced by Napoleon, and the teletype was replaced by the General Staff Wargaming System, I argue that MATE could (or soon will be able to) pass such a test (subject matter experts would not be able to discern if it was MATE or Napoleon giving orders).

Can MATE analyze current military situations?

Though MATE came out of the TIGER (Tactical Inference GenERator) project funded by DARPA, it is currently set up specifically for the General Staff: Black Powder project which limits analysis to scenarios in the 18th and 19th centuries. It is intended that this project will be followed up with General Staff: Modern Warfare to specifically work with 20th and 21st century combat.

References[+]

References
↑1	David Chandler, Waterloo: The Hundred Days, Macmillan Publishing Co., Inc. New York 1980, p. 85