ICS 23 / CSE 23 - Project #2: End of the Game

The rules of the game

The game of Kalah is played on a board that looks like this:

Kalah Screenshot

There are two players, which we'll refer to as the "top" player and the "bottom" player. Each player has six holes on his side of the board and one pot to his right (the "kalah"). (In the picture above, the hole on the far left is the top player's pot, and the hole on the far right is the bottom player's pot.) The game typically begins with six beans in each hole. Players take turns moving.

A move begins with a player picking up all of the beans out of one of his holes. Then, proceeding counterclockwise, he puts one bean in each hole -- be it his or his opponent's -- and his pot, should he reach it, until all of the picked-up beans are dispersed. (If the opponent's pot is encountered during a move, it is skipped.) Depending upon where the last bean was placed, one of three things occurs:

If the last bean was placed in the player's pot, he takes another turn.
If the last bean was placed into one of the current player's holes, that hole was empty, and the opponent's hole directly across from that hole is not empty, then all of the beans in both the opponent's hole and the player's hole are placed into the player's pot; the turn then ends.
In all other cases, the turn ends.

Whenever a turn ends with all the holes on one side of the board empty, the game is over. The beans on the non-empty side of the board are all placed into the player's pot that "goes with" that side of the board. (For instance, if a turn ended with the top player's holes empty, all remaining beans would go into the bottom player's pot.) The player with the most beans in his pot at the end of the game is the winner.

Be sure you know how to play the game before attempting to complete this program; it will save you much time and effort. As provided, the program will already play a game of Kalah with two human players, but it not allow you to play against a computer player until you create your AI class and write the necessary code into the KalahAIFactory class (which is described later in the write-up).

Starting point

All of the code that you'll need to complete this project is included in this Zip archive. Much of the code is provided in compiled (i.e. .class) form. The provided .java files are heavily commented.

You'll only need to work on two classes. First, you need to create a new class that implements the provided KalahAI interface. Your class needs to named in a certain way: specifically, you need to include your student ID# in the name of the class. So, if your student ID# is 12345678, your class should be called KalahAI12345678. This is important!.

Once you've created your AI class, you'll also need to write one line of code in the KalahAIFactory 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 Kalah class contains a main( ) method. To run the program, execute the Kalah class. The provided GUI is simple and straightforward to use. When you run Kalah, a window will appear with some status messages, a blank Kalah board and a Game menu. The menu has two choices, New... and Exit. Exit, of course, exits the game. New... brings up a dialog box from which you can choose whether the top and bottom players are to be human- or computer-controlled, the number of holes per player, the number of beans in each hole at the game's start, and the speed at which the GUI animates each move. Clicking on OK starts the game.

A human-controlled player makes a move by double-clicking a hole (from which he is allowed to move beans). The computer simply moves when it is its turn. We make the beans yellow as they move, so that you can see moves "in action." When the move is over, the beans are returned to their normal brown color. Status messages remind you whose move it is and let you know if you have tried something illegal (such as moving beans from your opponent's hole).

You can exit a game, as well as start up a new game, at any time.

Some necessary terminology

You will be building a rudimentary artificial intelligence (AI) so that the computer can play a game of Kalah 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 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 in compiled (i.e. .class) form, rather than as source code, for this very reason.

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

Consider each of the holes on the board. We'll call these holes positions. The notion of a position is encapsulated in an interface called Position. You can uniquely describe any hole on the board by noting whether it belongs to the top player or the bottom player, and then specifying a "hole number." Each hole in the top and bottom row of holes is numbered, starting at 1 on the lefthand side of the board (as shown on the GUI). The pots are given a special hole number, indicated by the constant Position.POT.
As your AI analyzes possibilities, it will be necessary for it to evaluate the current game situation. Collectively, we'll call the description of the current situation a game state or, more tersely, a state. A game state is comprised of the number of beans in each position, a flag indicating whether it is currently the top or bottom player's turn, and a flag indicating whether the game has ended. The notion of a game state is encapsulated in the GameState interface.
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 provided KalahAI interface, which consists of a method called chooseMove() that analyzes all of the possibilities and picks the AI's next move. Since a move constitutes picking up all of the beans from a particular position, chooseMove() returns that Position. Remember to name your AI class appropriately as described above (i.e. if your student ID# is 12345678, name your AI class KalahAI12345678).

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 Kalah game before the first move is made. The children of this initial state are all of the possible states that can arise from the top player making a valid opening move (since the top player goes first). There are six such states, corresponding to moving the beans out of each of the top player's six holes. (All other moves are illegal and, as such, are not considered.)

Here is a partial look at a Kalah game tree:

Game tree example

In the picture, from the initial state, there are six possibilities from which the top player may choose his move. From one of those, "choice 3," the picture indicates that there are four choices that bottom player will then have. Not pictured are the choices that the top player can make as a result of each of the bottom player's choices. (Not surprisingly, the game tree can grow large rather quickly.)

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, she wants to pick the one that will lead to a winning game state. We can 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 as many as six 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 six possible moves that can be made from any particular state, the number of nodes in the tree would be 6²⁰ + 1, which is roughly equivalent to 3x10¹⁵.) 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 makes a decision in a reasonable amount of time and using a reasonable amount of memory.

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.

This approach reduces our storage needs significantly -- and we don't waste time or memory processing parts of the tree that we can no longer reach.

Even if we generate only the part of the tree that we need, that part may still be much too large to store. This is where a heuristic search comes into play. 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.

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 is the following:

eval(state) = beans in my pot in this state - beans in opponent's pot

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.

Putting these ideas together, we can develop a search algorithm that will look for the move that leads to the game state that evaluates to the highest value. That algorithm looks something like this:

int search(GameState 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 couple of things we need to discuss about the algorithm above:

First, notice that there are two cases of recursion: either it is the computer player'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 the computer player's turn, the maximum value is returned. In other words, the computer player wants to make the best possible move it can.
...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 is in our worst interest).

You may not assume that the computer player will always be the top or the bottom player. The top or the bottom player (or both!) might be a computer player. 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 is of a manageable length. Each time we recurse one level deeper, the depth is reduced by one, and we stop recursing when it reaches zero.

Thirdly, observe that when the top player makes a move, it isn't necessarily the case that the bottom player will be making the next move. So, care must be taken in deciding whose turn it is. The easiest way to deal with this problem is to let the current game state keep track of this for you.

Lastly, note that this algorithm returns the evaluation of the best state, not the best state itself. You'll need to exercise some care in actually implementing this algorithm so that it will be able to actually choose a move.

Deliverables

You need only turn in the Java source code to your KalahAIxxxxxxxx class (where xxxxxxxx is your student ID#), the KalahAIFactory class, and any new classes that you developed. (I don't expect you to write any new classes, but if you do, you'll need to submit them.) Since your AI class is expected to work correctly with all of the provided code left as-is, you should not turn any of the other code in.

Additional Work for Advanced Students (How to Win)

Instead of the heuristic search we used above, the winner of the tournament typically will be someone who writes searches that use other heuristic techniques, perhaps ones that take a completely different approach to searching a game tree. Try out other approaches to see how well they perform relative to the depth-first search approach used above and when used against each other. For instance, an approach called alpha-beta pruning, which is in essence a smarter depth first search, is a good alternative technique to employ (try googling "alpha-beta pruning").

Our evaluation function may not always be—may even never be—the best to use: a move that puts more beans into your pot now might set up the board so your opponent could later obtain a larger quantity of beans than you did. Perhaps another move would have left the board so that your opponent would be in a poor position. Remember, the goal is not only to obtain beans for yourself but to obtain more beans than your opponent. So, modify your evaluation function, or write several that you can “swap in and out“ of your program, and see how they do against a human and computer player, and against the evaluation function we gave above.