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

UBC-Search Applet

(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)

Introduction

We start with a simple game that is not completely but nearly dissimilar from the famous board game "The settlers of catan". Your task is to create a player which is able to beat our quite randomly acting player.
Below you can see the game board.
The main goal of the game is to build villages. To win the game, you have to build 27 villages. (Of course you can play the game with another number of villages you need to win)
At the start phase of a game, each player gets two villages for free and can set them on the game board (there are 54 possible positions - see the small black dots).
To buy more villages, you need resources: a villages costs 2 wood-units and 2 stone-units.
Here is how you get resources: Each turn, two dices are rolled. If one of your villages is next to a field that shows the same number as the two dices show (their sum, actually), you get 1 resource unit. If it's a green field you'll get wood, if it's a grey field you'll get - guess what - stone. If you have two villages next to the field you'll get two units - and so on.
As soon as you have at least two units of wood and two units of stone, the computer buys a village for you - and you set it at a nice positon with high probability to get resources.
So basically your task is to set villages - write a setVillage()-method in the Player class that ist better than our method. Have a look at the code to get more detailed information.

: The game board

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.