HW3: Constraints and Games
out 3/4, due 3/14
(1) Magic Squares (35 points)
In class we showed examples of using the python constraint package to generate magic squares of size three (see also ms3.py). In general, there is always a magic square of size N whose magic sum is equal to N*(N**2+1)/2 for n>2. (Others may also exist.)
Complete the function ms() in the ms.py file in your repo that takes an integer for the size, an optional number for the sum and a solver from the constraints package and generates a magic square of that size. You can use the code for the 3x3 case as a guide, but extend this to create a function that takes an argument for the magic square size (n) and an argument for the constraint solver algorithm to use (solver).
You will have to use pip to install two packages in your python: python-constraint and wrapt-timeout-decorator. The second package does not work on Windows, though it does on Unix and Macos. There are some work arounds for Widows, but we recommend debugging this function on gl. You can clone your repo on your own computer and also clone it on gl, where yiu can develop the ms.py program. To install packages on gl, you'll need to use the "--user" flag, e.g.:
- pip install --user python-constraint
- pip install --user wrapt-timeout-decorator
When you have it working, you can commit the ms.py file and push it back to your repo on GitHub.
Our ms_sizes( ) function will test this on sizes from 3 to 6 using each of the three solvers that the constraint package supports: BacktrackingSolver, RecursiveBacktrackingSolver, and MinConflictsSolver, printing the results and time taken. Run this and copy the results to a file ms_out.txt. You can see our results here: model_ms_out.txt.
Commit and your completed ms.py file to GitHub and answer the questions in questions.md
(2) Minimax (20 points)
Note: the game trees for problems 3 and 4 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.
In the game trees in this problem, the value of the static evaluator functions is shown 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. Indicate which initial move the maximizing player should make.
(3) Minimax with Alpha-Beta (20 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.
(4) Questions in the git repository (25)
Add your answers using git's markup as necessary.
What to submit
Commit changes to the files ms.py, game_trees.ppt, game_trees.pdf, and questions.md and push the results back to your repository.
|
