(i)     [12 marks]      Write down the full list of visited nodes (in order) when searching the graph  using the following algorithms. Where the algorithm does not define the order explicitly, the nodes should be visited in alphabetical order.

(a)  [6 marks]    Breadth-first search

(b)  [6 marks]    Depth-first search

(ii)    [8 marks]      Suppose we added another directed arc to the graph from D to A. Briefly

describe how this would affect your search when using:

(a)  [4 marks]    Breadth-first search

(b)  [4 marks]    Depth-first search

2       (20 marks)     Consider the following puzzle, which is commonly referred to as the Three Cups

Problem:

Consider the game in which three cups are placed on a table. The initial state of the game assumes all three cups are facing the right way up. Each move consists of selecting any two of the three cups and turning them upside down, so if the cup was facing up, it would face down, and vice versa. The game ends when all three cups are in a bottom-up position. The aim is to solve this with as few cup flips as possible.

(i)     [10 marks]      Define a problem representation for the three cups problem. Recall that a  problem representation consists of a state representation, initial state, goal test, successor function, and path cost.

(ii)    [6 marks]      Demonstrate that the game can never reach its goal state. You can do this either

by exploring the state space of the problem or by designing an appropriate heuristic function and studying its properties.

(iii)    [4 marks]      Suppose I decide to use A* search for a larger version of this problem with m   cups, define an admissible heuristic function that directly references some part of the problem representation (i.e. you cannot just specify h(n) = 0). Note that this does not need to be a   good heuristic, just needs to be an admissible heuristic for the problem.

3       (20 marks)     This question is about propositional and predicate logic.

(i)     [2 marks]      What is a model in propositional logic?

(ii)    [3 marks]      Consider the following formulae in propositional logic:

1.  a ^ b

2.  a ^ (¬a ∧ b)

3.  a ∧ ¬a

(a)  [2 marks]    Which of these formulae are valid?

(b)  [1 mark]    Which of these formulae are unsatisfiable?

(iii)    [5 marks]      Suppose we are using propositional logic with only the two symbols a and b. Use

inference by enumeration (of models) to show that a ∧ (a → b) ⊨ b

(iv)    [3 marks]      In fewer than 40 words explain what can be expressed in first-order logic that cannot be expressed in propositional logic.

(v)     [3 marks]      What is a model in first-order logic?

(vi)    [4 marks]      Consider the following formulae in first-order logic:

1.  2 = 3

2.  (AxP(x))  ⇐⇒   (¬3x¬P(x))

3. Ax Swan(x)  =⇒  White(x)

(a)  [2 marks]    Which of these formulae are valid?

(b)  [2 marks]    Which of these formulae are satisfiable?

4       (20 marks)     This question concerns adversarial tree search. Consider the following zero-sum game tree, T, where player Max is to move first and there are two possible actions for each  move: A, and B.

A

1      7      4      3

(i)     [15 marks]      Apply the minimax search algorithm to T. More specifically, define what the

minimax values are for each of the three game states, s1 . . . s3 .

(ii)    [5 marks]      Which move should Max make?

5       (20 marks)     Consider the following scenario, S:

The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American.

(i)     [10 marks]      Represent S in first-order logic.

(ii)    [10 marks]      Consider the following statement, P:

Col. West is a criminal.

Using your representation of S, apply backward chaining to infer the truth about P. Make sure you show the inference tree and final substitutions.

Question 1 (20 marks)       This question is about uninformed search. Consider the following graph:

Part (i) [12 marks]

Minor errors (subtract 1 mark each): missing one of the nodes.

Major errors (0 marks): getting nodes in the wrong order.

Sub-part (a) [6 marks]

[A,B,C,D,E,F,G]

Sub-part (b) [6 marks]

[A,B,D,E,C,F,G]

Part (ii) [8 marks]

Sub-part (a) [4 marks]

This would not affect the search, provided you recognise that you have already visited A. The search would still be optimal and complete. If you do not recognise that you have already     visited A, then the search tree would be infinite, and the corresponding search incomplete.

Sub-part (b) [4 marks]

This could introduce problems for DFS, as an infinite search tree is produced if repeated states are not detected. For the basic DFS (without detecting repeated states), the search is not      optimal or complete.

Question 2 (20 marks)       Consider the following puzzle, which is commonly referred to as the Three Cups Problem:

Consider the game in which three cups are placed on a table. The initial state of the game assumes all three cups are facing the right way up. Each move consists of selecting any two of the three cups and turning them upside down, so if the cup was facing up, it would face down, and vice versa. The game ends when all three cups are in a bottom-up position. The aim is to solve this with as few cup flips as possible.

Part (i) [10 marks]

There are other possible state representations. Provided these are accurate and the rest of the representation follows then marks should be awarded.

State representation: each state can be represented by a Boolean vector of size 3: S =< x,y,z >.

Initial state: x = y = z = False

Goal test: x ∧ y ∧ z = True

Successor function: Successor function can be defined as a series of actions with appropriate preconditions and postconditions. Actions in this case consist of flipping two cups, for example FLIP(x,y) would flip x and y. There are no preconditions in this case. The postconditions for FLIP(x,y) are as follows:

y\ = ¬y

x\ = ¬x

Path cost: number of cup flips made.

2 marks for each part of the problem representation.

Minor errors (subtract 1 mark): not specifying how the data is represented (i.e. a set of integers), or having a goal test which isn’t precise enough, for example.

Major errors (max 5 marks if 1 major error, max 2 marks if more than 1 major error): not specifying the preconditions, missing one of the components.

Part (ii) [6 marks]

Version 1:

Plot the state space: < F,F,F >← FLIP(x,y) → < T,T,F > etc. and show that the goal state is not reachable. (There will be only 4 reachable states incl. the initial state. Give 3 marks for each non-initial state complete with all steps/operators that use it as input (3 x 2 = 6 marks).

Version 2:

Define h(n) as the number of bits that need to be flipped to reach the goal state (2 marks), then show that every operator will change this value by either 2 or 0 (2 marks). As h(initial state)=3 (odd), h(n) will always remain an odd number, and therefore will never become zero (2 marks).

Part (iii) [4 marks]

One possible admissible heuristic could be to use the number of cups that are still facing up, h(n) = #(x|x = T ∧ x ∈ S). Any admissible heuristic should attract full marks. If they provide a heuristic that is not admissible, 0 marks.

Question 3 (20 marks)       This question is about propositional and predicate logic.

Part (i) [2 marks]

An assignment of a truth value to each propositional symbol.

Part (ii) [3 marks]

Sub-part (a) [2 marks]

None

Sub-part (b) [1 mark]

3

Part (iii) [5 marks]

There is only one model where a ∧ (a → b) holds, namely the one where both a and b are   true. Clearly b is true in this model. Students should show this by considering each of the 4   possible models and deriving the truth values for a and a → b and then a ∧ (a → b), in each of these models.

Part (iv) [3 marks]

In first-order logic we represent objects and relations and functions between them. Quantifiers and variables are used to express what holds for all or some objects satisfying given relations. Students can also mention that functions are represented.

Part (v) [3 marks]

It is a non-empty domain together with an interpretation. The interpretation maps: function symbols to functions; predicate symbols to set of tuples (of the appropriate arity) and constant symbols to domain elements. Full marks also available if constants recognised as zero-arity    function symbols.

Part (vi) [4 marks]

Sub-part (a) [2 marks]

2

Sub-part (b) [2 marks]

All

Question 4 (20 marks)     This question concerns adversarial tree search. Consider the following 

zero-sum game tree, T, where player Max is to move first and there are two possible actions for each move: A, and B.

A

1      7      4      3

Part (i) [15 marks]

s1 = 3

s2 = 1

s3 = 3

5 marks each for correct answers to s2 ,s3 , 5 marks for correct answer to s1 .

If s2 = 7, s3 = 4, and s1 = 4, award 7 marks (means they mixed up min and max).

Part (ii) [5 marks]

B

Question 5 (20 marks)       Consider the following scenario, S:

The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American.

Part (i) [10 marks]

...it is a crime for an American to sell weapons to hostile nations

American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z)  =⇒  Criminal(x)

Nono has some missiles

3xOwns(Nono,x) ∧ Missile(x)

Owns(Nono,M1 ) ∧ Missile(M1)

all of its missiles were sold to it by Col. West

AxMissile(x) ∧ Owns(Nono,x)  =⇒  Sells(West,x,Nono)

Missiles are weapons

Missile(x)  =⇒  Weapon(x)

Enemy of America counts as “hostile”

Enemy(x,America)  =⇒  Hostile(x)

West, who is American

American(West)

The country Nono, an enemy of America:

Enemy(Nono,America)

Any first-order representation of S is acceptable, provided it captures the information accurately. Subtract marks for missing any key information.