What was covered in tutorial on Wednesday, 30 October: An ADT for tic-tac-toe
===============================================================================

The problem
-----------

 - Develop an ADT definition for the game tic-tac-toe.
	This should connect very nicely with the assnt.

 - (If you aren't familiar with the game, please see Diane.)

 - Below is a sample solution.  But you may come up with something
	slightly different.  


Solution
--------

A tic-tac-toe board consists of:

 - a 3-by-3 square of entries, each of which is either marked
	X or O, or is not marked.


The operations one can perform on a tic-tac-toe board are:

 - mark spot: marks the given spot with the given mark, which must
	be X or O.  The square must not already be marked.

 - initialize board: returns a board with all spots unmarked.

 - marked: returns true if the given spot is already marked, and
	false otherwise.

 - X won: returns true iff
	there are 3 X's in sequence in
	some row, column, or on some diagonal.

 - O won: returns true iff 
        there are 3 O's in sequence in
        some row, column, or on some diagonal.

 - tie: returns true iff (neither X won nor O won, but every spot is marked).


Things to notice
----------------
 - One could carve up the operations differently.
	Eg, there could be a single somebody-won operation that
	returns who has won (if anyone) or some other value if
	there is no winner yet.

 - Which is a better design is an aesthetic choice;
	either way, it is possible to describe play of the whole game
	in terms of what the ADT provides.

 - Try writing a game algorithm that uses the ADT
	It would control turn-taking etc.
		Often this leads to reconsidering the ADT details, as you 
   	find that you left out an operation that is needed.  Or you may 
	realize that, although you can accomplish your task with the 
	given ADT definition, a modified ADT definition would make your 
	task less awkward.

 - The operations indicate information flow to and from themselves.

 - Some operations say that a spot on the board must be specified,
   	but they don't say _how_ to specify a spot on the board.
	That's an implementation issue.
	This is one of the (few) kinds of things that has to be decided
	when designing a module signature for an ADT.

 - We could implement this ADT in chalk on the blackboard, writing "X"
	for the Xs and "O" for the Os.
	Or we could use a pink square for the Xs and a blue square for
	the Os (if we had coloured chalk).
	Or we could not use "X" or "O" at all -- just colour in a square
	pink to indicate X, and blue to indicate O.
	Or we could implement it in a program.
	Or in our heads.

 - The ADT for assnt 2 is a little more complicated.
	For one thing,
	there are more objects in it (tiles, prizes, player pieces).
	Some students have the instinct to want to break the ADT down,
	and use several modules to implement the bits.
	This is a good instinct!
	We will learn how to do this later (and A3 will use these ideas)