ICS 23 / CSE 23 Summer 2012, Project #2: Black and White

Due date and time: Friday, July 20, 11:59pm

Introduction

Othello, also known as Reversi, is a well-known two-player strategy game. In this project, you have been provided with a Java program that allows human players to play Othello against one another. Your goal is to develop an intelligent algorithm to play Othello against a human player (or against another intelligent algorithm). In particular, you're being asked to write the search and strategy routines that will allow your program to play the game instead of a human player.

After everyone has submitted this project, I'll run a tournament in which your algorithm will compete against those written by others. While the tournament has no course credit associated with it, you are competing for the notoriety of putting together a better algorithm than anyone else's. May the best algorithm win!

The game of Othello

Othello is a strategy game played on a square board divided into an 8x8 grid. The rules of the game, along with some notion of strategy, are described in the Wikipedia entry on Reversi; if you haven't played Othello before, or have seen it previously but don't remember how it works, you should at least read the sections of the Wikipedia entry that cover the rules of the game; knowing how the game is played before attempting to complete this project will save you a lot of time and effort.

As provided, the program will already play a game of Othello with two human players, but it will not allow you to play against a computer player until you create your AI class and write the necessary code in the OthelloAIFactory class (which is described later in the write-up).

Starting point

All of the code that you'll need to complete the project is included in this zip archive. Much of the code is provided as a JAR (as in the previous project). The provided .java files are heavily commented, to give you a sense of what parts need to be written and how to use the parts that your code will need to interface with.

You'll only need to work on two classes. First, you need to create a new class that implements the OthelloAI interface. Your class needs to be named in a certain way; specifically, the name of the class needs to begin with OthelloAI, followed by your eight-digit student ID#. So, if your student ID# is 12345678, your class should be called OthelloAI12345678. This is important; I can't include you in the tournament unless you've done this!

Once you've created your AI class, you'll also need to write one line of code in the OthelloAIFactory class. The comments in that class will explain what you need to do and why.

Everything else is to be left as-is.

How to run the program

The Othello class contains a main() method. To run the program, execute the Othello class. The provided GUI is simple and straightforward to use. When you run Othello, a window will appear with a green area with the label "Click here to start game." Click the green area and you'll be asked to specify whether each player should be controlled by a human or the computer; for now, specify human for both, as you haven't implemented your AI yet. Clicking on OK starts the game.

A human-controlled player makes a move by double-clicking an empty square on the grid. Not all squares constitute valid moves; the mouse cursor will turn into a "hand" when a square is a valid one, much like when you hover over a link in your browser. The computer simply moves when it is its turn. The GUI animates the placing and flipping of tiles, so that you can see the moves "in action." Status messages display the score and remind you whose move it is.

Some necessary terminology

You will be building a rudimentary artificial intelligence (AI) so that the computer can play a game of Othello against you (or against another instance of your artificial intelligence). Your task for this project is fairly narrow, so you can disregard the vast majority of the code that we gave you, most of which implements either the GUI or the game logic. In fact, most of the code has been provided as a JAR, rather than as source code, for this reason.

There are three main abstractions that you need to understand in order to write the code required for this project:

The contents of each grid cell are represented by the enumeration OthelloCell, which has three possible values: OthelloCell.NONE (for an empty cell), OthelloCell.BLACK (for a cell containing a black tile), and OthelloCell.WHITE (for a cell containing a white tile). The locations of the grid cells are denoted by ordered pairs (r, c), where r is the row and c is the column. As is the custom with two-dimensional arrays in Java, the row numbers and column numbers begin at 0, so the range of possible locations is (0, 0) through (7, 7).
As your AI analyzes possibilities, it will be necessary for it to evaluate the current game situation. Collectively, we call the description of the current situation a game state or, more tersely, a state. A game state is comprised of the contents of each grid cell, the score of the game, a flag indicating whose turn it is, and a flag indicating whether the game has ended.
Since it's possible to have two AI's playing against each other, it makes sense to encapsulate the AI into a class, so that two objects of that class could be created and play against one another. You'll implement your AI in a class that implements the OthelloAI interface, which consists of a method called chooseMove() that analyzes all of the possibilities and picks the AI's next move. Since a move is denoted by the square in which a new tile should be placed, chooseMove() returns an object of type OthelloMove, which contains a row number and column number.

Game trees

You can think of the possible game states as being arranged, conceptually, in a kind of search tree called a game tree. Each node of the tree contains a particular game state g. Its children are the game states that can result from making each valid move from the state g.

The root of the tree is the initial game state — that is, the Othello game before the first move is made. The children of this initial state are all of the possible states that can arise from the black player (who moves first) making a valid opening move. There are four such states, corresponding to the four possible moves that the black player is permitted to make at the opening. (All other moves are illegal and, as such, are not to be considered.)

Here is a partial look at an Othello game tree:

In the picture, from the initial state, there are four possibilies from which the black player can choose its initial move. From the first of those, we see that there are three possible moves that the white player can make in response. Other moves aren't pictured, but the tree continues to grow in this fashion. (Not surprisingly, the game tree can grow large rather quickly, so you'll find that it's difficult to draw very much of it on paper.)

We'll call the leaves in such a game tree the final states. These leaves indicate the states in which one player or the other has won the game.

Exhaustively searching all possibilities

Each time a player wants to pick a move, he or she wants to pick the one that will lead to a winning game state. One algorithm for doing that would determine the best move in three steps:

We apply an evaluation function to each final game state. An evaluation function typically returns a number, where higher numbers are considered better. We then identify the final state with the highest value — that is the "end game" that we would like to occur, as it is the best win for us.
We determine the path from the current game state to the final state that we chose above.
We make the move that takes us from the current game state down the path toward the chosen final state.

Assuming that you had a complete game tree at your disposal, this is a simple approach to implement. However, practical limitations make this approach impossible. First of all, the number of game states on each level of the tree grows exponentially as you work your way down the tree, since there are a number of possible moves that can be taken from any particular game state. There simply won't be enough memory to store the entire game tree. (You can imagine that, if you build the game tree 20 levels deep, and there are four possible moves that can be made from any particular state, the number of nodes in the tree would be greater than 4²⁰, which is more than one quadrillion nodes!) Besides, even if there were enough memory available to store the tree, the processing time to create the entire game tree would be prohibitive.

So we'll need to find a compromise — an approach that perhaps doesn't always find the best possible outcome, but that makes a decision in a reasonable amount of time and using a reasonable amount of memory.

Also, it's important to realize that just because you've found a path to the end game you want doesn't mean that you can force the events to take place that will get you there. Just as your goal is to make moves that are in your best interest, your opponent's goal is the opposite. So your algorithm will need to account for the fact that our opponent wants to beat you as much as you want to beat your opponent.

Heuristic search

The study of artificial intelligence has much to say about good ways to search toward a goal when it's impractical to check all possible paths toward it.

We can first make use of the following observation: Suppose the top player has made a move in the game, and the bottom player wants to figure out the best move to make, using the search tree approach we've been discussing. Then the bottom player need only concern himself with the subtree that has the current game state as its root. Once a move is made, all the other moves that could have been made can be ignored, as it is now not possible to take those paths down the tree. Thus, when analyzing the next move to make, we need only generate the part of the search tree that originates from the current game state. That's a good step toward reducing our storage needs significantly, though it's only the first step; especially early in the game, there might still be huge numbers of states that can arise from the state we're currently in.

To reduce our workload even more, we can employ a technique called heuristic search. In a heuristic search, we generate as much of the relevant subtree as is practical, using the resulting game states to guide us in selecting a move that we hope will be the best, even though we don't have time to get full information about how the move might turn out.

There are several strategies that we could use. At the heart of the strategy that we'll use is the notion of an evaluation function that we discussed earlier. We'll need to rate each particular game state in some way, so that we can decide which of a large number of game states is the best outcome for us. A simple approach — though one that ignores some important aspects of the game — is the following:

eval(state) = number of tiles belonging to me − number of tiles belonging to my opponent

It's also important to note here that you do not need to actually build a game tree in memory. Our algorithm will perform a sort of depth-first search on the game tree, meaning that we can use parameters in a recursive method (stored on the run-time stack) to perform the search, negating the need to actually build and store a game tree. This will dramatically reduce the amount of memory needed to choose a move, since only one path in the tree will ever need to be stored on the run-time stack at a time. So, in an eight-level-deep search, we'll store as many as eight nodes, rather than all of the nodes that can be reached in eight moves (which might be huge).

Putting these ideas together, we can develop a search algorithm that will help us to evaluate each of the possible moves we might make. That algorithm looks something like this:

int search(OthelloGameState s, int depth)
{
    if (depth == 0)
        return evaluation of s
    else
    {
        if (it's my turn to move)
        {
            for each valid move that I can make from s
            {
                make that move on s yielding a state s'
                search(s', depth - 1)
            }
            
            return the maximum value returned from recursive search calls
        }
        else
        {
            for each valid move that my opponent can make from s
            {
                make that move on s yielding a state s'
                search(s', depth - 1)
            }
            
            return the minimum value returned from recursive search calls
        }
    }
}

There are a few things we need to discuss about the algorithm above. First, notice that there are two cases of recursion: either it is your algorithm's turn (who is currently making the decision) or its opponent's turn. In each case, the algorithm is almost the same, except:

...when it is your algorithm's turn, the maximum value is returned. In other words, the algorithm wants to make the best possible move it can on its own behalf.
...when it is the opponent's turn, the minimum value is returned. This is because it is assumed that the opponent will also make the move that's in its best interest (which, in turn, is in our worst interest).

You may not assume that your algorithm will always be the black or the white player. Either the black or the white player (or both!) might be played by your algorithm. When deciding whether it's "my turn" or "my opponent's turn," you'll have to exercise some caution to ensure that you're making the right decision.

Second, notice the depth parameter. This will be used to limit the depth of our search, to make sure that our search does a manageable amount of work. Each time we recurse one level deeper, the depth is reduced by one, and we stop recursing when it reaches zero. You'll need to experiment a bit to decide what depth can be handled in a reasonable amount of time, but without limiting the depth, you'll find that moves will take orders of magnitude longer than you'll be willing to wait.

Third, observe that when one player makes a move, it isn't necessarily the case that the other player will be making the next move; occasionally, in Othello, the same player gets to move twice in a row. So, care must be taken in deciding whose turn it is. The easiest way to deal with this problem is to count on the current game state to keep track of this for you; it can always tell you reliably whose turn it is.

Lastly, note that this algorithm returns the evaluation of the best state, not the best state itself. In short, calling search(s, 4) for some state s asks the following question: "Looking four moves into the future, and assuming I do the best I can do and so does my opponent, how well will the state s turn out for me?" You'll need to exercise some care in actually implementing this algorithm so that chooseMove() will be able to call search() and use the result to help it choose the right move.

Evaluation functions

The core of your AI — what will set it apart from others — is the evaluation function that it uses to decide how "good" each board configuration is. I'm leaving this as an open problem and you're welcome to implement your evaluation function however you'd like. You might want to poke around the web looking for strategy guides or other information, taking into account, for example, that some squares on the Othello board are considered more important than others.

It's intended to be fun to play against your own program to see if you can beat it, and I also hope you enjoy fine-tuning your program until you have trouble beating it.

A tournament!

After this project's due date has passed, I'll be gathering all of your AIs together and running a tournament to determine who has the best AI. In fairness, I'll explain here how the tournament will be organized:

Each AI will play two games against each other AI, one each as black and as white.
The primary factor in determining the "best" AI is the total percentage of games won. (Draws will count as 1/2 of a win and 1/2 of a loss.) So, first and foremost, it's important to win games.
A secondary factor, to be used in the case of a tie, is the total number of tiles accumulated in all games. This means that winning games big, as opposed to squeaking out close wins, is important if there's a tie, but that winning small more often still trumps winning big less often.
Your AI will be given 5 seconds of CPU time to choose each of its moves. (I'll be running the tournament on a 1.7 GHz Intel Core i7; though it has multiple cores, I will only be using one core for each game and running multiple games simultaneously.)
Your AI is not permitted to launch additional threads or processes; it must do its work entirely on the thread that calls into the chooseMove() method.
If your AI takes too long to make a move, returns null, throws an exception, isn't named according to the naming convention, or violates any of the other rules laid out in the project write-up, it will be disqualified from the tournament.

The outcome of the tournament will have no bearing on your grade, but it will hopefully motivate you to think a bit about how you might tune up your evaluation function — or explore alternative ways of helping your AI to see farther into the future. (You are required, fundamentally, to use the algorithm shown in this write-up, though there are optimizations you can make to it, if you're so inclined. If you're not sure whether your idea is permissible, ask me and I'd be glad to let you know what I think about it.)

Good luck!

Deliverables

You need only turn in your OthelloAIFactory.java file and the file containing your AI class, along with any additional classes you created, if any. You do not need to turn in any of the other files that were provided to you. Follow this link for an explanation of how to turn in your project.