This assignment is based primarily on the material covered in lecture “Minimax”.
We will work with “Tic-Tac-Toe” as a simple game to help us work through various algorithms.
Part 1: (Multi-agent) State Spaces
1.1) [1pt] Similar to Homework 1, we will first need to create a starting state for you to work from. Starting from the beginning of the game is too much work to do by hand, so we will have you work from a game in progress.
So, to start play a game of tic-tac-toe with yourself. Make sure you don’t win (or lose), forcing the game to a draw will make the rest of the homework assignment much easier (fewer states to consider).
Now, roll the game back to the 3rd-to-last move (last move->next-to-last move->2nd-to-last move->3rd-to-last move). This will be the initial state you use for the rest of the assignment. (Equivalently, choose as your initial state the game board that had 4 blank spaces.)
Note, this means that you (the agent/Max) will be playing “O” and the opponent (Min) will be playing “X”.
1.2) [2pts] Now draw out the search tree starting from the initial state you created in (1.1). Draw out the full search (which should be fairly small since we are starting from near the end of the game).
When considering successor states (i.e., possible game moves), evaluate moves starting with the top-left, then left-to-right and finally top-down. That is, use the following order:
#1#2#3#4#5#6#7#8#9
Draw the states in your tree from left to right when following the above order.
Hint: Make sure to leave some space in your diagram, you will be adding information to it in the following sections. In fact, I recommend reading the rest of the assignment first, so you know what you need to leave space for.
Hint 2: It may be a good idea to clearly mark which level of the tree represents states Max is considering and which Min is considering. Just as on the slides, you would start with Max on the root level of the tree.
Part 2: Minimax
Now we move on to some actual algorithms.
2.1) [2pts] Now, go back to your search tree in Part one and add utility scores to all the terminal states (those with no children, i.e., where the game ended). Rather than simple win lose, we will use a more complicated utility function (to help avoid ties). This utility function is positive for wins, negative for losses, and closer to zero the longer a game took to finish. Specifically:
Number of moves playedNumber of moves leftScore if O (agent, Max) wonScore if X (opponent, Min) wonScore if draw545-5634-4723-3812-2901-10
2.2) [5pts] Now, perform the minimax algorithm to determine “Minimax scores” for each of the states in the tree all the way back to the root (initial state).
Using these scores, which move would Max choose to make?
Part 3: Alpha-Beta Pruning
3.1) [6pts] Now go back and repeat the search from part 2, only this time perform alpha-beta pruning as well. Make sure to show what alpha and beta values are considered (and how they change) for each state in the search tree. Use alpha > beta as the pruning check (do not use greater than or equal to). Also be sure to clearly mark which parts of the tree would be pruned off.
Hint: Remember, at the root of the tree (initial state) alpha, beta start off as: alpha=-infinity and beta=infinity.
Part 4: Extra Credit
4.1) [+1pts]
Go back and redo 3.1, only this time use alpha >= beta as the pruning check. Remember you will have to be careful about what you do with tie in this case. To resolve this use a pruning flag to indicate a branch that higher levels should ignore (e.g., if you decide a branch should be pruned, set it’s minimax value to “X” instead of a number).
Discuss the differences that you see. (Warning, both the new search results/tree and discussion are required to receive credit.)
You may work electronically (word processor, etc) and submit a final pdf of your work.