Assignment #3 consists of 3 parts: 

The first part is about decision trees.

The second part deals with Bayesian networks.

In the third part you have to solve another pen and paper exercise and to add some probabilistic reasoning to your settlers-player

Total credit of this assignment is again 100 points.

Due date: Tue May 13th, 2008

What and how to hand in :

Paper solutions for all pen and paper assignments have to be handed in before the lecture on May 13th in the lecture hall. eMail-only submissions can only be accepted if there are serious reasons for not handing in a paper version (e.g. sickness)

The archive (*.zip or *.tgz) of your complete and buildable project sources (complete because this time we leave you a lot of modification options) has to be submitted by eMail to Cathrin Weiss latest by 2 PM on May 13th.

If you submit any written answers by eMail, make sure that the files are in pdf format.

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

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.

a) Pen and Paper (10) :

Imagine that 99% of the time RE Disease (RED) causes red eyes in those with the disease, at any point in time 2% of all people have red eyes, and at any point in time 1% of the population has RED.
 
You have red eyes.  What is the probability you have RED?

Put down your complete calculations.

b) Programming (60) :

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 disappear.

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

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 behavior, you are free to change it.

- We changed the number of villages you need to win to 15.