Othello

Authors: Paul Reid, Daryus Lung, Marina Chun

What is the problem?

We will implement the 2-player board game Othello (a variant of Reversi) using Haskell. Game description from Wikipedia:

There are sixty-four identical game pieces called disks, which are light on one side and dark on the other. Players take turns placing disks on the board with their assigned color facing up. During a play, any disks of the opponent's color that are in a straight line and bounded by the disk just placed and another disk of the current player's color are turned over to the current player's color. The object of the game is to have the majority of disks turned to display your color when the last playable empty square is filled.

What is the something extra?

We implemented the following AI players:

1.Random AI

This AI evaluates all the valid moves from the current game state and randomly picks one of the valid moves.

2. Heuristic AI

This AI evaluates all the possible moves from the current game state and calculates the potential score of each board. After calculating the value of the score, if a valid move includes a corner. more weight is added to the score. Then, it makes the move that will give them the maximum score out of all the possible moves.

3. Heuristic AI with Lookahead

This AI evaluates the possible game states that could occur three moves ahead. It then calculates the score of all the potential boards. After evaluating the score of each board, if a valid move includes a position that surrounds a corner, the score is decreased, but if a valid move includes a corner, the score is increased. The AI then makes the move that could lead them to the highest score.

4. Minimax AI

This AI picks a move based on the minimax algorithm. There were two differences in our implementation from the in-class example. First, in Othello it is possible for a player to have multiple moves in a row (because the other player has no valid moves available), so our algorithm does not always switch between being maximizing and minimizing. Second, since the Othello game tree grows very quickly our algorithm cannot play out the game until it reaches the end. We had to set a maximum search depth, and when the algorithm hits the maximum depth it uses a heuristic board evaluation function to estimate the value of the game state.

Additionally, we included an AI vs AI tournament where a Random AI plays a number of games against another AI (Random, Heuristic, Heuristic with Lookahead, or Minimax). We can pick which of the AI players we want to have play against the Random AI player. We used this tournament to evaluate the performance of our AIs. To keep the console output readable, this option does not print the game states as the tournament progresses, it just returns the number of wins for each color and ties.

What did we learn from doing this?

What we learned from implementing the AIs

With a game like Othello, where there are a lot of potential combinations of moves and states, the game tree grows large very quickly. This means that our implementation of minimax can't look very far ahead in the game tree and is quite slow. Given more time we could have improved our AI by implementing more advanced techniques such as caching and/or alpha-beta pruning.

This also made it difficult for us to test as it was impossible for us to manually play the game and try all the possible moves given the time constraints. Also we had initially implemented the game so that we can pick any AI player for the tournament; however, we quickly realized that each AI will always make the same decision, depending on who goes first (second player has the advantage).

Haskell language

Packages: we used some useful packages from Haskell's standard library, especially the Data.Maybe package. This made it much easier to deal with Maybe values, such as when reading user input from the console.
Record syntax: Haskell's record syntax made it very easy to update the game state as we passed it through each iteration of the game loop.

Overall, what we learned was that functional programming is suitable for working on a game where the players take turns, which leads to different game states. The code is much more clean and simple and is suitable for a game like Othello where we had to implement recursive functions. Also, as Haskell has a strong-typed nature, we were able to fix our type errors easily.

While we felt that functional programming was suitable for implementing the game to play with two from any of the three (human, Random AI, or Heuristic AI), we were not too convinced that it was the best for the other two AI players (Heuristic with Lookahead and Minimax). However, looking back we could also possibly have implemented the AI players in a way that they remember the potential board states so that it would not evaluate the potential game states over and over again.

Links to code etc

github