Tag Archives: A Star

Why Machines May Kill Us In Our Sleep

4 Replies

An amazing screen capture of the AI’s solution to a problem. It has found a 1 pixel gap between the data and the edge of the screen and is exploiting it to successfully find an ‘open flank’ of Red. Click to enlarge.

Professor Alberto M. Segre was my thesis advisor and one day he said to me, “You know when your AI is really working because it will surprise you.” Today I got to have one of those weird surprises.

The screen shot (above) is a visual representation of what the AI is up to. You won’t get to see this in the actual game. The program that’s running is called the AI Editor which is a bit of a misnomer because you don’t actually edit the AI in it; you mostly just get to observe what it’s doing. There’s a lot of stuff going on in the above image. There are multiple layers visually displaying different types of data (check out the blog – Layers: Why a Military Simulation is Like a Parfait – for more information about these). But, what interests us are the AI layers: Battle Groups, Objectives, and that thin yellow line that snakes from a group of blue units, crossing Antietam Creek at the Middle Bridge and then, amazingly, exploiting a data anomaly to reach its goal: a point far behind enemy lines.

Some background on the situation:

The map of the Antietam Battlefield (screen shot) with terrain and elevation layers displayed. Click to enlarge.

Underlying all the clutter from the first screen capture, top, is the battle of Antietam (above). The map has been rotated 90 degrees to the left so north is now pointing to the left; east is at the top of the screen.

After adding Blue (Union) and Red (Confederate) units to the map in their historical positions at 0600 September 17, 1862 the AI performed a tactical analysis from the perspective of Blue.

The AI ‘strategic’ analysis for Antietam playing Blue (Union).

The above are a list of Predicate Statements all of which the AI knows to be true. Statements preceded by the logical sign ∴ (therefore) are conclusions, or inferences, derived from the predicate statement referenced in the brackets. It is this analysis that determines if the AI will be on the offensive or defensive and what its objectives will be.

Next, the AI performs Range of Influence (ROI) calculations for the entire observable battlefield. I plan on doing a video about this later, but for now the darker the red (in the topmost screen capture) the more – and more powerful – weapons the Red army can bear on that point.  The AI next divides all the units on the map into a forest of minimum spanning trees called Battle Groups. I want to do a video about this, too. However, if you can’t wait, these subjects are covered in my paper, Implementing the Five Canonical Offensive Maneuvers in a CGF Environment (free download).

Again, referring to the top screenshot you can see the AI’s calculations to this point:

  • It has determined it (Blue) will be on the offensive.
  • It has calculated enemy ROI.
  • It has assigned objectives to the first Battle Group.

Flanking Algorithm published in, “Algorithms for Generating Attribute Values for the Classification of Tactical Situations”. Click to enlarge.

Now the AI needs to determine if the enemy has an ‘open or unanchored flank’. In Algorithms for Generating Attribute Values for the Classification of Tactical Situations I published the Algorithm for Flanking Attribute Value Function (right). It basically comes down to this: can the AI trace an unbroken path from the center of the Blue Battle Group to a specific point (called the Retreat Point) far behind enemy lines without crossing into ‘No Go Areas’ (water, swamp) or entering any area controlled by Red’s ROI (literally the red areas in the topmost screen shot).

The reason that I was using Antietam as a test case for anchored / unanchored flanks is because years ago I had analyzed the battle for my doctoral thesis and knew it to be a classic example of anchored flanks; Lee’s left flank rests on the Potomac and his right flank is anchored on the Antietam. Granted, the Confederate flanks were held by Stuart’s cavalry with a little horse artillery support but they were still, by definition, anchored flanks.

Due to an error in the data that made up the Antietam terrain map a 1 pixel (about 3.8 meter wide) strip of ‘no terrain’ was inserted at the far right hand edge of the map (see blow up of screen capture, right; it’s the thin line between the water, represented in red, and the brown edge of the map). This meant there was a ‘land bridge’ across Antietam Creek where none existed in real life. A digital parting of the Red Sea, if you will. But, by the rules of the game the AI perfectly performed its function. There was no error in the AI – again, the AI performed better than I had dared hope – the error was with the data set.

And that’s how fifty years from now I can see a cyber-detective standing over the chalk marks around a body saying, “Yeah, the machine performed perfectly, brilliantly, in fact. But, the error in the data set killed him.”

It’s already happened in real life. For cars with autopilot the data set of the world in which it operates is crucial. However, “against a bright spring sky, the car’s sensors system failed to distinguish a large white 18-wheel truck and trailer crossing the highway, Tesla said. The car attempted to drive full speed under the trailer, “with the bottom of the trailer impacting the windshield of the Model S”, Tesla said.” The driver died. The AI functioned perfectly. But, the error in the data set killed him.

So, I fixed the error in the data set (probably caused by not using the right values in InkScape when I converted the Antietam Water.bmp into paths) and imported it back into the Antietam map using the General Staff Map Editor, saved it out, and ran the AI Editor again and saw this:

The AI did not display a yellow path from the center of the Blue Battle Group to the Red Retreat Point because none existed. Instead, it just wrote the first Predicate Statement in the Tactical Analysis stack: “Red’s flanks are anchored”.

Again, the machine was performing perfectly. And its results were no longer surprising.

Addendum

I recently got to experience this again (though this time it was caused by a different data bug) when I was reviewing the AI’s decisions at the battle of Manassas:

Because the Range of Influence was not calculating the very bottom row the AI found another, perfectly legal, way to reach its goal. Screen shot from the General Staff AI Editor. Click to enlarge.

In this instance, the error in the database was caused by the Range of Influence (basically a map of what red and blue can see and hit) not calculating the very last row. Consequently, the AI was able to legally trace a path from the blue forces in the northeast to their goal at the bottom of the map.

After this bug was corrected the AI performed as expected:

The AI correctly sees going around red’s left flank as the solution to the problem. Screen shot from General Staff AI Engine. Click to enlarge

In the above screen shot the AI has demonstrated the correct solution to the tactical problem facing blue at Manassas on July 20, 1861 (the day before the actual battle). Red’s left flank is unanchored. It’s wide open. Note how the AI identifies the one choke point (Sudley Springs Ford) in the plan.

So, the AI surprised me again. I think it’s looking pretty good. When you play against it, watch your flanks.

Maps, Commanders & Computers

3 Replies

How a map of the battle of Antietam looks to us humans. Screen shot from the General Staff Map Editor. Click to enlarge.

How the computer sees the same map (terrain and elevation). This is actually a screen shot from the Map Editor with the ‘terrain’ and ‘elevation’ layers turned on. Click to enlarge.

Computer vision is the term that we use to describe the process by which a computer ‘sees'1)When describing various AI processes I often use words like ‘see,’ ‘understand,’ and ‘know’ but this should not be taken literally. The last thing I want to do is to get in to a philosophic discussion on computers being sentient. the world in which it operates. Many companies are spending vast sums of money developing driverless or self-driving cars. However, these AI controlled cars have had a number of accidents including four that have resulted in human fatalities.2)https://en.wikipedia.org/wiki/List_of_self-driving_car_fatalities The problem with these systems is not in the AI – anybody who has played a game with simulated traffic (LA Noir, Grand Theft Auto, etc.) knows that. Instead, the problem is with the ‘computer vision’; the system that describes the ‘world view’ in which the AI operates. In one fatality, for example, the computer vision failed to distinguish a white semi tractor trailer from the sky.3)https://www.theguardian.com/technology/2016/jun/30/tesla-autopilot-death-self-driving-car-elon-musk Consequently, the AI did not ‘know’ there was a semi directly in front of it.

In my doctoral research I created a system by which a program could ‘read’ and ‘understand’ a battlefield map4)TIGER: An Unsupervised Machine Learning Tactical Inference Generator http://www.riverviewai.com/download/SidranThesis.html. This is the system that we use in General Staff.

The two images, above, show the difference in how a human commander and a computer ‘see’ the same battlefield. In the top image the woods, the hills and the roads are all obvious to us humans.

The bottom, or ‘computer vision’ image, is a bit of a cheat because this is how the computer information is visually displayed to the human designer in the General Staff Map Editor. The bottom image is created from four map layers (any of which can be displayed or turned off):

The four layers that make up a General Staff map.

The background image layer in a General Staff map is the beautiful artwork shown in the top image. The place names and Victory Points layer are also displayed in the top image. The terrain and elevation layers are described below:

The next three images are actual visual representations of the contents of memory where these terrain values are stored (this is built in to the General Staff Map Editor as a debugging tool):

Screen shot from the Map Editor showing just terrain labeled as ‘water’. Click to enlarge

Screen shot from the General Staff Map Editor showing the terrain labeled as ‘woods’. Click to enlarge.

Screen shot from the General Staff Map Editor showing the terrain labeled ‘road’. Click to enlarge.

A heightmap for Antietam. This is a visual representation of elevation in meters (darker = lower, lighter = higher). Click to enlarge.

To computers, an image is a two-dimensional array; like a giant tic-tac-toe or chess board. Every square (or cell) in that board contains a value called the RGB (Red, Green, Blue5)Except in France where it’s RVB for Rouge, Vert, Bleu  ) value. Colors are described by their RGB value (white, for example, is 255,255,255).  If you find this interesting, here is a link to an interactive RGB chart. General Staff uses a similar system except instead of the RGB system each cell contains a value that represents various terrain types (road, forest, swamp, etc.) and another, identical, two-dimensional array, contains values that represent the elevation in meters. To make matters just a little bit more confusing, computer arrays are actually not two-dimensional (or three-dimensional or n-dimensional) but rather a contiguous block of memory addresses. So, the terrain and elevation arrays in General Staff which appear to be two-dimensional arrays of 1155 x 805 cells are actually just 929,775 bytes long hunks of contiguous memory. To put things in perspective, just those two arrays consume more RAM than was available for everything in the original computer systems (Apple //e, Apple IIGS, Atari ST, MS DOS, Macintosh and Amiga) that I originally wrote UMS for.

So, not surprisingly, a computer stores its map of the world in which it operates as a series of numbers 6)Yes, at the lowest level the numbers are just 1s and 0s but we’ll cover that before the midterm exams. that represent terrain and elevation. But, how does a human commander read a map? I posed this question to Ben Davis, a neuroscientist and wargamer, and he suggested looking at a couple of studies. In one article7)https://www.citylab.com/design/2014/11/how-to-make-a-better-map-according-to-science/382898/, Amy Lobben, head of the Department of Geography at the University of Oregon, said, “…some people process spatial information egocentrically, meaning they understand their environment as it relates to them from a given perspective. Others navigate more allocentrically, meaning they look at how other objects in the environment relate to each other, regardless of their perspective. These preferences are linked to different regions of the brain.” Another8)https://www.researchgate.net/publication/251187268_USING_fMRI_IN_CARTOGRAPHIC_RESEARCH reports the results of fMRI scans while, “subjects perform[ed] navigational map tasks on a computer and again while they were being scanned in a magnetic resonance imaging machine.” to identify specific, “involvement or non-involvement of the brain area.. doing the task.”

So, how computers and human commanders read and process maps is quite different. But, at the end of the day, computers are just manipulating numbers following a series of algorithms. I have written extensively about the algorithms that I have developed including:

  • “Algorithms for Generating Attribute Values for the Classification of Tactical Situations.”
  • “Implementing the Five Canonical Offensive Maneuvers in a CGF Environment.”
  • “Good Decisions Under Fire: Human-Level Strategic and Tactical Artificial Intelligence in Real-World Three-Dimensional Environments.”
  • “Current Methods to Create Human-Level Artificial Intelligence in Computer Simulations and Wargames”
  • Human Level Artificial Intelligence for Computer Simulations and Wargames.
  • An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps’

These papers, and others, can be freely downloaded from my web site here.

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

References

References
↑1 When describing various AI processes I often use words like ‘see,’ ‘understand,’ and ‘know’ but this should not be taken literally. The last thing I want to do is to get in to a philosophic discussion on computers being sentient.
↑2 https://en.wikipedia.org/wiki/List_of_self-driving_car_fatalities
↑3 https://www.theguardian.com/technology/2016/jun/30/tesla-autopilot-death-self-driving-car-elon-musk
↑4 TIGER: An Unsupervised Machine Learning Tactical Inference Generator http://www.riverviewai.com/download/SidranThesis.html
↑5 Except in France where it’s RVB for Rouge, Vert, Bleu
↑6 Yes, at the lowest level the numbers are just 1s and 0s but we’ll cover that before the midterm exams.
↑7 https://www.citylab.com/design/2014/11/how-to-make-a-better-map-according-to-science/382898/
↑8 https://www.researchgate.net/publication/251187268_USING_fMRI_IN_CARTOGRAPHIC_RESEARCH

New, Faster Pathfinding AI

Leave a reply
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.