Making a computer learn to play TicTacToe.

Background

As we talked about in class, you can write a program to play TicTacToe and which also learns strategy using MiniMax. As the program plays, it adds nodes to a game graph. The outcome of the games become the values (weights) of the end nodes. After each game, a MiniMax process (a double recursion you will write) is run to re-calculate all the weights. As the graph grows, the node weights will prevent the computer from following old losing paths. It will get to a point that you cannot beat it.

We do not implement any methods for playing. Well, that's not exactly true. We do assume that after a certain small number of games the computer would know to block the user if they already have 2 squares in a row and the third winning square has nothing in it. Similarly, we assume it would know to make a winning move if it had 2 squares in a row with the winning third square open when it is its turn to move. You can control when this knowledge appears by adjusting a const in the program called Early
(const int Early=3) near the beginning of the program. You can set Early to a high number and see that the computer will learn to block and notice winning moves, but it will take longer.

Your task(s)

The program is moderately large. To get into it, load the project TicTacToe2.vcproj. The main program is too long to ask you to do the whole thing. I wrote it all for you (in a file tictactoetemplate.cpp) except for the part that updates the graph weights after each run. There is a function in the program: void UpdateTree() that you need to fill out using the double recursion we discussed in class. I've also included a skeleton for 2 other functions you'll need, Min and Max. Without these doing minimax, the program plays but does not learn. So this is your end task. Write the needed functions. (They are quite short if you do it correctly.) But you also need to do a few other things.

It is not easy to test your work and to sort out how to integrate it with all the date structures and variables in the program. So I am posting (in the zip file) 2 other files that you must work with to get your code working. First, there is a node file (called nodesteatin.dat that has a "fake" set of 23 nodes. Your tasks are:

1. On paper, draw the tree/graph for this file (circles as nodes and lines from parents to children). The board positions in the nodes are real. The weights are not what would be in the real game, but they are good for testing. One node has 2 parents. The game starts with Min's move. Turn in your diagram.

2. Testing an algorithm inside a complex program can be hard. Often we write a "stub" program that just runs a new algorithm to test whether it works, but doesn't do the whold main program. You will complete such a test stub program in this part. Complete the test program I've posted in the zip file called updatenodestesttemplate.cpp. It does only 3 things. It reads the node value into the 2 dimensional array Tree[1500][19]. It then runs UpdateTree(), and it writes the updates tree (after minimax) to another file. So write your own UpdateTree and other needed functions here. Test your program and see that you get what you worked out on paper. (Note that in order to make writing and testing of this program easier, the input and output files are different so you do not overwrite the input file after the run. The main big program uses the same file for input and output so that you can run a session of 20 games, for example, and then another session of 30 games and the learning just goes on.)

3. Copy your functions into the main program and run it. Note that the main program has another constant you must adjust. It determines whether you will start and build a brand new nodes file or continue with a previous one. If you set const int GameCount = 0; then it will start over even if you have a nodes file. If you set the value to anything else, it will load the file named nodes.dat and continue with it and write its results to it when you finish.

Things to turn in:

1. Your diagnostic program.

2. Your main program and your final nodes.dat file.

3. On paper, turn in your graph of the 23 nodes including the weights and the board condition for each node.

Optional

Do you wonder what happens when the program is trained? I'm also enclosing two files called nodes400.dat and nodes500.dat. The numbers indicate the number of games played in each case to build that "brain." I can beat nodes400, but I can't beat nodes500. See if you can for fun. To run either, make a copy of it (to not mess up the original) and change its name to nodes.dat and run your main program.