Computer Reversi, Part 1 (Or how I learned to stop worrying and love the bits)

After noughts and crosses I thought I’d try Reversi (Othello). Reversi has simpler rules than chess but remains complex enough that it hasn’t been mathematically solved, yet.

I thought I’d find a wealth of information on the net about how to program a Reversi game. However, there wasn’t all that much out there. I found some helpful blog entries at Red Alt Blog. I used that as my starting point.

The best resource for understanding how to program Reversi is at the chess programming wiki. They have an Othello page as well as pages that helped me do a bitboard version of Reversi, with move generation and resolution (dumb7fill), population count (i.e., number of bits on the board) and board serialisation (using bitscans). I'm hoping it'll also be helpful for position evaluation later on.

The tasks needed to code a Reversi computer game with a learning computer opponent are

1. Game state representation
2. Move generation
3. Move resolution
4. Determine game over and winner
5. Graphic User Interface
6. Save/load and undo/redo moves
7. Position evaluation (i.e., fitness/objective function)
8. Depth-first search algorithm (e.g., mini-max or nega-scout)
9. Book/database based analysis (e.g., opening book, transposition tables) 
10. Mathematical optimisation (e.g., simulated annealing or genetic algorithm)

This blog entry addresses steps 1-6, providing source code for a Unity implementation of Othello. The game logic is written as C# and compiles as mono inside Unity. I assume knowledge of:

• C#
• Unity 3D
• Reversi rules

The following sections describe some interesting parts of the source code, relating with the first six steps outlined above.

Reading the source code

The entry point for the application (the Main method) is the Start method of the GameBehaviour.cs file. This file is attached to the main camera in Unity. The GameBehaviour.cs file creates the board and pieces as 3D objects and hosts an instance of GameManager (see below). It also manages the UI controls to save/load games, undo/redo moves, setup the human/computer players, start a new game, etc.

The files that do all the real work are:

• GameBehaviou.cs
• GameManager.cs
• GameState.cs
• BitBoardHelper.cs
• Play.cs

There are source files, 64-bit Windows binaries and Mac OSX binaries. There are two solutions files contained in the source files. The one named with VS2010 is the one you should open in Visual Studio. It contains a test project and a preliminary attempt at reading the Thor database format. But that will be for another post. You can load the project in Unity via the "Reversi.unity" in the Assets sub-folder.

GameManager

The GameManager class does the work-a-day tasks of the game. Tasks such as:

• Save/load
• Undo/redo
• Tells you whose turn it is
• Tracks the list of plays
• Tracks the turn number

GameState

My GameState class handles most of the game rules of a Reversi game. You pass it two unsigned 64-bit integers (ulong in C#). These numbers are a bitboard representation of the game. The first number represents the current player's pieces. The second number represents the opponent's pieces. E.g., the starting position for black is represented as 0000000000000000000000000001000000001000000000000000000000000000 in binary. When you lay out those zeros and ones on an Reversi board, you get:

Why represent the pieces like this? Bitboards appear to have advantages over other board representations. They appealed to me because I often feel withdrawn from the goings on of the computer. Bitboards were a chance to get in closer to the CPU and play around with individual bits.

One interesting aspect of the GameState class is that it is temporally agnostic. It doesn't know what turn of the game it is. It doesn't even know whose colour is to play next. All it cares about is that it is someone's turn and it figures out where they can play and what happens to the board once they do. I like the simplicity of not needing to deal with time.

The GameState class will tell you if the game is over and whether the current player has won.

BitBoardHelper

I created a BitBoardHelper class to add some extension methods to my ulong bitboards. These methods allow me to count the number of bits, find the indices of the bits and find the unoccupied bits of any two bitboards. I'll probably expand this class when I work on the computer opponent.

For finding the indices (bitboard serialisation) I used the De Bruijn method to do the bitscanning. For the bit count (population count) I used the SWAR Popcount routine.

Play

There is a Play class in the project that will find all the valid moves for the current player and also resolve a chosen move (i.e., flip of the pieces that need to flipped once a piece has been played). The basic idea is to focus one direction (cardinal or ordinal) at a time, scanning 8 locations in parallel. Red Alt explains it well (see under the bitboard heading). Once I could detect where a player could place a piece, I used a very similar method to resolve that move. This class is called by the GameState class and is only different to the BitBoardHelper class in that it has specifically Reversi functionality.

Graphic User Interface

The GUI uses the Unity 3D graphics engine. Much of the code that I use in the Reversi project is a simpler version to what is found in a previous article on Unity and path-finding. Unity displays the board and captures user input.

Save/load games and undo/redo moves

Save/load and undo/redo are interrelated. To do them, I need to keep track of the moves made by the players. If I do that, I can:

• Save: Write the move list to the hard drive.
• Load: Read the move list from the hard drive, start a new game, apply move list - one move at a time - until the last move is applied.
• Undo: Start a new game, apply move list until the desired turn (similar to load).
• Redo: Identical to undo.

Part 2

In Part 2, I intend to cover the aspects of creating a computer opponent for Reversi. The primary goal is to be able create an opponent that can beat me in a game. (Not a highly goal.) Hopefully, I'll be able to have it beat all but the best Reversi players.

Google Translate

Google Translate works quite well. Occasionally it does some weird things. For instance, it translates (from Spanish)

No me acuerdo bien cómo me aparecìa.

to

I do not remember exactly how I appeared.

That is exactly what I'd expect it to say. However, when I change it by one word, 

No me acuerdo muy bien cómo me aparecìa. 

I get

I remember very well how I appeared.

rather than

I do not remember very well how I appeared.

If you change the initial verb to a synonym, it's correct. I.e.,

No recuerdo muy bien cómo me aparecìa.

becomes

I do not remember very well how I appeared.

I assume it's an error in Google Translate rather than me missing the subtleties of the Spanish language. Yet it seems like such a weird thing to get wrong. I'd really like to get into natural language parsing one day. Maybe then I'd discover the answer.

Paragliding Tasmania

I and four other paragliding pilots went to the South West Tasmania in December 2011 to fly. On the first day we looked at the Sentinels then flew 12 Trees (5min flight, unfortunately). On the second day we did a couple of good flights off Mt Elisa. We had excellent conditions, mostly blue skies with a little bit of cumulus. Wind was light and nicely flowing up the ridges. Launching was relatively easy. Some of the thermals were strong but the cores were tight and difficult to exploit for beginners.

Flying with Lake Pedder in the background was amazing. Only Klaus (our Austrian import) had a good flight. He flew down to the last ridge then made his way up, above launch, above Mt Elisa, then eventually above Mt Anne. It was really impressive stuff. The rest of us merely delayed our descents. Nevertheless, it was incredibly good fun.

Photos from the trip can be found here.

After the South West, Mark and I tried to fly Winton (the most accessible site out of Hobart). Unfortunately the wind was high and we didn't have the confidence/experience to give it a go. It was good to watch the locals fly the site, however. Hopefully next time we'll get to fly there.

Editing IE settings in the registry via C#

We have a weird setup at work where our Internet Explorer LAN configuration settings are periodically reset by people who manage the network. This brings IE and TFS to a crawl for the programmers. It doesn't seem to happen to everyone all at once or at a designated time. It can take a few minutes to realise what is going on as there are a number of issues that show similar behaviour. For new programmers, this is especially frustrating because they're not aware of this strange policy.

To the Windows registry Batman! I haven't played with this thing in years. I never really understood it very well. "Hierarchical database? All these weird names? Huh? What's going on?!" Seems so simple now.

Editing the registry in the .NET environment is easy. See here.
Finding how to change LAN proxy configuration settings took a little longer to find. Explained here.
Proxy exceptions? See here.

With the app working, all that is left to do is set the script to run every 15mins on the programmers' computers, and we're done.

Code looks like:

var key = Registry.CurrentUser.OpenSubKey(@"Software\Microsoft\Windows\CurrentVersion\Internet Settings\Connections", true);
 
if (key == null)
  throw new NullReferenceException("Registry SubKey not found.");
 
const string defaultConnectionSettings = "DefaultConnectionSettings";
var defaultConnectionSettingsValue = (byte[])key.GetValue(defaultConnectionSettings);
 
defaultConnectionSettingsValue[8] = 1;
key.SetValue(defaultConnectionSettings, defaultConnectionSettingsValue, RegistryValueKind.Binary);

Code generation in C#

I wrote my first code generator on the weekend. The real work - generating the C# class files - was trivial. Getting the generator into a state so that it could be easily used was more difficult.

There are a few ways you could do code generation in .NET. I explored:

• Console application that churns out ".cs" files
• Custom Tool for Visual Studio
• T4 Templates

I went with T4 Templates. They were a little obscure at first but provided the easiest entry point into using the code generator. You just build-up your source file and then right-click and select "Run Custom Tool" on the .tt file to generate the code.

I encounted a few issues when trying to write my template. They were:

• Extension methods can't be embedded into a T4 Template. There is a workaround. I ended up converting my extension methods into normal methods (I only had two).
• Accessing your assemblies is difficult in Visual Studio 2010. It has been explained very well. I managed to access my assemblies by writing something like <#@ assembly name="$(SolutionDir)..\DomainEntities\bin\Debug\Cpa.DomainEntities.dll" #>

The example T4 Templates I found on the Internet were a little more complex than what I wanted. (Examples should be as simple as possible.) I wanted to load a source file into memory and generate class files from that. Download my example template if you want something similar. It loads in a CSV file that has two columns (first column is the name of the class, second column the name of the property) and generates some puesdo-code of what the class files will eventually look like. I used this as my base template, then expanded it to create proper C# class files.

Comments on Skyrim

I've been playing Skyrim in my (ever dwindling) spare time.

Good things:

• I play by simply allowing myself to be drawn to whatever seems interesting. I don't particularly care about completing quests, I wander. It's working really well for me. I'm often stumbling onto something interesting.
• I went on a quest to recover a helmet. (I deliberately chose the most banal of the quests.) It was fun. I crossed over a bridge in a treacherous cavern. I fought a couple of frost trolls. Burnt 'em.
• I started back to Solitude (a city of Skyrim) and saw the ghost of a headless horseman ride by. It just appeared and rode off. I tried to follow it for a while but was distracted by some midnight revellers who offered me a drink. I drank. When I looked back, the horseman was gone.
• I saw some rabbits hopping around underwater. Then I saw a white wolf walking underwater. Mammals in Skyrim have strong lungs.
• On the quest to "find King Olaf's verse," I made my way to the body of Svaknir, at the bottom of a stairway. I was expecting to find a book here. There was no book. My character became trapped in a dungeon, never to escape. (Some bugs are cool.)

Bad things:

• Books in Skyrim are boring. Tip for next time: Bethesda, if you're going to have poorly written text, write less of it and link it to the gameworld in some way. I only open books because of the possible quests or skill bonuses.
• Food appears to be useless. They've put so much effort into it, it would have been good to have a requirement where you need to eat and drink occasionally to keep your stamina up.
• The UI is bad. You can use it and thankfully the core of it (choosing spells and items) is okay, but it's still bad. You have to hit 'tab' to close the menu? What's wrong with 'esc'? See: interface comments.

Skyrim screenshots

Occupy Melbourne

I went to my first Occupy Melbourne general assembly this evening (the 16th they've had). It wasn't deliberate, I was walking on Swanston St, eating my chips & tomato sauce, and there they were. I stayed for a couple of hours. My impressions follow.

I'm not very good with numbers, maybe there were 100 people. They used the (predominate) megaphone and the human microphone. Decisions were run on a consensus basis.

It was very much a left ghetto event. However, it was as though the factions had set their differences aside for participation in Occupy Melbourne.

The first hour was reports from various workgroups (legal, direct action, media, etc.) on what they’d been doing since the last GA. The legal team were going to court over whether Occupy Melbourne could have structures and political posters at Treasury Gardens. They wanted people to await the outcome of legal proceedings before Occupy Melbourne decided to do anything more.

I was disinterested by the first hour. If I were a part of Occupy Melbourne, maybe I’d have been more interested (but probably not).

After the reports there were some more substantial suggestions. The first motion was that Occupy Melbourne has a minute silence for the dead of WWI. I was shocked. I had thought that nothing so conservative would ever dare to be tabled. A show of hands for, then against. There was massive dissent. It was quickly reformulated as "all that have died in all wars". There was massive dissent. Others spoke against war per se. They didn’t want to honour victims, they wanted to attack the perpetrators of war, the 1%. I was encouraged by this, but by then, 10-20min of my life had already disappeared before the motion was thrown out. (I definitely would have walked away forever if it had been accepted in any of its forms.)

After, there was a proposal that we build structures on Saturday, regardless of the legal outcome. There was general (60-70%) support for this. One dissenter made an absurd analogy to guerrilla tactics saying "now is not the time to attack but harry the enemy." This received quite a bit of support. One commenter riposte with "This isn't the Vietnam war." Another dissenter talked of not wanting to jeopardise legal proceedings (the interim outcome, everyone already knew, would be known before Saturday). This rhetorical nonsense (clearly suffering for causal misdirection), received even more support than the guerrilla fighter. However, speakers for or against were unable to sway the numbers significantly. (I voted for occupation with structures, too horrified by the nonsense of the dissenters to abstain any longer.) It was decided to revisit the issue on Saturday. After that, I left.

I was generally quite impressed. For all my critical thoughts, it seemed like a movement with promise. Are the "Occupys" around the world the beginnings of a 21st century soviet? I don't know. I don't think anyone could know that. They probably aren't though. They'll probably fizzle and burn out. To avoid that fait, they need to inspire people to take control of their lives. I have no idea how they're going to do that. Hundreds of years of failure gnaws at the edges of the general assembly.