Introduction

As announced assignment # 1 consist of 3 parts: a self-explorartory on-line 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: Di 24.4.2007

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: STRIPS (20)

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)

Please note:

We found that the current version of applet only has limited number of predefined constraints, which make it unsuitable for our sudoku puzzle. Please feel free to skip Part 2b (c). Sorry for inconvenience.

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. If you hand in a correct solution of the problem(screen-dump/output of the applet) you'll get 5 bonus points.

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:

b) 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.
c) A screen-dump/output of the applet if you want 5 extra points....

Part 3: Programming a "Settlers"-Player (80)

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 SettlerAssignment1.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 Jiwen Li if you have questions or remarks of any kind.