Friday, July 27, 2012

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.

Monday, July 23, 2012

The Walking Dead review

Fashionable zombie pop-culture bores me. I have a negative interest in anything to do with zombies. And yet... there is DayZ and now Telltale's latest adventure game series, The Walking Dead.

The Walking Dead is the only adventure game in the last fifteen years that simply must be played. Why?
  • The narrative and plot are compelling
  • The script is good
  • The characterisation is generally quite good
  • The puzzles are a balance between tricky, frustrating and satisfying
  • The art style is really good
  • The interface is one of the best I've seen in an adventure game
But importantly, it's because
  • It appears to have meaningful choices at almost every node of the dialog tree
  • What you need to do to survive is a great blend of disgust and grotesque fascination. (I think I've said "Oh my God!" more times playing The Walking Dead than any other game!)
Many dialog trees in the game have a timer on them. You often need to respond in moments. This is the most fantastic innovation in adventures games since the dialog tree was created. I doubt The Walking Dead was the first to use it, but it uses it extremely well. It's so tense. I was often locked in indecision. Occasionally, I simply couldn't decide, resulting in awkward silence. I love how not saying anything is an option! Of course, no matter what you say, it can't matter too much, yet it doesn't feel like that at the time. And that's the important thing.

Often events don't go the way I wanted or how I expected, but I just went with it. It's part of the story and it all seems meaningful. Only once have I re-started a section because of the way things turned out. This is great in two ways; 1) even though things don't necessarily go the way you wanted, it's not necessarily bad enough to force you to rewind and 2) I care enough about some events that I simply can't allow the game to continue after an event that was simply too wrong for me to be happy with. That might sound contradictory, but isn't.

The reason why DayZ and The Walking Dead are such good zombie games is because they're not really zombie games. DayZ is about the other people you play with, whether other survivors or bandits that hunt you. The Walking Dead is all about the other characters in the game. The zombies are there in a way that function almost as a relief. Zombies are simple. All you have to do is kill them (again). It's everyone else you have to be worried about. (But that would make a great twist, if zombies weren't exactly as we assume. If they transitioned from a Nazi SS officer to an Itialian fascist infantryman, then you'd have a whole new depth of narrative to explore.)

Episodal format? Seems like a dodgy way to get people to pay for a game that isn't finished. Episodal gaming is a bit of a relic in the era of kickstarter. It's proto-kickstarter, where some of the risks are put onto the consumer rather than all. In effect, I don't mind at all. In fact, I think I prefer it. I don't have the desire or time to sit down and play a game for hour on end. This way I can play it in chunks over a period of months. At episode two of six, I feel like I've gotten all I thought I would get from this game and I'm not even halfway. If quality drops by the end of the season, I don't think it matters. It's already been a whole lot better than many games I've played recently (looking at you Diablo 3).

This is the first game in years that I want everyone to play. I'm not just talking about my friends that don't play games anymore now that they've "grown up." I mean, my mum. She should play it. Sure, it's horrific, but it's done so horrifically well.

Friday, July 20, 2012

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.

Friday, July 13, 2012

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.

Wednesday, July 11, 2012

Julia Kristeva

On Anthony's visit to Melbourne, he mentioned something about Julia Kristeva that I simply had to know more about. It was the idea that Kristeva suggests we move away from the scientific binary logic of false and true (0 and 1) to a poetic logic of 0 and 2. I was astounded to hear that. It seemed completely absurd (it's been a while since I read any post-modernism). I got the document and found the quote. Here it is:
The polyvalent logic presupposing an infinite number of values in the interval false-true 0  x  1 is a part of bivalent (0-1), Aristotelian logic. Poetic logic is inscribed on a different surface. It remains indebted to Aristotelian logic not in being a part thereof, but insofar as it contains and transgresses that logic. Since poetic unity is constructed in relation to an other as double, the problem of truth (of the 1) does not concern it. The poetic paragram bypasses the one, and its logical space is 0-2, the 1 existing only virtually. (pg 44, Towards a Semiology of Paragrams)
Admittedly, I didn't read all of the document. What I read, I didn't understand. I'm taking Kristeva out of context because I don't understand the context. Nevertheless, I got questions:
  1. How is polyvalent logic "part of" bivalent logic? The inverse (bivalent part of polyvalent) seems more reasonable to me. Yet, polyvalent and bivalent seem to have quite different logical rules.
  2. Unlike polyvalent logic, Kristiva claims that poetic logic (what's that?!) has a logical space of 0-2. It's therefore still bivalent, but because it doesn't contain 1 (truth) it need not concern itself with truth. Hm... but isn't the "1" merely a symbol to represent "truth"? Couldn't "2" also represent "truth"? Or "0" for that matter? In fact, you could be really crazy and suggest "√-1" to be the symbol for "truth". It wouldn't matter, would it?
I will leave you with another quote from earlier in the document. I find it entirely incomprehensible, though it does appear to contradict the above by saying that paragrammatic numerology (which I think is the same as poetic numerology) is "two" and "all" rather than "0" and "2". I like the "The zero is two which are one" statement, though that is very similar to another phrasing I know (i.e., the doctrine of the trinity - god, son and holy ghost are three that are one.) I'm not sure that the bible is a good source for learning logic, however...
The zero as non-sense does not exist in the paragrammatic network. The zero is two which are one: in other words, the one as indivisible and the zero as nothingness are excluded from the paragram, whose minimal unity is both an (empty) all and an (oppositional) two. We shall examine more closely this paragrammatic numerology, where there is no 'one' or 'zero' but only 'two' and 'all'. Unity is empty, does not count, the one is zero but it signifies: it controls the space of the paragram, it is there to fix the centre, but the paragram does not give it a value, a stable meaning. This 'unity' is not the synthesis of A and B; but it has the value of one because it is all, and at the same time it cannot be distinguished from two, because within this unity come together all the contrasting semes, both opposed to each other and united. At once unity and couple, the oppositional dyad, to apply a spatial expression, is realized in the three dimensions of volume. (pg 37, Towards a Semiology of Paragrams)

Saturday, July 7, 2012

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.

Friday, July 6, 2012

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.