HW3: Games
out 2/28, due 3/13
Note: the game trees for problems 1 and 2 are in your repository in the file game_trees.ppt. You can edit it using either of two methods:
- Edit the file in powerpoint and save the file as both powerpoint and also as pdf.
- Using Google Docs slides, import the powerpoint file game_trees.ppt, edit it, and then download it as both powerpoint and pdf.
(1) Minimax (15 points)
In the game trees in this problem, the value of the static evaluator functions is show for the leaves. Squares are maximizing nodes and circles minimizing nodes. For this game tree, use the minimax algorithm to compute a value for each non-leaf node. Squares represent max nodes and circles represent min nodes. Indicate which move the maximizing player should make.
(2) Minimax with Alpha-Beta (15 points)
Simulate the alpha-beta algorithm on this game tree, crossing out the nodes that are pruned. For each non-leaf node that is not pruned, show the exact value (e.g., =3) or the last constraint (e.g., <= 2, >=8) that the alpha-beta algorithm determines.
(3) Nim (45 points)
The AIMA book's Python code games4e.py has a generic framework for multi-player deterministic games along with examples for Tic-Tac-Toe and Connect Four. Use this framework to implement a game and players for the simple game Nim. Nim has been used as an exercise for computer programs for a long time -- see this short article on an electronic Nim playing device from the New Yorker from 1952.
Nim is a simple two-person, turn-taking fully-observable game in which the two players take turns removing objects such as coins or sticks, from a set of distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The last player to take an object loses, i.e., the player who is left without a move wins. One thing that makes Nim simple is that it is a finite game. At each turn, one of more objects are removed from a heap, so eventually no more objects are left. The last player to remove an object is the winner.
Nim has been completely solved for any number of initial heaps and objects, e.g., in games with heaps of three, four, and five, the first player will win with optimal play. You can
Your representation should be able to support games with any non-zero number of heaps with an arbitrary number of initial objects. For example, you should be able to handle a game of Nim with three heaps that initially contain seven, six and five objects. You should review the code in nim.py in your repository and look for calls to pass to see where you have to add nim-specific code. We recommend you look at the code and comments in games4e.py in your repo, especially the several games it implements.
Complete the file nim.py and test it using play_nim.py. Commit your modified version of nim.py. You should examine carefully the comments in nim.py and the testing programs playnim.py, testnim.py, and well as the code in the aima-python file games4e.py, which is in your repository. You can also review this slide that gives an overview of the assignment
The playnim.py program can be called to play one game of nim by specifying the initial heap configuration, what algorithms should be used for the two players, and whether or not a heuristic could be used to estimate the value of a non-terminal state (e.g., one where the objects in all of the heaps have not been removed). The following example runs a game using your nim code with initial heaps of 1, 2 and 3 objects and where the first player will use minimax and the second alphabets with a cut-off at depth two.
hw3-finin> python playnim.py [1,2,3] mm ab2
NIM with heaps [1, 2, 3] using players mm and ab2 and heuristic False
Initial state: GameState(to_move=1, utility=0, board=[1, 2, 3], moves=[])
Player 1 moves (0, 1) ==> GameState(to_move=2, utility=0, board=[0, 2, 3], moves=[])
Player 2 moves (2, 1) ==> GameState(to_move=1, utility=0, board=[0, 2, 2], moves=[])
Player 1 moves (1, 1) ==> GameState(to_move=2, utility=0, board=[0, 1, 2], moves=[])
Player 2 moves (2, 1) ==> GameState(to_move=1, utility=0, board=[0, 1, 1], moves=[])
Player 1 moves (1, 1) ==> GameState(to_move=2, utility=0, board=[0, 0, 1], moves=[])
Player 2 moves (2, 1) ==> GameState(to_move=1, utility=-inf, board=[0, 0, 0], moves=[])
Player 2 wins
hw3-finin>
You can call the testnim.py script to run a set of problems as a way to test your code. Our solution produced this output.
The game trees for nim can be large and we might not want to use a version of alphabeta search that always continues to a terminal state. We've provided the following game search algorithms you can specify via the playnim.py script command:
- me: for a player that takes input from the user for each move
- random: for a player that selects legal moves randomly
- mm: for a player using a simple minimax algorithm that continues searching until all games states are terminal
- ab: for a player using the alphabeta algorithm that that continues searching until all games states are terminal
- abN: where N is an integer between 1 and 10, for a player that uses alphabeta and generates a lookahead tree for each move to depth N. Example: ab3 always looks ahead three plys.
If you read about Nim, you will learn that minimax is not really needed, since there is a perfect static evaluation, based on the binary digital sum. We don't want you to o do this. is not fun, so try to invent some less perfect heuristic, that is simple to compute.
Here are some examples I found if you're the player to make a move for the misere version Nim, where the person to take the last stone loses. You might be able to modify and adapt some of them.
- very good: only two piles, different size
- good: odd number of odd piles
- good: the biggest pile is much larger than the others
- bad: even number of odd piles
- very bad: only two piles, with same size (exception: (1,1))
- very bad: only 1-piles, odd number.
Keep your heuristic simple, but do implement something other than always returning the neutral value 0.
Some notes on Python
The AIMA code uses several Python features that may be unfamiliar.
- Named tuples, which are like lightweight objects, are used to represent the state of a game
- Using max and min with a key is used in the game search functions. It's an easy and compact way to find the thing in an iterable like a list that is largest with respect to some function. For example
>>> words = "a large dog chased the cat".split()
>>> words
['a', 'large', 'dog', 'chased', 'the', 'cat']
>>> max(words, key=len)
'chased'
(4) Questions on Git (30)
See the file questions.md in the git repository. Add your answers using git's md markup as necessary.
What to hand in
Commit changes to the files nim.py, game_trees.ppt, game_grees.pdf, and questions.md and push the results back to your repository.
|
