Introduction
As announced, assignment #1 consists of 3 parts: a self-exploratory online task, some paper and pencil work, and some programming. The total credit is 100 points for the whole assignment. Points are given in brackets.
Due date: Tue March 23rd, 2010
Solutions to theoretical assignments have to be handed in in the lecture hall before the lecture starts.
Important: Your submission should contain, your source code and any extra classes (even those already provided to you) required for compilation and execution. Also, in your submission you should include a README file that contains instructions on how to run your code, any problems that you have encountered and any other details that your TA should know.
Submission format: All source code for the practical assignments has to be archived using ZIP. The archive has to adhere to the following naming convention: {last name}_{first name}_pai2010.zip, and should contain no other folders except for the source files. The archive has to be submitted by E-Mail to Cosmin Basca until due date, 2 PM. The SUBJECT of the email has to be PAI2010_A1.
Part 1: Self Exploration
Please go to
(page protected with the usual username & password)
alternatively go to:
http://www.cs.ubc.ca/labs/lci/CIspace/Version4/search/index.html
and try out all the search algorithms. Ask yourself whether you can find all the differences between the algorithms addressed in class.
Part 2: Paper and Pencil: (30)
Part 2a: Formulate the "Sussman anomaly" with STRIPS language (10)
The following figure shows a blocks-world problem known as the Sussman anomaly. Formulate it in STRIPS language.
Part 2b: Solving a problem with CSP (10)
Consider the sudoku puzzle below. If you don't know sudoku read this.
Formulate the problem in terms of variables, domains, and constraints.You may want to enter the problem into the applet that can be found and downloaded here.
Using the applet is not mandatory because it's quite time-consuming.
Please note: If you choose the applet, you might NOT want to use any string-set domains (but integers), as the number of constraint types is too limited with strings!
What to hand in:
A textual definition of the problem (domains, variables, etc.) Handing in the textual definition of the problem (without solution) is mandatory and worth the 10 points.
Part 2c: Minimax applied to the TicTacToe Game (10)
On the image below, you can see a state of the popular TicTacToe Game.
Your task is now to draw the full minimax search tree starting from this state, and ending in terminal nodes.
Show the utility value for each terminal and non-terminal node.
Utility values are +1 if X wins, 0 for a tie, and -1 if O wins. Assume that X makes the next move.
Part 3: Programming a "Settlers"-Player (70)
Implementation Notes:
A small application providing seven classes has been written to provide an appropriate environment that allows a direct implementation of your heuristic function at the setvillage method in the player class. The Java source code of the application can be downloaded as PAI2008-Assignment01.zip. First unpack the zip file into a directory. If you have not installed Java on your system go to Sun's Java web page and download the appropriate Java package for your machine. Follow the instruction on the page to install Java on your machine.
Just a few remarks about the code:
We have coded the fields and village positions according to the following figure.
We list the public methods in the Board class that you could use to access the game board information.
- int VillageOwner(int Village_ID).
This method check if the given village location is being occupied and is being occupied by which player. - int fieldResource(int Field_ID).
This method returns the resource type of given field location. - int fieldNum(int Field_ID).
This method return the number which is associated with the given field location. - int buildVillage(int Village_ID, int Player_ID).
This method update the game board by building a new village on a given village location by given player. - int[] NeighbouredField(int Village_ID).
This method return all the field locations which is neighboring to the given village location.
What to hand in:
- Part2a) A textual description of the answer
- Part2b) A textual description of the answer, and a screen dump of the applet for extra credits.
- Part3) A modified player.java file, which contains the extended setVillage method and a short (less than half a page) explanation about the design of your player.
Please do not hesitate to contact Basca Cosmin if you have questions or remarks of any kind.