TIC-TAC-TOE

"...nearly all the people I take down there have precisely the same
response to the prospect of playing ticktacktoe with a chicken.  After
looking the situation over, they say, 'The chicken gets to go first!'
  'But she's a chicken,' I say.  'You're a human being.  Surely there
should be some advantage in that.'
  Some of my guests, I always report with some embarrassment, don't
stop there.  Some of them say, 'The chicken plays every data.  I haven't
played in years.' " (Calvin Trillin, The New Yorker, Feb. 8, 1999)


As a goal for some of our C programming exercises, we are going to write
a program to play tic-tac-toe.   Although tic-tac-toe is a fully solved
game in the sense that it is well known that a draw always results if
both players play optimally (indeed even chickens have been trained to
play the game), it is of sufficient complexity that writing a working
program may seem a daunting task to the beginning programmer.  As is
usually the case, however, the problem can be made more tractable by 
splitting the task up into smaller pieces.

Let us consider how we are going to approach this problem in C.  Clearly
we will need a way to store the current state of the board (who has
moved where), some kind of flag for who is x and who is oh, some kind
of flag for who goes first, etc.  We will also need a way to display
the board and to input moves from the human player.

There are obviously many, many different ways to write this program.
However, to make sure that our programs will readily be able to play 
each other, it will be good to agree on some standardization of the
different components.

First, let us assume that the spaces on the board are defined by
the numbers 1-9, e.g., 


 1 | 2 | 3 
---+---+--- 
 4 | 5 | 6 
---+---+--- 
 7 | 8 | 9


Thus, when the program asks the human for a move, the human will
enter a number from 1 to 9.  For convenience, let's use the same
convention for storing the moves within the program.  Define
an array called board that will store the moves that have been
made:

int board[10];

Because C arrays are zero-offset, note that we must define board
to have 10 elements (we won't use board[0]).

Now, let us specify that board will have the value 0 if the space
is still open, 1 if the human has moved in the space, and 2
if the computer has moved in the space.  Obviously there are
other choices that we could have made for this (1 for x, 2 for oh; 
1 for 1st player, 2 for 2nd player), but this makes the most sense
to me because the human vs. computer difference is fundamental
to the program.  x vs. oh is simply a naming convention; 1st vs.
2nd will simply determine where the program starts.

Let us begin by writing a function that will print to the screen 
the current state of the board.  We will need to input to the
function the board variable and a variable to define which player
is x in the game.  In other words, this function might have
the form:

int printboard(int board[], int playerx) {

We assume that playerx = 1 if the human is x, playerx = 2 if
the computer is x.


-----------------------------------------------------------------
ASSIGNMENT TTT1

Write the function printboard, together with a test main program 
to check if it is working properly.  Here are some examples:


int board[10] = {0, 1, 2, 1, 
                    0, 2, 0, 
                    0, 0, 0};
int playerx = 1;

printboard should produce:

 x | o | x 
---+---+--- 
   | o |   
---+---+--- 
   |   |   


int board[10] = {0, 0, 0, 0, 
                    0, 2, 1, 
                    0, 0, 2};
int playerx = 2;

printboard should produce:

   |   |   
---+---+--- 
   | x | o 
---+---+--- 
   |   | x 


Please name your printboard function printboard_lastname
where lastname is your last name.  This will make it easier
for me to write a master program to check the operation of
all of your codes at once.

Hint:  Define a character array cboard[10] within your function,
the elements of which you set to ' ', 'x', or 'o', depending
upon the contents of board and playerx.  Then write a series
of print statments to do the actual output.
--------------------------------------------------------------------


Next, our program will need some way to determine if a proposed
move is a valid move, i.e., if there is currently a blank space
in the move location.  To implement this, let us write a function
of the form:

int checkmove(int board[], int move) {

which will return 1 if the move is valid, 0 otherwise.  Note that
board is the array defined above and move is the proposed move.


------------------------------------------------------------------
ASSIGNMENT TTT2

Write the function checkmove, together with a test main program
to check if it is working properly.  To make the function robust,
return zero if move is outside of the range 1 to 9.  Do not print
out anything within this function to warn of an invalid move.  We
may want to use this function for multiple purposes in the program
and we don't necssarily want it to print anything out.  If a
warning is necessary, the calling program can print out the message.
-------------------------------------------------------------------


Next, we need a function that will prompt the human for a move.
It should check to see if the move is valid and prompt the
human again in the cases of invalid moves.  Let's call this
function readmove:

int readmove(int board[]) {

which will return a valid move as entered by the keyboard.


------------------------------------------------------------------
ASSIGNMENT TTT3

Write the function readmove, together with a test main program
to check if it is working properly.  The function should ask
the user to enter a move, then use the checkmove function to
check whether it is valid.  If it is valid, return the move
to the main program.  If it is invalid, then alert the user
and prompt again for a valid move.  Repeat until a valid move
is entered.
-------------------------------------------------------------------


Next, we need a function to determine if there is a current winner
(3 in a row) or if the game is drawn (all spaces filled, no winner).
This function will have the form:

int checkwinner(int board[]) {

and will return 1 if player 1 has won, 2 if player 2 has won, 3 if
the game is drawn, and 0 otherwise.


--------------------------------------------------------------------
ASSIGNMENT TTT4

Write the function checkwinner, together with a test main program
to check if it is working properly.  

Hint:  Define an 2-D integer array that stores the locations of the 
possible ways to win, e.g.,

int win[8][3] = {{1,2,3}, {4,5,6}, {7,8,9}, {1,4,7}, {2,5,8}, etc.};

Then loop over these 8 possibilities and check to see if the 3 board
values are all ones or all twos.  If there is no winner, then check
to see if all board locations are full (the draw criteria).
--------------------------------------------------------------------


The most challenging part of your TTT program will be determining
the best move for the computer to make.  We will implement this
as a function:

int findmove(int board[]) {

which will return the "best" move for the computer (player 2) to
make.  Testing this function will be easiest once the complete
program is finished.  To complete the program, however, one needs
a working version of findmove.  To get around this problem, let's
write findmove in two stages.  First, let's write a very stupid version
that will simply return a valid move.  Then, after we have the complete
program working, we can make improvements to findmove.


--------------------------------------------------------------------
ASSIGNMENT TTT5

Write a working version of findmove, together with a test main program
to check if it is working properly.  Hint:  Just loop through the moves
1 to 9 until you find an empty space (board[i] = 0).  For a slightly
more interesting "stupid" program, pick a random valid move.
---------------------------------------------------------------------


Now we are ready to put these pieces together into a main program
that will actually play the game.  This program should ask the
user if he/she wants to go first and if he/she wants x or oh (the
latter is the playerx flag in the printboard function).  The board
array should be initialized to zero.  For each move, the program
will have to determine whose move it is (a function of the move
number and who went first) and then either prompt the user or use
the findmove function to pick a move.  Following the move, the
program should check for a win or draw.  If there is a win or draw,
a suitable message should be printed and the program stopped.  If
there is not a winner/draw, then the program should continue with
the next move.


--------------------------------------------------------------------
ASSIGNMENT TTT6

Construct a working version of the complete tic-tac-toe program.
---------------------------------------------------------------------


Finally, we will want to improve on our initial findmove function
to make the program smarter.  An obvious strategy for this is
to first check to see if any winning moves are possible.  If not,
then next check to see if there is a winning move for the human
that should be blocked.  Beyond this, you're on your own!


--------------------------------------------------------------------
ASSIGNMENT TTT7

Refine your program to incorporate a smart findmove function.  Send
me the complete program, including all functions in an e-mail.  I
will check the operation of your program and also attempt to have the
programs play each other.  To facilitate the latter goal, please
give your findmove function the name:

int findmove_lastname(int board[])

where lastname is your last name.  This will make it easier for me
to test your routines all at once.
-------------------------------------------------------------------