COMP 590-096 Fall 2011
Assignment 2: Constraint Satisfaction, Local Search, Minimax Search
Due date: October 27, 11:59PM
Part 1: Map coloring
(Based on question 6.10 in 3rd edition of the textbook.)
Generate random instances of map-coloring problems as follows: scatter n points
on the unit square; select a point X at random, connect X by a line segment to
the nearest point Y such that X is not already connected to Y and the segment
crosses no other segment (see, e.g., here
how to test for segment-segment intersection); repeat the previous step until no more connections
are possible. The points represent regions on the map and the lines connect
neighbors. Now try to color each map with 3 and 4 colors using the following
For each n, generate several random instances, and try to make n as large as you can manage.
On average, how many constraints (edges) do your map coloring instances have for each n?
Report the performance of each search algorithm as a function of n. For both variants of
backtracking search, you can characterize performance in terms of the number of variable
assignments attempted. For hill climbing search, report the number of uphill moves and
random restarts required in order to reach a solution. Of course, you can also report raw running
times as a function of n.
- Backtracking search without forward checking;
- Backtracking search with forward checking;
- Hill climbing search with the min-conflicts heuristic.
- For segment-segment intersection code, see, e.g. here.
- Feel free to generate random map coloring problems using an alternative method,
for example, using a Delaunay triangulation of a set of random points.
- For backtracking search, experiment with different variable and value ordering
heuristics, as discussed in this lecture. If you find interesting
differences in the performance of different heuristics, comment on them in your report.
- For hill climbing search, you may want to experiment with several simple ways of breaking ties
and escaping local optima. You may also want to try beam search.
Part 1: For bonus points
- Implement simulated annealing.
- Apply your backtracking and local search code to other constraint satisfaction problems,
such as n-queens and sudoku. For a list of sudoku problems, see here.
- Write a graphical interface to display your map coloring problem instances and solutions.
Part 2: War game
(Adapted from www.cool-ai.com.)
The goal of this part is to implement an agent to play a simple "warfare" game.
The rules of the game are as follows:
Your task is to implement an agent to play the above game, one using minimax search
and one using alpha-beta search. Your program should read in each of these five game boards,
two copies of minimax or alpha-beta agents should play against each other, and at
the end of the game, you should report
- The game board is a 5x5 grid representing a city.
- Each square has a fixed point value between 1 and 99.
- There are two players, "blue" and "green". Each player takes turns:
blue moves first, then green, then blue, etc.
- The object of the game is to be the player in the end with the largest total value
of squares in their possession. That is, one wants to capture the
squares worth the most points.
- The game ends when all the squares are occupied by all players since no more moves are
- Movement is always vertical and horizontal but never diagonal.
- Pieces can be conquered in the vertical and horizontal direction, but never the diagonal
- The values of the squares can be changed for each game, but remain constant within a
- In each turn, a player can make one of two moves:
Commando Para Drop:
You can take any open space on the board with a Para Drop. This will
create a new piece on the board. This move can be made as many times as one wants to during
the game, but only once per turn. A Commando Para Drop cannot conquer any pieces.
It simply allows one to arbitrarily place a piece on any unoccupied square on the board. Once you
have done a Para Drop, your turn is complete.
The image below illustrates a Commando Para Drop. In this case, green drops a new piece on square [B,3]. This
square is worth 48, which is a higher number, meaning that it contains some juicy oil wells or other
important resources. After that, the score is green 48 : blue 2. A Commando Para Drop could have been
carried out on any squares except for [C,2] since blue already occupies it.
M1 Death Blitz:
From any space you occupy on the board, you can take the one next to it (up,
down, left, right, but not diagonally) if it is unoccupied. The space you originally held is still
occupied. Thus, you get to create a new piece in the blitzed square. Any enemy touching the
square you have taken is conquered and that square is turned to your side (you turn its piece to
your side). An M1 Death Blitz can be done even if it will not conquer another piece. Once you
have made this move, your turn is over.
The image below illustrates an M1 Death Blitz. Green blitzes the piece in [D,4] to [D,3]. This conquers the blue
piece in [D,2] since it is touching the new green piece in [D,3]. A blitz always creates a new piece and
always moves one square, but it does not conquer another piece unless it is touching it. Thus, another
valid move might have been for [D,4] to have blitzed [E,4]. Then the green player would own [D,4] and
[E,4] but would have conquered none of blue's pieces. Note, the score before the blitz was green 16 : blue
54 but afterwards is green 28 : blue 43.
Here is another illustration:
Here blue blitzes [C,3] from [C,2]. In the process green's pieces at [D,3] and [D,4] are
conquered since they touch [C,3]. Notice that in its next move, green will not be able to conquer any of
blue's pieces and only the piece at [D,4] would be able to execute an M1 Death Blitz since [D,2] has no
neighboring unoccupied squares.
Your program should use depth-limited search with an evaluation function
(which you, of course, need to design yourself).
Try to determine the maximum depth to which it is feasible for you to do the search
(for alpha-beta pruning, this depth should be larger than for minimax).
The worst case number of nodes for a tree with a depth of three in this game is 132,651.
Thus, you should be able to do minimax search to a depth of three.
- The total number of moves, the final state of the board (who
owns each square) and the total scores for each player;
- The total number of nodes examined by each player in the course of the game;
- The average number of nodes examined per move and the average amount of time to make a move.
Pseudocode for alpha-beta pruning is given in Figure 6.7, p. 170 in the 2nd edition,
and Figure 5.7, p. 170, in the 3rd edition.
- For alpha-beta pruning, try to come up with a move ordering to increase
the amount of pruning.
Part 2: For bonus points
- Design an interface for the game that would allow you to play against the computer.
How well do you do compared to the AI? Does it depend on the depth of search,
evaluation function, etc.?
- Design your own game boards and show results on them. Try to play the game
on a larger board. How large can you go?
- Implement any advanced techniques from this lecture
to try to improve efficiency or quality of gameplay.
- Implement an agent for a version of the game where you have to flip a coin in order to figure
out whether adjacent enemy squares can be conquered by a M1 Death Blitz move.
You will need to turn in the following:
- A report in PDF format. The report should briefly describe
your implemented solution and fully answer the questions for every part of the assignment. Your description
should focus on the most "interesting" aspects of your solution, i.e., any non-obvious
implementation choices and parameter settings, and what you have found to be especially
important for getting good performance. Feel free to include pseudocode or figures if
they are needed to clarify your approach. Your report should be self-contained and it should
(ideally) make it possible for me to understand your solution without having to run your source code.
The name of the report file should be lastname_firstname_assignment2.pdf.
- Your source code compressed to a single ZIP file.
The code should be well commented, and it should be easy to see the correspondence between
what's in the code and what's in the report. You don't need to include executables
or various supporting files (e.g., utility libraries) whose content is irrelevant to the
assignment. If I find it necessary to run your code in order to evaluate
your solution, I will get in touch with you.
The name of the code archive should be lastname_firstname_assignment2.zip.
Submit both your files through Blackboard as follows:
Log in to Blackboard and access COMP590.096.
Select Tools | Digital Dropbox from the navigation menu on the left.
Use Send file to submit an assignment for grading. Add file merely stores a file in your personal dropbox.
In Digital Dropbox, the file should be listed as Submitted, and not just Posted.
Late policy: You lose 25% of the points for every day the assignment is late.
If you have a compelling reason for not being able to submit the assignment on time
and would like to make a special arrangement, you must let me know at least a week before the due date
(any genuine emergency situations will be handled on an individual basis).
Academic integrity: Feel free to discuss the assignment with each other in general terms,
and to search the Web for general guidance (not for complete solutions). Coding should be done
individually. If you make substantial use of some code snippets or information from outside sources,
be sure to acknowledge the sources in your report.