Assignment #3 consists of 2 parts: 

The first part is about decision tree.

In the second part you add some probabilistic reasoning to your settlers-player

Total credit of this assignment is again 100 points.

You are allowed to hand in the assignment 3 in teams of two persons.

Due date: Di 12.06.2007

The goal of this exercise is to get familiarized with decision tree. Therefore a simple dataset about wether to go skiing or not is provided. The decision of going skiing depends on the attributes snow, weather, season, and physical condition as shown in the table below.

a) Build the decision tree based on the data above by calculating the information gain for each possible node, as shown in the lecture. Please hand in the resulting tree including all calculation steps. (20)

Hint: There is a scientific calculator on calculator.com for the calculation of log2(x). By the way: log2(ax)=log10(ax)*log2(10) or log2(ax)=ln(ax)*log2(e).

b) Decide for the new instance given below whether to go skiing or not, based on the calculated classifiers: (5)

c) Now, an instance including missing values has to be classified (use the classifier built on the original data set): (5)

Decide whether to go skiing or not.

Introduction

In the final extension of our "settlers"-game you will use some probabilistic reasoning.

We added three "hidden treasures" (they don't exist in the actual board-game, we know...)

Your task is to update your player with some probabilistic reasoning about where treasures are based on hints you get from the board (= flags that say: "treasure near here!")

The problem is very similar to the one described in Section 13.7 of the book. ("The wumpus world revisited", p.483-486)

Some positions on the board contain a hidden treasure. If you set a village on a "treasure-position", you get two points for free (=your village count will be incremented by two, but - to keep it simple - you won't get the villages on the board). In other words: if you have e.g. eleven  villages and have discovered two treasures, you have 15 points (your village count variable is 15).

All fields bordering to a position containing a treasure have a flag.

(Note the difference between "positions" - where you can set your villages - and "fields" -  the  fields containing resources)

You can see if a field contains a flag if you have at least one village bordering to the field.

Use the flags to reason about where  treasures could be and consider the new knowledge in your setVillage() method.

Implementation notes

We made some changes to the Board, the SettlerView and the Controller class.

Update those classes in your current version from assignment two.

Download the new Version here.

To reuse you Player  from former assignments, you need to do one small change in your player-class:

Please change the  setVillage(int stage) from void to return type int ("public int setVillage(int stage)") and return the position where you set your village in the method ("Village_ID") - the controller class needs this information to decide if you got a treasure.

The board class now contains a new method getFlagLocation(int player_id) that returns an array with all the flag information currently visible to the player. The array has a fixed length of 19 - each array position represents a field. If the field contains a flag, the corresponding array entry is the constant "2000", if not, "2001" (see code).

The board class also contains a method numUndiscoveredTreasure() that returns the number of undiscovered treasures.

If a treasure is discovered, the corresponding flags will dissapear.

For your convenience we paint the visible flags for both players on the board.

In your code, you are not allowed to use the flag location your opponent sees (= to use the method above with your opponents player_id in the argument) and of course you are not allowed to use the getTreasureLocation() method in the board class (this would be a little bit too easy :-) )

A good approach to find the three treasures may be to add just another weighting to your heuristic function from assignment 1 based on the "treasure-probability".

Please read "the wumpus world revisited" on pages 483-486 in the Russel/Norvig-book to see a good but maybe quite complex solution to a very similar problem

There may be simpler solutions that are not as good but we accept as well as your time to finish this assignment is shorter than usual.

Please comment your code so we can understand what you did.

BTW: Of course, the rules from assignment two still apply.

 Please also note the following:

-If you find a treasure by setting a village in the start phase , you wont get the two free villages.  If you don't like this behaviour, you are free to change it.

- We changed the number of villages you need to win to 15 - mainly because the current code get's into trouble if your player runs out legal positions when setting free villages. This is quick an dirty, but we didn't want to make big changes...

What to hand in

Part I

1. The decision tree in paper

2. The answer for b) and c) in paper.

Part II

1. Email us the complete code of your new working version.