Othello World | flow2

Home

Archive

Projects

About

Search

I was introduced to the board game Othello (also known as Reversi) on a recent trip to Japan. It's one of those games where you can learn the rules in 5 minutes, but the gameplay dynamics are surprisingly deep. When I saw it's played on an 8x8 board, like chess is, I immediately started thinking about how to program a game engine for it.

The 8x8 board is helpful because it allows you to represent the board state with 64-bit longs; each set bit in the number indicates the presence of a piece on that square. When you perform a bitwise operation on these numbers you're essentially computing multiple piece movements in parallel with a single CPU instruction. This computational efficiency enables deep searching of the move tree.

I purposely started out without reading too much about game strategies because I wanted to explore it through coding the engine logic. It didn't take long to create an algorithm that is significantly stronger than me. Although it's not a high bar.

There's a demo available here if you're interested in playing it.

Engine Overview

The basic building blocks of the game engine are as follows:

Board representation

Move generation

Position evaluation

Game tree search

Once you have these four elements built and wired together, you have a functional game engine to play against. The first two pieces are fairly straightforward—the real strength of an engine comes from how the last two are implemented.

Board Representation

Like I mentioned above, we can represent the complete board state with just two 64-bit Long numbers. One number represents the black piece positions and the other for the white pieces.

How you encode the 64 squares to the 64 bits is arbitrary, but I chose to represent each row as one byte (8 bits) and from left to right, top to bottom in terms of bit significance. In other words:

// the board:<br>63 62 61 60 59 58 57 56<br>55 54 53 52 51 50 49 48<br>47 46 45 44 43 42 41 40<br>39 38 37 36 35 34 33 32<br>31 30 29 28 27 26 25 24<br>23 22 21 20 19 18 17 16<br>15 14 13 12 11 10 9 8<br>7 6 5 4 3 2 1 0

// maps to the bits of a long as follows:<br>MSb [63, 62, 61 ... 0] LSb

// Example: white's starting piece positions:<br>0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0<br>0 0 0 1 0 0 0 0<br>0 0 0 0 1 0 0 0<br>0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0

// maps to:<br>0b00000000_00000000_00000000_00010000_00001000_00000000_00000000_00000000L

And that's all that's needed to represent the piece positions. I created an immutable data class to encapsulate this:

data class BoardState(<br>val whitePositions: Long,<br>val blackPositions: Long,

In Othello, if one player has no legal moves at any point in time, they skip their turn and the other player gets to go again. If both players have no legal moves, the game ends. Instead of computing both player's legal moves every time to check for those situations, I created a GameStatus enum so that information is somewhat pre-computed.

enum class GameStatus {<br>BLACK_TO_MOVE,<br>BLACK_TO_MOVE_WHITE_PASSING,<br>WHITE_TO_MOVE,<br>WHITE_TO_MOVE_BLACK_PASSING,<br>BLACK_WINS,<br>WHITE_WINS,<br>DRAW;

The combination of BoardState and GameStatus provides everything needed to determine the state of the game for the other stages in the engine.

Move Generation

This is where things get tricky. Move generation requires codifying the rules of Othello in such a way that, given a board state, all the legal moves for either player can be computed—quickly, ideally.

In Othello, you can only place a piece somewhere that will "sandwich" the other player's piece(s) between the piece you're placing and another "anchor" piece of yours. There can't be any blank spaces either. This rule applies to any of the 8 directions of the board (diagonals count).

Example: the dotted squares are valid moves for black

This getMoves function will calculate all the eligible squares for a single direction of movement (up, down, up-left etc.). What's cool is that it calculates eligible squares for all 8 rows/columns/diagonals at the same time.

fun getMoves(movingPieces: Long, otherPieces: Long, ineligibleMask: Long, moveFn: (Long) -> Long): Long {<br>val unoccupied = (movingPieces or otherPieces).inv()<br>var eligible = movingPieces and ineligibleMask.inv()<br>eligible = moveFn(eligible)<br>eligible = eligible and otherPieces

var validMoves = 0L<br>while (eligible != 0L) {<br>eligible = eligible and ineligibleMask.inv() // remove squares that are ineligible from the next move (e.g. leftmost column when shifting left)<br>eligible = moveFn(eligible)<br>validMoves = validMoves or (eligible and unoccupied) // add the valid squares<br>eligible = eligible and otherPieces<br>return validMoves

It's invoked as follows. For each of the 8 directions, you pass in a movement function and an ineligible square bitmask if required for that direction. For example, if shifting towards the left, you need to mask out the pieces on the leftmost column to prevent wrapping to the other side of the board (similarly...