08 February 2009

Game Theory Week: The Homicidal Chaffeur

To most gamers, and probably even most mathematicians, the games in Game Theory don't actually have much to do with the games we like to play for fun. The Curmudgeon Gamer put it very aptly:
In case you aren't aware, "Game Theory" is a bait-and-switch ruse right up there with "Greenland". Somehow they managed to take the field of strategic game-playing and restrict it only to games no one would ever want to play. (Apparently there was some analysis of actual games in there at the beginning, but that was swiftly excised, lest anyone actually enjoy themselves.) [emphasis added]
A fair criticism too, because I looked long and hard in the literature without finding any real mention of the mathematical exploration of games. It turns out I wasn't looking in the right place, but one day a very crafty lady (my wife, naturally) made a good find, and got me a nice birthday present: old book by some guy named Rufus.

Rufus Isaacs Differential GamesRufus Isaacs gave mathematical formulation to real problems such as games of Pursuit and Evasion. In doing so, he opened up a new field of mathematics. His book Differential Games is a classic (available at Amazon.com for under $13!). It probably helps to have a good math background to follow along, because it makes use a lot of use of trigonometry, calculus, and differential equations, but it's written as a discussion and introduction to the problems rather than as a textbook. You can read the first chapter and most of the second on Google Books.

Differential Games Bomber Intercept guarding targetIsaacs did a lot of classified work at the RAND Corporation, are many of the problems he discusses are versions of pursuit and evasion that are actual real military considerations, such as intercepting a bomber before it can reach a target area. These are not simple problems, but it's not too hard to see this sort of problem is not too different from that of playing a game that represent a real military problem.
[Image Google Books]

Rufus Isaacs Differential Games Homocidal ChaffeurOne of the most basic problems in differential game is that of a vehicle trying to intercept a moving target, and Isaacs called this problem (with some humor intended) the "Homicidal Chaffeur". You can find a nice description and short discussion of The Homicidal Chauffeur at Reasonable Deviations.

Rufus Isaacs Differential Games Homocidal ChaffeurDifferential Games go a long way toward taking game theory in the direction of games we know and love to play. It's NOT a simple topic, but we already knew that games are far from simple. It's not surprising - and perhaps even gratifying - to learn the games we play are so fantastically complex. I've actually worked through a few simple examples of discrete differential games that occur in boardgames (well, Battletech anyway). Those examples will probably find their way to becoming blogs posts eventually, but I have some other ground to cover before I tackle differential games for myself.
[Image Google Books]

2 comments:

scrapyardarmory said...

Oh goodness, You better get around to those posts. Suicidal Chauffeur Battletech implications? I'm totally there with you.

Dan Eastwood said...

You are already there, every time you play! Just picture the chauffeur armed with a medium laser. (The pedestrian might be armed too)