Program 4

Program 4 - February 5

Summary

This is a complex assignment, so a summary is provided. Please read the whole thing anyway. Based on our discussion in class, you are to do the following:

Revise your TicTacToe class to meet new requirements.
Create a TicTacToeHumanPlayer class that asks for and gets moves from a human.
Revise the program you wrote for assignment #3 to work with objects of both classes.
(Extra Credit) Develop a TicTacToeMachinePlayer class which has the same interface as a TicTacToeHumanPlayer but which figures out the move in some way or another.
(Extra Credit) Modify the program for part 3 above so that it uses one TicTacToeHumanPlayer and one TicTacToeMachinePlayer.

The following sections describe the overall architecture of the programs you are to develop as well as what you are to do for each of the five parts.

Architectural Summary

The set of programs you are developing use objects of the following classes:

	TicTacToe Represents a board position. Receives calls from TicTacToePlayer and TicTacToeMachine objects but doesn't know anything about them.
	TicTacToeDisplay This is optional. You may decide to separate the output of the tic-tac-toe board into a different class as we discussed in class. If you do so, there are several ways that the TicTacToe class and the TicTacToe display class might communicate with one another - keep reading.
	TicTacToeHumanPlayer Represents somebody playing tic-tac-toe. Knows how to get a move from the user. Knows about the TicTacToe interface so it can check that a move is legal, and make a move if you decide to architect it that way.
	TicTacToeMachinePlayer Also represents someone playing tic-tac-toe, but this someone is the computer itself. This class should be polymorhic with TicTacToeHumanPlayer - they should share a common interface. It should know all about the TicTacToe class for the same reasons that TicTacToeHumanPlayer does and so it can figure out the best move.
	Your Program(s) should know all about the public interface of these three classes and use them as it needs to - It should not in any way depend on internal stuff that you are not making public.

For more details, keep reading.

Part 1 - TicTacToe Class

That's easy, you already did it. However, let's make some changes so it will be more interesting.

Your class should have no public data members.

There should be accessor functions (Get functions) to get the following information

How many moves have been made?

Is the game over? If so, who won or is it a draw?

Whose move is it?

What is on a given square? You choose whether to use numbers, characters or whatever but be consistent.

You may want some other things, such as, can I legally move to a given square? Is this even a valid index (Hint- that one could be a static function)

There should be operations that do various things

Clear the board (and initialize anything else) so you can play several games using the same object.

Make a move returning true if the move was OK. Note that you cannot assume a move is OK just because you have a public function for checking moves but you can use that function to make the check yourself - possibly again. Hint - the object knows who move it is, you can either just pass in the location or pass in who is moving and have the object check that it is the player whose turn it is.

Put a given piece on a given square, no matter whose move it is. This would be to set up problems. Hint - you can make the preceeding function do this by giving it an extra boolean parameter that causes it to force the move in even if it's not the right player. This parameter would default to false so you would only use it when you wanted this special behavior.

Print the board if you decide to put it here. See TicTacToeDisplay class for the alternative. Whether you do it here or in the separate class, make a display such that it is easy for the user to figure out the number associated with a square and enter that number.

Part 1 (still) - TicTacToeDisplay class

If you decide to be really cool and object-correct about it, create a special class that displays a tic-tac-toe position. Since it's optional for your own creativity, I'll just sketch it out. If anyone does this, I'll try to create a graphic display example that uses it.

You really only need one operation here - to display the board. You can give it a pointer or a reference to the TicTacToe object when you call this operation, or you can give it the pointer in its constructor and have it saved. The former is super easy. The latter is about 1% harder.

Part 2 - TicTacToeHumanPlayer class

This class is another fairly lightweight one.

	Since it needs to know where the board is that it's playing on, give it a pointer to the board object in its constructor. It should save that pointer in a private member of type TicTacToe * for later use.
	If you want to have the player know its name (so it can say "What's your move, Charlie?") you can either give it a function to set the name or have it ask the user and remember it the first time it is called. This would be a nifty but optional feature.
	Mainly, your player object just has to have a function that gets a move from the user. The function should prompt the user and get the move. It should make sure that the input is completely valid - no extra stuff, in range, square not occupied - and not return until it has one. Since this might be annoying if the user really just wants to quit the game, detect a 'Q' to mean "I quit". If the user wants to quit, return false. Otherwise, make the move on the board and return true so the program will keep going.
	Just a note - in case you wondered, it's quite possible to have just one object that does all of this for both players. However, that would not allow the later substitution of a machine player for one of them. Besides, this helps you keep the difference between objects and classes straight, so do it with one object representing one person.

Part 3 - Two person game program

Here is an incomplete version of a main program to get you started. It does not use the TicTacToeDisplay object. If you use the display object, then that's who you tell to display the board.

main ()
{
    TicTacToe board;
    TicTacToeHumanPlayer player1(&board);
    TicTacToeHumanPlayer player2(&board);

    // If you want names, ask for them and tell
    // the player objects who they are

    bool moregames = true;
    int who = 1;    // Or ask user who is first

    while (moregames)
    {
        board.Init();
        do
        {
             if (who == 1)
             {
                if (!player1.MakeMove())
                    break;    // user quit
                who = 2;
             }
             else    // who == 2
             {
                 if (!player2.MakeMove())
                    break;    // this one quit
                 who = 1;
             }

             board.DisplayBoard();

        } until (board.GameOver());

        // code here to see who won and announce it

        // code to set moregames to true or false
    }
}

Part 4 - TicTacToeMachinePlayer class

Take a copy of your .h and .cpp files for the TicTacToeHumanPlayer class and change the names everywhere.

Rewrite the MakeMove function so that it no longer does any user input. Use some strategy to figure out the move that you want to make and make it on the board. The program that calls this won't care if the move was figured out by a program or entered by a user.

You can figure out how to move in a variety of ways. Don't do them all.

Guessing - randomly pick a square and use it if it's good. If not, keep trying till one is good. Alternatively, pick a random number up to the number of empty squares and then play on the nth empty square.

Check to see if you can immediately win, and play on the winning square. That means finding a row, column or diagonal with 2 Xs (or Os) and a blank.

Check to see if you should block the other player from winning. This is the same as the preceding test but the pieces you check for changes (Os instead of Xs, for example).

See if you can move on a square that has a high strategic value - like a corner.

(For the brave) Implement a recursive function that tries out all possible moves, then all possible responses, all possible responses to the responses, until you find a clear win. Hint - The board object will need a way to remove moves as well as make them. Your machine player could give a rating of 1 to moves where only the machine wins, -1 to those where the player always wins, and a 0 to all other moves. Change the sign of the function each time the player changes.

Rate positions as follows: 100 points if you just won. 10 points for every column, row or diagonal where you could win immediately. 1 point for every column row or diagonal where you have one piece and two blanks. -10 and -1 for each place where the other person has the same situations. For each move you could make, rate the resulting position and pick the one with the highest rating.

Probably, you will want to implement this at first using a simple technique and then add others. A pretty good player can be created if you -

Win the game immediately if possible.

Otherwise block the other guy

If none of those work, play on a corner. A refinement is to try to get your mark on two opposite corners, unless the opponent has taken the center.

Finally, just pick a move at random.

Or you think of a method.

Part 5 - One person vs. the machine program

This part is easy. If your machine object has been created correctly, just change the above so that one of the players is the machine object. If you have to change your main program, try to fix it so it works for either kind of object. If you like, you can use conditional complilation to create both kinds of game from the same set of source files!

Some Hints on Internal structure

When all you are doing is making moves and printing the board, the internal structure doesn't matter so much. But if you are trying to figure out how to win, it becomes important. How can you store data so as to easily find out Is there any place I can win? or Is there any place I should block?

Probably the handiest structure is to have an array of 9 squares instead of a three by three array. That allows you to refer to the squares by a single digit. Now create a 3 x 8 array that lists all the winning combinations like 1,2,3 or 1,4,9. This makes it possible to look at all the winning possibilities easily. Another trick is to store 1s and 10s on your board rather than 1s and 2s. If you add up all the numbers in a row, it tells you what was there: 3 means 3 Xs, 30 means 3 Os, 2 means X can win, etc.

Another method works if you like bit manipulation. Store the Xs and Os as two separate bit values - nine bits each. An X bit value of 101000101b means that Xs are in all four corners. You can create masks for all the winning values: 111000000, 000111000, 100010001, and so on. This allows fast testing to see if you won but makes it a bit harder to see where you can play in order to win, so you would use this if you were going to try out the move before really making it.

By the way, labeling the board with single digit values gives an easy way for the user to make entries. Consider a display like this as a possiblility:

1 X   X |2       |3 OOO
   X X |        | O   O
    X   |        | O   O
   X X |        | O   O
X   X |        |   OOO
--------*--------*--------
4       |5       |6
            etc.

Finally...

If you do all of the above, you are doing some serious object-based programming. Even if you only do the required parts, you will be well on the way to having a grasp of what this stuff is all about.

Grading for this assignment will look at both what you have done and how you have done it. To get full credit, you should use code correctly and clearly, comment reasonably, check your input for validity and deal with any error conditions. As usual, if you turn something in that shows you are working on the problem, I'll give you extra time to deal with any problems after the next class.