1. Adversarial Search

Consider the following 2-player game:

The game begins with a pile of 5 matchsticks.

The players take turns to pick matchsticks from the pile.  They are allowed to

pick 1, 2, or 3 matchsticks on each turn.

The game finishes when there are no more matchsticks remaining in the pile. Each matchstick is worth 1 point.

The player who picks the last matchstick from the pile loses 5 points.

The goal of the game is to get the maximum number of points compared to your

opponent.

The state of the game at any given time can be described using the notation a-n-b where a is the number of sticks the first player (i.e. the player who goes first) has, n is the number of sticks remaining in the pile, and b is the number of sticks the second player has. This means the initial state of the game is 0-5-0.

When performing search, always use the following ordering for the actions at any given state:  the action of taking 3 sticks should be considered first, then the action of taking 2 sticks, then the action of taking 1 stick.

(a) Fully characterise the intelligent agent environment for this game based on

the criteria introduced in the lectures.                                                              [3 marks]

(b) Draw the full game tree. Clearly mark the players acting at each level or at

each node of the tree.  You are suggested to leave enough space in the page for a maximum of 16 nodes in width and 8 nodes in depth to ensure that the

tree will fit.                                                                                                         [6 marks]

(c)  Calculate integer utility values of the leaf nodes of the tree based on the point system of the game.  Assume the first player is MAX. Add the utility

values to your game tree in circles next to their respective leaf nodes.            [3 marks]

(d)  Calculate the MrNrMAx values of all of the nodes in the game tree. Add these values to your game tree in squares next to their respective nodes (excluding

the leaf nodes).                                                                                                   [2 marks]

(e) According to the MrNrMAx algorithm, what is the optimal action for MAX

when the game starts and why?                                                                        [1 mark]

(f)  Consider the ALPHA-BErA-SEARcH algorithm as presented in the lectures.

How many search nodes will be pruned by α–β pruning? Mark those nodes putting an X next to them in your game tree. Explain why these nodes are

pruned, giving the corresponding α or β value at that point.                          [6 marks]

(g)  Give the order of nodes that will be visited by the ⅠrERArrvE-DEEPENrNG-SEARcH

algorithm when searching for state 2-0-3.                                                        [4 marks]

2. First-Order Logic

Consider a Knowledge Base of a logical agent comprising the following sentences in First-Order Logic:

Knowledge Base:

Ax, y, z . P (y, z) A P (x, y) ÷ G(x, z)                           (1) Ax, y . P (x, y) ÷ F (x, y) V M (x, y)                             (2) Ax, y . F (x, y) ÷ P (x, y)                                              (3) Ax, y . F (f (x), x)                                                         (4) Ax, y, z . S(x, y) A G(z, y) ÷ L(x, z)                            (5) 3x. S(R, x)                                                                  (6)

(a) Does this Knowledge Base belong to the class of Datalog knowledge bases?

Explain your answer giving all the reasons that apply.

(b)  Give a model of the Knowledge Base from a domain of your choice.

(c)  Consider the following sentence:

3x. G(x, R) ÷ L(R, x)

Explain the meaning of this sentence in the interpretation you gave for part (2b) using at least one example of an object representing x.

(d)  Give the existential instantiation rule and apply it to sentence (6) in the Knowledge Base. Explain the result in detail.

(e)  Give the most general unifier for the following pairs of terms. For full marks,

show all of the steps made by the FOL unification algorithm:

i.  S(x, R)

ii.  S(f (x), z)

iii.  S(f (x), g(y))

    S(R, x)

    S(z, f (y))

    S(z, z)

(f)  Consider the following query:

L(R, x)

Give a backward chaining proof to provide a binding for x that answers the query.  The proof should be provided in the form of a full proof tree.  Use the Knowledge Base provided above, but replace  (6) with the result you obtained from part (2d).  Mark every node of the tree with the rule that was used and the resulting unifier.

3. Decision Making

A rational agent R must choose between two lotteries, the outcomes of which depends on which colour ball is picked from a jar:

Lottery A: If the chosen ball is red, then you win f1 with probability p and

f0 with probability (1 _ p). If, on the other hand, the chosen ball isn’t red, then you are certain to get f0.

Lottery B: If the chosen ball is red, then you are certain to win f0. If, on the

other hand, the chosen ball isn’t red, then you win f1 with probability q and f0 with probability (1 _ q).

(a)  Suppose that R doesn’t know how many balls are in the jar, nor which

colours they are. Define the expected utility of lottery A and lottery B.         [6 marks]

(b)  Suppose that p and q are such that the agent R is indifferent between lot-

teries A and B and suppose further more that R always chooses an action that maximises R’s expected utility.  Then using the definition in part (a), define what R must believe the probability of picking a red ball from the jar must be in terms of (only) p and q . Be sure to show all the workings in

your answer.                                                                                                       [10 marks]

(c) Now suppose that there are  10 balls in the jar;  4 are red and 6 aren’t. Furthermore, suppose R is indifferent between lotteries A and B. Then define

p in terms of q .                                                                                                   [3 marks]

(d) Now consider an irrational agent I .   I has a choice between 3 lotteries: lotteries A and B as defined above with p = q = 1, and lottery C:

Lottery C: You win £1 with probability 0.5 and £0 with probability 0.5

I prefers lottery C to both lotteries A and B. Show that I cannot be max-

imising expected utility, whatever the values of U(£1) and U(£0).                 [6 marks]