CSSE 413: Heuristic Search Programming Assignment
The aim of this assignment is to understand and implement effective heuristic functions.
Problem
We ask you to develop, implement and test a heuristic function for the
game you developed so far.
Work on this assignment by yourself.
The following specifications are added to this more complex version
of "Capture the Flag":
- Instead of a 10 x 10 grid, from now on, we will be using a 30 x 30 grid.
- There may be more than one flag for your team.
- There will be one home base.
- Players must return a flag to base.
- Players must step on flags to pick them up, but only must be adjacent
to home base to drop it off.
- A person may carry zero or one flag.
- The game terminates when all flags are have been returned to base.
The following specifications are added to your software:
- Modify your code so that it prints the total number of nodes
placed on the "open" priority queue. In other words, increase some
counter by one, everytime you add a state to the "open" priority
queue.
Study
In addition to the software, we also ask you to perform a brief study
and turn in a write-up of your results.
- Study the performance of three different heuristics. Feel
free to have them build on each other. Provide the total number of
nodes placed on the open priority queue over the course of a
run. Do this for the test cases given below.
- Explain the heuristic you implemented in the software you
submit.
- Prove that the heuristics are admissibile.
Testcases
- Here are the test cases.
- The updated server will be posted shortly.
Turnin
- Submit your code and write-up to the appropriate drop box on Angel
by class on Day 10.