Introduction
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 18th, 2010
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 Cosmin Basca latest by 2 PM on May 18th.
If you submit any written answers by eMail, make sure that the files are in pdf format.
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_a3.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_A3.
Part 1: Decision Trees (20)
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.
snow | weather | season | physical condition | go skiing |
sticky | foggy | low | rested | no |
fresh | sunny | low | injured | no |
fresh | sunny | low | rested | yes |
fresh | sunny | high | rested | yes |
fresh | sunny | mid | rested | yes |
frosted | windy | high | tired | no |
sticky | sunny | low | rested | yes |
frosted | foggy | mid | rested | no |
fresh | windy | low | rested | yes |
fresh | windy | low | rested | yes |
fresh | foggy | low | rested | yes |
fresh | foggy | low | rested | yes |
sticky | sunny | mid | rested | yes |
frosted | foggy | low | injured | no |
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)
snow | weather | season | physical condition | go skiing |
sticky | windy | high | tired | ? |
c) Now, an instance including missing values has to be classified (use the classifier built on the original data set): (5)
snow | weather | season | physical condition | go skiing |
- | windy | mid | injured | ? |
Decide whether to go skiing or not.
Part 2: Bayesian Networks (10)
Consider the Bayesian Network below, where variables A-D are all Boolean-valued.
a) What is the probability that all four of these Boolean variables are false?
b) What is the probability that C is true, D is false, and B is true?
It is not sufficient to just put down the final result. Show your calculations!
Part 3: Probabilistic reasoning (70)
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.