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
