Assignment #2: Knowledge Representation & Logic


Assignment #2 consists of 2 parts: The first part is about logic and logical proofs whereas the second part deals with knowledge representation. Total credit of this assignment is 100 points. 

Due date: Tue April 20th, 2010


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}, 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_A2.


Paper solutions must be handed in in the lecture hall before the lecture on due date.

Programs and Source Code must be submitted by eMail to Cosmin Basca latest until 2 pm, due date.

Part 1: Logic (30)


Part 1a   (15)

Given the following clause forms, prove whether there exists an x ∈ {John, Mike, Tom} that satisfies both Climber(x) and ¬Skier(x)? If it exists, who is x?

  1.  Alp(Tom)
  2.  Alp(Mike)
  3.  Alp(John)
  4.  ¬Alp(x) ∨ Skier(x) ∨ Climber(x)
  5.  ¬Skier(x) ∨ Like(x, Snow)
  6.  ¬Climber(x) ∨ ¬Like(x, Rain)
  7.  ¬Like(Tom, y ) ∨ ¬Like(Mike, y )
  8.  Like(Tom, y ) ∨ Like(Mike, y )
  9.  Like(Tom, Rain)
  10.  Like(Tom, Snow)


What to do:

  1. Write down your proof step by step and say in each step which clause you've applied.
  2. Hand in the paper.



Part 1b   (15)

The unicorn is a mammal if it is horned. If the unicorn is either immortal or a mammal, then it is horned.
If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal.

What to do:

  1. Encode these statements in propositional logic.
  2. Use resolution to prove that the unicorn is a mammal.
  3. Hand in the paper solution of 1. and 2.



Part 2: Knowledge Representation (70)


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


What to hand in

Part I

1. The fist order logic rules 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 the working game using the knowledge base to infer legal village positions (two instances of your player class playing against each other according to the rules).

Create an archive (.zip or .tgz) of your project directory including source code and submit this by eMail to Cosmin Basca