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:
Start the lab as follows:
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:
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.
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.
Home | | Syllabus | | Assignments | | Lecture Notes