Assignment 2: Representations for State-Space Search
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2009
The reading for this assignment is Chapters 5 of The Elements of Artificial Intelligence Using Python.
Due Friday, October 16. Catalyst CollectIt at 11:00 AM.

You should turn in one file containing your answers to all the problems. When writing code is asked for, paste in the code you have written, without any of the unmodified starter code.
 

1. Counting a Few States (5 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? (Justify your answer.)
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.
3. Representing "Equilibrium" (20 points). At the end of the reading on state-space search, 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. (d) Give a detailed description of each operator in your set. What is its precondition? How does it transform the state?
4. Representing Another Problem (20 points). Adopt one of the following puzzles and create a state-space representation for it, including (a) state representation, (b) operator descriptions, and (c) goal state predicate description. --Railroad shunting puzzles: Riverside Yard http://precisionlabels.com/shunt/jpage200.html Skowhegan and Athens Railroad http://precisionlabels.com/shunt/jpage320.html --Any jigsaw puzzle --Any crossword puzzle Your state space should have at least 10 states in it and probably very many more. (d) Describe the size of your problem's state space, and give upper and lower bounds, if not an accurate description.
5. Using A Static Evaluation Function (20 points). Using the code from Lab 2 as a starting point, implement a Tic-Tac-Toe player that, at each move, generates the successors of the current state and chooses 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. The player should also emit an utterance that depends directly on the static value of the new state. Implement a new "player" module that is imported into a game just like JohnsTicTacToe.py but instead of automatically making its move it asks the user to input a move (through some kind of text-based dialog that you design, making use of the Python function raw_input(prompt)). Demonstrate two sample games with your program. The first game should involve your automatic player playing against itself. The second should involve your automatic player playing against a human (you). You should make a point to play differently from your program, so we can see how it responds in a different situation.
Updates and Corrections If necessary, updates and corrections will be posted here and mentioned in class or on the mailing list.