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 algorithms:

  1. Backtracking search without forward checking;
  2. Backtracking search with forward checking;
  3. Hill climbing search with the min-conflicts heuristic.
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.

Tips

  • 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:

  • 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 left.
  • Movement is always vertical and horizontal but never diagonal.
  • Pieces can be conquered in the vertical and horizontal direction, but never the diagonal direction.
  • The values of the squares can be changed for each game, but remain constant within a game.
  • 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 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 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.
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.

Tips

  • 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.

Submission Instructions

You will need to turn in the following:
  1. 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.

  2. 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:

  1. Log in to Blackboard and access COMP590.096.
  2. Select Tools | Digital Dropbox from the navigation menu on the left.
  3. Use Send file to submit an assignment for grading. Add file merely stores a file in your personal dropbox.
  4. 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.