Othello World
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. The basic building blocks of the game engine are as follows: 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. Like I mentioned above, we can represent the complete board state with just two 64-bit 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: And that's all that's needed to represent the piece positions. I created an immutable data class to encapsulate this: 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 enum so that information somewhat pre-computed. The combination of and provides everything needed to determine the state of the game for the other stages in the engine. 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: This 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. 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. The function will return all valid moves for a given position for the "moving" pieces (the 1st argument). The moves are returned as a where each set bit is a valid square to place a piece. 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. I have two piece scores actually. The 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: 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: And that's it. The top-level 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. 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: 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 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 again with the SAME and reverse the score returned from that call. With those 4 components built, I now had a functional engine to play against. I created an class that accepts a move selection algorithm. It exposes 3 methods: - for showing valid player moves in the UI - which validates and then applies a specified player move - which chooses and applies the best move using the I exposed the via a stateless REST API. Each request needs to supply the current game state information in order to make a move. For example: 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. 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. Board representation Move generation Position evaluation Game tree search