Assignment #3:Probabilistic reasoning


Assignment #3 consists of 2 parts: 

The first part is about information retrieval.

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

Total credit of this assignment is again 100 points.

To be admitted to the final exam, you have to reach at least 50% of the points in each assignment.

Please note the due date. You have two weeks to do the assignment so there is time enough to give you some feedback before the final exam.

Because of the limited time, you are allowed to hand in the assignment 3 in teams of two (maximum 3) persons.

Due date: Mo 20.06.2007

Part 1: Information Retrieval (30)


1. Rank the following by decreasing similarity using cosine similarity and TFxIDF weighting:

- Two documents that have only frequent words (such as "the", "a", "an", and "of") in common.

- Two documents that have no words in common.

- Two documents that have many rare words in common.

2. What is the IDF value for a term that appears in all documents?

3. Which of the following have identical bag-of-word representations?  Which are different?

(1) He moved from London, Ontario, to London, England.

(2) He moved from London, England, to London, Ontario.

(3) He moved from England to London, Ontario.

What to hand in

The answers in paper.

Part 2: Probabilistic reasoning (70)


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 fist order logic rule in paper

2. The proof trees in paper.

Part II

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