BAC4202 ARTIFICIAL INTELLIGENCE FOR GAMES.
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
BAC4202 ARTIFICIAL INTELLIGENCE FOR GAMES. Read Post »