As on Assignment 1, you have the option of working in groups of up to three people. You are free to either stay with the same team or pick a new one, but as before, all the group members must be enrolled in the same section for the same number of credits (except for online students, who can work with Section Q students enrolled for the same numer of credits).
Part 1: CSP - Flow FreeCreated by Litian Ma and Jialu Li based on Flow_Free
Introduction and rulesd Flow Free is a puzzle game for iOS and Android released by Big Duck Games on June 2012. The goal for this game is to fill in colors on all empty grid cells to form "pipes" such that the colors are able to flow between two given sources. You will be given a puzzle with multiple color inputs. Each color has two sources on the grid, and you will need to draw a pipe of the same color to connect them. The pipes cannot intersect with each other, and a complete solution cannot contain any empty grid cell. For this assignment, each puzzle only has one unique solution. The following picture shows an example of the start state and goal state for one Flow Free instance.
The other constraint for this assignment is that no zigzag pattern is allowed. This means that for each non-source cell, its four-connected neighborhood (consisting of cells above, below, to the left, and to the right, if they exist) should have exactly two cells filled with the same color. For each source cell, its neighborhood should have exactly one cell filled with the same color. The following picture shows an example of the disallowed "zigzag" pattern.
First, you need to formulate Flow Free as a CSP. In your report, give your definitions of variables, domains, and constraints. Next, with these in mind, implement backtracking search. You should create two versions of your implementation: the "dumb" one with random variable and value ordering (and no forward checking), and the "smart" one that includes any variable and value ordering heuristics that make sense for your formulation (which would probably include forward checking). In the report, describe your "smart" implementation and give a brief explanation of why you chose to use your particular combination of heuristics and inference techniques.
You need to run both your solvers on several input puzzles. You will use the input and output formats illustrated by this sample 5*5 puzzle and the corresponding solution.
For each of the inputs below, please include in your report:
1.1 Smaller inputs (for everybody)In this part, you are required to solve the following three puzzles:
1.2 Bigger inputs (for four credits only)In this part, you should improve your "smart" implementation with a better inference technique or constraint propagation technique (arc consistency). Then use both the "smart" and the new "smarter" implementation to solve the following bigger puzzles. As in Part 1.1, report your solution, attempted assignments, and running time for both methods.
For bonus points
Part 2: Game of BreakthroughCreated by Shreya Rajpal, revised by Akshat Gupta
The goal of this part of the assignment is to implement an agent to play a simple 2-player zero-sum game called Breakthrough.
Rules of the game
2.1 Minimax and alpha-beta agents (for everybody)Your task is to implement agents to play the above game, one using minimax search and one using alpha-beta search as well as two evaluation functions - one which is more offensive (i.e., more focused on moving forward and capturing enemy pieces), while the other which is more defensive (i.e., more focused on preventing the enemy from moving into your territory or capturing your pieces). The evaluation functions are used to return a value for a position when the depth limit of the search is reached. 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 leaf nodes for a tree with a depth of three in this game is roughly 110,592, but in practice is usually between 25,000 - 35,000. Thus, you should at least be able to do minimax search to a depth of three.
We provide the following two dummy heuristics:
Finally, you should summarize any general trends or conclusions that you have observed. How does the type of evaluation function (offensive vs. defensive) affect the outcome? How do different combinations of evaluation functions do against each other?
2.2 Extended rules (for four-credit students)Modify your implementation and evaluation functions to support the rule changes below and run several matchups for alpha-beta agents only with the maximum depth you can manage. You can choose any combination of offensive or defensive agents. Report outcomes of 2-4 representative matchups (or averages over several matchups of the same type), and summarize any interesting trends and differences from part 2.1.
For bonus points
Report ChecklistYour 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 us to understand your solution without having to run your source code. For full credit, your report should include the following.
Statement of individual contribution:
Submission InstructionsAs for Assignment 1, one designated person from the group will need to submit on Compass 2g by the deadline. Three-unit students must upload under Assignment 2 (three credits) and four-unit students must upload under Assignment 2 (four credits). Each submission must consist of the following two attachments:
Late policy: For every day that your assignment is late, your score gets multiplied by 0.75. The penalty gets saturated after four days, that is, you can still get up to about 32% of the original points by turning in the assignment at all. 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 send me email at least four days before the due date (any genuine emergency situations will be handled on an individual basis).
Be sure to also refer to course policies on academic integrity, etc.