Pathfinding revisited

The other day someone enquired about some code I wrote almost 10 years ago. It's about pathfinding, hexagons and Unity.

Unity projects are a pain. When I don't use it for about 2 weeks, I forget everything about it. Getting it into source control is another issue in itself.

It's working again. It's on github. I followed How to Git with Unity to get the code properly under source control.

Maybe I'll look at it again in another ten years.

Troubles with Unity and Mono

Using Unity for my Othello game was not without issues. The biggest issue I experienced related to Unity's use of Mono. Here is why:

A depth-first search generates a lot data. Oridinally, in .NET, that would be fine. You create the data, process it and forget about it - the .NET garbage collector (GC) will release the data from memory when required. That isn't true of Mono 2.6. The garbage collector in Mono 2.6 is kind of rubbish. (See what I did there?) Mono 2.8 has a new garbage collector, but Unity 3.5 uses Mono 2.6. And my Othello game uses Unity 3.5.

For my Othello implementation, every turn by the computer player was a new search. It leaked memory all over the place because the GC wasn't dumping the data. It could easily use a gig of RAM over a game, even with shallow searches (depths of 5 or less).

To resolve this issue, I - though Andrew came up with the idea - used a struct instead of a class for the objects used in the search (EvaluationNode and GameState). I re-used memory by storing search results in arrays where the indexes were reset every turn of the game. This negated the need for garbage collection. In the source code, the classes that manage this process are called the EvaluationNodeBuffer and EvaluationNodeCollection.

These changes turned out to be a really good use and re-use of memory. It is also an excellent example to demonstrate the differences between a struct and a class. It also allowed me to search to much greater depths for the computer player.

A problem with this technique is that it makes it very difficult to write code to re-use part of the search tree between turns. Finding which parts of the tree to prune and to then re-organise the arrays and indexes would be technically tricky and CPU intensive. Therefore, for now, the computer player continues to re-searche all game states between turns. Furthermore, any sort of parallel programming to speed-up the search would be hindered by this approach.

What about Unity 4? That's out soon. Will that support the newer version of Mono? Unfortunately not.

We will be shipping Mono 2.6 with Unity 4.0. This will allow the same subsets of .NET features as in Unity 3, depending on the profile you choose in your player settings. (Unity 4 FAQ)

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.

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 in a github repo.
A Windows binary is available here.
A Mac binary is available here.

Screenshot of the result