ICS 46 Spring 2017
Project #2: Black and White

Due date and time: Monday, May 8, 11:59pm


Introduction

Many of you have played video games, and while it can be more compelling to play them against other people, we've all become quite accustomed to the idea that you can often play them without anyone else being involved, with the game making its own decisions about how to play against you. This project explores one way to write programs that can make these kinds of decisions, that provide a kind of artificial intelligence (AI). In our case, we'll focus our efforts on techniques based around search trees, which will also give you more practice with the kinds of algorithms that can be used to traverse tree-based structures and with implementing a more complex recursive algorithm than the ones you built in the previous project, which will be a necessary skill for our later work.

Finally, after everyone has submitted this project, I'll run a tournament in which your AI will compete against those written by others. While the tournament has no course credit associated with it — you don't get a higher grade for finishing the tournament rated higher than others, though we do pay attention to who finishes it without being disqualified — you are competing for the notoriety of putting together a better algorithm than anyone else's. May the best algorithm win!


Getting started

Before you begin work on this project, there are a couple of chores you'll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with this project. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll want to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with this project.

2017-04-25 00:55:06
Project #2 template added 

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this project, containing a similar structure to the basic template you saw in Project #0, but including a fair amount of code (both source code and compiled libraries) that is being provided as a starting point. So you'll absolutely need to use the project2 template for this project, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME project2 to create your new project directory using the project2 template. (For example, if you wanted to call your project directory p2, you would issue the command ics46 start p2 project2 to create it.) Now you're ready to proceed!


The project directory

Change into your project directory and take a look around. Having already completed Project #1, what you will see will look very familiar. Once again, your project directory is capable of building (any or all of) three separate programs that you can run by issuing the commands ./run app, ./run exp, or ./run gtest. As before, a lib directory contains precompiled libraries that make up the part of the project that you won't be implementing yourself, an include directory contains declarations of things (only some of which you'll need to use directly), and the usual app, core, exp, and gtest directories for writing your code.


The game of Othello

This project asks you to implement an artificial intelligence for a game called Othello. Othello (also known as Reversi) is a well-known two-player strategy game. The game is played on a square board divided into a grid — usually 8x8, though the size of the grid can vary. Players alternately place tiles on the game board; one player's tiles are black and the other player's are white. When tiles are placed on the game board, other tiles already on the board are flipped (i.e., a black tile becomes a white tile or vice versa). The game concludes when every cell in the grid contains a tile, or when neither player is able to make a legal move; the winning player is the one who has more tiles on the board at the end of the game.

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 covers the rules of the game; knowing how the game is played is crucial to implementing code capable of playing the game well.

If you want to try playing the game, you'll find that a complete, working version of Othello is included as part of this project already.


The application

Your work on this project begins with an already-working Othello game with a graphical user interface (GUI), allowing two human players to play the game against each other. Also included are two rudimentary artificial intelligence implementations — neither is all that intelligent, actually, but they are at least capable of selecting moves automatically so you can play against them.

When you start the application, a window arranged like the one below will appear:

Screenshot of Othello UI (1)

You'll be asked to choose who will play in game, human players or the available AIs. Click Start Game to start a new game, which will launch a new tab in which an Othello board and score are displayed.

Screenshot of Othello UI (2)

When it is a human player's turn to move, all you need to do is click on a square to make your move. When it an AI's turn to move, the AI will make its own decision and the GUI will be updated automatically once the move has been chosen. If you'd like to quit the game, or if you'd like to dismiss it after it's ended, you can just click the Close button. Any time an AI makes an invalid move or throws an exception, an error message will be displayed along the bottom of the windows.

In addition to the score, you'll be able to see which AIs (or human players) are playing against each other.

A brief word of warning

When you start the application on your ICS 46 VM, you may notice an error message like this one in your Terminal window:

QApplication: invalid style override passed, ignoring it

This is something you can safely ignore, since it has no effect on our work here.


The requirements

This project actually requires you to complete only a single task: write an AI that is capable of choosing moves in an Othello game, by using the recursive, search-tree-based algorithm described below. Optionally, you can implement as many additional AIs as you'd like, but one of them constitutes your "official" submission that will be graded; the others are strictly for use in the tournament (described below).

Each of your Othello AI implementations is subject to a few restrictions:

Naming your Othello AIs

Each of your Othello AIs is registered with a display name using the ICS46_DYNAMIC_FACTORY_REGISTER macro. The display name serves three purposes:


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:

  1. 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.
  2. We determine the path from the current game state to the final state that we chose above.
  3. 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 420, which is more than one quadrillion nodes!) Besides, even if there was 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 uses 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 your opponent wants to beat you, just 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 black player has made a move in the game, and the white player wants to figure out the best move to make, using the search tree approach we've been discussing. Then the white player need only be concerned 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, sketched in a very rough pseudo-code, 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:

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. There's more than one way to solve that problem, but you'll need to choose one. One thing to be aware of, though, is that you won't be able to use a global variable to solve this problem, as there might be two instances of your AI playing the game against each other, or there might be multiple simultaneous games being played at the same time.

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, 6) for some state s asks the following question: "Looking six 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 — probably the most important factor that 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 and your friends can beat it, and I also hope you enjoy fine-tuning your program until you have trouble beating it.


A tournament!

After the 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; you'll need to follow these rules in order to win (or possibly even to participate).

How well you do in 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 to implement your "required" AI, though you can additionally do anything you'd like, and you can apply any optimizations to your required AI, provided that you're still basically implementing a recursive search tree based algorithm.)

Being disqualified from the tournament is an indicator we'll use in the grading, however, particularly because it will demonstrate to us that your AI has some kind of flaw (e.g., it chooses invalid moves, or crashes in certain circumstances).

Good luck!


Deliverables

After using the gather script in your project directory to gather up your C++ source and header files into a single project2.tar.gz file (as you did in Project #0, submit that file (and only that file) to Checkmate. Refer back to Project #0 if you need instructions on how to do that.

Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're reponsible for submitting the version of the project that you want graded. We won't regrade a project simply because you submitted the wrong version accidentally. (It's not a bad idea to look at the contents of your tarball before submitting it; see Project #0 for instructions on how to do that.)

Can I submit after the deadline?

Yes, it is possible, subject to the late work policy for this course, which is described in the section titled Late work at this link.