COE 312 Project 3, Fall 2012

COE 312 (Data Structures) Fall 2012 W. FAWAZ Project III Project III (Due date: Thursday January 17, 2013) I. Objective This project is about writing a Java application that allows two players to play Tic-Tac-Toe. The Tic-Tac-Toe game is played on a two-dimensional three-by-three board. Two players alternate placing their symbols on squares. The first to get three squares in a row, column, or a long diagonal wins. In the context of this project, the computer makes the moves for one of the players and consequently you will be designing a single player Tic-Tac-Toe game where your end user will be challenging the computer. II. Brute-force implementation As the title of this section suggests, we will first opt for an implementation where the computer does not make optimal moves. In particular, during the course of the game, the computer will be inserting his symbols into randomly selected cells. The skeleton for a TicTacToe class is given below. TicTacToe has a data object called board that represents the current game position. A host of trivial self-descriptive methods are also defined within the TicTacToe class, including methods to clear the board, test whether a square is occupied, place a symbol on a square, and to test whether a win has been achieved. Kindly go over the provided implementation before proceeding to accomplishing your first assigned task. public class TicTacToe { public static final int HUMAN = 0; public static final int COMPUTER = 1; public static final int EMPTY = 2; private int[][] board = new int[3][3]; // Constructor public TicTacToe() { clearBoard( ); } public int [] [] getBoard() { return board; } // Play move, including checking legality public boolean playMove(int side, int row, int column) { if( row < 0 || row >= 3 || column < 0 || column >= 3 L E B A N E S E A M E R I C A N U N I V E R S I T Y Electrical and Computer Engineering Dept || board[ row ][ column ] != EMPTY ) return false; board[ row ][ column ] = side; return true; } // Simple supporting routines public void clearBoard() { for( int i = 0; i < 3; i++ ) for( int j = 0; j < 3; j++ ) board[ i ][ j ] = EMPTY; } public boolean boardIsFull( ) { for( int row = 0; row < 3; row++ ) for( int column = 0; column < 3; column++ ) if( board[ row ][ column ] == EMPTY ) return false; return true; } public boolean isAWin( int side ) { int row, column; /* Look for all in a row */ for( row = 0; row < 3; row++ ) { for( column = 0; column < 3; column++ ) if( board[ row ][ column ] != side ) break; if( column >= 3 ) return true; } /* Look for all in a column */ for( column = 0; column < 3; column++ ) { for( row = 0; row < 3; row++ ) if( board[ row ][ column ] != side ) break; if( row >= 3 ) return true; } /* Look on diagonals */ if( board[ 1 ][ 1 ] == side && board[ 2 ][ 2 ] == side && board[ 0 ][ 0 ] == side ) return true; if( board[ 0 ][ 2 ] == side && board[ 1 ][ 1 ] == side && board[ 2 ][ 0 ] == side ) return true; return false; } // Play a move, possibly clearing a square private void place( int row, int column, int piece ) { board[ row ][ column ] = piece; } private boolean squareIsEmpty( int row, int column ) { return board[ row ][ column ] == EMPTY; } } Your first task, if you choose to accept it , is to supplement the TicTacToe class presented earlier with another class called TicTacToeMain whose responsibility is to define a user interface for your application. More specifically, TicTacToeMain should present the user with a two-dimensional three-by-three grid of nine JButton objects. Each of the players involved in the game will be expected to place his/her symbol onto one of the enabled buttons. After a player has made his/her move, the button receiving the symbol gets disabled. Whenever the human player makes a move, make sure to place the letter X in the specified square and the letter O whenever the second player (i.e., computer) moves. It is needless to say that each move must target an empty square. After each move, use the methods of the TicTacToe class to determine whether the game has been won and whether it is a draw. When the game is over, display a dialog box indicating who won in case there was a winner and enabling the human player to play the game again. The main limitation of this first implementation of the TicTacToe game is that your opponent is not following an optimal strategy when making his moves. In view of this, you may have noticed that beating the computer was within your reach, to say the least! It would be nice if we can come up with a more optimal implementation of the game in which the computer would resort to a move selection algorithm to make his moves. This is what we will try to achieve through the next task. III. Backtracking-based implementation The objective of this section is to have the computer select an optimal move during the game and then to have you incorporate his strategy into your previously developed user interface. The challenge is to decide, for any position, what the best move is. The class Best, shown below, will be used to store the optimal move that is returned by the move selection algorithm employed by the computer. public class Best { int row; int column; int val; public Best( int v ) { this( v, 0, 0 ); } public Best( int v, int r, int c ) { val = v; row = r; column = c; } } The general strategy involves the use of a backtracking algorithm. A backtracking algorithm uses recursion to try all the possibilities. The basis for making the optimal decision will be the positionValue method that is included below as part of a modified version of the TicTacToe class. Go over the amended version of TicTacToe carefully before moving on. public class TicTacToe { private int [ ] [ ] board = new int[ 3 ][ 3 ]; public static final int HUMAN = 0; public static final int COMPUTER = 1; public static final int EMPTY = 2; public static final int HUMAN_WIN = 0; public static final int DRAW = 1; public static final int UNCLEAR = 2; public static final int COMPUTER_WIN = 3; public TicTacToe() {// Same implementation as before} public int [] [] getBoard() {// Same implementation as before} // Find optimal move public Best chooseMove(int side) { int opp; // The other side Best reply; // Opponent's best reply int simpleEval; // Result of an immediate evaluation int bestRow = 0; int bestColumn = 0; int value; if( ( simpleEval = positionValue( ) ) != UNCLEAR ) return new Best( simpleEval ); if( side == COMPUTER ) { opp = HUMAN; value = HUMAN_WIN; } else { opp = COMPUTER; value = COMPUTER_WIN; } for( int row = 0; row < 3; row++ ) for( int column = 0; column < 3; column++ ) if( squareIsEmpty(row, column)) { place( row, column, side ); reply = chooseMove( opp ); place( row, column, EMPTY ); // Update if side gets better position if( side == COMPUTER && reply.val > value || side == HUMAN && reply.val < value ) { value = reply.val; bestRow = row; bestColumn = column; } } return new Best( value, bestRow, bestColumn ); } // Compute static value of current position (win, draw, etc.) private int positionValue( ) { return isAWin( COMPUTER ) ? COMPUTER_WIN : isAWin( HUMAN ) ? HUMAN_WIN : boardIsFull( ) ? DRAW : UNCLEAR; } public boolean playMove(int side, int row, int column) { // Implementation provided earlier } public void clearBoard() { // Implementation given earlier } public boolean boardIsFull( ) { // Same implementation as before } public boolean isAWin( int side ) { // Refer to previously presented implementation } private void place( int row, int column, int piece ) { // Same implementation as before } private boolean squareIsEmpty( int row, int column ) { // Same implementation as before }} As indicated earlier, at the heart of the optimal decision made by the computer are the newly-introduced methods called chooseMove and positionValue. The method positionValue returns HUMAN_WIN, DRAW, COMPUTER_WIN, or UNCLEAR, depending on what the board represents. As a matter of fact, the strategy used is the minimax strategy, which is based on the assumption of optimal play by both players. The value of a position is a COMPUTER_WIN if optimal play implies that the computer can force a win. If the computer can force a draw but not a win, the value is DRAW. If the human player on the other hand can force a win, the value is HUMAN_WIN. Given that the strategy utilized by the computer should favor him over the human player, it makes sense to have HUMAN_WIN < DRAW < COMPUTER_WIN. Your second task as you might have expected is to update your previous implementation of the user interface by integrating the minimax strategy described above into the decision-making process of your computer. Your job is not only to add both the Best and the modified TicTacToe class to your project but also to make use of the chooseMove method offered by the latter. Before approaching this task, it is strongly recommended that you read through the following paragraphs that aim at explaining in more details the main idea behind the minimax strategy. I would like though to attract your attention to the fact that failing to understand the discussion provided below would not deter you from completing this second task, so there is no need to worry or panic if you don’t grasp the concept! For the computer, the value of the position is the maximum of all the values corresponding to the positions that can result from making a move. For example, suppose that one move leads to a winning position, two moves lead to a drawing position, and six moves lead to a losing position. Then, the move that leads to the winning position is the move to make. In contrast, for the human player, we use the minimum instead of the maximum. This approach suggests a recursive algorithm to determine the value of a position. If the position is a terminal position (game is over, i.e., we can see right away that Tic-Tac-Toe has been achieved or the board is full without Tic-Tac-Toe), the position’s value is immediate. Otherwise, the chooseMove method recursively tries all moves, computing the value for each resulting position, and chooses the maximum value. In summary, if we have an immediate answer, we can return. This possibility is handled by the base case of the chooseMove method. Otherwise, the chooseMove method looks for the best position value and returns it in a Best object. Although this approach optimally solves Tic-Tac-Toe. It performs a lot of searching. Particularly, to choose the first move on an empty board, it makes 549,946 recursive calls. Therefore, you are encouraged to make the first computer move on an empty board in a random way. Moreover, by using some algorithmic tricks, you can compute the same information with fewer searches. One such technique is known as alpha-beta-pruning, which is an improvement over the minimax algorithm. You will get bonus marks if you go the extra mile and introduce the alpha-beta-pruning strategy to your project for the purpose of achieving the highest level of optimality. Note that Google is a good starting point if you are interested in knowing more about alpha- beta-pruning. What to turn in? This project is due at the beginning of class on the due date. You have to turn in the following material in both hard and soft copies. Criteria Percentage HTML Documentation of your code. In addition, provide explanations and illustrations in one or two pages along with a short write-up of questions and/or problems that you encountered while doing this project. 2 pts (10%) Source code that contains an appropriate amount of comments. Well- organized and correct code receives 18 pts, messy yet working code receives 12 pts, code with bugs receives 6 pts, and incomplete code receives 3 pts. 18 pts (90 %) Total 20pts (100%) Good Luck!