1. Consider the minimax solution tree for a complete game of tic-tac-toe. Answer the
following questions; show your work in deriving the answers.
- How many levels are there in the tree?
- How many nodes at each level? How many nodes in total? (to simplify, you can
assume that game continues play until the board is filled – no early stop when
the game is won).
- How many terminal nodes are there?
- How many terminal nodes have utility value +1 (X wins)? How many terminal
nodes have utility value -1 (O wins)? How many have utility value 0 (draw)?
2. Consider the game Yahtzee (if you are not familiar, you can find the rules here:
[login to view URL] ). Imagine that you are designing an AI
system to play Yahtzee. Formulate the problem using a search tree. What are the
levels in the tree? What decisions need to be made? Write two or three paragraphs
on your approach to solving the problem. Be specific.