COMP3702/COMP7702
Assignment 1: Search
Due 5pm,
Friday, 11th of September 2009
This assignment counts 10% toward the final marks.
Purpose
This
assignment is intended to practically acquaint you with informed search methodology
and techniques. Additionally, it should provide some understanding of how an
informed search algorithm for simple games, such as the 15-puzzle, can be
implemented.
Code
The supporting material can be used freely in your work: zipped source code, jar package, Netbean5 project file, and package description. For this assignment you can ignore classes related to MiniMax and Tic Tac Toe, which are included for your interest.
The supporting code is in Java and we recommend that you to use and modify this to complete the assignment. If you do not know Java currently, you will not need to learn a great deal of Java to do the assignment, but working in a pair might be a good idea.
Administration
The assignment is worth 10% of your final grade and you may
work individually or in pairs. There are more than the maximum marks available.
You may create a “buffer” of marks, but your grade will be capped at 10 marks
for this assignment, even if your raw score is over 10. You are required
to submit two separate components for this assignment, these are:
- A single
file containing all the source code files (e.g. *.java), including any you
modify. Modified sections of source code should include comments
and overall, the code should compile. There is no excuse for handling in a program which does not
compile/interpret or run. If you are having trouble, some features may be
omitted. Package and submit all the source code (*.java), including
unmodified files, maintaining directory structure as necessary. You may package
the source code into e.g. a .zip or .jar file.
- A pdf with the written component of the assignment (see template/example for general guidance). Please indicate in your pdf which source code files you modified and if there are any new files. Also indicate in your pdf exactly what parts you have attempted, in part or in full, so that we know what to look for when marking.
Submission of both parts is via the ITEE online submission
website found at http://submit.itee.uq.edu.au.
Your group name should be the student number of the person submitting the
assignment. You should use your student number(s) within the pdf and code, and as part of the pdf
and packaged code filenames. Note:
There will be marks deducted if your PDF and code do not contain your names and
Student IDs.
If you resubmit your assignment, please resubmit all files
relating to your solution. Your most recent submission will be the only
submission marked.
In line with University policy collusion and plagiarism will
not be tolerated; see the course profile for more details on these topics.
Each group must submit an assignment cover sheet signed
by all members of the group. The online submission system will offer you a
printable cover sheet as you submit your assignment. Otherwise, a
suitable ITEE assignment cover sheet can be obtained from http://studenthelp.itee.uq.edu.au/assignments/
. You should drop your completed form into the COMP3702/7702 submission box on
level 1 of GP South as soon as possible after submitting your assignment.
You can discuss aspects of the assignment with other members of the class on the comp3702 newsgroup (see my.uq.edu.au). If you want to ask the lecturer any questions, sending an email to ruth@itee.uq.edu.au is the best option.
The Assignment
The
15-puzzle is an apparently simple puzzle for a single player, containing 15
numbered tiles and a blank space on a 4x4 board. The puzzle is set up in a
random configuration and the goal is to move the tiles around until an ordered
goal state is reached, having the tile numbers in order across and down the
board, with the blank in the bottom right-hand corner (see below). The only
moves available are to move a tile into a vertically or horizontally
adjacent empty square. The state space for this problem is quite large,
containing approximately 1013 states, so exhaustive search is a poor
problem-solving strategy. (You can play with an applet
for inspiration.)
|
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
8 |
|
9 |
10 |
11 |
12 |
|
13 |
14 |
15 |
0 |
Source code has been provided
which implements a breadth-first search strategy to solve the 15-puzzle (see
Code above).
In this
assignment, you are asked to implement heuristic search algorithms to solve the
15 puzzle, including the use of your own heuristic functions, and to document
and describe the algorithms and their behavior.
The following is the
marking scheme. You should carefully document all the parts of the assignment
in a single PDF. Your programs should be well designed and should use
meaningful variable names, correct indentation of code, etc.
|
Part |
Description |
Marks |
|
1 |
Problem
Representation Formally represent the 15-puzzle problem. Your assignment must contain the following: 1. List all relevant objects in the problem description (0.25 marks); 2. Represent the states in a well-known data structure, such as array, queue, stack, linked list, or your choice of mathematical model (0.25 marks); 3. Represent the state space with mathematical formulas, operations, and constraints (0.25 marks); 4. State the initial
state of the game, goal test conditions, and step cost / path cost (0.25
marks) |
1 |
|
2 |
Heuristic Functions Implement two heuristic functions h1 and h2 (1 mark each): Your assignment must contain the following for each heuristic: 1. Formal description of your heuristic (0.25 marks each); 2. Pseudocode for your heuristic (0.25 marks each); 3. Descriptions of these pieces of pseudocode (0.25 marks each); 4. Correct implementations of the pseudocode in Java (0.25 marks each). You cannot use the following heuristic functions described in the text book: - h3 = the number of misplaced tiles, - h4 = ( - h5 = max{h3,h4}. |
2 |
|
3 |
Informed Search
Algorithms Implement the Greedy and A* search algorithms (1 mark each): Your assignment must contain the following for each search algorithm: 1. Formal description of the search algorithm (0.25 marks each); 2. Pseudocode of the search algorithm (0.25 marks each); 3. Descriptions of the pseudocode (0.25 marks each); 4. Correct implementation of the pseudocode in Java (0.25 marks each). |
2 |
|
4 |
Repeated States Implement detection of repeated states: Your assignment must contain the following: 1. Formal description of how to detect and avoid repeated states (0.25 marks); 2. Pseudocode showing how you detect and avoid repeated states (0.25 marks); 3. Descriptions of the pseudocode (0.25 marks); 4. Correct
implementation of the pseudocode in Java (0.25
marks). |
1 |
|
5 |
Evaluate Evaluate your heuristic functions with Greedy and A* search. Your assignment must contain the following: 1. Effective branching factors (EBFs) for depths (solution lengths) 5, 10, 15, 20, and 25 for both heuristic functions and both search algorithms. EBFs should be averaged over 5 runs for each depth. (1 mark) 2. Evaluation of strengths and weaknesses of your heuristic functions based on evaluation of EBFs, space and time complexity for evaluating your heuristic functions, accuracy of your heuristic functions, completeness, and optimality. (2 marks) Note: You can use the supplied code for generating random puzzle states to collect 5 test results for each depth. Then, run the supplied code (in Node.java) or write and run your own code to calculate EBFs for each depth. For each test run, you need to obtain the total number of nodes generated and the depth (solution length) to obtain its effective branching factor. |
3 |
|
6 |
Compare Implement the following heuristic functions and compare your heuristic functions with them, using the evaluation methods of part 5. - h3 = the number of misplaced tiles - h4 = ( Your assignment must contain the following: 1. Formal description of h3 and h4 (0.25 marks); 2. Pseudocode for h3 and h4 (0.25 marks); 3. Descriptions of these pieces of pseudocode (0.25 marks); 4. Correct implementations of the pseudocode in Java (0.25 marks). 5. Comparison of the four heuristics implemented based on evaluation of EBFs, space and time complexity for evaluating your heuristic functions, accuracy of your heuristic functions, completeness, and optimality. (1 mark) |
2 |
|
- |
Program
documentation Source code is well documented, uses meaningful variable names and correct indentation. |
0.5 |
|
- |
Report Report is well presented with correct English expression. |
0.5 |
Implementation marks are given based on the following criteria: Your program is well designed, and can solve 15-puzzle problems with Greedy and A* search and your heuristic functions (within a reasonable time).
Notes:
- To assist with testing, we
recommend the following restrictions on your code:
The jar file must contain the class named
"search.fifteen.FifteenSearchApp"
with the methods named "solveH1G", "solveH1A", "solveH2G"
and "solveH2A" (naming: 1 = heuristic 1, 2 = heuristic 2, G =
Greedy, A = A*) as in the supplied code. These should:
1. Take a PuzzleState
object (a 4x4 array representation of the 15-puzzle),
2. Solve a puzzle with your own Greedy
and A* implementations (with detection and avoidance of repeated states if
implemented) with your own heuristic function 1 and heuristic function 2 ,
and
3. Return an array of actions defined
in class PuzzleState. (Note: the actions in the array
must be ordered so that performing each action (starting from the last element
of the array and working towards the first element) on the given original state
will solve the problem.)
Examples of these methods are provided. You
must modify these methods to solve the puzzles with your own Greedy and A*
implementations with your heuristic functions. Do not modify any other classes
provided (especially class PuzzleState), but you can
extend the classes to implement your own representations of states, nodes, and
actions. You will need the action definitions given in class PuzzleState in order to return valid action sequences in FifteenSearchApp.solveH_().
If you extend PuzzleState
to use your own representation of states, make sure that you map the array
representation of puzzle in PuzzleState into your own
representation in FifteenSearchApp.solveH_(). If you use your own action definitions, you also need
to map your action sequences of solutions into the actions defined in class PuzzleState when you return an array of actions in FifteenSearchApp.solveH_().
Important note: make
sure that your goal state is the same as the following (i.e.
numbered tiles positioned as shown, blank
in the lower right corner):
|
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
8 |
|
9 |
10 |
11 |
12 |
|
13 |
14 |
15 |
0 |
- You may find an Eclipse project creation tutorial useful.
- To prepare a PDF document, you can use OpenOffice or
MS Word to prepare your assignment and export a PDF version. Instructions for
creating PDF files from MS Word in ITEE can be found here.
- In all cases, describe how to compile/interpret and run your program (include name and version of compiler/interpreter).
- Once again, where possible, include your student number (if working individually) or both student numbers with a separator (if working in a pair) at the beginning of submitted filenames. An exception - in Java, use search.jar, as described below. Also make sure to include your name and student number(s) in your document and in any modified code files.
- If using the supplied Java code to implement your own FifteenSearchApp.solveH1G(), FifteenSearchApp.solveH1A(), FifteenSearchApp.solveH2G() and FifteenSearchApp.solveH2A(), we should be able to test and evaluate your code.
- Otherwise, you need to provide basic test and evaluation code for your program and document this.
Java notes:
- Read the package description to understand the classes that you will need
to change for this part.
- To use the supplied jar package, unpack it
using e.g. UNZIP or WINZIP. In NetBeans, after
creating a project named search, simply copy all provided source files
(including directory) into your project source directory. Make sure your
package name is “search”.
- To package your source and compiled classes
into a single jar file,
1. Create a file named MyManifest containing the following line:
Main-Class: FifteenSearchApp
2. Run the following command to include
all the files and directories under a directory named foo
jar cvfm
search.jar MyManifest –C foo/
3. After preparing a jar file in
this manner, you can run the application within it via
java -jar search.jar
If you are using NetBeans, a single jar file will be automatically created in a folder named ‘dist’ when you BUILD the project. Make sure you include source files by removing "**/*.java" from the file exclusion list of packaging option on the project property window.