This assignment emphasises the application of recursion in solving a problem. In preparation for this assignment, create a folder called Assign_4 for the DrJava project for the assignment.
Tic-tac-toe is a game played on a 3x3 grid. Each player, in turn, places a marker (X for one player and O for the other) in one of the empty spaces on the grid. The first player to have three of their markers in a row (vertical, horizontal or diagonal) wins. If after the grid is filled no one has won, it is a tie.
Write a program that will play Tic-tac-toe against the user. Each move, the program writes the current state of the board to an ASCIIDisplayer such as: see image.
The user, playing O, makes the first play. An ASCIIPrompter may be used to input the row and column (from 0) of the user's play. The program then responds with its play, and so on until either someone loses or all 9 moves have been made and no one has won (a draw). The program then displays the result (i.e. who won or if it is a tie): see image.
The board can be represented as a 3x3 array of characters (i.e. 'X', O, or ). Write a method:
private void printBoard ( ) {
that prints, to an ASCIIDisplayer, the current state of the board as in the figures above. Test your method by using an ASCIIPrompter to enter the position (first for the row and second for the column) of O's play and then Xs play, printing the board after each play, until you have entered 9 moves (i.e. filled the board). Use two methods:
private void playO ( ) {
and
private void playX ( ) {
to abstract the play by the appropriate player (i.e. inputting the coordinates from the prompter and putting the marker on the board). At this point, the program could actually be used to play a game between two users.
It is necessary to determine who wins the game. Write a method:
private boolean win ( char player ) {
that takes the player's marker (i.e. 'X or O) as a parameter and determines if the board contains a winning configuration (i.e. three of the players marker in a row: horizontally, vertically or diagonally) for that player. A player can only win after having played a marker. Rewrite your test to check, after each player has played their marker, if the player has won and if so end the game and display who won. Now the program can really allow two users to play.
Now we get to the fun part, having the computer play as one player (say X). At any point in the game, when it is Xs turn, some of the squares will be filled (i.e. either X or O) and some will be empty. The computer can choose any of the empty squares, but some will be better plays than others. What we need is an evaluation function that, given a board configuration with X's potential play (i.e. where it might play next), computes a value indicating how good the play will be, with a positive value indicating the resulting configuration is good for X and a negative value indicating the configuration is bad for X (i.e. good for O). The computer can try all possible plays (i.e. each square that is empty), compute the evaluation function for each, and determine the play (i.e. row and column) that produces the maximum value.
Rewrite the playX method to choose a play based on the maximum evaluation. It should, in turn, try each square that is blank (i.e. try putting an X there), evaluate the resulting configuration and then remove the marker and try again, until there are no more possible moves. Ultimately it determines the coordinates that gives the maximum evaluation value. That is where the X should be placed and that is the end of X's move.
To test your program, use a simple evaluation function:
private int eval ( int r, int c ) {
where r and c are the row and column of the play being checked, and returns the sum of r and c. This won't choose the best move, but it does allow the playX method to be tested. Try out the program and see that it does allow a game to be played against the computer, except the computer isnt very smart.
Now we add the "intelligence" and here is where recursion comes in. The value of a particular play is dependent on the outcomes that happen after that play has been made. Basically we want to check out each combination of plays (configurations of the board) by O and X from this point until either one player wins or there is a tie. The value of the play we are evaluating can then be determined as the sum of the values of each of the possible next plays. This sounds recursive, the evaluation of this move is based on the evaluations of each of the next moves etc.
When evaluating a move, the move could result in one of the two players winning, it could be a tie (because all 9 moves have been played) or it could be indeterminate (i.e. we have to check the next play). If it is a win for X, the value should be positive, if it is a win for O, the value should be negative, if it is a tie the value is 0, if it is indeterminate, the value is the sum of the values of each of the possible next plays.
One refinement is needed. When an immediate loss is threatened (i.e. O has two in a row with an empty space in the third position), we need to choose a move that prevents this. Similarly, if an immediate win is pending, we want to choose that move. This can be accommodated by assigning a larger positive value to a win that is imminent and decreasing values the more moves necessary before the win is achieved. Similarly we can assign a larger negative value to an imminent loss and decreasing negative values the more moves until the loss would occur. This is achieved with the parameter weight decreasing (divided by 10) on each recursive call to the eval function (below).
Rewrite the eval method from Part C to incorporate this approach as:
private int eval ( int move, int weight, char player ) {
If the current configuration is a win for X, it returns weight. If it is a win for O, it returns -weight, if all nine moves have been played (i.e. move > 9, a tie) it returns 0. Otherwise it tries each possible next move for the indicated player, placing the marker in the square, evaluating of the resulting configuration with one more move played, 1/10 the weight and the other player playing adding this value to the sum, and then removing the marker from the square before going on to the next possible move. The sum computed over all the possible moves is the value returned by the method.
The playX method should now call the evaluation function passing the move number of the move X is trying, a weight of 1000000000 (which can be divided by 10, 9 times and still be non-zero), and player being 'O' (since O is next to play).
The program should now be functional and "intelligent".