Tag Archives: AI

A Wargame 55 Years in the Making

I was introduced to wargames (Avalon Hill, of course) about 55 years ago when I was seven years old by my buddy Carl Hoffman who lived down the street. Carl and I ended up owning every Avalon Hill wargame and we played them all. Eventually, Carl and his family moved away (I think Carl became a professor at LSU but I can’t confirm that) and I was faced with the grim realization that all of us Grognards inevitably confront: there was nobody to play wargames with.

Tactics II from Avalon Hill. The first wargame I played. What was the first wargame you played?

Tactics II from Avalon Hill. The first wargame I played. What was the first wargame you played?

Over the years I would occasionally find someone interested in playing  (or, more likely, coerce a friend who really had little interest in wargames) to set up a game but rarely would we ever complete a full campaign or battle.  By the late 1970s playing wargames for me was a rare event (the one exception being my good friend from my undergrad college days, Corkey Custer). Then, about this time, I saw an episode of PBS’s NOVA on what was then the infancy of Computer Graphics (CGI). There, flickering on my black & white TV, was what we would eventually call ‘wire frame’ 3D. Wire frame 3D just shows the edges of 3D objects. They are not filled in with a texture (as CGI is done now). Computers just didn’t have the processing power to pull this off back in the late ’70s and ’80s. But, I immediately thought to myself, “this technique could be used to render 3D battlefields!” And that was the spark from UMS: The Universal Military Simulator was born.

Screen capture of the original UMS running in 640 x 400 x 2 resolution in MS DOS. This is an example of wire frame 3D.

Screen capture of the original UMS running in 640 x 400 x 2 resolution in MS DOS. This is an example of wire frame 3D.

By the mid 1980s I was about to graduate with a bachelor’s degree in computer animation and, more importantly, a working demo of UMS. I had hypothesized that one of the biggest selling points of computer wargames was the ability to always have an opponent handy (the artificial intelligence or AI). I borrowed a copy of the Software Writers Market from the library and sent out dozens (maybe even hundreds) of letters and, eventually, papered an entire wall of my apartment with rejection letters from game publishers. But, Dr. Ed Bever, who designed Microprose’s Crusade in Europe, Decision in the Desert and NATO Commander (pretty much the only computer wargames that were out at the time) saw my pitch letter and gave me a call. Microprose wasn’t interested in publishing UMS per se, rather their CEO, “Wild Bill” Stealey, wanted me to come work for Microprose (and they would own UMS). That deal didn’t appeal to me but a short time later, at the 1986 Consumer Electronics Show in Chicago, Ed Bever introduced me to Microprose’s competitors, Firebird/Rainbird. Within 48 hours I had my first game publishing deal.

Crusade in Europe from Microprose (1985) designed by Dr. Ed Bever, originally programming by Sid Meir.

Crusade in Europe from Microprose (1985) designed by Dr. Ed Bever, originally programming by Sid Meir.

UMS sold about 128,000 units and was the #1 game in the US and Europe for a while.

The European Microdealer Top 30 Chart with UMS as #1 with a bullet on the 16 game chart. What other classic games can you find on the charts? (Click to enlarge)

The European Microdealer Top 30 Chart with UMS as #1 with a bullet on the 16-bit game chart. What other classic games can you find on the charts? (Click to enlarge)

Ed Bever helped on the design of UMS II: Nations at War which was an extremely ambitious global wargame that had unprecedented detail and allowed the user to edit numerous variables and equations:

UMS II: Nations at War screen shots from the MS DOS version. Click to enlarge.

UMS II: Nations at War screen shots from the MS DOS version. Click to enlarge.

UMS II screen shot (Macintosh) showing active weather systems.

UMS II screen shot (Atari ST) showing active weather systems.

An example of the numerous variables that the user could adjust in UMS II. Click to enlarge.

An example of the numerous variables that the user could adjust in UMS II.; in this case adjusting the attrition level based on experience for ground units. Macintosh screen shot. Click to enlarge.

UMS II was named “Wargame of the Year” by Strategy Plus magazine and enjoyed strong sales. In many ways it was the ‘ultimate’ in complex wargaming.  It was far more detailed than any other wargame I’ve seen before or since (and that includes my work on DARPA, Department of Defense, US Army, Office of Naval Research and Modeling Simulation Information Analysis Center (MSIAC) wargames. Ironically, it was published by Microprose because they bought out Firebird/Rainbird and with it my publishing contract.

My next wargame, in 1993, was The War College.  We used data from US Geological Survey to create the 3D maps. Again, it was very detailed and allowed the user to edit combat values and featured an interactive hyperlinked history of each scenario (it shipped with Antietam, Austerlitz, Pharsalus and Tannenberg). Unfortunately, our publisher, GameTek, pretty much ceased to exist just as we were about to release this game. To this day I have no idea how many units it sold. We never got a royalty statement.

Screen shot (MS DOS) of the Austerlitz scenario in The War College. Click to enlarge.

Screen shot (MS DOS) of the Austerlitz scenario in The War College. Click to enlarge.

The War College also had an interactive history for each battle (screen shot from MS DOS, click to enlarge).

The War College also had an interactive history for each battle (screen shot from MS DOS, click to enlarge).

The War College allowed users to adjust melee effectiveness and values. MS DOS screen shot, click to enlarge.

The War College allowed users to adjust melee effectiveness and values. MS DOS screen shot, click to enlarge.

I also would be terribly remiss if I did not mention my good friends who worked on various ports of the above mentioned games, Ed Isenberg (Amiga and MS DOS), Andy Kanakares (Apple IIGS and MS DOS) and Mike Pash (MS DOS).

(left to right) Ed Isemberg, Andy Kanakares, Ezra Sidran. Not pictured; Mike Pash.

(left to right) Ed Isemberg, Andy Kanakares, Ezra Sidran. Not pictured; Mike Pash.

One of the problems of getting old is that your stories get longer to tell. This blog post is far longer than I intended and we haven’t even got to this century and all my research into computational military reasoning (Tactical and Strategic AI) and my new wargame, General Staff.  I’m afraid we’ll have to end this here and pick up the story in Part 2 next week.

Slope Weight Added to Least Weighted Path Calculations

An example of slope avoidance in General Staff. Note how the cavalry unit skirts the edge of the hill on the way to its objective. (Click to enlarge)

An example of slope avoidance in General Staff. Note how the cavalry unit skirts the edge of the hill on the way to its objective. (Click to enlarge)

We have added a new feature, the cost of traversing up a slope, to our proprietary least weighted path algorithm. This will create even more realistic (and, frankly, optimal) unit order paths.  A key element to General Staff is its ability to assist the user in calculating optimal paths for units so the user only has to click where he wants the unit to go and the AI figures out the rest. In fact, the user doesn’t even have to click on the map, but can select the unit’s destination from a list of objectives.

The original least weighted path algorithm with slope weighting was created by Dr. Sidran when he was in graduate school. Dr. Sidran said, “I should probably write a paper describing the new algorithm, called EZRoadStar. However, as I am no longer an active member of academia there is no pressure to, ‘publish or perish’.” Instead, he will concentrate on finishing General Staff.

General Staff is expected to be released for Windows, XBox and iOS later this year.

 

New, Faster Pathfinding AI

A screen shot showing traditional A* (pronounced A Star) pathfinding. The green areas are 'nodes' that the algorithm explored on its way to finding the optimal path (in Brown).

A screen shot showing traditional A* (pronounced A Star) pathfinding. The green areas are ‘nodes’ that the algorithm explored on its way to finding the optimal path (in Brown). Click on picture to enlarge to full size.

Artificial Intelligence (AI) plays an important role in wargame development; it’s what separates a good game from a great game. One of the most important algorithms employed in wargame AI is the A* (pronounced ‘A star’) pathfinding algorithm that was created in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael. The paper describing it, A Formal Basis for Heuristic Determination of Minimum Cost Paths can be downloaded here. I did my doctoral Qualifying Exam on optimized pathfinding. My paper, “An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps'” can be downloaded here.

How long will it take for your orders to arrive?

How long will it take for your orders to arrive at this unit? How long will it take for the unit to send a courier back to headquarters with its current location?

Pathfinding is important in wargames because it’s how units, under computer control, move around on the map. Also, and we’re announcing this for the first time here, when you give orders in General Staff a courier has to ride from your headquarters unit to the unit that is to receive your orders. Also, units on the battlefield that are not directly visible to the Headquarters unit (this is done with a 3D Bressenham line algorithm; more about this later) slowly begin to fade from view on the map. However, every hour a courier is dispatched from every unit to headquarters with an update on their position. As we can see from the information box, above, the courier will take 41 minutes to deliver the new position information to headquarters.

The top screen capture shows an implementation of the classic A* algorithm for calculating the optimal path from Blue’s headquarters unit to a far-flung cavalry unit. Note, this is an especially difficult path to calculate because the unit is across a river and there are only three bridges across. The A* algorithm performs perfectly but it is just too slow to be used with a real-time tactical wargame like General Staff. After some thought I wrote a major optimization of A* which we present here for the first time.

An example of the new EZRoadStar pathfinding algorithm created for General Staff. Compare it to the top screen capture which uses the classic A* algorithm. Click to enlarge.

An example of the new EZRoadStar pathfinding algorithm created for General Staff. Compare it to the top screen capture which uses the classic A* algorithm. Click to enlarge.

Above is a screen shot of the results of the new EZRoadStar algorithm. It is almost identical to the original A* algorithm but runs thousands of times faster (my fellow computer scientists would probably prefer if I did some tests, wrote a paper and published the exact figures and I promise I’ll get around to that, some day).

In the screen shot, above, you can see the path of the courier (in green) from the Blue HQ unit to wayward cavalry unit. The new pathfinding algorithm, EZRoadStar, first looks for roads and then calculates how to get on and off the roads. This is much faster than the A* algorithm.

 

Computational military reasoning.

Computational military reasoning is a phrase that I coined to describe the process of a machine performing human-level analysis of tactical and strategic problems. I have spent the last 30 years of my life working on this problem. It was the theme of my doctoral research in computer science. The abstract for my doctoral dissertation reads:

We present here TIGER, a Tactical Inference Generator computer program that was designed as a test-bed program for our research, and the results of a series of surveys of Subject Matter Experts (SMEs) testing the following hypotheses:

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 to group tactical situations by similarity.

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

We have conducted three surveys of SMEs and have concluded that there is, indeed, a statistically significant confirmation of Hypothesis 1, that there is agreement among military SMEs that tactical situations exhibit certain features (or attributes) and, that these features can be used to group, or identify, similar tactical situations. The statistical confidence level for this confirmation of Hypothesis 1 is greater than twice the prior probability.

In order to test Hypothesis 2 we constructed, after SME survey analysis, a series of algorithms, which we present here, for the analysis of SME identified tactical features (or attributes) including: interior lines, restricted avenues of approach, restricted avenues of attack, slope of attack, weighted force relationships and anchored or unanchored flanks. Furthermore, the construction, and implementation, of these algorithms, required the design and implementation of certain ‘building block’ algorithms including: range of influence, optimal FindPath, ComputeGroupsByThreshold and ComputeGroupsByNumber.

We further present an overview of TIGER, itself, and the built-in utilities necessary for creating three-dimensional tactical situations, complete with terrain, elevation and unit types as well as our implementation of Gennari, Fisher and Langley’s CLASSIT classification system.

Lastly, we present TIGER’s classification of twenty historical tactical situations and five hypothetical tactical situations and the SME survey results of TIGER’s classification that resulted in TIGER correctly predicting 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).

TIGER logo from my doctoral research.

TIGER logo from my doctoral research.

The entire dissertation can be downloaded here

I have also written a number of papers about implementing tactical maneuvers: “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment,” which can be downloaded here. And “Algorithms for Generating Attribute Values for the Classification of Tactical Situations,” which can be downloaded here.

What will make General Staff stand out from other wargames is that it will be the first commercial computer wargame to implement this research. I have high hopes that General Staff will have the most advanced tactical AI ever produced in a computer wargame.