 |
ARI711S - ARTIFICIAL INTELLIGENCE - 2ND OPP - JULY 2022 |
|
|
1 Page 1 |
▲back to top |
nAmlBIA UnlVERSITY
OF SCIEflCE AnD TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF COMPUTERSCIENCE
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE
QUALIFICATION CODE: 07BACS
COURSE: ARTIFICIAL INTELLIGENCE
DATE: JULY 2022
DURATION: 3 HOURS
LEVEL: 7
COURSE CODE: ARl711S
PAPER: THEORY
MARKS: 75
SECOND OPPORTUNITY/ SUPPLEMENTARY EXAMINATION QUESTION PAPER
EXAMINER{S)
MODERATOR:
Prof. JOSE QUENUM
Mr STANTIN SIEBRITZ
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 3 PAGES
(Excluding this front page)
PERMISSIBLE MATERIALS
CALCULATOR
|
|
2 Page 2 |
▲back to top |
ARl711S
First Exam (continued)
June 2022
Question 1 ..................................................................
[20 points]
The diagram in Figure 1 represents an adversarial game. Using the o:- (3pruning, solve the
game. You will indicate the values of o:and (3at each node and where pruning occurs.
Figure 1: Adversarial Search Problem
Question 2 ..................................................................
[35 points]
1
1
3
2
3
2
(a)
(b)
Figure 2: a: Initial configuration; b: Goal configuration
(a) The diagram in Figure 2a represents a grid. It contains four tiles, including an empty
[12]
one. Each tile is located with row and column numbers and may contain a value. For
example, the tile in row 2 and column 1 contains the value 1. In this problem, we wish to
rearrange the tiles in the grid using a planning approach. The planner can execute four
possible actions:
• left: moving the empty tile to the left;
• right: moving the empty tile to the right;
• up: moving the empty tile up;
• down: moving the empty tile down.
Note that these actions can only be executed when possible. Note also that when moving
the empty tile to a new location, it swaps its location with the one it is replacing. We
provide the following predicates to represent the knowledge base:
• above(x, y): tile xis located immediately above tile y;
• is - left(x, y): tile xis located at the left of tile y
• is - empty(x): tile xis empty;
• value(x, y): tile x has value y;
Page 1 of 3
Please turn over to the next page...
|
|
3 Page 3 |
▲back to top |
ARl711S
First Exam (continued)
June 2022
• coord(x, y, z): tile xis located at row y and column z.
Following the STRIPSnotation, define the actions as operators for the planner.
(b) Express the goal (in Figure 2b) as a well-formed formula.
[5]
(c) Using the Manhattan distance between tiles (the sum of the absolute values of the row
[18]
difference and column difference) as a heuristic and the number of steps as path cost,
generate the plan using the A* search strategy. You will explicitly indicate the evaluation
step-by-step during the plan generation.
Question 3 ..................................................................
[20 points]
The Millionaire is your favourite TV show. It is a ten-round game. Except for the first round,
the player can choose to play or quit at each round. When the player quits, the game ends,
and s/he can collect the rewards that s/he has earned so far. When the player plays, s/he
can succeed and move to the next round or fail, leading to the end of the game. Note that
s/he loses all the rewards s/he has accumulated so far in the event of a failure. Note also that
when the player reaches the last round, whether s/he plays or not the game ends with the
appropriate reward.
Model this problem as a Markov Decision process and find the optimal policy using the value
iteration approach. You will indicate the utility values during each iteration. You will use a
discount factor of 0.95.
Table 1: Millionaire - Rewards and success probability
Round Success Probability
1
0.99
2
0.9
3
0.8
4
0.7
5
0.6
6
0.5
7
0.4
8
0.3
9
0.2
10
0.1
Reward
10
50
100
500
1000
5000
10000
50000
100000
500000
Question 4 ..................................................................
[18 points]
(a) Company Z operates near a river which it pollutes. This has harms the fishermen who
[8]
fish from the river. Company Z's profit is P. Normally, the fishermen get a profit of A.
However, with the negative effect on the river, they now lose Ao (A > A0) from their
profit. The fishermen and Company Z engage in litigation. Both teams will simultane-
ously indicate an amount. For Company Z, the amount represents their claim about the
company's profit, while for the fishermen, the amount represents their profit loss. If
the company's profit is less than the fishermen's lost profit, Company Z will shut down.
Otherwise, it will pay a settlement to the fishermen corresponding to their lost profit
Page 2 of 3
Please turn over to the next page...
|
|
4 Page 4 |
▲back to top |
ARl711S
First Exam (continued)
June 2022
claim. Represent the strategic form of the game, describing the strategies and the payoff
functions. Is it a dominant strategy for the fishermen to choose their actual loss? Why?
(b) Consider the game represented in Table 2. Determine the values of a 1 and /31 such that
[10]
of¥ the mixed strategy with Player 1 playing the strategy a0 with a probability of½ and Player
2 playing the strategy b0 with a probability
is a Nash equilibrium.
Table 2: Game Board
Player 2
ao 2, 2
Player 1 a1 6,2
Page 3 of 3
End of Exam