Assignment #2: Knowledge Representation


Assignment #2 consists of 2 parts: The first part is about the forward and backward chainng proving methods whereas the second part deals with knowledge representation. Total credit of this assignment is 100 points.

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

Due date: Mo 30.05.2006

Part 1: Forward and backward proof (20)


In the settler of catan game board, each field is associated with either wood or stones as resource, and the field is also associated with a random number between 2 and 12. Two dice are thrown to get a random number, which is the sum of the two dice. The player will get a unit of the resource from a field, if one of his/her village is next to this field and the random number associated with this field is equal to the random number produced by the dice.

James is a player, who has built a village. He has a village next to three fields. The first field is associated with random number 3 and has the resource 'wood'. The second field is associated with random number 7 and has resource 'stones'. The third field is associated with random number 8 and has the resource 'wood'. James throws the dice and gets the summed number of the dice as 7.



  1.  Write down the rule in first oder logic about how a player gets resource.
  2. Draw your forward chaining proof tree to prove that James gets stones.
  3. Draw your backward chaining proof tree to prove that James gets stones.

What to hand in

  1.  The fist order logic rule in paper.
  2.  The proof trees in paper.

Part 2: Knowledge Representation (80)


In Assignment 1 we played a really simple version of the settlers game.
This is what we do next:
We add some rules to the game according to the placement of villages.
The start phase remains the same. You get two villages for free and can set them at any position you want (if there isn't another village, of course)

For the rest of the game, the following rules apply:

- You have to set  new villages next to an existing village you own (at an adjacent position)

- You are not allowed to set your village next to an existing village your opponent owns

Your task is to implement those rules so that the players set their villages correctly.

Implementation notes

This is how to do it:

Build a knowledge base containing facts about the current game and the game rules. During the game,
infer new facts about legal positions for your next village.
So before setting a village, a player has to ask the knowledge base what positions are legal - and after setting a
village, the player has to update the base.

We made a new version of the game - it contains a new class KnowledgeBase. It can (and should) be used as a framework
for your knowledge base - you just have to make decisions about the design of facts and rules in
your KB and complete the code. See the code comments to get more information on where and how to do it.

Download the new version here.

Please note: this version will not work if you try to run it, because it's incomplete. The executable, complete code is what you have to do and hand in..

For an executable example of a knowledge base see below.

Consolidate your player from assignment 1 with this new version.

The reasoner we use is part of the "Jena Semantic Web Framework". Download Jena from
Find a simple example here we made to show you how to set up a  knowledge base in Jena and fill it with rules and facts - and infer new facts.
Find more information on the reasoner here.

Note that your player may not make the optimal choice using the heuristic function from assignment1, but it willl be
better than a random choice anyway. You don't have to update your heuristic function (but you are allowed to, of course...) If a player runs out of legal village positions, the other player wins, no matter what player owns more villages.

Note also that we kept the board class and other stuff that now could be handled by the knowledge base - we wanted to have some sort of "backward compatibility" for your heuristic functions.

BTW: Two of you guys seem to have met problems with the java random number generator we weren't able to reproduce (but we know it's not the best random number generation..) You may want to use a different random number generator (or install Java 1.5?)

What to hand in

Part I

1. The fist order logic rule in paper

2. The proof trees in paper.

Part II

1. Complete the code and implement the simple rules we added to the game. Hand in (email us) the working game using the knowledge base to infer legal village positions (two instancesof your player class playing against each other according to the rules).