Edison Robot

Wow, over 5 years since I wrote a blog entry. Seems like yesterday.

Aida, Luis and I bought a programmable robot! I've been looking for a toy robot for some time, wanting to get a writing robot (I used to love turtle graphics on the computer when I was a child - I didn't know it was designed with real drawing turtle robots in mind.) I bought a Mirobot v3 and assembled it with Aida. It didn't work (well, we made it beep, once). That was a shame.

We saw a little robot called Edison. It doesn't draw, unfortunately (though you could hack-it in). It was really cheap, for a robot. It's programmable with a number of  different sensors, lights, buttons and 2 drive motors for the wheels. Programs are loaded via a stereo-jack cable that get converted into light and read underneath the robot. The programs are compiled into wav files. It's an ingenious data transfer method that I haven't seen before.

The robot looks like this:

Below is the first program we wrote. It's called Zackaboomba.

The iterations on coding it were interesting. The bugs were:

• We didn't realise the numbers below the drive blocks (blue) were measured in seconds. We had the robot turning right for 90 seconds at one point (I presumed it was measured in degrees);
• The robot almost ran off the table because of a bug in the loop (it drove forward for 2 seconds instead of 1). That was funny. Made me think of some of the errors that rocket engineers working for NASA do (similar level of complexity);

Below is a video of Zackaboomba in operation.

I think we're going to have quite a bit of fun making Edison do things. Some other things about the robot:

• It takes 4 AAA batteries;
• You can attach lego to the top and the wheels (there were squeals when little lego people started spinning round-and-around);
• It can drive over and read bar-codes to load pre-programmed routines. This will be great when the children just want to reset it back to one of the more game-orientated programs (such as obstacle avoidance);

I still want a drawing robot. Here is my shortlist (in order of preference): 

• Root Robot (not out yet but maybe soon)
• Open Source Turtle Robot (OSTR) 
• Valiant Roamer (history)

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.

Computer Othello, Part 5: Resources

This post lists the best info I could find on how to write a computer version of Othello.

General

http://en.wikipedia.org/wiki/Reversi#Rules
Rules for Othello/Reversi

http://chessprogramming.wikispaces.com/Othello
Details on bitboards, hashes, deep-first searches and transposition tables. Contains source code (generally in C or C++)

http://www.radagast.se/othello/howto.html
A description of what is required to implement a better than average computer player.

https://skatgame.net/mburo/ps/compoth.pdf
A paper that describes the best Othello computer players from the 80s and 90s (IAGO, BILL and LOGISTELLO)

Strategy (human and computer)

http://radagast.se/othello/Help/strategy.html
http://www.samsoft.org.uk/reversi/strategy.htm

Implementation

http://users.informatik.uni-halle.de/~jopsi/dass4/
A break-down of the tasks involved in creating an Othello game. Has info on implementing the rules and how the minimax search works.

http://www.dcs.gla.ac.uk/~daw/masters-projects/dissertations/Colquhoun.2008.pdf
Computer science student's paper.

http://www.cs.kent.edu/~jmelnyk/othello/
A description of someone's attempts to write-up Othello depth-first searches (alpha-beta, negascout, MTD(f), Multi-ProbCut, etc.)

Computer player

http://samsoft.org.uk/reversi/openings.htm
A list of the standard Othello openings.

http://xenon.stanford.edu/~lswartz/cs221/desdemona_writeup.pdf
Description of various evaluation strategies.

http://othello.dk/book/index.php/Thor_Database
The Thor database was the only archive of Othello games that I could find on the net.

Finally

If you want to see what I did with this information, there is my source code for Othello. It's fairly well written, the UI looks okay and is easy to use and the computer player plays well. I implemented most things you'd do in a world-class computer player. However, you'd have to make it a lot more efficient, if you wanted to take on those players.

It was interesting, frustrating and fun to try to write a decent Othello game. I learnt a huge amount too.

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 3: Othello computer opponent

After working on the game archive stats, I was ready to create a computer player. Previously, the computer player had played randomly (even Andrew was able to beat it!) To create a computer opponent, I needed to do two things; create an evaluation method and plug-in a search algorithm to find the best estimated play to make.

Evaluation

One of the trickiest things to do with the computer opponent is to evaluate the current game state. Given any arrangement of pieces, you need to be able to determine which of the possible plays is the best. You need an heuristic to do this. An heuristic is an estimation of what you think is a good play to make. The factors that I used to evaluate the state of the game were:

* Number of pieces
* Number of playable squares (usually called "mobility")
* Number of empty squares next to the player's piece ("the frontier", or "potential mobility")
* Various corner and edge patterns (edges and corners are usually better moves)

Pieces and mobility

The most naive heuristic is to count the number of pieces each side has. Ultimately, this is the only measure, piece count determines the winner. However, until the end game, it has little to do with who is going to win.

A less naive approach is to count how many plays can be made. A state where 7 plays are possible is almost certainly better than one where you have to skip your turn because you can't make a play. I had already calculated where a player could place a piece in their turn as part of the user interface. Therefore, I got the mobility measure for nothing.

Finding the empty squares next to a player's pieces was also relatively simple to implement. It was little more than a variation on the mobility algorithm.

Patterns

Image that elucidates where the X and
C-Squares are on an Othello board.

Implementing the patterns was relatively easy to do but it was one of the last additions to the evaluation function that I made. I had previously dismissed this approach as too simplistic to provide much of an improvement to the evaluation. I couldn't have been more wrong. Once I had coded the patterns, the computer player beat me easily. I've since beaten it once or twice, but it went from a disgustingly below average player to a better than average player.

The patterns that I check for are:

• Corners (a good play for the current player)
• X-Squares (bad play)
• C-Squares (bad)
• Corners and X-Squares (good)
• Corners and C-Squares (good)
• Edges (good)

Furthermore, I check for lots of combinations of these patterns. I.e., not only does a game state get points for a play on a corner, but gets even more points for the multiple corners. I didn't check to see if this approach improved play, but I suspect it would.

Piece stability and parity

There were a couple of major components of a good Othello evaluation function that I didn't include. These were piece stability and parity. Piece stability, i.e., finding the pieces that cannot be flipped, is one of the trickier things to determine. There is a good description of how to do it here. I couldn't think of a really efficient way to implement stability, so I left it out.

Parity, i.e., determining who plays last, was relatively simple to implement in its basic form. By default, white will always play last, and therefore has an advantage. For black to play last, someone has to miss a turn. The basic approach to parity didn't really seem to impact the performance of the computer player, so I left it out of the evaluation. A sophisticated form of parity - one where isolated parts of the board are evaluated for parity (an isolated section is one that is surrounded by pieces and edges) - seemed too tricky to implement, so I never tried.

Depth-First Search

I took my negamax, alpha-beta pruning negamax and negascout search methods from my noughts and crosses source code and adapted it to work for Othello. That was fairly easy to do, although my original code was a bit rubbish.

Initially, I thought I'd use negascout for Othello as it is the best of the three. However, for it to work effectively (i.e., better than an alpha-beta pruning negamax), it needs to do shallow searches of the game tree, or find some other way to have a pretty good attempt at pre-ordering the plays from best to worst. Negascout generally does a mini-search within a normal negamax search. It was a more involved task than I suspected. Once I had implemented the patterns approach to the evaluation function, I realised that my computer player was pretty good. Therefore, I decided not to pursue a negascout algorithm for Othello.

Opening book

With all the work that I did to be able to display the history of games to the human player (percentage of games that made a play, percentage of those where black wins), I was serendipitously writing the code for the computer player. The computer opponent uses this information in a similar way as a human.

End game search

One of the things that I didn't do for the computer player was an put any work into an end-game search. This sort of search is much deeper and tries to get search until the end of the game. Once a computer has this information, it'll know if it has won and exactly which moves to make to ensure victory. Until the end-game search, all other plays are calculated guessing. All I did to the computer player approaching end game was increase the search depth.

Conclusion

I completely underestimated how difficult it would be to create a competent computer player. I now have a much greater respect for people who managed to create computer players that are vastly superior to mine on machines that are vastly inferior to today's technology. It's true that .NET is not really up to the challenge (unmanged code like C and assembler would be much more suitable), but you'd think a modern processor using .NET could get close to Pentium using C. From my experience, it didn't. But in truth, it was the algorithms that weren't good enough. I would have many more things to do to be able to compete with other computer Othello players. E.g., stability detection, parity, better potential mobility, negascout, Multi-ProCut, end-game solving, much deeper searching, training and machine learning etc. There is an immensity of improvements that I didn't even touch on. I'm not unhappy with what I achieved, more very impressed that people have done so much better.

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.

GitHub for Windows

I'm tired of using Skydrive as a "source code control" solution. That's no solution, just a file back-up. What about versioning and sharing code?! I've used lots of revision control systems before. Here's the list:

• Visual SourceSafe
• SourceGear Vault
• Subversion
• TFS
• Mercurial

They've all been adequate but frustrating. The Internet is abuzz with talk of Git and GitHub. I tried setting up a GitHub account last month. After the first few steps, I looked at the long list of remaining tasks and decided it was "too much work."

To my rescue comes GitHub for Windows. Not only did it create my repository in seconds, it filtered out all the useless gunk that I don't want going into the code repository, namely binaries, ReSharper and Visual Studio profiler files. It still had some NCrunch files to ignore, but that's a minor issue. Could this be my revision control Holy Grail?

My Othello repository can be found at: https://github.com/ledpup/Othello.

How to write software

A friend from my previous job sent me the below a couple of days ago. These suggestions fit perfectly with the exact opposite approach to what we were taking on the project I was working on there. It looks like things are changing.

It's all straight-forward stuff. If you work in enterprise software development, you already know how often these ideas are not followed.

---

Code Smells Within Classes

·         Comments: There's a fine line between comments that illuminate and comments that obscure. Are the comments necessary? Do they explain "why" and not "what"? Can you refactor the code so the comments aren't required? And remember, you're writing comments for people, not machines.

·         Long Method: All other things being equal, a shorter method is easier to read, easier to understand, and easier to troubleshoot. Refactor long methods into smaller methods if you can.

·         Long Parameter List: The more parameters a method has, the more complex it is. Limit the number of parameters you need in a given method, or use an object to combine the parameters.

·         Duplicated Code: Duplicated code is the bane of software development. Stamp out duplication whenever possible. You should always be on the lookout for more subtle cases of near-duplication, too. Don't Repeat Yourself!

·         Conditional Complexity: Watch out for large conditional logic blocks, particularly blocks that tend to grow larger or change significantly over time. Consider alternative object-oriented approaches such as decorator, strategy, or state.

·         Combinitorial Explosion: You have lots of code that does almost the same thing... but with tiny variations in data or behavior. This can be difficult to refactor-- perhaps using generics or an interpreter?

·         Large Class: Large classes, like long methods, are difficult to read, understand, and troubleshoot. Does the class contain too many responsibilities? Can the large class be restructured or broken into smaller classes?

·         Type Embedded in Name: Avoid placing types in method names; it's not only redundant, but it forces you to change the name if the type changes.

·         Uncommunicative Name: Does the name of the method succinctly describe what that method does? Could you read the method's name to another developer and have them explain to you what it does? If not, rename it or rewrite it.

·         Inconsistent Names: Pick a set of standard terminology and stick to it throughout your methods. For example, if you have Open(), you should probably have Close().

·         Dead Code: Ruthlessly delete code that isn't being used. That's why we have source control systems!

·         Speculative Generality: Write code to solve today's problems, and worry about tomorrow's problems when they actually materialize. Everyone loses in the "what if.." school of design. You (Probably) Aren't Gonna Need It.

·         Oddball Solution: There should only be one way of solving the same problem in your code. If you find an oddball solution, it could be a case of poorly duplicated code-- or it could be an argument for the adapter model, if you really need multiple solutions to the same problem.

·         Temporary Field: Watch out for objects that contain a lot of optional or unnecessary fields. If you're passing an object as a parameter to a method, make sure that you're using all of it and not cherry-picking single fields.

Code Smells Between Classes

·         Alternative Classes with Different Interfaces: If two classes are similar on the inside, but different on the outside, perhaps they can be modified to share a common interface.

·         Primitive Obsession: Don't use a gaggle of primitive data type variables as a poor man's substitute for a class. If your data type is sufficiently complex, write a class to represent it.

·         Data Class: Avoid classes that passively store data. Classes should contain data and methods to operate on that data, too.

·         Data Clumps: If you always see the same data hanging around together, maybe it belongs together. Consider rolling the related data up into a larger class.

·         Refused Bequest: If you inherit from a class, but never use any of the inherited functionality, should you really be using inheritance?

·         Inappropriate Intimacy: Watch out for classes that spend too much time together, or classes that interface in inappropriate ways. Classes should know as little as possible about each other.

·         Indecent Exposure: Beware of classes that unnecessarily expose their internals. Aggressively refactor classes to minimize their public surface. You should have a compelling reason for every item you make public. If you don't, hide it.

·         Feature Envy: Methods that make extensive use of another class may belong in another class. Consider moving this method to the class it is so envious of.

·         Lazy Class: Classes should pull their weight. Every additional class increases the complexity of a project. If you have a class that isn't doing enough to pay for itself, can it be collapsed or combined into another class?

·         Message Chains: Watch out for long sequences of method calls or temporary variables to get routine data. Intermediaries are dependencies in disguise.

·         Middle Man: If a class is delegating all its work, why does it exist? Cut out the middleman. Beware classes that are merely wrappers over other classes or existing functionality in the framework.

·         Divergent Change: If, over time, you make changes to a class that touch completely different parts of the class, it may contain too much unrelated functionality. Consider isolating the parts that changed in another class.

·         Shotgun Surgery: If a change in one class requires cascading changes in several related classes, consider refactoring so that the changes are limited to a single class.

·         Parallel Inheritance Hierarchies: Every time you make a subclass of one class, you must also make a subclass of another. Consider folding the hierarchy into a single class.

·         Incomplete Library Class: We need a method that's missing from the library, but we're unwilling or unable to change the library to include the method. The method ends up tacked on to some other class. If you can't modify the library, consider isolating the method.

·         Solution Sprawl: If it takes five classes to do anything useful, you might have solution sprawl. Consider simplifying and consolidating your design.

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.

JavaScript - Accessibility and Useability

There has been talk at work about having to provide non-JavaScript alternatives for any of our web-pages that use JavaScript. A few people were suspicoius of this idea and given that we're using MVC3, they were finding it very difficult to implement functionality without JavaScript. Below is the document I created after reading compliance info on the net. You can also download as a Word doc.

---

JavaScript - Accessibility and Useability on the Web

Below are the relevant sections of documents concerning JavaScript and its impact on website accessibility and useability. I have checked documents relating to accessibility compliance under Australian law, compliance for US law and more general accessibility sites. In the conclusion, I explain a public website’s responsibilities regarding JavaScript and accessibility/useability.

Disability Discrimination Act Advisory Notes

http://www.hreoc.gov.au/disability_rights/standards/www_3/www_3.html

It is important for developers to understand that in many cases the accessibility of a particular technology will be determined by how it is used. For example, it is widely considered that JavaScript can be implemented so as to be accessible. However, JavaScript can also be used in ways that are inaccessible, particularly if full keyboard support is not provided.
Ten Common Web Accessibility Failures

1. Failure to include appropriate text descriptions (such as “alt-text” labels) for images;

2. Failure to provide accessible alternatives when using a visual CAPTCHA;

3. Failure to use technologies (such as Flash and JavaScript) in ways that are accessible;

4. Failure to use HTML features appropriately to indicate content structure such as the hierarchy of headings;

5. Failure to explicitly associate form input controls with their labels;

6. Failure to ensure sufficient difference between foreground (text) colour and background colour;

7. Failure to identify data tables with Summary or Caption, and failure to mark-up data tables correctly;

8. Failure to provide a way for users to disable content such as advertisements from flashing rapidly (rapidly-flashing content may cause seizures in susceptible individuals), and failure to provide a way for users to stop a page from auto-refreshing;

9. Failure to ensure that web pages can be used from the keyboard (that is, without the mouse);

10. Failure to alert the user to changes on a web page that are triggered automatically when selecting items from a dropdown menu.

How to Meet WCAG 2.0

http://www.w3.org/WAI/WCAG20/quickref/

1.1 Text Alternatives: Provide text alternatives for any non-text content so that it can be changed into other forms people need, such as large print, braille, speech, symbols or simpler language.

1.2 Time-based Media: Provide alternatives for time-based media.

1.3 Adaptable: Create content that can be presented in different ways (for example simpler layout) without losing information or structure.

1.4 Distinguishable: Make it easier for users to see and hear content including separating foreground from background.

2.1 Keyboard Accessible: Make all functionality available from a keyboard.

2.2 Enough Time: Provide users enough time to read and use content.

2.3 Seizures: Do not design content in a way that is known to cause seizures.

2.4 Navigable: Provide ways to help users navigate, find content, and determine where they are.

3.1 Readable: Make text content readable and understandable.

3.2 Predictable: Make Web pages appear and operate in predictable ways.

3.3 Input Assistance: Help users avoid and correct mistakes.

4.1 Compatible: Maximize compatibility with current and future user agents, including assistive technologies.

(No specific mention of JavaScript.)

Migrating from WCAG 1.0 to WCAG 2.0

http://wipa.org.au/papers/wcag-migration.htm

Ensure that pages are usable when scripts, applets etc are turned off or not supported. If this is not possible, provide equivalent information on an alternative accessible page. [Priority 1]

NO MATCHING WCAG 2.0 S.C. Issue is addressed as part of "Conformance requirements".

NB: WCAG 2.0 does not require alternative to be always provided for JavaScript etc. But nominated "accessibility supported technologies" must be used in a way that is accessible. Conformance requirement 4: Only accessibility supported technologies are relied on to satisfy the success criteria. AND Conformance requirement 5: If technologies that are not accessibility supported are used, they do not stop users accessing the rest of the page.

Accessible Rich Internet Applications (WAI-ARIA) 1.0

http://www.w3.org/WAI/PF/aria/introduction#intro_ria_accessibility

New technologies often overlook semantics required for accessibility, and new authoring practices often misuse the intended semantics of those technologies. Elements that have one defined meaning in the language are used with a different meaning intended to be understood by the user.

For example, web application developers create collapsible tree widgets in HTML using CSS and JavaScript even though HTML has no semantic tree element. To a non-disabled user, it may look and act like a collapsible tree widget, but without appropriate semantics, the tree widget may not be perceivable to, or operable by, a person with a disability because assistive technologies may not recognize the role.

Screen readers vs JavaScript

http://webaim.org/projects/screenreadersurvey3/#javascript

JavaScript Enabled = 98.4%, Disabled = 1.6%

10.4% of respondents to the October 2009 survey indicated that they have JavaScript disabled in their web browser. As respondents submitted responses to this survey we detected the presence of JavaScript. We found that very few respondents had it disabled or unavailable in their web browser. Of the 19 respondents with JavaScript disabled, 12 were using Firefox (presumably with the NoScript add-on enabled) and 5 were using Lynx with Linux.

Creating Accessible JavaScript

http://webaim.org/techniques/javascript/

Making JavaScript accessible involves looking at the following issues. Each of these will be discussed in the next lessons.

·         When using event handlers, use only those that are device independent (e.g., do not require the use of the mouse only).

·         Content and functionality that is provided through scripting must be made accessible to assistive technologies.

·         Web pages that utilize scripting must be fully navigable using a keyboard.

·         JavaScript should not modify or override normal browser functionality in a way that may cause confusion.

·         When JavaScript cannot be made natively accessible, an accessible alternative must be provided.

Accessible forms: Guidelines, examples and accessible JavaScript tricks.

http://www.websemantics.co.uk/tutorials/accessible_forms/

So what will you find here?

·         A list of form guidelines based on current and on-going research into accessibility, usability and web standards.

·         Simple examples of accessible forms including: a login form, a search form and a contact form.

·         Examples and help on each form element.

·         Styling forms with CSS.

·         Using accessible inline JavaScript to aide form functionality.

·         Using accessible JavaScript with the DOM to aide form functionality.

·         A comprehensive list of external form related articles and resources.

Conclusion

W3C, Australian law and US law either make no comment on JavaScript or state that JavaScript is acceptable as long as accessibility is maintained.

WCAG 1.0 required that non-JavaScript alternatives were required. WCAG 2.0 does not have this requirement. In compliance with WCAG 2.0, we are permitted to implement pages that would not be useable without JavaScript so long as they remain accessible.

The guidelines at http://webaim.org/techniques/javascript/ and http://www.websemantics.co.uk/tutorials/accessible_forms/ can assist in determining how to ensure the use of JavaScript on a website is accessible.

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);