Turn in two files: (i) a text file in PDF form, named A3text.pdf, for exercise answers and program test runs, and, (ii) source code for your Tic-Tac-Toe agent, final version (after completing exercises 7 and 8). See exercise 7 for specifying the name of this file.

1. Counting a Few States (10 points). In the game of Tic-Tac-Toe there is one initial state, said to be at Ply 0, and 9 children of the initial state. These 9 children are said to be at Ply 1. How many states are at Ply 2? How many distinct states are at Ply 3? Ply 4? At Ply k? (Justify your answer. You may assume for this exercise that having 3 Xs in a row or 3 Os in a row does not end a game and thus such a state might still have successors.)
2. Counting More (5 points). In a Painted Squares puzzle with 5 pieces, a plus-shaped board (one center square and squares neighboring it on each of its four sides), how many distinct states are there? Assume all 5 pieces are different, and each piece has all of its sides differently painted, i.e., no piece has two sides painted the same way. Also assume that two arrangements of squares that can be obtained from each other by a rotation or flip of the entire board are considered distinct. (Assume that a state that is not a goal state is allowed to have squares placed in ways that violate the matching-sides constraints.)
3. Representing "Equilibrium" (20 points). At the end of the reading on state-space search (see link from the course home page), a class of puzzles called "Equilibrium puzzles" is described in Exercise 7. Give (a) a possible Python representation for the first piece (number 1), shown in Figure 5.11, and (b) a possible state representation for the arrangement of the 6 given squares in a 3 by 2 array suggested by the diagram. (c) Describe, in English rather than Python, what an adequate set of operators would be for solving puzzles in this class of puzzles. (d) Give a detailed description of each operator in your set. What is its precondition? How does it transform the state?
4. Detecting Wins in Tic-Tac-Toe (10 points). Download the starting code for this assignment Try running it to make sure you have it all and have it set up properly. Write a Python function winTester (whose functionality matches that of the given file winTester.cpython-32.pyc).
5. Creating All Children (5 points). Write a function successors_and_moves(state) that returns a pair of lists (as a list). One list consists of all the new states that can be generated from the given state, in Tic-Tac-Toe. The other list gives the corresponding [row,column] locations where the new move is made for each new state. If there are no successors, then the list [[], []] should be returned. Note that each child must be an actual state that includes both a board and the player to move.
6. Move Selection (5 points). Write a function chooseMove(statesAndMoves) that returns a list of length two containing one of the states in the given list and the corresponding [row,col] pair. It must return a win state if there is one. That is, it can just return the first state (and move position) for which winTester does not return 'No win'. If no such entry exists, it should return one of the entries that are there. If the list is empty, it should return None.
7. Your Tic-Tac-Toe Player (15 points). Create a Python file with a filename that consists of your UWNetID followed by TicTacToe.py, with no spaces or dashes. (a) Define a function introduce() that returns a string representing an "introduction", such as "I am Tommy the Tacky Tic-Tac-Toe player, created by John Student. I love Tic-Tac-Toe." Define a function nickname() that returns a short name, such as "Tommy". Define a function makeMove(state, lastUtterance, timeLimit) that makes a move, returning a list of the form [[move, newState], newUtterance], where move is a pair such as [1,2] that tells where the new X or O is being put, and newState is the state that results from making the move. Also, newUtterance is string representing a remark or comment by the simulated player. The timeLimit parameter can be ignored in this assignment, but it is a placeholder for something that will take on importance in the next assignment. (It is an integer representing how many milliseconds will be allowed for making the move.)
8. Using a Static Evaluation Function (10 points). Modify your player to return the "best" move, where by "best" we mean the move whose resulting state optimizes the value of the static evaluation function described on page 200 of the reading. As part of this, implement a function staticEval(state) that returns the value of the static evaluation function on the given state. The player should include the static value of the chosen new state at the end of the utterance. For example, it might report something like, "I have made a move to a very good state, and its static value is -22."
9. Matches (20 points). Modify the file RunTicTacToe.py so that it loads your program and your partner's program as player1 and player2 and runs a game. Run the game. Capture the output and include it in your PDF file A3text.pdf.

If necessary, additional updates and corrections will be posted here and mentioned in class or on GoPost.