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.

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

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.

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 2²³ (8,388,608) different possible reproductive cells per parent. Each egg could combine with any of the 2²³ different sperms, so there are 8,388,608² 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).

WPF copy/paste column names on DataGrid

I always forget that you can easily include column names when copying a DataGrid by setting

ClipboardCopyMode="IncludeHeader"

in the XAML of the DataGrid.

Death in Haiti

From my sister:

One of my neighbours, Abner, caught cholera a few weeks ago. He is the baker and the father of the girls who fetch my water, do my washing and occasionally cook for me.

Anyway he spent a week or so in hospital, was let out, went to someone we would probably call a witch doctor, and then returned home yesterday on a stretcher, no longer able to speak. He died last night, his daughters and wife started wailing at 2am in the morning - the traditional way of expressing grief and letting everyone know that he passed away. Of course, the worse part is that he leaves behind his family of 4 daughters (one of whom has a 4 month old baby) and 2 sons (one 4 years old, the other a teenager). I have no idea how they are going to survive this. I suspect the girls wont be going to school for much longer.

Cholera has returned to my zone, after a brief reprieve... I just wish they’d wash their bloody hands.

Just one person dead, yet it made me feel a lot more sad than "By late January 2011 some 4,131 people have died and 117,312 are hospitalised." (wikipedia) Of course, I already knew it would, but even as someone who has tried to think/feel in large numbers and concepts, to feel worse about a single case than other 4,130, is really pathetic. Truly pathetic. Even more so because the cholera outbreak is a tiny number of people. As far as deaths go, this has only just surpassed the most over-hyped event of the naughties. (Though, to be fair, millions of people had their lives ruined because of it - 1 & 2) Compared with other events, it's not even worth mentioning (and isn't mentioned). It's an order of magnitude less people than the earthquake in January 2010. Not even worth mentioning.

The second thing that affects me is "I just wish they’d wash their bloody hands." I know exactly what my sister means. It seems utterly absurd. A simple, obvious, easy solution. It's as though Haitians are willing themselves to die. Are they simply stupid brown people? I think a lot of people in the West would answer "yes" to that question. I lot of people I know would answer "yes" to that question. The same people who live their lives drowned in their own absurd beliefs and superstitions. This society functions - its modus operandi - is faith and superstition. Just because our beliefs don't have us dying of easily preventable water-born diseases, doesn't mean that our own absurdity doesn't cripple our existence as obese, angry, faithful, TV watching drones.

It's sad, it's strange, but it's perfectly understandable why someone wouldn't think to wash their hands and go to a witch doctor instead of getting proper treatment.

It's a fucked-up world and all I know is that it doesn't actually have to be like this. The solutions exist already - the solutions to cholera, obesity, faithfulness and irrationality all exist. But finding that path out of madness, that's the only difficult problem left to solve.

The worst thing about Entity Framework

Generally, I like Entity Framework, especially the newest version (part of Visual Studio 2010). The absolute worst thing about it is the error message you can get when you are hooking-up your POCO files to an entity model. The error message is: "Mapping and metadata information could not be found for EntityType [...]"

EF tells you in which class the error is located, but that's it. It could be any of the properties that don't work! If you have a database table with 20 or 50 fields, good luck in tracking down the error. The best info I've found is that the error can be caused by:

• Misspelled properties (case-sensitive!)
• Properties missing in the POCO class
• Type mismatches between the POCO and entity-type (e.g., int instead of long)
• Enums in the POCO (EF doesn't support enums right now as I understand)

It has got to be the worst error message I've seen from Microsoft in a long time.