Thursday, June 30, 2011

Le Jeu de la Guerre thoughts

During 2005 I tried to make a computer game version of Le Jeu de la Guerre (war game) by Guy Debord. I never finished it. It didn't help that the translation was poor (and still is in the latest English translation. Corrections here and here.)

I stumbled on Kriegspiel again while writing a negamax algorithm to play noughts and crosses. Debord said of Kriegspiel:
So I have studied the logic of war. Indeed I succeeded long ago in representing its essential movements on a rather simple game-board… I played this game, and in the often difficult conduct of my life drew a few lessons from it — setting rules for my life, and abiding by them. The surprises vouchsafed by this Kriegspiel of mine seem endless; I rather fear it may turn out to be the only one of my works to which people will venture to accord any value. As to whether I have made good use of its lessons, I shall leave that for others to judge. (Panegyric, 1989)

Debord need not have feared, I doubt Kriegspiel will ever be accorded much value. It's not a terrible game, but it doesn't offer all that much either.

One concept that Kriegspiel does very well is the lines of support. I've always loved how you need to keep your units supplied from the arsenal and relay units, else they become useless. That idea is evocative and well implemented.

Nevertheless, I think Heller sums up the game nicely: "Between the arithmetic and the boggling geometries, it may, in fact, be reminiscent of a certain dream you had the night before the SAT." (What is it good for? Guy Debord believed his war board game would be his legacy)

Of more interest, however, is trying to determine who Debord was by the rules he defined for Kriegspiel.

Kriegspiel is a perfect information game. In war, there are spies, scouts, propaganda, miscommunication, stealth, radar, etc. I don't see how a perfect information game captures the "essential movements" of warfare. I wonder why he chose it. Did Debord not like leaving anything to chance? Was he always completely honest (wasn't interested in hidden units/movement)?

The terrain is asymmetric, yes, but the opponents face each other as equals. For someone who lived the class war, I find it strange that Debord didn't apply the asymmetry to the players. There has probably never been a battle where opponents faced each other with equal force. Not Bored discuss this lack of asymmetry in Dispensing with Clausewitz, though I don't agree with their defence of Kriegspiel/Debord. As McHugh points out, Debord would have experienced asymmetry in '68, yet it's not there in Kriegspiel. Yes, '68 wasn't a war but it was an armed conflict and even so, there are hundreds of historical examples of asymmetrical conflicts (Battle of Thermopylae, Battle of Rorke's Drift, US vs Vietnamese, US vs Afgans, etc.)

Debord designed Kriegspiel as a zero-sum game. Zero-sum games are great but they often don't reflect the subtly of reality. They are just on/off, binary type games. Zero-sum games are not what I imagine a communist or someone who thinks dialectically would create.

Still, Kriegspiel is an interesting game. I noticed that the two computer implementations of it don't have a computer opponent. One day I might get around to writing one. I wonder what Debord would have thought when a computer plays the game better than he could ever have.

Tuesday, June 28, 2011

Computer Opponent: Noughts & Crosses

The next task on my list for making a strategy game is writing a computer opponent. In the tutorial I describe how I’ve used variations on the minimax algorithm to play noughts and crosses (tic-tac-toe). I chose noughts and crosses because it’s finite (always ends in 5-9 moves) and simple, yet there are thousands of different solutions. Eventually, I plan on using a minimax type algorithm for a game which will use the hex board tutorial I created in Unity earlier.

The C# source code for this project is available here.
The tutorial is available here.

The end result of this project is a console application that plays noughts and crosses with itself. It cycles through games using negamax, alpha-beta pruning and negascout. Every game is, of course, a draw. (You may notice that negascout is slower than alpha-beta pruning. This is because I haven’t ordered the search tree, it’s such a simple game that it isn’t worth it.) There is also a test project that runs a number of tests to make sure that the algorithms are doing what I expect them to do.

Friday, June 17, 2011

Unity, hexagons and path-finding

I’m creating a strategy computer game again. This time I thought I’d write some tutorials as I go. In this tutorial, I bring path-finding on an hexagonal grid together with Unity.

I assume a good knowledge of C# and no knowledge of Unity. If you know how the A* search algorithm works, you’ll probably be able to read all the code without any problems.

You can access the tutorial here.
The source code and Unity project file are available here (7zip).
A Windows binary is available here.
A Mac binary is available here.

Screenshot of the result

Wednesday, June 8, 2011

MSI, Orca and file permissions: or it's 2011 and installers still suck

I had to create an MSI for distributing some software. After installing, I noticed that one of the files didn't allow read/write permissions to my application. You'd think that would be easy to fix: just go into Visual Studio, select the file and change the security permissions, right? Wrong.

If you have the same problem, one way to resolve it is:
  1. Download Orca (it allows you to edit MSI files)
  2. Run Orca and open an MSI file
  3. Go to the LockPermissions table
  4. Add a new row and fill in four of the five fields (see image). The fields are:
    1. LockObject (the ID of the file, this is found in the File table);
    2. Table (the name of the table that you're editing, in this case the "File" table, but it could be "Registry" or something else);
    3. Domain (I left this bank);
    4. User (I put in "Everyone" which is incredible insecure, but I really don't care);
    5. Permission (the meaning of the numbers is explained here);
  5. Save the MSI and exit Orca

Usually, installed files take on the permissions of the directory they are installed to. If you install to "C:\Program Files," your files will get the permissions that the program files directory has. However, using LockPermissions will overwrite all of these permissions and just assign SYSTEM and the permissions you added in the LockPermissions table. This is super-dodgy, but then, the whole thing is super-dodgy. Other people recommend using a custom action as part of the installation, e.g., using "ICacls". This is probably a better way to do it, I was just running out of time.

Tuesday, June 7, 2011

1 in 70 trillion

I was talking to Liz about Aida (our new child) the other day. She wanted to see a catalogue of what all the different versions of our children would look like. "Hmm...", I thought. "I think that would be quite a big catalogue." It's currently impossible to produce such a catalogue as we don't know all the genes that contribute to appearances. However, I did figure out how unique Aida is.

There are 46 chromosomes per individual. During reproduction 23 chromosomes come from each parent. Therefore, there are 223 (8,388,608) different possible reproductive cells per parent. Each egg could combine with any of the 223 different sperms, so there are 8,388,6082 or 70,368,744,177,664 (70 trillion) different combinations of people that could result between any human couple.

Aida is not so much one in a million, but 1 in 70 trillion. (This does not take into account random mutation.)

If we were going to look through the catalogue, at one snapshot a second, it would take a million years to see every possible combination.

If Liz and I were any other of the great apes, Aida would be far more unique, 1 in 281,474,976,710,656 (281 trillion) as most of the great apes have 48 chromosomes rather than 46 (one of ours got fused along the way).