Update to project 5 requirements
------------------------------------

- do not (in fact, you most likely cannot) build an entire search tree
for the link4 computer AI.

- better to build a new tree, given the current board state, every
time the computer has to make a move (should only examine 5-8 moves
into the future otherwise will take WAY too long).

- there are many ways to optimize your AI, start with a complete tree
builder that examines every possible state for the next 5 moves and
write routine for finding the 'shortest path' to a win state, given
the tree.

- here are some notes on Trees.  This is far from complete and
contains no actual code, just for example.

- read savitch chapter on binary trees to a get a feel for recursive
tree construction but remember the tree for proj5 is a.) not binary
and b.) not a tree that uses a operation to decide which way to
descend.

Trees
--------------------

- tree is a very useful data structure

- binary, ternary, n-ary

- usually created using recursive routine

class node {
	public:
		int data;
		node *rchild, *lchild;
};



addnode(int data, node *&child) {
	if (child == NULL) {
		child = new node(data);
		return(child);
	} else if (data < child->data) {
		return(addnode(data, child->lchild));
	} else {
		return(addnode(data, child->rchild));
	}
}


main() {
node *root;

addnode(10, root);
addnode(15, root);
addnode(4, root);
addnode(8, root);

}

- tree created looks like:

	10
     /      \
    4	     15
      \
       8


- cool thing is, the numbers are now implicitly ordered!
left/center/right recursive routine will give you a sorted list

	- printnode(node)

	- if node->lchild and node->rchild == NULL, print data

	- else
		- printnode(node->lcihld)
		- print data
		- printnode(node->rchild)

	

- Other kinds of trees

- proj5 for instance uses a tree, but not really as a 'data' mechanism
but more as an 'algorthm' mecahnism.

- root node, six children representing all moves from root node

- each of those has six children, each representing player moves

- how would you insert? from main:

{
node *root = NULL;
int **boardstate;

// init boardstate somehow

buildtree(boardstate, root)
}


buildtree(int **data, node *&child)

if (child == NULL)
	child = new node(data)
}

// am i player of computer?
me = one or the other

// for each column
for i = 0 to 5
   
    // make the move as if i chose column i
    me make move on column i

    // set 'i'th child to a new node with new boardstate
    child->children[i] = new node(newmove)

    // did i win? did player win? mark the current tree depth
	
    // build a new tree starting from the child i just created
    buildtree(newmove, child->children[i])


- NOTE: you cannot enumerate all possible board states on 6x6 board
	- 3x3 had around 10k states
	- 4x4 had > 20 million states
	- approx 3 orders of magnitude, 6x6 might be ~50 trillion

- pruning the tree

	- first of all, we're checking for wins every time right?
	  board states don't need to go beyond a win state

	- that helps but still too many

	- is it reasonable to look 20 moves into the future?  what is
	  the probability of landing in that state?  1/number of
  	  states on the way, unlikely

	- can set the depth of the tree to decide how many moves in
	  the future to examine

	- my computer (GHz G4) can do about 6 future moves in a
	  'reasonable' amount of time