**UNIVERSITY EXAMINATIONS: 2017/2018**

**EXAMINATION FOR THE DEGREE OF BACHELOR OF SCIENCE IN **

**APPLIED COMPUTING**

**BAC4202 ARTIFICIAL INTELLIGENCE FOR GAMES**

**FULL TIME/PARTTIME**

**DATE: APRIL 2018 TIME: 2 HOURS**

**INSTRUCTIONS: Answer Question One & ANY OTHER TWO questions.**

**QUESTION ONE**

(a) Describe the meaning of the term ‘Artificial Intelligence (AI) for games’ in the context of

artificial intelligence for games (2 Marks)

(b) Artificial intelligence (AI) for games model is divided into three sections. Describe each of

these sections (2 Marks)

(c) Describe the meaning of the following terms as used in artificial intelligence for games.

Give one example in each case

(i) Intelligent agents (2 Marks)

(ii) Utility (2 Marks)

(d) Describe three major assumptions in games (3 Marks)

(e) Briefly explain three differences between searching and games (3 Marks)

(f) Describe any four types of games. Give one example in each case (4 Marks)

(g) There are three key elements for implement AI for Games. Describe each of these elements

(3 Marks)

(h) Briefly explain five roles of artificial intelligence Techniques in Games (5 Marks)

(i) State and explain two AI for games approaches (4 Marks)

**QUESTION TWO**

a) Briefly explain the following terms as used in artificial intelligence for games. Give one

example for each case

(i) Zero sum game (2 Marks)

(ii) Heuristics (2 Marks)

(iii) Hacks (2 Marks)

(b) Consider the following Payoff matrix for prisoner’s dilemma

(i) Describe four possible outcomes for actions taken by both agents and their respective

rewards. (4 Marks).

(ii) Explain the meaning of the term nash equilibrium. Identify strategies that are in nash

equilibrium in prisoners’ dilemma. Justify your answer (4 Marks).

(iii) Identify the dominant strategy in prisoners’ dilemma. Justify your answer (2 Marks).

c) Given the following 8-puzzle, define the problem as a search problem in terms of states,

operators, a goal test and a path cost. (4 Marks)

**QUESTION THREE**

(a) A farmer and his wolf, goat, and cabbage come to the north side of a river that they wish to

cross. There is a boat, but it has only room for two, and the farmer is the only one that can cross

alone If the goat and the cabbage are left alone together, the goat will eat the cabbage. Similarly, if

the wolf and the goat are together without the farmer, the goat will be eaten.

i. Devise a series of crossings of the river so that all concerned make it across safely (4 Marks)

ii. Define the search problem (3 Marks)

iii. Use a graph to represent the search problem (3 Marks)

(b) Briefly explain reinforcement learning. Use a diagram to illustrate your answer (2 Marks)

(c) Describe one application of how reinforcement learning can be used in game theory

(2 Marks)

(d) Consider a building with five rooms connected by certain doors as shown in the figure below

Where A to E is rooms inside the building while F represent outside the building. There are

two doors leading to the building from F, that is through room B and room E.

(i) Use a state diagram to represent the scenario. (2 Marks).

(ii). Suppose you put an agent in any room, and you want the agent to go outside the building

the doors that lead immediately to the goal have instant reward of 100 and other doors that do

not have direct connection to the target room have zero reward. Draw state diagram to

represent the problem indicating rewards for each movement made by the agent. Identify any

absorbing goal state and justify your answer (4 Marks)

**QUESTION FOUR**

(a) Briefly explain four types of agents’ environments (4 Marks)

(b) State and explain any four characteristics of an intelligent agent (4 Marks)

(c) Briefly explain three ways in which intelligent agent is different from other software?

(3 Marks)

(d) Many matatus in Nairobi have drivers and conductors (manambas). The two work together.

Lets assume that both are intelligent agents. (the setting is before 2003, before the new psv

regulations were affected)

Fill-in the table below for the conductor (manamba) (4 Marks)

e) Given the following search tree, apply the alpha-beta pruning algorithm to it and show the

search tree that would be built by this algorithm. How many nodes did you not have to visit With

alpha- beta pruning when compared to the full MIN-MAX search ? Show all intermediate values

at each node as they get updated including where the alpha and beta cuts are applied. Give the

number of nodes that (5 Marks).

**QUESTION FIVE**

(a) Briefly describe the following terms as used in artificial intelligence for games. Give an

example for each case

(i) Path finding (2 Marks)

(ii) Directed costed graph (2 Marks)

(b) Consider the following graph

Find the in-Degree of v1, out-degree of v3 and degree of v2 in the above a graph (3 Marks)

c) The following figure shows a MIN-MAX game tree. Cross out the branches that are pruned by

alpha-beta pruning and determine the number of nodes that you did not have to visit with alphabeta pruning when compared to the full MIN-MAX search. Show all intermediate values at each

node as they get updated. (4 Marks)

(d) Show how the following search algorithms can be implemented using appropriate pseudo code

(6 Marks)

i) Breath-First-Search

ii) Depth-First-Search

(e) Consider the search tree below

(Assuming F is the Goal node, show at each step what nodes are in the queue for Depth-FirstSearch (3 Marks)

5 8 6