CIS 479/579 Machine Problem 2

Summer 2019

 

For your second assignment, you are to write a program (using Lisp or some other language) that will allow you to examine the effectiveness of the A* search algorithm compared to that of ordinary branch and bound search. The problem to be solved is a simplified version of the Four Kights puzzle.

 

The Four Knights puzzle is played on a 3 by 3 chess board. The opposing knights (blue and red) start in the corners opposite each other as shown below. The object of this puzzle to have the opposing knights change sides of the 3 by 3 chess board. The knights are moved one at a time using the usual rule for movements (two squares forward in any direction followed by one square left or right.

 

 

Start:  image001.jpg                                End:

 

 

To use A* you will need an estimate of the cost of traversing each path and an underestimate of the distance remaining to the goal state. For cost of path traversal you may use path length. You are left to your own devices to design a measure that uses underestimates of the remaining distance to the goal.

 

You will need to devise an expand function that does not rely on hard coded problem state relations (if you use hard coded relations you will lose 1 point). You will also need to devise a data structure for the nodes in the problem state space. It may also prove to be helpful to rethink the structure of the elements in the queue of partial paths. It may be wise to store the accumulated cost and the underestimate as part of the path stored in the queue.

You will need to turn in a well-commented program listing, sample runs (with neatly organized output), and a memo discussing your solution. In your memo you should describe your rationale for choosing the operational definitions of your measures). In your memo you should discuss the relative effectiveness of A* to Branch & Bound using quantifiable language (as evidenced by your sample runs). Your memo should contain tables and/or graphs summarizing the run data.

 

 

Assigned: 5/15/19

Due date: 5/29/19