1) Defend this position
2) Look ahead
3) General Probabilities
4) Know your opponent

What are our Goals?
	Win game vs Win war?
Does randomness add anything significant?-----Tic Tac Toe-----

Objective: Make the ultimate Tic Tac Toe player

The problem is that as dicribed in the rules of Tic Tac Toe

The Rules of Tic Tac Toe

A single turn in Tic Tac Toe is described as both players placing one
mark in a cell on a 3x3 cell board where one player may only place an
'X' and another player may only place an 'O'. The player with the mark
'X' shall go first, and the player using the 'O' mark shall go second
in placing  their mark.  No cell may be marked twice during the game,
nor may a mark be  removed from a cell once it has been placed.  No
two pieces may occupy the same cell during the game.  The game starts
with the board devoid of any pieces. A win is defined as 3 of the same
piece occupying a 3 cells on the same line paralel to one of the sides
of the board, or on a 45 degree angle with respect to one of the sides
of the board.

Sub Problems of Tic Tac Toe

The game of Tic Tac Toe can be boiled down to board analysis.

Board anlysis can take many forms, Minimax, Rules or a hybrid of the two.

Rules are based on takeing the state of the current board and reacting
to it.  This makes any algorithm coded in this manner unsutable for
conversion to Minimax as minimax seeks to develope possible states and
assign them values where the rules follow states putting priority on
known situations, and not looking ahead in the game.  Experience can
provide a sort of natural look ahead, but that is getting into the
generalization of the game.  The rules where consturcted as questions
to be asked of the board and ar as follows:

1) Will one side win on the next turn? Place a mark there (this will
either win the game for the player or block and immenent win for the
opposition).  These rules were originally in the form of will I win or
will I lose.  Generalizing the two more specific rules allowes for
faster computation and a smaller representation of the solution of the
problem.

2.1) On the first move if making the first mark, take a corner.  The
notable properties of this position are that it is the endpoint of 3
lines.  This gives 3 options for winning.

2.2) On the first move, if making the second mark, take the center.
The properties that are notable about this position are that it
obstructs 4 possible wins for the opposition.  There is also the
possibility for the comuter to force the oposition into an
unproductive position.  This assumes that the oposition is not going
to attempt to win the game in the next few moves with a direct attack.

Already there is a small opening book developeing for this game

After these rules more specific ones are implemented to account for
more specific instances of the board.  [insert rules used in java code]

An alternate view of the problem yeilds a better means of handling the
data with respect to a computer, and lends itself to heuristic
computation more redily.  Start by labling the Tic Tac Toe board with
numbers as shown in fig 1.

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

Now arrange all the winning solutions into an 8 by 3 array where each
triple represents a winning path represented by the set of the numbers
representing the cells in that path. See fig 2.

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

Looking at these sets of triples, patterns begin to emerge.  This has
not been explored but may have some benefits embedded in it.  It is
certainly an insight worth noting, if nothing else.  If these cells
were to be arranged in a linear array, winning patters could be found
by staring at x, such that 1<=x<=3 and incrementing x by 1 or
3. Diagonal wins can be found by starting with x=1 and incrementing by
4 or x=3 and incrementing by 2.

To form a heruistic function using this new format of data we will
regard each array of 3 as a subgame.  Each sub game has a value which
can be calculated very simply.  The values are then summed together to
give the final value of the entire board.  The rules are as follows
with the first rule satisfied being the one adhered to:

NOTE: In this scheme, positive is good

1) If there are 3 of a kind the mini game value will + or minus 32 (or
infinite).  If the mark is the opositions, -32, if not then +32.

2) If there are 2 marks of any kind and one of another kind present in
a minigame, then the game value is 0.

3) For each of my marks in a minigame, add one to the game's value.
For each of the oponent's marks in a minigame, subtract one from the
game's value.

Once the value of all minigames have been calculated, sum the value of
all 8 minigames and use that in Minimax.  This method has not been
tested yet.

There may be the instance when 2 boards evaluate to the same value.
In this instance a learning database may be a solution or hard coding
some deciding code to pick between each option.  There is also the
option of using radomness to make that decision.