Tag Archives: Gameplay

A Wargame 55 Years in the Making (Part 2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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.

The Fog of War

A key element of General Staff gameplay is the notion of ‘fog of war’. In essence we keep three maps: what blue thinks the situation is, what red thinks the situation is and where all units actually are on the map.

A courier reports that an enemy unit was observed four minutes ago. Note: the enemy unit has almost certainly moved on since then. (Click to enlarge.)

A courier reports that an enemy unit was observed four minutes ago. Note: the enemy unit has almost certainly moved on since then. (Click to enlarge.)

Location of your headquarters (HQ) unit is vitally important in General Staff. If an enemy (or friendly) unit is not directly observable to your HQ unit, the information of an enemy unit sighting is passed to HQ via courier. The amount of time for the courier to travel from the observing unit to the HQ is precisely calculated (see screen capture, above). Friendly units report their position every hour and dispatch a courier to HQ with this information as well. The time for a courier to travel from the reporting unit to travel to HQ is also calculated.

In essence, then, locating your HQ unit on a hill, ridge or other prominent feature is important if you want a clear view of the battlefield. Otherwise, you will be dependent on your couriers to penetrate the fog of war.

The phrase, ‘Fog of War’ (or Nebel des Krieges in German) was first written by Carl von Clauswitz in his famous treatise, On War (in 1832, first English translation in 1873):

War is the realm of uncertainty; three quarters of the factors on which action in war is based are wrapped in a fog of greater or lesser uncertainty. A sensitive and discriminating judgment is called for; a skilled intelligence to scent out the truth.

— Carl von Clausewitz

Update: some readers at Kriegsspiel Forum have quite correctly pointed out that at great distances units would certainly not be able to ascertain the name of the unit that they are observing. Consequently, we have changed the information provided to this:

Dispatch from observing unit modified to include distance and just unit type. (Click to enlarge.)

Dispatch from observing unit modified to include distance and just unit type. (Click to enlarge.)

Now the question arises: how far could you see with a 19th century telescope? Do we need to include a maximum range for line of sight? Interesting question. Would like to hear your comments.

General Staff Gameplay

Screen capture of General Staff showing the 3D Line of Sight (LOS) areas that are visible to the blue HQ unit.

Screen capture of General Staff showing the 3D Line of Sight (LOS) areas that are visible to the Red HQ unit (grayish areas are not visible). (Click to enlarge.)

We are very pleased to show screen captures of General Staff that demonstrate some of its unique gamplay features. General Staff is different (at least as far as we know, and if there are other computer wargames that have these gameplay techniques, we haven’t seen them) in that you, the user, are assuming the role of the commanding general with his general staff. You do not have an omniscient view of the battlefield. The only unit locations (both friendly and OPFOR, or OPposition FORces) that you know for certain are the ones that you can directly observe. The above screen capture displays the areas that the Red HQ unit (U. S. Grant and staff) can see from their location on Riverview Hill. The 3D Line of Sight (3D LOS) algorithm in General Staff uses elevation and terrain maps to calculate the LOS for each unit.

An example of how units that are not directly visible to HQ are displayed. The longer that a unit remains unobserved, the fainter it becomes. (Click to enlarge.)

An example of how units that are not directly visible to HQ are displayed. The longer that a unit remains unobserved, the fainter it becomes. (Click to enlarge.)

When units are hidden from direct LOS they begin to fade (as seen in the screen capture to the right). The longer it has been since the unit has been observed, the fainter the unit is drawn. However, every hour, every friendly unit dispatches a courier to headquarters with its current unit location. When the courier arrives (his path is calculated and described below) the unit’s position is updated and the unit is displayed in full color. In the above screen capture, arriving messenger reports are displayed in the bottom of the screen. Enemy units, however, that have not been observed for an hour disappear completely from the map.

CourierTime

Screen capture showing easy to use interface for giving orders. Also displays unit information, distance from HQ, morale and fatigue. (Click to enlarge.)

Orders are not given directly to units, as in other wargames, but are sent, via courier, from HQ to the unit.  The screen capture (right) shows the interface for constructing a unit’s orders. Orders are entered via unit-specific pop-up menus that specify the formation, direction, facing and speed for the unit. Also displayed is how far the messenger will travel and how long it will take for to deliver the orders. Couriers travel at 17.5 kilometers per hour and will attempt to use roads whenever possible.

This screen capture displays the path from Blue HQ to the unit that the courier will travel, the future orders for the unit and confirmation of the orders. (Click to enlarge.)

This screen capture displays the path from Blue HQ to the unit that the courier will travel (in green), the future orders for the unit (thicker blue) and confirmation of the orders. Note how the courier automatically takes advantage of roads. (Click to enlarge.)

The above screen capture shows the path the messenger will take (in green), the orders (in transparent blue) and a confirmation pop-up that shows the time the messenger will arrive at the unit with the new orders.

We have since updated the Messenger box to look like this (in keeping with the 19th century late Victorian theme of General Staff):

A screen capture of the new Messenger information box.

A screen capture of the new Messenger information box.

We believe that this structure not only is an authentic depiction of warfare in the 19th century and how the generals experienced ‘fog of war’, but will greatly enhance the gameplay of General Staff.

 

First Scenario Created!

ScenarioScreenCap2

Screen capture of the Select Scenario screen from General Staff. Click on image to enlarge.

The above is a screen capture of the Select Scenario screen from General Staff. We anticipate shipping with about 20-30 scenarios and this is the first. This first scenario is an – obviously – fantasy match-up between Napoleon commanding portions of the Young Guard and U. S. Grant commanding the famous Iron brigade supplemented with an extra artillery battery and two regiments of cavalry.

We anticipate producing three or more scenarios for every map that we create. Most of the maps will be of historical battles from the 19th century and before. Are there particular battles that you would like to see in General Staff? Please drop us a line.

This first scenario was created to test the AI (crossing rivers and defending bridges), taking advantage of hills and the road net.