CPSC352 -- Artificial Intelligence -- Fall 2011
Programming Project -- Due TBA

NOTE: You may work in pairs on this assignment. Both team members received the same grade.

Choice 1: The Sliding Tile Puzzle

Develop a heuristic PROLOG solution to the sliding-tile puzzle described in the Luger text. To simplify this problem a bit, assume that all moves have exactly the same cost (= 1). The goal is to develop a truly useful heuristic for solving the sliding tiles puzzle and then to analyze it and write up your results. A useful heuristic for a given problem is NOT one that is merely admissible but one that is also much more efficient than a breadth first search. For the sliding puzzle problem, it should be possible to develop a heuristic that finds the shortest path by checking fewer than 50 states. Your goal should be to find such a heuristic.

Required Writeup: In addition to the PROLOG program itself, provide both a theoretical and empirical analysis of your heuristic. The theoretical part should be based on the discussion of heuristics in the text. That is, discuss why it is a heuristic (rather than a deterministic algorithm), whether it is admissible and how informative it is. The empirical analysis should be based on experimental results. Try running the heuristic with different start and goal states and show that it remains both admissible and efficient. You may also wish to compare its performance against breadth-first search and also against a different heuristic (e.g., against the one described on heuristic homework assignment).

One of the key issues in designing a PROLOG solution to this problem is deciding on how to represent the puzzle. Another issue is how to describe all possible moves. Code your PROLOG solution into a single file and incorporate it into the heuristic search framework you used in the knight's tour problem. For example, if you name the file containing the solution to the sliding puzzle sliding.pl, your main program would look like this: 

/* sliding.heur.pl -- main file for sliding tile puzzle */

setup :-
	reconsult('sliding.pl'),	/* moves and heuristic for sliding tile puzzle */
	reconsult('bf.pl'),		/* best-first search predicates */
	reconsult('pq.pl'),		/* priority queue predicates */
	reconsult('set.pl'),		/* set predicates */
	reconsult('small_lib.pro').	/* miscellaneous predicates */
start :-
	go([b,b,b,x,w,w,w],[w,w,w,_,_,_,_]).	/* go from start to goal state */

unsafe(_):- fail.            				/* everything is safe */

precedes([_,_,_,_,X],[_,_,_,_,Y]) :- X =< Y.  	/*  f(i) <= f(j) for states i, j */

Note that the precedes() predicate is necessary for the heuristic. It compares the values of f(n) = g(n) + h(n) for two states, i and j. The smaller value is given higher priority.

Choice 2: Warnsdorf's Heursitics

Write a PROLOG program that implements Warnsdorf's heuristic for the full Knight's Tour. According to this heuristic, the knight would select the square that has the fewest choices for future knight moves. In effect, this forces the knight to cover the squares on the periphery of the board before trying squares on the interior of the board.

There are several subproblems that you must solve in order to obtain a solution to this problem:

To help with the backtracking problem, here's a select/3 predicate that is suitable for backtracking: 

/**
 * select/3 selects an Item from OldList, giving NewList. By using
 *  append, select/3 will return a different element each time it
 *  is called, thus making it suitable for backtracking.
 */
select(Item,OldList,NewList) :-
   append(X,[Item|Tail], OldList),
   append(X,Tail,NewList).

Because it uses append, it will select a different Item from OldList each time it is backtracked on. To test this, trying running it and typing ';' after each solution.

For this problem, provide an analysis of Warnsdorf's heuristic comparable to the required writeup described with Choice 1.

Choice 3: Minimax Two-person Game

Using the programming language of your choice, write a program to play a 2-person game, such as tic-tac-toe, that incorporates the min-max algorithm. In order to use min-max, you'll need to develop some sort of heuristic to evaluate each state, unless of course you're able to search all the way to the end of the game on each move (unlikely even for a game like tic-tac-toe). Your write up in this case should include complete documentation of your solution, from knowledge representation, search strategy and an analysis of the program's performance. You're completely on your own for this one!