CS 206 -- Assignment 7

Game Playing

Questions:

1. Suppose you wanted to explore the entire game tree for tic-tac-toe. In the worst case, how many leaves does it have?
2. In the game tic-tac-toe conventional wisdom players should try to get as many corners as possible. Suppose you are at a position in which X has taken two corners on one side of the board, while O has the center and the side position between the corners controlled by X. It is X's move. Show the expansion of the entire game tree from this point. (Note that the entire tree is not limited by rational choices.)
3. Using the game tree and setup from question , what is the likelihood of X winning, of O winning, of a tie?
4. Is it possible to do an analysis similar to the above 2 questions to figure out the probability of winning a chess game? Explain.
5. In your expansion of the question 2, many positions are symmetric reflections of each other (that is, two boards are are mirror images of each other). Suppose that you built a system that was able to take advantage of this observation. How much work would it save (for question 2)? Is it worth the effort for tic-tac-toe. Explain.

Due Date

Hand in