Pente

Group Members

David Kron (MTD(f)), Matt Renzelmann (NegaScout), Eric Richmond (SSS-2), Todd Ritland (Alpha/Beta with Transposition Table)

Download

Download everything related to this project here: pente.zip.

Presentation - Added December 9th

Click here to download a copy of our presentation in PowerPoint format. Click here for PDF.

How to play

Pente is pretty simple. The version of it we use is even simpler. Play alternates between two players on a board (default 13x13 grid in size). One player is red, the other green. Play consists of choosing a square on the board. Once chosen, the square changes to the player's color, and it becomes the other player's turn. The goal is to get several squares in a row (default 5) either horizontally, vertically, or diagonally. The only twist is that the first player must move in the center of the board. The first player's second move must be outside of a small box around the center. This rule is necessary to negate the first player's otherwise substantial advantage.

Project Introduction

In this project, we examine the following game tree search algorithms: MiniMax, MiniMax with Alpha-Beta pruning, NegaScout, MiniMax with Alpha-Beta pruning and a transposition table, SSS-2, and MTD(f). These search algorithms are well-suited to zero-sum, perfect information, two player games like Chess, Checkers, Tic-Tac-Toe, and of course, Pente. They operate by searching the "game tree" and choosing the best possible move. A node in a game tree represents the state of the game (i.e. the board layout), while an edge in the tree represents the move a player could make to transform the game state from the source node to the destination. Because the players alternate turns, the tree is divided into neat layers, with alternating rows of nodes corresponding to the positions the players will need to consider.

Technical detail: Please view this page in something other than IE6, since it doesn't support PNG transparency. Sorry for the inconvenience.

Game Setup

If you'd like to play a game against the computer using a Java applet, use the settings below to customize the game, and then click "Go!" Alternatively, download the code above, and execute "javac Pente.java" followed by "java Pente" to play a command line version of the game.

The command line version of the program has a number of features not found in the applet version. In this section, we'll discuss how to run the command line version, and the various features it offers.

First, to run the command line version of the program, compile it via "javac Pente.java". To execute it, run "java Pente". It will prompt you for various parameters.

Pente mode 1 - Play the game

To play the game against the computer on the command line, execute one of the following commands:

If the second command line parameter is a number, the program interprets this to be a board size. The board size should be an odd number, and should be fairly large (e.g. 9, 11, 13 etc). Alternately, if the second command line is anything other than a number, the program interprets this as a filename. The file contains a board that has already been setup. Play always begins with the first player, regardless of how many squares are occupied on the board. This mode is handy for testing the program's behaviour in various scenarios.

The third command line parameter is simply how many squares in a row are needed to win. Normal Pente rules set this value at 5.

The fourth parameter is the number of milliseconds allotted per turn. The human player always gets unlimited time, but the computer opponents are required to make a move after this amount of time has passed. We use an iterative deepening search to ensure the result provided by the computer is always meaningful.

The fifth and sixth parameters control who or what is playing the game. Values include: minimax, alphabeta, negascout, sss2, mtdf, tt, or human. Any kind of player can be player 1 or player 2.

Pente mode 2 - Test the players

Since playing the game doesn't lend itself to easy algorithm debugging, we've included a second mode in which the user supplies a sample game tree, like those covered in class or on homework. The program then runs on this tree, and shows which nodes it examined. Using this mode, it's possible to see easily how the algorithms compare to one another. This mode was also used to construct many of the examples seen later on this page.

To run the various algorithms on such a tree, execute the command: "java Pente 2 <filename> <algorithm>".

The second parameter specifies the file containing the game tree to examine. The format is demonstrated by the following example. The format is pretty simple: a string with only characters and no integer represents an internal node, whereas a string with an integer at the represents a leaf node.

This particular example is from homework 2, in which we were asked to run the Alpha/Beta pruning algorithm on a provided game tree. The output from the program is shown below. It seems to match the solution to the assignment.

MiniMax

MiniMax represents the classic game search algorithm. Assuming the game has two players who alternate turns, and assuming both players have complete knowledge of the state of the game, minimax is a simple, but effective means of deciding what move to make. The idea behind its operation is as follows: the player who is currently choosing which move to make needs to consider which move his opponent will make in response, and the move he will make in response to his opponent's, and so on. By assuming his opponent will play perfectly, the player who is moving can make the best choice possible.

Definitions

Algorithm

Below is an outline of the minimax algorithm in pseudocode.

            int miniMax (int depth, boolean myMinFlag) {
                // Check if the game is over, and the depth limit
                if (gameOver) {
                    return utility();
                } else if (depth > depthLimit) {
                    return staticBoardEvaluator ();
                }
        
                // Get next moves
                nextMoves = getNextMoves ();
                if (myMinFlag == true) {
                    int value = INFINITY;
                    // Iterate over possible moves for that player.
                    for (int i = 0; i < numNextMoves; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER2);
        
                        // Run miniMax on the modified board
                        value = min(value, miniMax (depth + 1, !myMinFlag));
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER2);
                    }
        
                    // Return the minimum value seen.
                    return value;
                } else { // maximizing
                    int value = -INFINITY;
                    // Iterate over possible moves for that player.
                    for (int i = 0; i < numNextMoves; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER1);
        
                        // Run miniMax on the modified board
                        value = max(value, miniMax (depth + 1, !myMinFlag));
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER1);
                    }
        
                    // Return the maximum value seen.
                    return value;
                }
            }
            

Example Game Tree

The image below shows an example game tree. Assume the bottom nodes are terminal states, and the numbers inside each node represent the utility of that game state. Thus, the game will end in just three moves. In this example, the first player is attempting to maximize the game state's utility, while the second player is attempting to minimize the game state's utility. The initial state of the game is represented by the node at the root of the tree. At the start of this game, the first player has 3 choices. He examines his opponent's response to each of these three choices. His opponent, recall, is trying to minimize the game state's utility. Therefore, he assumes his opponent will move according to this goal. Therefore, the game will play out as follows: the first player will choose node B, and the second player will choose node E.

MiniMax with Alpha-Beta Pruning

One of the main problems with MiniMax is its performance in practice. Although it will generate the optimal solution to a game given an infinite amount of time, this is insufficient for most practical applications. Consequently, researchers have attempted to modify MiniMax in ways which allow it to skip the examination of certain moves, while still producing the optimal solution. MiniMax with Alpha-Beta pruning is the result of one such effort. The idea is as follows. While a player examines his available moves, he also keeps track of the best and worst values seen so far. These values are called Alpha and Beta.

Definitions

Algorithm

Below is a description of the MiniMax with Alpha-Beta Pruning algorithm in pseudocode.

            int alphaBeta (int depth, boolean myMinFlag, int alpha, int beta) {
                // Check if the game is over, and the depth limit
                if (gameOver) {
                    return utility();
                } else if (depth > depthLimit) {
                    return staticBoardEvaluator ();
                }
        
                // Get next moves
                nextMoves = getNextMoves ();
                if (myMinFlag == true) {
                    // Iterate over possible moves for that player.
                    for (int i = 0; i < numNextMoves; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER2);
        
                        // Run alphaBeta on the modified board
                        beta = min(beta, alphaBeta (depth + 1, !myMinFlag, alpha, beta));
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER2);
        
                        // Alpha beta
                        if (beta <= alpha) {
                            return alpha;
                        }
                    }
        
                    // Return the minimum value seen.
                    return beta;
                } else { // maximizing
                    // Iterate over possible moves for that player.
                    for (int i = 0; i < numNextMoves; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER1);
        
                        // Run alphaBeta on the modified board
                        alpha = max(alpha, alphaBeta (depth + 1, !myMinFlag, alpha, beta));
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER1);
    
                        // Alpha beta
                        if (beta <= alpha) {
                            return beta;
                        }
                    }
        
                    // Return the maximum value seen.
                    return alpha;
                }
            }
            

Example Game Tree

The following list outlines how the AlphaBeta algorithm proceeds on the game tree below. The important thing to get out of this example is that with Alpha/Beta pruning, the computer does not need to examine every node of the game tree. It can prune entire branches, thereby saving considerable time. Another thing to note is that if the computer examines the nodes in the best order possible, it can prune many more branches than it could otherwise. Indeed, in the worst case, Alpha/Beta pruning doesn't prune anything, making it identical to plain MiniMax (luckily, the worst case is, in general, very unlikely in practice).

NegaScout

Algorithm

Below is a description of the NegaScout algorithm in pseudocode. NegaScout was designed with assumption that the moves would be well ordered, like alpha beta. The difference is that NegaScout tries to take better advantage of "somewhat" well ordered moves than AlphaBeta. It does this by using what's called a "null window", that is, a window whose values are of the form (x, x + 1). Such a window could not contain an actual value, instead, it will cause the algorithm to stop immediately (with a value that's either too high or too low). The trouble with NegaScout is that sometimes the next move list is not well ordered. As a consequence, NegaScout will actually perform a re-search of an entire subtree. Consequently, NegaScout performs best when it has at its disposal a transposition table, or a means of spotting such redundant searches.

            int negaScout (int depth, boolean myMinFlag, int alpha, int beta) {
                // Check if the game is over, and the depth limit
                if (gameOver) {
                    return utility();
                } else if (depth > depthLimit) {
                    return staticBoardEvaluator ();
                }
        
                // Get next moves
                nextMoves = getNextMoves ();

                // Initialize additional NegaScout variables
                int g = 0;
                int startAt = 1;
                char whoseMove = myMinFlag ? PLAYER2 : PLAYER1;
                
                // Find starting point
                // Make first move
                makeMove(nextMoves[0], whoseMove);

                // Run negaScout on the modified board
                g = negaScout (depth + 1, !myMinFlag, alpha, beta);

                // Reset board back to reality.
                undoMove(nextMoves[0], whose_move);

                if (myMinFlag == true) {
                    int newBeta = beta;

                    // Iterate over possible moves for that player.
                    for (int i = startAt; i < numNextMoves && g > curAlpha; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER2);
        
                        // Run negaScout on the modified board
                        newBeta = min(g, newBeta);
        
                        int t = negaScout (depth + 1, !myMinFlag, newBeta - 1, newBeta);
                        if (t < newBeta && t > alpha) {
                            t = negaScout (depth + 1, !myMinFlag, alpha, t);
                        }
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER2);
        
                        // Save best value
                        g = min (g, t);
                    }
                } else { // maximizing
                    int newAlpha = alpha;

                    // Iterate over possible moves for that player.
                    for (int i = startAt; i < numNextMoves && g > curBeta; i++) {
                        // Modify the board
                        makeMove(nextMoves[i], PLAYER1);
        
                        // Run negaScout on the modified board
                        newAlpha = max(g, newAlpha);
        
                        int t = negaScout (depth + 1, !myMinFlag, newAlpha, newAlpha + 1);
                        if (t > newAlpha && t < beta) {
                            t = negaScout (depth + 1, !myMinFlag, t, beta);
                        }
        
                        // Reset board back to reality.
                        undoMove(nextMoves[i], PLAYER1);
    
                        // Save best value
                        g = max (g, t);
                    }
                }
                
                return g;
            }
            

Example Game Tree

The following example tree demonstrates a situation in which NegaScout outperforms Alpha-Beta, although the difference is very small due to the size of the example. The first tree shows the resultant game tree after performing MiniMax with Alpha-Beta pruning.

The recursive calls to AlphaBeta proceed as follows:

The second tree shows the result of running NegaScout. Note that the values of alpha and beta are all the same: it can be proven that a call to NegaScout returns the same value as a call to AlphaBeta, and that every node visited by a call to NegaScout must also be visited by a call to AlphaBeta.

As a final example, the tree below demonstrates the possibility that NegaScout visits the same node more than once. This property suggests that NegaScout performance is at its highest when a transposition table is also used. Transposition tables are used to store the values of a game state so they don't need to be recalculated should they occur again during a search. In this case, the exact same node is considered, making a transposition table more important. Our implementation does not include a transposition table with NegaScout.

Alpha-Beta with Transposition Table

A transposition table is simply a hash table that stores previously calculated board configurations. When Alpha-Beta starts to run on a given board, the algorithm checks to see if this board is in the hash table (and therefore, has already been computed). If the board IS in the hash table, the result is simply drawn from the table. If the board ISN'T in the hash table, alpha-beta minimax continues as usual, and the result is stored in the table.

So this looks like this:

        for (all possible moves){
	        if (board with this move is in hash table){
		        get alphabeta value from table;
	        }
	        else {
		        alphabeta(this table);
		        store result in hash table;
	        }
        }
        

Hash Function

The basic hash function is to look at some set of positions on the board as a string of:

0 if not occupied

1 if occupied by player 1

2 if occupied by player 2

This string is considered a base 3 number, and is calculated as such. Here is the code:

        hashForwardDiag(BoardInterface board){
    		int[] position = new int[2];
		    double value = 0;
		    char temp;
		    for(int i = 0; i < this.size; i++){
    			position[0] = i;
			    position[1] = i;
			    temp = ((Board)board).getPosition(position);
			    if(temp == 1)
    				value += Math.pow(3, (double)i);
			    else if(temp == 2)
    				value += 2 * Math.pow(3, (double)i);
		    }
		    return ((int)value/divisor);
        }
        

The hash table that I decided to use is a 3 dimensional array that stores "HashList" objects, which can hold as many table configurations as needed. The first dimension of the hash table is the hash function on just the middle row. The second dimension is the hash function on the middle column. The 3rd dimension is the hash function on the diagonal from the upper left of the board, to the lower right of the board. If the size of the possible base 3 numbers associated with each of these is too large (larger than 20,000), a divisor is used to divide the result of the hash function.

The reason the hash table was made in 3 dimensions is that most of the possible base 3 strings will not occur, so most of the arrays will never be initialized, greatly reducing the amount of space the hash table occupies. However, this means that the more entries that are added to the hash table, the larger it becomes.

SSS-2

The SSS-2 algorithm is a variant of an algorithm called SSS*. Minimax and Alpha-Beta searches typically proceed in a depth-first fashion, from "left" to "right" in the game tree. The order of the nodes visited in this way seems arbitrary, and so SSS-2 attempts to perform a "best-first" search. To do this, it generates a solution tree using a function called expand and then refines/updates this solution tree using a function called diminish. The algorithm maintains this solution tree globally, as well as the "best-so-far" value of the tree.

The algorithm for SSS-2 is as follows:

        G = {root};		//The global solution tree
        g = expand(root, +inf);		//The "best-so-far" value

        do {
	        temp = g;
	        g = diminish(root, temp);
        } until (g >= temp);
        

Only a few lines of code -- seems simple, eh? The fun has just begun. I decided including pseudocode for the expand and diminish functions would only confuse matters more than they are about to become. Therefore, I instead include detailed descriptions of these two functions.

Description of Expand

Expand takes two values as input: the node that is being visited (n), and the current "best-so-far" value of the global solution tree (v). When the node being visited is a MAX node, it visits each of its children, adding them to the global solution tree. When the MAX node finds in its children a single value greater than the "best-so-far" value, all of that node's children are purged from the global solution tree and that new, better value is returned. If it does not find a value better than v after checking all of its children, it will return the greatest value of all of its children. When the node (n) being visited is a MIN node, its children are visited one at a time, maintaining only the child currently being visited in the global solution tree. When a MIN node finds in its children a single value less than the "best-so-far" value, it drops everything and returns that new, better value. If it doesn't find a better value, it will return the least value of all of its children.

To get an initial "best-so-far" value, SSS-2 makes a call to expand(root, +inf). The MAX nodes won't find any children with values greater than infinity, so all children of all visited MAX nodes will be added to the global solution tree. On the other hand, the values of the children of the MIN nodes will all be less than infinity, so the first child visited of every MIN node will be added to the global solution tree.

Description of Diminish

Diminish will recurse down to the leaf node that contains the "best-so-far" value, v. If the parent of this node is a MAX node, then the node and all of its "siblings" are purged from G. Otherwise, if the parent of this node is a MIN node, the "siblings" of this node are searched for a smaller (better) "best-so-far" value. If one is found, this new, smaller (better) node remains in G and its value is returned. If no smaller value is found, the same old "best-so-far" value is returned.

Next, diminish works its way back up the tree in the following way.

Maximizing: If a better (smaller -- better for the child node) value is found by the child (minimizing) node which contains the "best-so-far" value, this node re-evaluates its children and returns the value of its child that NOW has the greatest value. If no better value is found by the child (minimizing) node which contains the "best-so-far" value, all of this node's children get purged from G, and the same old "best-so-far" value is returned.

Minimizing: If this node's single child in the solution tree (G) returns a value smaller than v through a recursive call to diminish, the node returns this new value. Otherwise the child node that contains the old "best-so-far" value is removed from the global solution tree. The node's next child is added to the global solution tree and inspected using the expand function. If this call finds a new, smaller "best-so-far" value, this value is returned immediately. If not, the node removes this child from the solution tree, and repeats this process for all of its children. If no child has a smaller value, the same old "best-so-far" value is returned.

MTD(f)

The idea behind MTD(f) is that it is simpler than other new minimax algorithms such as NegaScout. It gets it's efficiency from doing only zero-window alpha-beta searches. This means that instead of sending an alpha and beta as -/+ infinity it sends a value of beta-1 for alpha. They use these approximate values to hopefully approach the real MiniMax value. The algorithm is the following:

        MTDF(pos, depth, f)
        {
            int score = f;
            upperBound = +INFINITY;
            lowerBound = -INFINITY;
            while(upperBound > lowerBound) do
            {
                if(score ==lowerBound) then beta = score+1;
                else    beta = score;
                score = AlphaBeta(pos,beta-1,beta,d);
                if(score < beta) then upperBound = score;
                else lowerBound = score;
            }
            return score;
        }
        

f is the estimate of the final score. The algorithm works better when f is close to the final score so when using iterative deepening it's a good idea to start by using the f of the previous depth. Another way to make MTD(f) perform as the current best algorithm is by instead of using AlphaBeta in the algorithm, to use AlphaBeta with transposition Tables (see AlphaBeta w/ Transposition Tables).

Comparison - Added December 2nd

After running each algorithm against every other algorithm, we obtained the following results. Since this experiment included running each algorithm against itself one time, every algorithm is guaranteed at least one win.

Other Resources

Here are some papers we used for reference while implementing these algorithms: