In Tech

Othello World

May 22, 2026

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:

  1. Board representation
  2. Move generation
  3. Position evaluation
  4. 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:
63 62 61 60 59 58 57 56  
55 54 53 52 51 50 49 48  
47 46 45 44 43 42 41 40  
39 38 37 36 35 34 33 32  
31 30 29 28 27 26 25 24  
23 22 21 20 19 18 17 16  
15 14 13 12 11 10  9  8  
7  6  5  4  3  2  1  0  
 
// maps to the bits of a long as follows:  
MSb [63, 62, 61 ... 0] LSb

// Example: white's starting piece positions:
0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  
0  0  0  1  0  0  0  0  
0  0  0  0  1  0  0  0  
0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  

// maps to:
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(  
    val whitePositions: Long,  
    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 somewhat pre-computed.

enum class GameStatus {  
    BLACK_TO_MOVE,  
    BLACK_TO_MOVE_WHITE_PASSING,  
    WHITE_TO_MOVE,  
    WHITE_TO_MOVE_BLACK_PASSING,  
    BLACK_WINS, 
    WHITE_WINS,
    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). This screenshot illustrates the valid moves for black in this position:

Screenshot 2026-05-21 at 6.34.45 PM.png

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 {  
    val unoccupied = (movingPieces or otherPieces).inv()  
    var eligible = movingPieces and ineligibleMask.inv()  
    eligible = moveFn(eligible)  
    eligible = eligible and otherPieces  
  
    var validMoves = 0L  
    while (eligible != 0L) {  
        eligible = eligible and ineligibleMask.inv() // remove squares that are ineligible from the next move (e.g. leftmost column when shifting left)  
        eligible = moveFn(eligible)  
        validMoves = validMoves or (eligible and unoccupied) // add the valid squares  
        eligible = eligible and otherPieces  
    }  
    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 for moving right). Moving up or down doesn't require a mask because shifting the bits "up" or "down" enough will just drop them from the number entirely.

//e.g.
fun getUpLeftMoves(movingPieces: PiecePositions, otherPieces: PiecePositions) = getMoves(movingPieces, otherPieces, LEFT_COLUMN) { it shl 9 }
fun getDownMoves(movingPieces: PiecePositions, otherPieces: PiecePositions) = getMoves(movingPieces, otherPieces, 0L) { it ushr 8 }

// so all together:
fun getAllMoves(movingPieces: PiecePositions, otherPieces: PiecePositions): Long =  
    getUpMoves(movingPieces, otherPieces) or  
    getDownMoves(movingPieces, otherPieces) or  
    getLeftMoves(movingPieces, otherPieces) or  
    getRightMoves(movingPieces, otherPieces) or  
    getUpLeftMoves(movingPieces, otherPieces) or  
    getUpRightMoves(movingPieces, otherPieces) or  
    getDownLeftMoves(movingPieces, otherPieces) or  
    getDownRightMoves(movingPieces, otherPieces)

The getAllMoves function will return all valid moves for a given position for the "moving" pieces (the 1st argument). The moves are returned as a Long where each set bit is a valid square to place a piece.

Position Evaluation

This part was interesting to me as I don't know much about strategy in Othello besides that the corners are important. The corners are important because once you claim a corner it can't be unflipped by the other player.

Also, simply maximizing for the most pieces isn't the best strategy either, apparently. I do have a "greedy" algorithm that you can select in the demo app if you want to see that strategy in action. But of course, closer to the end of the game, having more pieces is more important since that's how the winner is determined. I represented this in the eval function by linearly shifting the weighting towards piece score as you get closer to the end of the game.

/**  
 * Score is between -1 and +1
 * +1 is win for black
 * -1 is win for white
*/
fun evaluateBoard(board: BoardState): Double {  
    val ep =  board.endProximity()
    return (ep * board.simplePieceScore()) + ((1 - ep) * board.heuristicEval())  
}

fun BoardState.endProximity(): Double {  
    return (60 - this.remainingMoves) / 60.0  
}

fun BoardState.simplePieceScore(): Double {  
    return if (this.blackPieceCount > this.whitePieceCount) 1.0 else if (this.whitePieceCount > this.blackPieceCount) -1.0 else 0.0  
}

I have two piece scores actually. The simplePieceScore is a step function that only returns 1 or -1 depending on which piece colour has more pieces. But in the heuristic evaluation, I look at the actual piece differential score which returns between -100% and +100% depending on what "percentage" of the overall possible pieces the leading player has. That score is given 40% weighting in the heuristic evaluation function, the other 60% is a positional score based on the following square values I came up with:

val POSITIONAL_SCORE_WEIGHTS = intArrayOf(  
    10, 5, 5, 5, 5, 5, 5, 10,  
    5, 3, 3, 3, 3, 3, 3, 5,  
    5, 3, 2, 2, 2, 2, 3, 5,  
    5, 3, 2, 1, 1, 2, 3, 5,  
    5, 3, 2, 1, 1, 2, 3, 5,  
    5, 3, 2, 2, 2, 2, 3, 5,  
    5, 3, 3, 3, 3, 3, 3, 5,  
    10, 5, 5, 5, 5, 5, 5, 10  
    )

This was my best guess at which squares matter most. My reasoning is that the more central the square is, the more likely it is to be flipped. The closer to the edge it is, the less likely it is to be flipped and the more likely it is to be used as an anchor piece. So putting this all together, the heuristic evaluation is computed as follows:

fun BoardState.heuristicEval(): Double {  
    return heuristicEvalWeightsAndFunctions.sumOf { (weight, function) -> weight * function(this) }  
}  

val heuristicEvalWeightsAndFunctions = listOf(  
    0.4 to BoardState::pieceDiffScore,  
    0.6 to BoardState::positionalScore,  
)  
  
fun BoardState.pieceDiffScore(): Double {  
    // max diff would be 64  
    return (this.blackPieceCount - this.whitePieceCount) / 64.0  
}  
  
fun BoardState.positionalScore(): Double {  
    return this.blackPositions.positionalScore() - this.whitePositions.positionalScore()  
}

And that's it. The top-level evaluateBoard function provides a relative score between -1.0 and +1.0 which represents the strength of a given position, relative to black. Since Othello is a zero-sum game, a good score for one player is an equivalently bad score for the other player. This is important in the next phase, the move search algorithm.

Game Tree Search

This part of the engine is fairly "textbook". There's lots of explanation for how these algorithms work on wikipedia and chessprogramming.org is an incredible knowledge base for this sort of thing too.

For zero-sum games, you can use a variant of minimax search called Negamax. That's what's shown here:

private fun getBestMove(  
    board: BoardState,  
    gameStatus: GameStatus,  
    depth: Int = initDepth,  
): Pair<Int, Double> {  
    nodesSearched++  
    val blackToMove = gameStatus.blackToMove()  
    val color = if (blackToMove) 1 else -1  
  
    if (depth == 0 || board.remainingMoves == 0) { // game over, no valid moves  
        return -1 to color * evaluateBoard(board)  
    }  
  
    val moves = getNextPossibleMoves(board, blackToMove)  
    if (moves.isEmpty()) {  
        if (gameStatus.previousPlayerPassed()) {  
            // if the previous player passed, and the current player has no moves either, then the game is over  
            return -1 to color * evaluateBoard(board, gameIsOver = true)  
        }  
  
        val newGameStatus = if (blackToMove) WHITE_TO_MOVE_BLACK_PASSING else BLACK_TO_MOVE_WHITE_PASSING  
        val (_, score) = getBestMove(board, newGameStatus, depth)  
        return -1 to -1 * score  
    }  
  
    var bestMoveAndScore = -1 to Double.NEGATIVE_INFINITY  
    for (move in moves) {  
        val updatedBoardState = updateBoardState(board, gameStatus.blackToMove(), move)  
        val nextStatus = if (blackToMove) WHITE_TO_MOVE else BLACK_TO_MOVE  
        val (_, score) = getBestMove(updatedBoardState, nextStatus, depth - 1)  
  
        val currentMoverScore = -1 * score // the current player's motive is to minimize the max score the other player can achieve  
        if (currentMoverScore > bestMoveAndScore.second) {  
            bestMoveAndScore = move to currentMoverScore  
        }  
    }  
    return bestMoveAndScore  
}

For Othello specifically, the Negamax function needs to handle the case that the moving player has no legal moves and must pass to the opposing player. This is in the if (moves.isEmpty()) branch in the middle. We check if we're already in a position where the previous player had to pass, which means both players can't move and the game would be over in this branch. If not, we simply call getBestMove again with the SAME BoardState and reverse the score returned from that call.

Putting The Pieces Together

With those 4 components built, I now had a functional engine to play against. I created an Engine class that accepts a move selection algorithm. It exposes 3 methods: - getValidMoves for showing valid player moves in the UI - makePlayerMove which validates and then applies a specified player move - makeEngineMove which chooses and applies the best move using the moveSelectionAlgorithm

class Engine(private val moveSelectionAlgorithm: MoveSelectionAlgorithm) {  
    fun getValidMoves(board: BoardState, gameStatus: GameStatus): List<Int> {...}  
    fun makePlayerMove(board: BoardState, gameStatus: GameStatus, move: Int): Pair<BoardState, GameStatus> {...}  
    fun makeEngineMove(board: BoardState, gameStatus: GameStatus): Pair<BoardState, GameStatus> {...}  
}

I exposed the Engine via a stateless REST API. Each request needs to supply the current game state information in order to make a move. For example:

<!-- Request -->
POST https://flowtwo.io/othelloworld/api/player/move  
Content-Type: application/json  
  
{  
  "whitePositions": 68853694464,
  "blackPositions": 34628173824,
  "status": "BLACK_TO_MOVE",
  "square": 19
}

<!-- Response -->
200 OK
{
  "whitePositions": 68719476736,
  "blackPositions": 34762915840,
  "status": "WHITE_TO_MOVE",
  "algorithm": "negamax",
  "validMoves": [
    18,
    20,
    34
  ],
  "lastMove": 19,
  "flippedSquares": [
    27
  ],
  "whitePieceCount": 1,
  "blackPieceCount": 4,
  "turnNumber": 1
}

For the demo, it uses HTMX instead to return a rendered board component. The request format is the same but it returns HTML instead of JSON.

AI (non-)Usage Disclaimer

I read this article recently that took a contrarian view on agentic coding and it's pitfalls. The author makes a lot of good points and it was thought-provoking. While I don't agree that using agentic coding will make you dumber per se... I do think there's something to be said for regularly exercising the critical thinking and problem solving part of your brain if you want to be a good software engineer. Side projects like this are a great opportunity to do that.

The incredible rise in coding competency for AI agents over the last 12 months has made a project like this into a one-shot, one prompt task for a recent LLM. I obviously didn't do that, because the point of this project was the act of doing it, not the end result. I learned a bit about Othello and refreshed myself on bitwise operations.

The parts I wasn't interested in doing, the UI and the API wiring, I delegated to an agent to implement for me. To me, that's one of the best parts about coding with AI. I can now offload the tasks I'm not interested in or that's not as critical, and focus on the parts of the system I want to work on. It's never been easier to build and bring ideas to life with software.