Laboratory 6

CSCI 132 Data Structures

Laboratory 6
Due at the beginning of class, Wednesday, 3/19

In today's lab you will practice using recursion for looking ahead in a game

The code for this lab is available in the directory:

~csci132/labs/lab6

Start the lab as follows:

Copy the code for lab six into your labs folder by typing:
Change directories into your new lab6 directory by typing:
Type ls to verify that the lab6 directory contains the following files:
- board.h
- board.cc
- eight.cc

The game of eight

Players take turns choosing a number: 1, 2 or 3.
A player may not choose the same number that his/her opponent most recently chose.
A running sum of the numbers chosen is kept.
If a player chooses a number to make the sum equal to 8, that player wins.
If a player chooses a number to make the sum greater than 8, that player loses.

In today's lab you will complete a program that allows the user to play the game of eight against the computer. The computer will use look-ahead to choose its next move. The computer will look ahead until the end of the game or some pre-defined number of moves to decide the best move to make. The computer and user will take turns until the game is finished. The main program and several of the board.cc functions have been written for you. Your job is to fill in the rest of the board.cc programs and to write the look_ahead() function.

First view the board.h file. The public member functions are very similar to those described in the text for the Tic-Tac-Toe program. The main difference is that instead of a function legal_moves() that returns a stack of legal moves, there is a function, is_legal(int move) that returns true if move is a legal move and false if it is not legal. Since each move is a single integer (1, 2, or 3) there is no move class for this program. There are 3 private data members for this class. moves_done keeps track of the number of moves taken (and can be used to determine which player's turn it is). last_move stores the last move made (this is needed to determine whether the next move is legal). total keeps track of the total of all the moves made so far (and is used to determine when the game is over).

Task 1: Complete board.cc
Write code for the following program stubs in board.cc:

int Board::evaluate( ) const
Determine the value of a given outcome of the game. This value should be 9 minus the number of moves if player 1 (the user) wins, and -9 plus the number of moves made if player 2 (the computer) wins.
bool Board::better(int value, int old_value) const
If value is better than old_value for the current player (Note that the move has not been made, so if there has been an even number of moves, the current player is player 1, whereas if there has been an odd number of moves, the current player is player 2), return true.
value is better for player 1 if value is greater than old_value. Whereas, value is better for player 2 if value is less than old_value.
int Board::worst_case( ) const
Return a number that is worse than the worst possible outcome for the current player.
bool Board :: is_legal(int move) const
Return true if the given move is legal (i.e. it is 1, 2 or 3 and is not the same as the previous move). Return false otherwise.

You may want to write a short test program to make sure your functions work correctly before you write the code for the look-ahead function in the second part of this lab.

Task 2: Write the look_ahead() function
Fill in the code for the look_ahead function. This function has 3 parameters, a game board, the depth for the number of moves to look ahead, and the move that is recommended by this function (in the reference parameter, recommended). It also returns the value of the current game configuration. You should base your code on the code for look_ahead in the tic-tac-toe game in the book, which is reproduced here:

int look_ahead(const Board &game, int depth, Move &recommended)
{
  if (game.done( ) || depth == 0)
     return game.evaluate( );
  else {
     Stack moves;  //not needed in game of 8
     game.legal_moves(moves);

     int value, best_value = game.worst_case( );

     //use try_it as for loop counter (1..3) instead of while loop
     while (!moves.empty( ))  {  
        
        //need to check if try_it is legal
        Move try_it, reply; //reply should be an integer
        moves.top(try_it);
        Board new_game = game;
        new_game.play(try_it);
        value = look_ahead(new_game, depth - 1, reply);
        if (game.better(value, best_value)) {
           // try_it is the best move yet found
           best_value = value;
           recommended = try_it;
        } //if this move is better

        moves.pop( );
     } //while there are still moves to try

     return best_value;
  } //else play the game

} //end of look_ahead

Note that in your version you will not be using the Move class, each move is simply an integer. Also, you will not be obtaining a stack of legal moves. Instead, you should use a for loop to loop through each possible number (1, 2 or 3) and test each to see if it is legal. If it is legal, then try the move and get the value for making that move.

When you are done, try out your program. You should find it difficult to beat the computer! Try recompiling the code after setting the initial value of depth to 3 instead of 8. Can you beat the computer now? After this test, set the depth back to 8 before submitting your code.

Sample output
Sample Game 1:

radius% ./eight
Welcome to the game of eight!
In this game the players take turns choosing a number, 1, 2 or 3.
You may not choose the last number chosen. 
A running total of the numbers is kept.
If a player chooses a number to make the total equal to eight, 
that player wins.
If a player chooses a number to make the total greater than eight, 
that player loses.

Please enter a number:  1
You have chosen the number 1.
The total score is 1.

The computer chooses the number 3.
The total score is 4.

Please enter a number:  1
You have chosen the number 1.
The total score is 5.

The computer chooses the number 3.
The total score is 8.

The game is over. The computer wins!

Sample Game 2:

radius% ./eight
Welcome to the game of eight!
In this game the players take turns choosing a number, 1, 2 or 3.
You may not choose the last number chosen. 
A running total of the numbers is kept.
If a player chooses a number to make the total equal to eight, 
that player wins.
If a player chooses a number to make the total greater than eight, 
that player loses.

Please enter a number:  1
You have chosen the number 1.
The total score is 1.

The computer chooses the number 3.
The total score is 4.

Please enter a number:  2
You have chosen the number 2.
The total score is 6.

The computer chooses the number 1.
The total score is 7.

Please enter a number:  1
That move is not legal, choose another number: 2
You have chosen the number 2.
The total score is 9.

The game is over. The computer wins!

Task 3: Draw the game tree
Draw the subtree that arises from the second branch of the user's first move (i.e. the branch for the first player choosing 2). Indicate the values of each node (use the mini-max method to compute them). Remember that the values of the leaves are calculated as 9-moves_done or moves_done-9 depending on who wins. Can you predict which choices the computer will make based on your tree? (If not, there may be something wrong with your tree or with your code!)

What To Turn In.

A printout of the eight.cc file
A printout of the board.cc file
A drawing of the sub-tree from branch 2 of the first move with all the values of each node indicated on the tree
Submit your lab with the submit function:

Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file.

Reminder.
Be sure to save a copy of each file in your labs directory. It is your responsibility to keep the copies of all programs written for this course until your graded assignment is returned.