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 day.  I haven't
played in years.' " (Calvin Trillin, The New Yorker, Feb. 8, 1999)


As a goal for some of our F90 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.  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:

   integer, dimension(9) :: board

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 an external subroutine that will print 
to the screen the current state of the board.  We will need to input 
to the subroutine the board variable and a variable to define which 
player is x in the game.  In other words, this subroutine might have
the form:

   subroutine printboard(board, playerx)

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


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

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


   board = (/ 1, 2, 1,   &
              0, 2, 0,   &
              0, 0, 0 /)
   playerx = 1

printboard should produce:

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


   board = (/ 0, 0, 0,   &
              0, 2, 1,   &
              0, 0, 2 /)
   playerx = 2

printboard should produce:

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

Hint: Define a character array cboard(9) within your subroutine,
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:

  function checkmove(board, 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:

   function readmove(board)

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


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

Write the external 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.  Note that this function should NOT be a function of
the playerx variable, that is, it does not matter if the human
is x or oh.  
-------------------------------------------------------------------


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:

   checkwinner(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 external function checkwinner, together with a test program
to check if it is working properly.  Do not print out anything within
the function itself.  As in the case of the readmove function, the 
checkwinner function should NOT involve the playerx variable.  

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

   integer, dimension(8,3) :: win
   win(1,1:3) = (/ 1, 2, 3 /)
   win(2,1:3) = (/ 4, 5, 6 /)
   win(3,1:3) = (/ 7, 8, 9 /)
   win(4,1:3) = (/ 1, 4, 7 /)
   .
   .
   etc.

Then loop over these 8 possibilities and check board(win(i,1:3)) for
i=1 to 8 to see to see if the 3-in-a-row 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:

   function findmove(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.

NOTE:  findmove should NOT change the values in board.  Rather it should
return the desired move to the main program, which will then change the
appropriate value of board.


--------------------------------------------------------------------
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.  VERY IMPORTANT: To facilitate the latter goal, 
please give your findmove function the name:

   function findmove_lastname(board)

where lastname is your last name.  This will make it easier for me
to test your routines all at once.  If your findmove subroutine calls
any other routines, like checkwinner, please modify these names also
(i.e., checkwinner_lastname, etc.) so that everything has a unique
name when I compile all of your codes together.
-------------------------------------------------------------------