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.

VB.NET cheat sheet

I've been doing quite a bit of programming in VB.NET recently. It's almost exactly the same as C# but a few things have caught me out. I've written up a small cheat sheet with the noticeable differences (plenty of websites will give you a huge list of irrelevant differences).

Keywords

C#	VB.NET
this	Me
base	MyBase
abstract	MustOverride/MustInherit
virtual	Overridable
sealed	NotInheritable
class Class : Interface	Implements (statement)
internal	Friend
static	Shared
typeof()	GetType()

If you want a static class in VB.NET, you'll need to use the Module keyword.

(One thing to note here is how much more intelligible some of the VB.NET keywords are.)

Logic

C#	VB.NET
&&	AndAlso
||	OrElse

There is no equivalent for And and Or in C#.

Numeric type suffixes

C#	VB.NET
12.34M (for Money)	12.34D (for Decimal)
12.34D (for Double)	12.34R (for Real)

Lambdas

C#	apples.Single(x => x.Colour = "red")
VB.NET	apples.Single(Function(x) x.Colour = "red")

Initialising lists and objects

C#	var apple = new Fruit { Colour = "green" };
VB.NET	Dim apple = New Fruit With {.Colour = "green"}

C#	var apples = new List { new Fruit { Colour = "red" }, new Fruit { Colour = "green" } };
VB.NET	Dim apples = New List(Of Fruit) From {New Fruit With {.Colour = "red"}, New Fruit With {.Colour = "green"}}

Anonymous types

C#	apples.Select(x => new { Colour = x.Colour });
VB.NET	apples.Select(Function(x) New With {.Colour = x.Colour})

Nulls and Nothing

If you're coming from C#, the Nothing keyword does not do what you'd expect. What would you expect the following code to do?

Dim value = ""
If value = Nothing OrElse value Is Nothing Then
    Throw New Exception()
End If

If you said "not throw an exception" you'd be wrong. Weirdly, the first condition is true but the second condition is false, so it throws. Compare with similar C# code:

var value = "";
if (value == null)
    throw new Exception();

In this case, the exception doesn't get thrown.

Euler problem 19

I started writing this blog entry a year ago. It's about an Euler problem I solved in F#. The code makes more sense to me now than it did a year ago and I haven't touched F# since then. I guess I'm just way smarter now.

---

Solving Euler problem no. 19 is the solution I'm most proud of. It's the first problem that I solved in F# with no assistance by the 'net.

The problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

It isn't an overly complex problem but there a couple of tricky aspects. The approach that I used was to start on the first Sunday of 1901 (6th Jan) and add seven days over and over (i.e., only counting Sundays) until the end of 2000. I could have used the .NET DateTime type to solve this problem very easily, but I decided to see if I could solve the problem using my own date type.

I solved the problem by using a few F# features, namely:

• pattern matching
• tuple
• record
• list

The first problem was February. February is a prickly month. Pattern matching will solve it! The febDays function accepts a year as a parameter and returns the number of days that February has.

    let febDays y = match y with
                            | y when y % 400 = 0 -> 29
                            | y when y % 100 = 0 -> 28
                            | y when y % 4 = 0 -> 29
                            | _ -> 28

After February was ready, I needed to know the number of days in any month, given the month (as a number) and the year. I used pattern matching again. Therefore,

    let daysInMonth (m, y) =
            match m with
            | 2 -> febDays y
            | 4 | 6 | 9 | 11 -> 30
            | _ -> 31

The other interesting function was to be able to add a day to a date. I did:

    let addDay date =
        match date.day with
        | d when d < 1 || d > daysInMonth(date.month, date.year) -> failwith "Not a valid day of the month."
        | d when d = daysInMonth(date.month, date.year) -> match date.month with
                                      | m when m < 1 || m > 12 -> failwith "Not a valid month."
                                      | m when m = 12 -> { day = 1; month = 1; year = date.year + 1}
                                      | _ -> { day = 1; month = date.month + 1; year = date.year}
        | _ -> { day = date.day + 1; month = date.month; year = date.year}

The code above isn't the whole solution, but it's the interesting parts. As you can see, I pretty much pattern matched the whole solution. It's a shame that C# doesn't have pattern matching because it's a really powerful language concept.

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 Othello, Part 4: Trials and Transposition Tables

By the time I implemented transposition tables for my computer player in Othello, I'd finished most of the components of what's required for a decent Othello computer player. I didn't really need to add a transposition table, but I really wanted to understand and implement all the aspects of a computer player for these sorts of games.

A transposition table is used to help speed-up a depth-first search. It does this by keeping track of game states that it has already searched. Along with the game state, it records the value it found for that state in the evaluation function. (Therefore, a suitable data-type for a transposition table in C# is a Dictionary<gamestate,float>. GameState overrides the GetHashCode method to provide an unique as possible hash of the game state. The float holds the value from the evaluation function.) If the search finds the same game state again (via a different path), it uses the value in the transposition table rather than re-calculating it. This saves time.

Intuitively, I wouldn't have thought Othello would have many ways in which different sequences of plays could result in the same game state. Any reading about computer Othello says otherwise, however. In practice, I managed to wipe a couple seconds off a search by using a transposition table.

When I began writing my transposition table I looked for a good way to hash a game state. I found a description of the Zobrist hash:

One useful method for hashing positions in games like Othello and Chess is Zobrist hashing [12]. A Zobrist hash consists of an XOR sum of several bitstrings. For each square on the board, there is one randomly generated bitstring representing a black piece and another representing a white piece. A position's Zobrist hash is formed by XORing together the appropriate bitstrings. The primary benefit of Zobrist hashing is that it can be incrementally updated very quickly by XORing it with the bitstrings for the pieces that have changed. Zobrist hashes also have the advantage of uniform distribution. (Applications of Arti ficial Intelligence and Machine Learning in Othello)

I implemented a Zobrist Hash for Othello, created a dictionary of type Dictionary<ulong,float>, then wondered why I was getting so many bad results. The problem? When you add a key to a dictionary it'll call GetHashCode on the object to retrieve the hash. What happens when you add a hash as a key to a dictionary? The same thing. I was double hashing! Not only that, I was going from a 64-bit Zobrist hash to a 32-bit .NET hash. I was burning time in creating the hash as well as losing information and most likely increasing the number of collisions between different game states. All pretty ugly stuff. The solution, outlined above, was very simple: ditch the Zobrist hash, override the GameState GetHashCode to have:

        public override int GetHashCode()
        {
            return (PlayerPieces | OpponentPieces).GetHashCode();
        }

and change the dictionary to have GameState as the key. The result isn't as fast as if I had implemented my own type of hashtable with my own hash type, but it was a lot easier to do.

In the end, adding a transposition table to my game was relatively easy to do, though I took a long and unnecessary detour to achieve it.

Computer Othello, Part 2: Game archive as trainer

I wanted to create a computer game of Othello that did more than simply defeat the human player. I thought of trying to provide a story to the player to help them learn and improve against others. One idea was to process the Thor archive and create stats to apply to each potential play. In that way, the player can see how many people have played the position in the past and how well they did. However, with 100,000 games in the archive, doing this efficiently was tricky.

Initially, I tried using a trie data structure. It seemed like an appropriate structure. However, performance was poor and programming against it wasn't overly intuitive. I tried changing how the data was stored to try to improve performance. Instead of using a human readable notation (i.e., algebraic notation, such as "E6"), I stored each play as a single Unicode character. With 60 possible plays, I used the alphanumeric set, capital letters and symbols. I did this by simply taking a numeric board position (0 to 63), adding 48 to it (to move it into the alphanumeric area of Unicode) and converting it to a char type. This improved things, but performance using the trie was still terrible.

I ditched the trie and wrote LINQ statements against a list of strings. Performance improved, but it was still poor. I switched the search from LINQ to use the BinarySearch method of a list. For a binary search to work, I had to order the data. I was surprised to find that the LINQ OrderBy method didn't sort my data the way I needed. I suspect that it doesn't distinguish case and can't cope with unusual characters. I switched to Array.Sort. Even that didn't work without the StringComparer.Ordinal option. I also needed StringComparer.Ordinal option for the BinarySearch method. All interesting little hurdles.

After all that (plus some more optimisations discovered by using Performance Analyzer in Visual Studio), performance was massively improved but still not perfect. I decided to process the calculations on a separate thread so that it didn't hang the user interface.

I was done. Stats appeared either instantly or within half a second and either way the user interface was not impacted. Yet, I still wasn't done!

Othello is a highly symmetrical game. The first play, a choice of four possible positions, is symmetrically equivalent. No matter where black plays on the first move, one could rotate the board and the board would look the same as any other play. The people who made the Thor database understood this. That's why they standardised the archive to have E6 as the first play for all games. I needed to display the same info on the C4, D3 and F5 tiles that I displayed on E6. Otherwise, the less knowledgeable player may wonder why 100% of games are played at E6.

To be able to display stats on a non-standardised position, I needed to test for symmetry in the game board. I found methods to flip and rotate bitboards. That solved half the problem. I could check if one game state was the same as another. Next, I rotated the stats from a standardised to a non-standardised board. I generated lookup dictionaries to be able to rotate the indices of the board positions. For example, position E6 would become position C4 on a rotated board.

Display of game stats for black.
The blue highlighted square displays black played there in 0.027% of games and won 10% of those games.

After all that, I had a well working set of stats that I could display to the player to assist them in learning where the best opening moves are. It doesn't really provide any sort of story for the player, but at least it gives an indication of where a good play might be.

Later, I also used this data to help the computer player make its opening moves. But that's for another day.

More interview questions

We had a coding competition at work last week. We had an hour or so to code-up a solution to:

I want to simulate a vote by providing a question, valid responses, and an integer representing the voting population size.

When the vote occurs, there should be 1 random vote for each member of the voting population.

 The entries were judged on the following criteria.

• Testability
• Maintainability
• Accuracy of solution
• Structure of solution files

I've uploaded my contribution to GitHub. I didn't win. I made a few weird assumptions (that I've corrected in the code online) and for some reason went off on a tangent playing around with JSON serialisation. However, the wining solution wasn't particularly different to mine.

The purpose behind the competition was to use this task (or something similar) when interviewing candidates. I guess the people interviewing wanted a base-line to work off, that's why they had the staff do the task.

Anyways, it was quite fun. I've never done anything like that in a workplace before.

Interview questions

I've been asked the same questions during interviews in the past. The two that come to mind are:

1. What's the difference between a clustered and non-clustered index in SQL Server?
2. What's the virtual keyword in C# mean?

I finally got around to looking up the answer to the second question. I generally don't override methods, so I've never had much use for it.

The short of it is that virtual is required if you want to override a method of the base class. If you don't supply virtual, the best you can do is use the new keyword to create a completely new method that just happens to have the same name of a method in the base class. To take it a bit further, sealed will prevent any further overriding down the inheritance chain. Therefore;

1. a base class may have a method with virtual assigned to it;
2. deriving from 1, you could override the method;
3. deriving 2, you could sealed override the method;
4. deriving 3, you can't override any more (but you could new the method);

Is this an important question? Not in-itself. I was offered the jobs without knowing the answer.

I have written an example gist to further clarify.

Computer Reversi, Part 1.5: The Thor database (Othello tournament files)

As part of my research into Reversi, I looked for an archive of games. The only substantial one I found is called the Thor Database. It's an archive of Othello games by French archivers. They have archived are over 100,000 games. You can download the game databases here.

My initial motivation for finding an archive was to have a easy way to unit test my code to ensure it implemented the Reversi rules correctly. If the game engine could play through 100,000 games and calculate the final score, that's a good indication that the rules have been implemented correctly. An archive can also be used for book openings. I have another idea for the archive too, which I will hopefully reveal soon.

My Reversi source code has a Thor project with a bunch of methods and classes for extracting the data for whatever nefarious needs you may have. I don't think there is any code in C# on the net for this, so maybe one day it'll be helpful for someone. Maybe. (Probably not.)

The file format documentation is challenging to understand because it is written in French. I have translated (thanks to Nuz and google translate) the core elements of the document in the section below. The aspects I found challenging were:

• Interpreting the meaning of the black player's score (I needed to calculate the score as the final check to ensure my rules were working)
• Interpreting the way they recorded the individual plays
• Converting elements of a byte-array to a 16-bit integer. (The data are stored as little-endian. One way: BitConverter.ToInt16(new [] { thorArray[i], thorArray[i + 1] }, 0).)

To calculate the Black Score:

• Get sum of black pieces and the sum of white pieces;
• Whoever has the most pieces wins;
• The winner adds to the sum the number of empty squares;

E.g., Black has 44 pieces, White has 8 pieces; Black's score is 56. Or, Black has 13 pieces, White has 35; Black's score is 13. In the case of a draw, Black's score is 32 (as the empty squares are shared between Black and White, 32 is the only possible score for a draw). I still haven't figured out what it means for Black's score when the game ends before neither player can play a piece. The score seems inconsistent. This only occurs in 406 of 107,473 games. (Not a big deal.)

---

The data, such as Word and Longint, are stored in Intel format, ie the lowest byte first. There is a game file for every year. Games are stored in any order, but normally grouped by tournament.

Database header fields
All files in the database Wthor have a header of 16 bytes, followed by a number of game records all having the same size. The header consists of the following fields:

• Century file was created
• Year file was created
• Month file was created
• Date file was created
• Number of records N1
• Number of records N2
• Year of game
• Parameter P1: size game board
• P2 parameter: type of games
• Parameter P3: depth
• X1 (reserved)

Game fields

• Tournament Number
• Number of Black player
• Number of White player
• Number of black pieces (true score)
• Theoretical score
• Move list 

The plays are stored in chronological order. Row number (1-8) and column (A-H) can be derived from the following operation: column + (10 * row). E.g., a1 = 11, h1 = 18, a8 = 81, h8 = 88.

Tournament file

Each record (26 bytes) is an array of characters terminated by a binary zero. The effective length is 25 characters. There is a 16 byte header for this file. 

Player file

Each record (20 bytes) is an array of characters terminated by a binary zero. The effective length is 19 characters. There is a 16 byte header for this file.

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.

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.

Some funny code...

I often sigh while reading the source code at me new job. Occasionally, I have a few laughs too. For example:

            catch (Exception exception)
            {
                throw new Exception(exception.ToString());
            }

I'm not sure what it is about exception handling but it seems to be the most frequently mis-understood/mis-used area of programming C#. The lines above are not nearly has bad as:

            catch (Exception exception)
            {
            }

which I've seen a lot of too, but it's more of a sigh moment than laugh.

Tools for learning F#

Every few months I try to learn me some more F#. It isn’t easy.

I stumbled across a nice learning tool by Chris Marinos. It works on the premise that you learn by making the unit tests pass (initially, they all fail). It's a nice idea. The only issue is that the testing framework it uses was written in NUnit. I don't use NUnit anymore. With a couple of little changes I switched it to Microsoft's unit testing framework. You can get my version here.

There is also http://www.tryfsharp.org/. It gives a good intro to F# that you can do online (don't need Visual Studio or nothink).

I tried to do some interoperability between C# and F#. When testing an F# console app in a C# test project, my functions didn't return results. I changed my F# console app to a F# library and it worked correctly. (Don't know why C# can't use an F# console app.)

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

Screenshot of the result

Learning a new (programming) language

I'm attempting to learn a new programming language. The main issue here is that F# isn't just a new language, it's a new type of language. There are three main (i.e. popular) paradigms of programming languages: imperative (the one you learn at school), object-orientated (the one most programmers use), and functional (the one I'm trying to learn). Object-orientated is really just an extension of imperative programming, so for me, learning F# is about learning how to re-think how to do things.

I thought I'd try to do the Euler problems like Andrew is doing at a misdirected effort.

My solution for problem 1 in F#:

let multiple x = if x % 3 = 0 || x % 5 = 0 then x else 0

let sequenceOfNumbers n = [1 .. n]

let euler1 numbers =
numbers
|> Seq.map multiple
|> Seq.sum

printf "Result = %i" (euler1 (sequenceOfNumbers 999))

The way I'd do it in C#, however, is:

static int Euler1(int maxValue)
{
 var sum = 0;
 for (var i = 1; i <= maxValue; i++
  if (i % 3 == 0 || i % 5 == 0)
   sum += i;

 return sum;
}

Is there really all that much difference? Could I have expressed it in F# in a more functional way? I don't know. Hopefully I can change the way I think about functional programming as I move through the problems.

Genetic Algorithms

There is something a little bit creepy about writing genetic algorithms. I'm not quite sure what it is...

// Run selected breeding program
while (stopWatch.Elapsed < _parameters.SimulationExecutionTime)
{
   population = Selection(population).ToList();

   var children = Breed(population);

   Mutate(children);

   population.AddRange(children);
}

How to switch between SQL Server and SQL Server Compact with Entity Framework

I wanted to be able to save data to either a database on a SQL Server 2008 or an equivalent database on SQL Server Compact 3.5 with the minimum of hassle. Enter the new features of Entity Framework 4.0. I followed POCO in the Entity Framework: Part 1 - The Experience to turn off code generation.

I added two EDMs to my project, one for each database. I modified the ObjectContext class to accept different contexts, i.e.:

public class TestContext : ObjectContext
{
    public TestContext(string contextName) : base("name=" + contextName, contextName)
    {
        _projects = CreateObjectSet<Project>();
    }

    public ObjectSet<Project> Projects
    {
        get
        {
            return _projects;
        }
    }
    private ObjectSet<Project> _projects;
}

After that, I can now connect to either database by specifying either:

var compactContext = new TestContext("CompactEntities");

OR

var context = new TestContext("Entities");

Now I can use the same class files to both databases, and sync up the data in both with quite easily. The only redundancy is the EDMs, but since they are generated by Visual Studio, I don't care.

All too easy.

My HSL colour class

Want a unique set of colours without having to do any work? You need HSL.

Use:

for (var i = 0; i < 10; i++)
 (Color)new ColorHsl((byte)((float)i / 10 * 255), 127, 127)

Class (Note, I mostly ripped this off from elsewhere, but mine 1) actually works, 2) is easy to use.):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Media;

namespace UserInterface
{
   public class ColorHsl
   {
       public ColorHsl(byte h, byte s, byte l)
       {
           H = h;
           S = s;
           L = l;
       }

       public byte H, S, L;

       public static implicit operator Color(ColorHsl colorHsl)
       {
           double r, g, b, h, s, l; //this function works with floats between 0 and 1
           double temp1, temp2, tempr, tempg, tempb;
           h = colorHsl.H / 256.0;
           s = colorHsl.S / 256.0;
           l = colorHsl.L / 256.0;

           //If saturation is 0, the color is a shade of gray
           if (s == 0)
           {
               r = g = b = l;
           }
           else
           {
               //Set the temporary values      
               if (l < 0.5)
               {
                   temp2 = l * (1 + s);
               }
               else
               {
                   temp2 = (l + s) - (l * s);
               }

               temp1 = 2 * l - temp2;
               tempr = h + 1.0 / 3.0;

               if (tempr > 1)
               {
                   tempr--;
               }

               tempg = h;
               tempb = h - 1.0 / 3.0;
               if (tempb < 0)
                   tempb++;

               //Red     
               if (tempr < 1.0 / 6.0) r = temp1 + (temp2 - temp1) * 6.0 * tempr;
               else if (tempr < 0.5) r = temp2;
               else if (tempr < 2.0 / 3.0) r = temp1 + (temp2 - temp1) * ((2.0 / 3.0) - tempr) * 6.0;
               else r = temp1;

               //Green       
               if (tempg < 1.0 / 6.0) g = temp1 + (temp2 - temp1) * 6.0 * tempg;
               else if (tempg < 0.5) g = temp2;
               else if (tempg < 2.0 / 3.0) g = temp1 + (temp2 - temp1) * ((2.0 / 3.0) - tempg) * 6.0;
               else g = temp1;

               //Blue    
               if (tempb < 1.0 / 6.0) b = temp1 + (temp2 - temp1) * 6.0 * tempb;
               else if (tempb < 0.5) b = temp2;
               else if (tempb < 2.0 / 3.0) b = temp1 + (temp2 - temp1) * ((2.0 / 3.0) - tempb) * 6.0;
               else b = temp1;
           }

           return Color.FromRgb(Convert.ToByte(r * 255), Convert.ToByte(g * 255), Convert.ToByte(b * 255));
       }
   }
}