copyright RIT 2003
$Id: writeup.xml,v 1.9 2006/09/14 14:41:23 cs4 Exp $
Part 1 is due on 28 September 2003.
Part 2 is due on 12 October 2003.
Part 3 is due on 26 October 2003.
Part 4 is due on 9 November 2003.
Part 5 is due on 10 November 2003.
You will improve your design skills while learning many new design techniques and styles.
You will learn what it takes to develop a larger program in the C++ language.
You will learn how to work in a team.
Some of the techniques you learned in more standard object-oriented languages may not apply here. In addition, C++ has some unique features that you may be able to exploit. This project should help expose you to these issues and show you how to make choices you can live with.
Below you will read about some specific two-person games you are to analyze. However, we will also show you how these games fit into a more general analysis pattern. If you know this, you can design your program to this more abstract model, thereby allowing you to plug in new games with less effort.
Here are some simple games that all have common characteristics. If you are not familiar with any of them, try playing the game a few times. The strategy discussions will then be clearer.
In front of both players is a pile of pennies. When it is a player's turn to play, the player must take 1, 2, or 3 pennies from the pile. At least one coin must be taken. The loser is the player who takes the last coin. A simple strategy is to try to leave your opponent 1, 5, 9, 13... coins or a multiple of four plus one. What ever your opponent does you can reduce the pile to the next number in this sequence until you leave one coin which your opponent must pick up. Think about how you would discover this strategy if you didn't know it.
Nim is played with several pebbles or stones. When it is a player's turn to play, the player may take as many stones as she wants from a single pile but she must take at least one. The winner is the player who takes the last pebble. A typical game might start with three piles of 3, 4, and 5 pebbles. What is the best strategy for each player?
Our version of Othello is played on an initially empty 3 x 4 checker board. There are two players, called "X" and "O". A player, when it is her turn to play, plases her mark (X or O) in any empty square and then checks all eight lines (horizontally, vertically, and diagonally) radiating from this square. if there is an unbroken sequence of the opponent's mark followed immediately by the player's mark then all of the opponent's marks are changed to the player's mark. It is important to notice that there can be no empty spaces in the run of opponent's marks and that a player's mark immediately follow this run of opponent marks. Only opponent marks up to the first player mark are changed. The game ends when there are no empty spaces to play in. The final score is the number of player marks minus the number of opponent marks.
In the above diagram player "O" can play in the lower right hand corner and change the two X's in the bottom row and the X along the right hand side to O's. If O plays in the rightmost empty space in the top line then only the leftmost X in the middle row can be changed to an O. The best strategy in this game may be to make moves that do not change many squares but set up a situation where future moves can be advantageous. If O plays in the upper left corner then no X's can be changed.
The best strategy in this game may be to make moves that do not change many squares but set up a situation where future moves can be advantageous.
The specifics of these problems will be given in the activity sections.
What do all of these games have in common? All of these games are "two player games with perfect information". They have the following properties (adapted from "Winning Ways" by Berlekamp, Conway, and Guy):
There are just two players, often called Left and Right.
There are several, usually finitely many, positions, and often a particular starting position.
There are clearly defined rules that specify the moves that either player can make from a given position.
The two players Left and Right move alternately.
There are specific rules that determine when the game ends.
The rules are such that play will always come to an end. This is called the ending condition. So there can be no games which can last forever.
Both players know everything that is going on, i.e., there is complete information.
There are no chance moves such as rolling dice or shuffling cards.
The moving/winning rules for Left and Right may not be the same.
At the end of the game there is a definite score. We will assume that the first player wants the largest possible score while the second player wants the smallest score. ( You might want to think of zero as a tie score and that the second player wants to maximize the negative of the final score. )
Let's see how the tic tac toe game maps to this abstraction.
There are just two players, often called X and O.
The allowed positions contain an X or O or blank in each square.
A player, at her turn, may place her mark in any vacant square.
Left and Right move alternately, in the game as a whole.
If a position has three tokens of the same kind in any row, column or diagonal, then the player with that token has won the game and play ceases. If all positions are filled with no player having three-in-a-row then the game is a tie and play ceases.
The rules are such that play will always come to an end because a square is marked on each turn and there are only 9 squares. A game may end sooner if one of the players wins by getting three-in-a-row.
Both players know everything that is going on, the state of the entire game is contained in the diagram that both players can see.
There are no chance moves such as rolling dice or shuffling cards.
For tic tac toe the rules are similar for each player except that each player has her own mark.
At the end of the game there is a definite score. A win counts +1, a loss -1, and a tie 0.
Suppose you were a player in one of these games. How would you decide your best move? If you knew the consequences of each move (assuming best play by both players after this move) then it would be easy. You would try all possible moves and make the move that has the best outcome. If we had a program that could calculate the final score starting from any position (assuming best play) then we could use it to determine the best move. ( Note that a position also implies which player is to move.) We would try all possible moves from the current position and chose the move that leads to a position with the largest score. We could also calculate the final score resulting from the current position to be the same as the final score of the position resulting by moving our best move. (If there are several moves that result in the same final score we could chose the first one or a random "best" move for more variety.)
It is easy to calculate the score at the end of a game - just use the rules of the game. It is also easy to determine if the game is over using the rules of the game. Otherwise, the game is not over and we must evaluate each possible move in turn. By calling this routine recursively we can determine all possible games that could be played (in a depth-first search). The only tricky part of this is to realize that the two players have different goals: one player wants to maximize the score while the other player wants to minimize the score of the first player.
We could write two functions - one for each player that calculates the value of the game from that player's viewpoint. Or we could write a single function and change the sign of the final score and the identity of the two players after each move. ( In checkers, this would be like reversing the colors of all the men and turning the board around on each move. Some games (such as Take Away or Nim) only change the sign of the score while others (such as Tic Tac Toe or othello) require changing the position and/or identity of the pieces.)
If we write out a complete game tree and evaluate the position from the viewpoint of the player who is to move we note that for each level the value of the game at that level is the maximum of the negative of the child nodes of that level. (The minus sign is because we reverse our viewpoint on each move. If we don't reverse our viewpoint then alternate levels of the game tree would have to minimize and maximize.)
Here is a game tree for the game Take Away with five pennies in the pile.
Note that these are game positions for us to evaluate with us to move. If we are left with 0 then our opponent must have taken the last stone and we have won. In all other cases we can move. Our objective is to move to a losing position for our opponent so, for example, if we are presented with 4 stones we should leave one since this is the only alternative that loses for our opponent. In general, if we can move to a losing position for our opponent then we move there and claim that the current position is a win. Otherwise, our opponent can win the game no matter what we do so we make a random move. For games with more possible scores than "win" or "lose" we would move to the position with the minimum score (from the viewpoint of our opponent).
Another way to eveluate game positions (if you find reversing viewpoints confusing) is to use two evaluation functions, one for us and one for our opponent. Then our evaluation function attempts to maximize the score and our opponent's function attempts to minimize the score. These two functions will call each other to evaluate the game tree. You might arrange for each of these two functions to call common functions for the common part of the analysis. You may use either a single evaluation function or an evaluation function for each player in your code.
Here is pseudocode for the board evaluation strategy:
If game position is a final position then
Return score of position
Generate all legal moves from this position
For each legal move
Calculate the resulting board position
Reverse the board (if necessary) to the other player's viewpoint
Call Evaluate Position on this resulting position
If this is the smallest value seen so far (our best is opponent's worst)
remember the move as the best move
remember the value as the best value
end-if
end-for
return best move and minus best value
This algorithm must terminate since there are only a finite number of possible moves for any game position and a game has only a finite number of moves. It also returns the best move against a perfect opponent because no other move can guarantee a better outcome. (Do you see why?)
Did you recognize a pattern in the way the algorithm organizes and traverses its search space? It's a depth-first search of all of the possible games. Some games, like chess, could theoretically be solved with such a program but the number of positions that would have to be searched makes the running time of this simple algorithm to be longer than the age of the universe. There are ways we could speed up this algorithm:
One way to speed up this algorithm:
The algorithm as given may analyze the same game position more than once if there is more than one way to arrive at the position. If we remember our analysis for each position then we can merely return the remembered analysis the second time. (You may have seen this same technique used for computing Fibonacci numbers.) This technique is called memoization because we write a memo whenever we calculate a result. You will be required to use memoization for your submission for parts 3 and 4.
Once you have a function that calculates the best move from a given position it is easy to add code to allow your program to play against a human opponent. You need to display the current position, input the human's move, make the human move to get the new position, calculate the best move in response given this position, make this move, and repeat. You will also need tests to determine if the game is over and code to print out the final score. You might want to be able to play a series of games and keep a running score.
One way to design this code is to write out an activity diagram or state chart containing the various possibilities. (Illegal move, game scoring, what to print when etc.)
The activities in this project will have you design a framework that is easily adapted to all the games of the classification described above. You will then implement and test all three of the games using that design.
The general process you should follow goes something like this:
Develop the initial framework design in the abstract.
Submit the design to your instructor.
Write the code for the abstract framework.
For each problem for which you must implement a solution,
Code the specific problem classes.
If the previous step forced a modification of your design,
Modify the code for the design as needed to make it work
Modify the code for the previous problems as needed
Submit the code for your latest design and all the problems solved so far
Because this is the only project you are doing in this course, and it is a team project, there is a possibility that we will not be able to accurately assess your programming abilities if your teammate does most of the programming. Therefore, each team member must be responsible for roughly half the code written in each activity, 2, 3, and 4. In the header comments, the name of the principal author should show up first, as always, in each code file. Both team members must be able to explain all code orally if asked by his/her instructor.
Part 1 is due on 28 September 2003.
In this first activity, you are mainly concerned with the design of the framework. The term framework means a set of classes that enable implementation of solutions to certain problems. However, the framework by itself is not a complete program. You will work with abstract notions such as position, move, and find-best-move. The find-best-move should be able to solve any game that conforms to an interface that you develop in your design. Think carefully about this interface, as you will later be writing classes that conform to it to calculate moves in the three games. You should also think about the user interface for playing a game. You might want to overload the input operator ">>" to read in a move from the terminal.
Your design document is a Rational Rose UML model that contains at least use case, sequence, and class diagrams. For this particular project you will have at least two use cases: a use case that determines the best move and a use case that plays a game with a human opponent.
The more interesting work is in the class and sequence diagrams. The classes you show for this activity are only the ones of the framework, not of any particular problem. For the sequence diagrams, show some interesting scenarios involving part of the above algorithm. Although this would be illegal in real code, include objects that are instantiated from your abstractions. Note that there must be a method in some class that runs an algorithm like the one described in the Background section. If you are planning to use a templated class you might draw the diagram as though the templated class were instantiated with a specific instance.
When you design the generic configuration class, make sure you include some kind of a display function that will, when implemented, print some textual representation of the configuration to standard output. This will be of great help while you are debugging your code. The problem solver algorithm can be enhanced by a call to the display function inside the loop. Of course, the implementations of your display function will only show up in the specific problems' configuration classes. This could be accomplished conveniently by overloading the output operator "<<".
Call your model file game.mdl.
It should contain all the diagrams you have developed.
try cs4-grd project1-1 game.mdl
Part 2 is due on 12 October 2003.
The purpose of this activity is to perform the first validation of your design. You will write the code for your design. Then you will add code for the Take Away game, put the two together, and see how they work. It is important to note that you are expected to be using a framework that is equally applicable to the other problems. (While you could conceivably use the simple "leave a multiple of four plus one" approach we discussed earlier, this isn't what we will be looking for: instead, you should be using the generic algorithm we've defined, which should generate the same results.) There are easier solutions for this game than the one we are having you build but we want you to solve it using the general framework you designed in part 1.
Now your design must get more detailed. This is probably the right time to think about exactly how you will realize your design within the constraints of the C++ language. Although you are free to make your own decisions, some suggested approaches are shown at choices.html that satisfy the requirement of a framework that adapts well to different "two-person games with perfect information".
Getting back to the Take Away game, it requires one integer as input:
the number of pennies in the pile
If you wish to play the game instead of calculating a single move then the first input argument should be the word "play" followed by the argument giving the number of pennies in the pile.
The program is to be called
takeaway, which means the
main function should be defined in a file
named takeaway.cpp. As submitted,
the program must print out, on standard output, the
best move or the number of pennies to take or, if the
play option is used, alternately allow the user to
play followed by the computer playing.
You must submit a file called readme
which is a text file containing instructions for
running your program. It should contain the format of
any input required by the program. For this submission
the instructions are simple but you should get used to
writing user documentation for the code that you write.
If you have modified the design, you must submit an
explanation of changes as part of your
readme file.
If you want to submit a custom gmake
file, rename it to be called
custom.mk and submit it along
with the other files.
If you submit your own custom.mk
gmake file, invoking
gmake without any arguments must produce
an executable called takeaway that
calculates the best move as described here described
here.
You must submit all the .cpp
and .h files required to
build the takeaway program. It
must be possible to compile the
takeaway program by executing
gmakemake and then simply
gmake or you must submit a
custom gmake file called
custom.mk. Your design model must
also be resubmitted, augmented with the classes
for the takeaway problem. If your underlying
design changed, include the changes and reasons in
the readme file mentioned
above.
try cs4-grd project1-2 readme takeaway.cpp other-needed-code-files game.mdl [ custom.mk ]
Part 3 is due on 26 October 2003.
The purpose of this activity is to implement the solution for a game that requires a slightly more involved position analysis. Write the code for the Nim game, plug it into your framework, and see how it works.
A position in Nim consists of several piles of stones. The program will read the number of stones in each pile from the command line arguments. There will be as many arguments as there are piles of stones and each argument will specify how many stones are in the corresponding pile. Any bad command line arguments should result in an error message on standard error and the program should terminate. For convenience, the first pile is pile number 0. Alternatively, the first argument can be the word "play" followed by arguments specifying the stone piles. In this case, the program will play the Nim game with a human opponent.
The program is to be called nim,
which means the main function should be
defined in a file named nim.cpp. As
submitted, the program must print out the best move by
listing the pile number and the number of stones to
remove from it.
You must submit a file called readme
which is a text file containing instructions for
running your program. It should contain the format of
any input required by the program.
If you have modified the design, you must include an
explanation of the changes in the
readme file.
You must use memoization for this submission.
This game, although more complicated than takeaway, is still fairly simple. The position basically consists of a vector of ints. Be careful not to change any shared data structures - always copy a vector or structure before modifying it if there exists any other use of the vector or data structure.
You must submit all the .cpp
and .h files required to
build the takeaway program
and the
nim program. It must be
possible to compile both programs by executing
gmakemake and then simply
gmake. Or submit
custom.mk as before. Your
design model must also be resubmitted, augmented
with the classes for the nim program. If your
underlying design changed, include the changes and
the reasons for them in the
readme file. (
If you
had to change your design, then you probably need
to update the takeaway program so that it
continues to work.)
If you submit your own
custom.mk
gmake file, invoking
gmake without any arguments must
produce two executables: one called
takeaway, and one called
nim that plays the nim game.
try cs4-grd project1-3 readme takeaway.cpp nim.cpp other-needed-code-files game.mdl [ custom.mk ]
Part 4 is due on 9 November 2003.
The purpose of this activity is to play a game that is more complicated. We hope that you will be surprised at how easily your framework can play this game. Write the code for the Othello game, plug it into your framework, and see how it works. (You should assume that the user will be playing as "X", both for the "best move" functionality, and for interactive play.)
Your program will need to be told the initial position to analyze. There will be command line arguments for each square of the Othello diagram with 1 for "X", -1 for "O", and 0 for an empty space. Trailing 0's may be omitted.
To play the game against the computer the first command line argument should be "play" followed by the arguments as above.
You should detect any errors in the command line arguments and terminate with an appropriate error message.
The program is to be called
othello, which means the
main function should be defined in a file
named othello.cpp.
You must submit a file called readme
which is a text file containing instructions for
running your program. It should contain the format of
any input required by the program.
If you have modified the design, you must submit an
explanation of changes in the
readme file.
Choose a simple data structure to represent the board.
You must submit all the .cpp
and .h files required to
build the othello
and
takeaway and
nim programs. It must be
possible to compile all three programs by
executing gmakemake and then
simply gmake. Or submit
custom.mk as before. Your
design model must also be resubmitted, augmented
with the classes for the Othello game. If your
underlying design changed, include the details in
the readme file.
(
If you had to change your design, then you
probably need to update the other two programs
so that they continue to work.
)
If you submit your own
custom.mk
gmake file, invoking
gmake without any arguments must
produce three executables: one called
takeaway, one called
nim, and an executable called
othello that plays the othello
game described here.
try cs4-grd project1-4 readme takeaway.cpp nim.cpp othello.cpp other-needed-code-files game.mdl [ custom.mk ]
Part 5 is due on 10 November 2003.
The last activity, due one day after the previous one, is the team evaluation.
Only a textual evaluation form is submitted. It is available as team-evaluation in the web directory for this project.
Do not submit this from your team account.
From your own account, submit your evaluation as follows:
try cs4-grd project1-5 team-evaluation
Grade Breakdown:
$Log: writeup.xml,v $ Revision 1.9 2006/09/14 14:41:23 cs4 Fixed a spelling mistake. Revision 1.8 2003/11/22 14:24:52 cs4 Added text to Part 4 requirements to indicate that the user will play as "X" in both modes. Revision 1.7 2003/11/22 14:20:01 cs4 Added text to Part 2 description, in an attempt to reinforce the goal for this level. Revision 1.6 2003/07/03 15:50:49 cs4 Almost ready for review (swm) Revision 1.5 2003/06/25 19:31:19 swm fix paragraph title problem Revision 1.4 2003/06/25 19:29:36 swm fixed xml syntax error Revision 1.3 2003/06/25 19:02:53 swm fixed xml syntax error Revision 1.2 2003/06/25 18:55:14 swm replaced quote characters Revision 1.1 2003/06/25 18:37:59 swm Initial revision