CSE 151 Introduction to Artificial Intelligence Programming Assignment 4 TD-Tic-Tac-Toe Due date: Monday, June 7 at 11:59pm Here is a first stab at the homework assignment. More information will appear soon further elaborating the learning method. RULES: - You will be responsible for any updates to the assignment that are posted to the discussion board, so please check it regularly. - The programs must be written in Matlab - Programs must be submitted using the turnin procedure by 11:59pm on the due date - You may work in groups of two or three - Turn in a writeup and all the source files (see what to turn in below) - Make sure to comment your code! This means have comments describing each function as well as comments throughout the code. For this assignment we are going to be implementing the TD(lambda) method like the one presented in class for backgammon, however, we will be doing it for tic-tac-toe. I've gotten you guys started by writing a simple simulator called ttt.m. This function takes as input the current state and a move and returns the next state and whether or not the game is over. Type help ttt for more information about this function. I've also included a function called display_board.m which gives a nice print out of the current state. Part 1: Implement a random tic-tac-toe player Write a function that takes as input a state, and outputs a random move. We'll use this as a baseline for comparison. Part 2: Implement a heuristic tic-tac-toe player Write a function that takes as input a state and outputs a good move. Spend a half an hour playing with this function to see how good a tic-tac-toe player you can write. Again, we'll use this as a baseline for comparison. Part 3: Implement TD-Tic-Tac-Toe Following the same setup as the TD-Gammon paper (posted on the web page) implement a TD-tic-tac-toe program. Your network will have 9 input units corresponding to the 9 locations on the tic-tac-toe board (there are 3^9 possible "states" in this world). Your network will have h hidden units, where h is a parameter and your network will have 2 output units corresponding to win X and win O (a tie will have utility .5). All units in the network can use the sigmoid function 1/(1+e^(-x)), but we recommend using 1.7159*tanh(2/3x). If you use this function, however, part of your homework will be to figure out the correct closed form of its derivative. Hint: tanh'(x) = 1 - (tanh(x))^2 If you use the sigmoid output, you probably should have the two outputs mentioned above for Win X and Win O. This is because the sigmoid goes between 0 and 1, and it is difficult to represent well a negative reward. On the other hand, if you use the scaled tanh function, then one output should suffice, with +1 meaning "win for X", -1 meaning "win for O", and 0 for a tie. You'll need to write at least two functions for this part. The first part will be a function that actually learns the weights of the network. This function will have the following outline: repeat - initialize for new game (previous output is draw, say). - while game not over - select a move for current player - update state based on move - update weights in network using TD lambda (game over? select targets depending on who won. Otherwise, use difference between this output and last output.) This function should run for some fixed number of iterations and then return the weights associated with the network. The weight update function should most likely be a separate routine that implements backprop. To select a move, we need to make sure that there is some balance between selecing the greedy choice and exploration. You can try different exploration functions. A simple one is "epsilon greedy," where, with probability epsilon, we choose an action randomly, and with probability (1-epsilon) we choose the current best action. The second function that you'll need to write is a function that given the weights, returns the next move (you may be able to recycle this from within the inner loop of the learning function). This function will take in the weights of the network and the current state and return a move. The way this works is, you take the current state and generate all possible moves, which lead to a set of new states. If you are using the epsilon greedy exploration strategy, you then flip a weighted coin with probability 1-epsilon of heads. If it comes up tails, return a random element from the set of moves (not just the first one, but a random one with uniform probability - so if there are 4 possible moves, you flip a coin with four sides with equal probability). If it comes up heads, you run each of these states through the network to get a score for that move. When moving for X, and you are choosing the one that looks best for X. When moving for O, you choose the one that looks best for O. (This would be the one with the highest "O" output for the sigmoid network, or the one with the lowest output for the tanh network). This will be the final agent that we use for comparison in part 4. Part 4: Experiments and Write-up Make sure to include the following in your paper: - heuristics used for hand written player - effect of learning rate parameter - effect of epsilon parameter - effect of the number of hidden units - a comparison between the neural net and your method as well as the random method (you may find these comparisons useful for other comparisons as well) Write a short paper describing your experiments, including an short abstract summarizing your results, an introduction very briefly describing the algorithms, an "experiments" section, describing how your experiments, a "discussion" section, where you discuss the results, and finally a short "conclusions" section. The paper should be in good English and should be formatted appropriately for a conference submission. See http://www-2.cs.cmu.edu/Web/Groups/NIPS/NIPS2001/formatting.html for styles files for word and latex. In your writing make sure that it is clear and concise. Make sure that you clearly explain the experiments you did and have clear arguments that are supported by the data obtained from your experiments. What to turn in: - A tar file with... - All of your commented matlab code. - Your paper in .doc, .ps or .pdf form from part 2. - A README file with - A very brief overview of the code - Example runs - A separate paragraph by each team member stating: what that team member contributed to the project. what that team member learned from the project.