CMPUT 657: Assignment 2

CMPUT 657

Heuristic Search

Assignment 2

Due Date: Wednesday November 10 (4:00 PM)
10% late penalty for anything handed within 24 hours of the due date. Anything later than that will not be accepted.

SuperPuzz (or "gaps") is a solitaire card game. You are to write a single-agent search program to prove whether a given puzzle is solvable or not solvable. In the case of a solvable puzzle, you are to give a solution.

Rules

One deck of 52 cards is used. All cards are dealt face up in 4 rows of thirteen cards each. The aces are removed, leaving four gaps. Here is an example starting position:

The objective is to rearrange the cards so that each row is a sequence of cards of the same quit (in order from 2 to 9, 10, J, Q, K), with the last entry being empty (a gap). Move consists of filling a gap by moving the card that logically follows the card to the left of the gap (same suit). In the example above, the 6 of clubs can be moved to the gap to the right of the 5 of clubs. Gaps on the left-hand side of the sequence (the first column) can be filled with a 2 of any suit. In the above example, any of the four 2s can be moved to the top left-hand-corner gap. Note that the rules imply that nothing can follow a king. Hence the gap to the right of the K of diamonds is useless. You keep playing until you find a solution or prove that there is no solution. Not all starting configurations are solvable.

Input

Input to the program is a set of starting positions separated by a blank line. Your program reads in a position, attempts to solve it, and then moves on to the next problem, until input is exhausted. A starting configuration is given by specifying the cards using the conventions that the numbers are represented by "2"-"9", "T" (ten), "J" (jack), "Q" (queen), and "K" (king); the suits by the lower-case letters "s" (spades), "h" (hearts), "c" (clubs), and "d" (diamonds); and the gap is given by the letter "g".

The above board would thus be represented by:

g 9c Qd 3s ks 6c 2c Jc Kd g 5c g 8c
Kh 5h Ts 8h 2s 6h 6d 4h 7h 3d g Qc 8s
Qh 4s 7d 4d 3c 7s 5s Qs Th Jd 7c 6s 8d
9d 2h 4c Jh Kc 9h Js 5d 9s Td Tc 3h 2d

The output is either the message "No solution", or a sting that begins "Solution is" and is followed by the sequence of moves that lead to the solution. Moves are given by just naming the card to be moved. For the above problem, a sequence of moves could be "4d 8d 6c". Note that there could be two gaps in the first column, and one must indicate which row the 2 moves to. Assume that the rows are numbers "1" to "4", from top to bottom. We will use the notation "2s1" which means that the 2 of spades moves to the gap in the first column of row 1.

Solution

Using A* or IDA*, your assignment is to solve a given puzzle or prove that no solution is possible. This should be done with the smallest search tree possible, while still proving the optimal result (minimum number of moves). Enhance A*/IDA* to eliminate as much of the search tree as possible using some of the standard techniques in the literature and, possibly, some of your own application-dependent enhancements. Of course, most of the magic happens in the evaluation function. Can you come up with a good evaluation?

A good way to test your program is to use positions that are a few moves away from a solution, and verify that your program finds the solution in the right number of moves.

As your program runs it should give information on the search progress. You should print a message each time the "f" value changes, and the amount of search done up to that point. For IDA*, that means printing out a message at the start of each iteration. For A*, it means printing a message when the value at the head of the Open List changes. For example, your output might look like this:

Iteration f=36 (1234 nodes)
Iteration f=37 (4376 nodes)
Iteration f=38 (11765 nodes)

At the end of a search, your program should output the following. For each input problem, show statistics on the number of nodes searched, execution time, and average h-value for all nodes where an evaluation occurred in the tree. When the program successfully terminates, print out the solution. Your output should look like this:

No solution
Tree size: 12345678 nodes
Time: 123.4 seconds
Evaluation: 12.4 average

Specifications

Your program should take input from stdin and output to stdout. The input file is in the format given above, with possibly multiple positions in the file.

Your program will run dedicated on chinook8. You can count on having roughly 3 GB of RAM.

You must implement the command-line option "-t nnn", where nnn is an integer. This option sets the program to stop searching a position after nnn seconds of real (not CPU) time. When time runs out, you should stop the search, output the message "Search aborted" (with the search statistics), and move on to the next input problem.

Hand In

Hand in the following:
(1) By e-mail, send kishi@cs the code for your program (including a Makefile). This email should be received no later than the due date given above.
(2) Include a short document describing your program. Skip the basics (such as A*/IDA*). I want to know any search enhancements that you tried. Described your heuristic function. Tell me what you did that was interesting. What problems did you encounter? How can your solution be improved? This document must be no longer than five pages and *must* be in pdf. Include a table of experimental results that shows the (positive?) impact of your enhancements.

Good luck!

University of Alberta

Computing Science