Category: Downloads

The following is a report on my C# program, WinOthello. I designed it for my Artificial Intelligence course in November 2006.

Download (57 KB) the game or the source code (85 KB).
Provided under a permissive open source license.
.NET Framework 2.0 required.

Abstract
As an exploration of artificial intelligence and particularly game state space search, I developed WinOthello to simulate Othello games. This application allows human and computer players to interact with a virtual game board displayed on the user’s screen. The primary objective of WinOthello was to devise an adept computer player that proves challenging to average human players. This goal was achieved via a depth-limited minimax search of the game space and quickened with the application of alpha-beta pruning.

What is Othello?
Othello is a strategic two-person board game. Players take turns placing pieces on an eight-by-eight board. Each piece has two distinct faces: a light face and a dark face. The first player is designated the dark player and places pieces on the board dark side up. The second player is the light player and places pieces light side up. Pieces can only be placed in positions that outflank the opponent’s pieces. Outflanking occurs when a player places a piece that causes a contiguous line of one or more of the opponent’s pieces to be bounded by the player’s pieces. All of the opponent’s outflanked pieces are then flipped over, and the turn ends. If a player can not place a piece, then play passes to the other player. The game ends when neither player can place any more pieces. The player with the most corresponding pieces on the board at the end of the game wins.

Why Othello?
I choose to explore Othello because it is a perfect candidate for applying state space search. This falls under the game playing field of artificial intelligence. Othello is suitable because it is a two-person game. One player can be viewed as trying to maximize his score, while the second tries to minimize the first player’s score. This is a foundational concept of minimax. Additionally, Othello provides well-defined moves, meaning that for any game state, a list of all possible immediate moves can be generated. The generation of moves allows the projection of later game states, another requirement of minimax. In Othello pieces can only be placed and can not be moved or removed. This means that only a finite number of moves are possible, which simplifies a minimax search. Another convenience is that Othello is purely strategic and doesn’t rely upon chance. This makes the game easy to accurately model. All of these factors make Othello an excellent choice for applying AI techniques.

Goals
My primary goal was to develop an effective Othello computer player. I planned on using a depth-limited minimax search to find good moves. As a further enhancement, I wanted to apply alpha-beta pruning to reduce the search time. The resulting computer player should decide upon a move within a reasonable amount of time, and win almost every game against an average human player. This portion of my project is referred to as the engine and directly relates to artificial intelligence.

My secondary goal was to develop a pleasant Othello GUI. The board should be displayed to the user and allow simple clicks to place pieces. Game settings are to be set at the start of each game. Additional features could include hints for human players and a game history allowing the undo of a move. This portion of my project is referred to as the GUI and isn’t directly related to artificial intelligence.

Approach
Minimax is at the heart of my Othello project. Minimax involves systematically searching possible future gamestates to decide the best move in the current situation. Starting with the current gamestate as the root node, child nodes are created for each currently plausible move. This generation of nodes continues recursively until a specified depth or an endgame situation. After node generation, each of the bottom nodes is evaluated. The higher a node’s value, the more advantageous it is to the current player (MAX). The lower a node’s value, the more advantageous it is to the opposing player (MIN). These values bubble up to their parent nodes. A parent node chooses the move leading to the maximum child node if the node’s game state represents MAX’s turn. If it is MIN’s turn, the parent node chooses the move leading to the minimum child node. This assumes that MAX will always wants to choose a move that maximizes his score, and MIN will choose a move than minimizes MAX’s score. Once the root node chooses a maximizing move, that move is chosen for play.

As an optimization, I extended the minimax search with alpha-beta pruning. This greatly reduced computation time without changing the result of the search. Alpha-beta pruning works by halting the generation and evaluation of nodes for portions of the search that will not be chosen anyway. To make the pruning more efficient, moves are sorted before evaluation with the most promising moves checked first. This increases the likelihood that poor moves will be pruned from the search. The decreased computation time allowed me to increase the depth of search. In general, greater search depths should result in better move decisions.

Static Evaluator
I implemented a very simple static evaluator. It simply counts the number of pieces MAX has on the board, and subtracts the number of pieces that MIN has on the board. The resulting number reflects the relative advantage that MAX has over MIN, with a high number indicating a higher advantage. If the gamestate is an endgame situation, a value of 100 is returned for MAX’s win, and -100 for MAX’s loss (or a tie).

Plausible Move Generator
The plausible move generator results a list of all possible moves available to a given player for a given gamestate. This turned out to be a tricky section of code that scans outward from each board location for possible ways to outflank the opponent. Each possible move location is also associated with a value indicating the number of pieces that would be flipped by the move. This value is used to sort the moves for effective alpha-beta pruning.

Results
WinOthello is an effective application of artificial intelligence. The engine implements minimax searching and prunes the search space to greatly reduce the computation time. Despite this efficiency, there is still a trade off between difficulty and quickness. The computer player’s difficulty is directly related to the depth of the minimax search. The greater the difficulty, the deeper the search and the longer it takes. A depth of six takes only seconds on modern computer hardware. I am relatively new to Othello and do not consider myself an expect player by any means. So if I can regularly beat the computer player, I consider it to be a weak player. Increasing the difficulty to 10 makes the computer a much more difficult opponent. However, at this depth, it can take the program about a minute for it to choose a move. It is debatable if this is a reasonable amount of time. It seems that, in WinOthello’s current form, challenging game-play and quick computation are mutually exclusive.

The GUI is simple, understandable, and easy to use. Many of the features outlined as goals were implemented. However, the undo feature hasn’t made it into the game yet. I suspect that it would be fairly easy to add, but I haven’t investigated its implementation yet. An additional feature I added near the end of WinOthello’s development was a game tree viewer. This function displays a tree containing each node traversed in the last minimax search performed by the program. The tree shows rudimentary information such as if a node is MAX or MIN, the value of the nodes, the fraction of each nodes’ children that were actually searched, and the best move selected from the node’s children. I consider this feature incomplete as it was added late for debugging purposes. I decided to keep it for its educational value.

Comparison
Many other people have developed Othello playing programs. Logistello was a strong Othello computer program written in the 1990s by Michael Buro.  This program rose to prominence during its time, winning computer Othello tournaments and soundly defeating the world champion, Takeshi Murakami, in August 1997. It used a more complex static evaluator that considered Othello strategies such as mobility and parity. Logistello also used a book of opening moves that guided its moves at the beginning of the game. It even learned, expanding its book as it played each game. WinOthello does not even begin to approach the complexity of Logistello. Although Logistello is far superior, WinOthello was still a useful exercise in applying and exploring artificial intelligence. A quick comparison to Logistello suggests that WinOthello could greatly benefit from an enhanced static evaluator.

Program Architecture
WinOthello is written in the object-orientated language C#. I will only discuss the architecture of the project’s engine because the GUI is not relevant to artificial intelligence. The board is represented by a board class. The class contains a pair of two-dimensional Boolean arrays, each eight-by-eight, one array for each player. Each piece on the board is represented by a true value in the corresponding array. Various operations can be performed on the board, such as getting a position’s color, testing the possibility of using a location for a move, getting the players’ scores, making a move, copying the board, running the static evaluator, and running the plausible move generator. The game knowledge is primarily represented by this class. Most other classes in the engine operate on this board class.

A player object represents each player. This class indicates if a player is human or computer, the difficulty level, and the player color. This class contains the recursive searching method used to get a computer player’s next move.

A move object also exists. It is used to store the moves found by the plausible move generator. Each move contains the location of the move on the board, a value representing the number of pieces immediately flipped as a result of the move, and a random number used to randomize the order of moves with the same value.

The game object serves as an interface for the GUI to access the engine and controls most aspects of the simulated Othello game. Methods are provided to start the game and allow players to move. Values such as the location of pieces, the scores, and the current turn can also be accessed through the game object. Because of WinOthello’s modular design, a completely different interface can be written that uses the exact same engine without having to rewrite any code game-specific code.

Extensions
Far more could be done with WinOthello. The static evaluator could be enhanced with better heuristics. Various parts of the program could be optimized. Some sort of memory could be added to quicken searches by recalling previously generated moves. An undo feature could be incorporated. Alternative interfaces could be implemented, such as a command line or web interface.

Reflection
My Othello journey has been both exciting and disappointing. I was happy to make quick progress in developing a GUI and working game engine, and thrilled to see it actually make good moves. However, my chosen approach proved limited. The simple static evaluator seems to be the program’s weak point. I choose it because I wanted to keep the design simple, and because I assumed that the program would choose good moves if it was allowed to search the game space deep enough. However time proved to constrain the search depth more than I anticipated. The program isn’t allowed to search as deep as it needs to effectively use such a simple static evaluator.

The greatest difficulty was in trying to design an elegant program structure. I started rewriting the engine several times, once completely rewriting it. It could have been beneficial to map out the program in detail before I started coding. However, given the experimental nature of the assignment, I think my approach was appropriate. I wasn’t sure of what would work best until I had tried it.

An interesting question raised by my project is what constitutes artificial intelligence? My program uses a brute force method to find an ideal solution. Such systematic probing does not seem very humanlike. Even a “smarter” Othello program works by searching a game space and evaluating game states based on preprogrammed heuristics. It seems that all the intelligent behavior stems from the programmer. Any program’s “intelligence” is a result of its design. Programs are simply tools imbued by their creators with a distinctly artificial form of intelligence.