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.

Best films I've seen this year

I don't see many new great films anymore. I watched most of the backlog years ago. Only one or two new noteworthy films are released every year. However, I've managed to watch some really good films this year. They are:

El Norte: About Guatemalans that escape to the US via Mexico. Probably the best film I've ever seen about a typical experience of an asylum seeker.

12 Angry Men: A jury discuss a murder they're to give a verdict on. They're stuck in a hot room debating the various accounts of the witnesses. The film must be every liberals favourite film, but that doesn't stop it from being a really exciting unravelling of preconceived ideas. "Nobody wears eyeglasses to bed."

Night of the Living Dead: Original zombie film. It has a simple but really effective plot. Extremely tense.

The Lady Eve: It's a rom com. There are a few cheesy bits, but it's generally pretty funny and endearing.

Frozen Planet (not a film): A nature documentary series about life in the Arctic and Antarctic. It made me appreciate just how utterly brutal life in the natural environment is for every living creature except (most) humans (and some pets). Nature is cruel, violent, and completely indifferent. Creatures spend their lives hungry, hunted, cold and alone.

It made fully realise that rather than trying to emulate (bourgeois rhetoric on markets), admire (people who like natural/organic products), or lament the loss of nature (millenarian and some Green movements) we should thank our lucky stars that we're somewhat removed from that pitiless existence. We should do everything we can to reject the laws of nature (that doesn't, in turn, threaten our existence).

Hardcore Minecraft

We played multiplayer Minecraft again tonight, after many moons. This time we played in hardcore mode; no re-spawn. It played like the game I've always wanted Minecraft to be. Challenging, tense and satisfying. I definitely want to play more.

A majestic canyon

A field of sheep

Mana from Heaven

My companion's remains. The rock fell out from under him, into lava. He followed.
It was a disturbing, saddening and somewhat guilt-ridden experience.

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)

The Lello-Lea Hypothesis

The Ice-Wall of Antarctica

A report from the Society:

The standard flat-Earth model (SFEM) postulates an ice-wall beyond Antarctica. SFEM supersedes waterfall theories of other flat Earth models and replaces the controversial spherical-earth conjecture's (SEC) notion of Antarctica as an island continent.

The Lello Hypothesis states: "the universe is a series of flat earths stacked within a vast crystalline cylinder folded back on itself to form a never ending torus. I.e., a cosmic, hollow, ice-donut." The Lea Modification, sometimes known as the Lello-Lea Hypothesis, states that: "interspersed with crystalline water (H₂O), exists an abundance of naturally occurring granular material composed of finely divided rock and mineral particulates forming 'deserts' - similar to observable regions on Earth."

It should be noted that these hypotheses are not to be confused with the weaker and frankly implausible set of ideas that A. Hayes has expounded in which a series of flat earths are distributed across the inner surface of a torus of indeterminate extent. Hayes is also known for the infinite cylinder hypothesis (ICH). ICH is perhaps even more unlikely than his inside-out donut.

The Society for the Lello-Lea Toroid Flat Earths Hypothesis is searching for intelligent life on other flat earths. First contact will provide the empirical evidence, and hence proof, of the Lello-Lea Hypothesis. Meanwhile, scientists are formulating a mathematical proof for the minimum quantity of flat earths that must exist.

Chalmers' recent work (unpublished, in correspondence with the author) has yielded a breakthrough on the topic, establishing deep relationships with elliptic curve theory and the calculus of manifolds, while raising the lower bound on the number of flat earths that must exist to -4. We are assured that more revelatory findings are to follow.

It is not expected that the combined forces of the Society and scientists will be able to provide the actual number of flat earths in our toroidal universe. However, we believe that within the next ten years, we will be able to prove that:

1. We do indeed live in a multi-earth, toroidal universe (i.e., SEC is fallacy.)
2. There are at least 3 flat earths.

A. Hayes, and others, have proposed expeditions to the Ice-Wall to conduct experimental drilling. A small party would also test a radical SFEM speculation of going "beyond the Ice-Wall." Funding and applications for strategic and/or technical approaches is being sought.

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.

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.