CS440/ECE448 Fall 2016 Assignment 2: Constraint Satisfaction Problems and Games Deadline: Monday, October 24, 11:59:59PM

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

Contents

• Part 1: CSP: Word Sudoku (inputs 1 and 2 for everybody, input 3 for four credits)
• Part 2: Game of Breakthrough
• 2.1 Minimax and alpha-beta agents (for everybody)
• 2.2 Extended rules (for four-credit students)
• Report checklist
• Submission instructions

Sudoku is a puzzle that has gained much popularity since its first release in a US Newspaper in 2004. The object of the original Sudoku is to fill in a partially-completed 9x9 grid with numbers 1-9 such that each row, column, and the nine 3x3 sub-grids contain no duplicate numbers. In this assignment, you will implement a variation on Sudoku where, instead of filling the grid with numbers, you will fill the grid with words. You will be given a word bank, or a list of words that must be used exactly once (unless otherwise specified), and you must arrange them so that every cell in the grid contains a letter. Note that words will take up multiple cells in the grid and can be oriented either horizontally or vertically, and words are allowed to overlap. Following the rules of Sudoku, each row, column, and 3x3 cell cannot contain duplicate letters. To familiarize yourself with this game, we recommend playing it for yourself at http://dkmgames.com/WordSudoku.htm. The only difference between the online game and the game in this assignment is that in the online version, you are given the orientation of the words, but in this assignment, your code must be able to determine this for itself.


Word Sudoku game

The word bank will contain one word per line (example). The grid files will contain nine lines of nine characters each. If the character is an underscore "_", assume that the letter that goes in that cell is unknown. Otherwise, assume that the character belongs in the corresponding grid cell (example).

Your task is to implement backtracking search (see lecture) to solove the puzzles below. First, you need to determine your formulation of the CSP and include it in your report. What are the variables, domains, and constraints in your formulation? With these in mind, implement any ordering heuristics that make sense for your formulation to make your search efficient. Briefly describe your implementation.

For each of the inputs below, please include in your report:

• Your solution, the filled 9x9 grid that satisfies all the constraints (example). Please either include an image of the filled grid, or inline it in a monospace font (Courier New, for instance).
• In order, the sequence of assignments made, where each assignment contains the word, the coordinate of the top/left letter, and the orientation. Please follow the format in the example file, corresponding to the sample grid above. The lines are formatted as O,R,C: WORD, where O is the orientation (either H or V) and R and C are the row/column for the top-left coordinate of the first letter in the word. If you did not place this word on your grid (see Part 3), use (N/A) instead.
• The number of nodes expanded in the search tree. A state (either a partial or full set of assignments) is considered expanded when its children states, if any, are computed. This definition is equivalent to the definition of expanding a node in a search tree.
• The execution time of your search algorithm, in seconds or milliseconds.

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

• The 8x8 board is initially set up as shown below. Each player has 16 workers in their team.

• Players play alternating turns, and can only move one piece (of their own workers) at a time.
• In each turn, a worker can only move one square in the forward or diagonally-forward directions, as shown below. Moreover, a worker can 'capture' workers of the enemy team if they are placed diagonally forward from it, as shown in the illustration below. Note that if enemy workers are directly in front of the player, then a capture isn't possible.

• The game finishes when (a) a worker reaches the enemy team's home base (the last row); or (b) when all workers of the enemy team are captured.

You are to run four games for each of the following match-ups:

1. Minimax vs. minimax;
2. Alpha-beta vs. alpha-beta;
3. Minimax vs. alpha-beta (minimax goes first);
4. Alpha-beta vs. minimax (alpha-beta goes first).

1. The final state of the board (who owns each square) and the winning player;
2. The total number of game tree nodes expanded by each player in the course of the game;
3. The average number of nodes expanded per move and the average amount of time to make a move.
4. The number of opponent workers captured by each player, as well as the total number of moves required till the win.

Tips

• Pseudocode for alpha-beta pruning is given in 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. Discuss any interesting choices in your report.
• For offensive vs. defensive evaluation functions, you may want to define the evaluation function as having two components: your score and your opponent's score. You would then weight these two components differently or combine them in different ways to get a more offensive or more defensive strategy. You can also read the Breakthrough Wikipedia page for possible features of a position to look for and prioritize for offensive vs. defensive play. Better yet, you should try playing the game yourself to get a better sense of what features or formations can occur.

1. A report in PDF format. As for Assignment 1, the report should briefly describe your implemented solution and fully answer all the questions posed above. Remember: you will not get credit for any solutions you have obtained, but not included in the report.

   As before, all group reports need to include a brief statement of individual contribution, i.e., which group member was responsible for which parts of the solution and submitted material.
   
   The name of the report file should be lastname_firstname_assignment2.pdf. Don't forget to include the names of all group members and the number of credit units at the top of the report.

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 we find it necessary to run your code in order to evaluate your solution, we will get in touch with you.
   
   The name of the code archive should be lastname_firstname_assignment2.zip.

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 a week 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.