CMPT 310 Artificial Intelligence Survey
Simon Fraser University Spring 2021
Instructor: Oliver Schulte
Assignment 1: Chapters 1, 2, Game Theory.
(Solutions)
NB: The clarity of your answers was considered when grading.
Chapter 1. AI Foundations. 21 points total.
1. (5 points) Consider these two statements.
• “Animals can do only what their genes tell them”. • “Therefore animals cannot be intelligent”
Is the first statement true, and does it imply the second?
The point of this exercise is to notice the parallel with the next one. Whatever you decide about whether computers could be intelligent in 2, you are committed to making the same conclusion about animals (including humans), unless your reasons for deciding whether something is intelligent take into account the mechanism (programming via genes versus programming via a human programmer). Note that Searle makes this appeal to mechanism in his Chinese Room argument (see Chapter 26).
2. (5 points) Consider these two statements.
• “Computers can do only what their programmers tell them”. • “Therefore computers cannot be intelligent”
Is the first statement true, and does it imply the second?
This depends on your definition of “intelligent” and “tell.” In one sense computers only do what the programmers command them to do, but in another sense what the programmers consciously tells the computer to do often has very little to do with what the computer actually does. Anyone who has written a program with an ornery bug knows this, as does anyone who has written a successful machine learning program. So in one sense Samuel “told” the computer “learn to play checkers better than I do, and then play that way,” but in another sense he told the computer “follow this learning algorithm” and it learned to play. So we’re left in the situation where you may or may not consider
learning to play checkers to be a sign of intelligence (or you may think that learning to play in the right way requires intelligence, but not in this way), and you may think the intelligence resides in the programmer or in the computer.
NB: For questions 1 and 2, you were given full grade if your reasoning about intelligence was consistent for both animals and computers or at least if you clearly explained that you assume the mechanism (genes vs computer) matters.
3. (5 points) For a given agent function, is there at most one agent program that implements a given agent function? If you answer “yes”, show why there is at most one agent program, or if you answer “no”, give an example of how there can be two or more.
The answer is “no” and you could provide any reasonable example. For instance, assume we are given an agent function whose actions only depend on the previous p percepts. One program can remember the previous p percepts to implement the agent function, while another could remember greater than p percepts and still implement the same agent function.
4. (6 points) Match the following concepts/statements with a discipline related to AI. Give your answer by filling in letters in the table provided. For example, if you think that “Statistics” best matches “Decision Theory”, put a “b” into the empty square next to “Decision Theory”.
a. Philosophy
b. Mathematics
c. Economics
d. Statistics
e. Psychology
f. Homeostasis
The mind operates according to rules.
a
Decision Theory
c
Laws of probability
d
Behaviourism
e
Computation Theory
b
Control Theory
f
Chapter 2. Agents. 14 points total.
4. a. (6 points) Fill in the table below for Watson to describe its environment when Watson plays Jeopardy. This question refers to Watson as we observed the system in the Youtube video. Briefly explain your answer.
Observable
Agents
Deterministic
Episodic
Static
Discrete
Observable
Agents
Deterministic
Episodic
Static
Discrete
Partially (don’t know what questions are hidden)
multi
Yes (answer is either right or wrong). Nondetermistic responses from other players
Yes Question by question. No if taking into account accumulated money from previous bets.
Semi
Time ticks down. Dynamic when other players may move first.
Yes
But potentially very large set of possible answers. (Could also be continuous if you consider bets as continuous, or probabilities as outputs).
4.b. (8 points) Specify a PEAS model for IBM’s Watson system.
Performance: winnings, coming first.
Environment: questions to solve, other players’ actions.
Actuator: output answers, amounts to bet on screen.
Sensors: reads questions via text message, sees other players’ bets.
Game Types. 10 points total.
Summary. Different payoff numbers can represent the same type of game. What matters is not so much the exact numbers, but qualitative relationships, like which numbers are bigger than others, what the equilibria and dominant strategies are. To transform a game matrix into another equivalent one, you can always change a player’s utility function u by a positive linear transformation: add constants or multiply by a positive number. For example, if u is the utility function of a rational agent, then the linear transformation
u’(x) = -5 + 3u(x)
defines a new utility function. If you can transform one game matrix into another using a
positive linear transformation, then they represent the same game.
1. (5 points) What type of game (i.e., BoS, PD, etc. – see lecture notes) does the following game matrix represent? Write down a positive linear transformation for each player that transforms the game matrix shown into the one shown in the lecture notes.
Solution: Prisoner’s Dilemma:
(ii) game matrix from lecture notes
Linear transformations that transform game matrix (i) into (ii):
– Row player: Ur’(x) = a*Ur(x) + b where Ur’(x) is the utility function for the row
player obtained from matrix (i) and Ur(x) is the utility function for the row player
obtained from matrix (ii).
Solve the linear system for constants a and b:
0 = a*(-1) + bèa = b 2 = a*(1) + bèb = 1 èUr’(x) = Ur(x)+1
– Column player: same reasoning as above èUc’(x) = Uc(x)+1
L
R
T
-1,-1
-3,1
B
1,-3
-2,-2
L
R
T
0,0
-2,2
B
2,-2
-1,-1
NB: you were given full grade if you explained the steps leading to finding the linear transformation.
2. (5 points) What type of game (i.e., BoS, PD, etc. – see lecture notes) does the following game matrix represent? Write down a positive linear transformation for each player that transforms the game matrix shown into the one shown in the lecture notes.
BoS (ii)
Linear transformations:
1) Row: Ur’(x) = a*Ur(x)+b
-1 a + b = 0àa = b
5 a + b = 2àa = 1/3 , b = 1/3
èUr’(x) = 1/3*Ur(x)+1
2) Col: Ur’(x) = a*Ur(x)+b 2a+b =2
-4 a + b = 0àa = 1/3 , b = 4 /3 àUr’(x) = 1/3*Ur(x)+4/3
Nash Equilibrium Analysis. 16 points.
Summary. Finding the Nash equilibria of a game is the first step in game-theoretic analysis.
1. (8 points) BoS: Find all deterministic Nash Equilibria, and at least one mixed Nash equilibrium.
L
R
T
2,2
-1,-4
B
-1,-4
5,-1
L
R
T
1,2
0,0
B
0,0
2,1
L
R
T
2,4
0,0
B
0,0
4,2
Sample Answer (not necessarily the solution):
[T,L] is the only deterministic Nash equilibrium. [p(T) = 1⁄2, p(L) = 1⁄2] is a mixed Nash equilbirum.
Reminder:
1. A pure or deterministic Nash Equilibria (NE) is a pure or deterministic pair of
strategies (s1, s2) such that s1 is a best response (maximizes payoff) against s2 and s2 is a best response against s1. In the case of a single move game, a pure strategy is a single action.
2. A mixed NE is a pair of mixed strategies that are each the best response to the other. A mixed strategy is a randomized strategy that selects actions according to a probability distribution.
BoS deterministic NE: (T, L) and (B,R)*.
If row player chooses T, best solution for column player is to choose L and vice versa. If row player chooses B, best solution for column player is R and vice versa.
*These are deterministic NE because if any player moves to a different strategy, that player will have a worst utility.
BoS Mixed NE:
– Mixed strategy for row player = p
– Mixed strategy for col player = q
– If row chooses T with probability p, the optimal strategies for Col are:
o Expected Payoff(L, p) = p x 4 + (1-p) x 0 = 4p
o Expected Payoff(R, p) = p x 0 + (1-p) x 2 = 2-2p
– According to the support theorem (if Col player randomizes, both L and R are equally good strategies):
o Payoff(L,p) = Payoff(R,p)ó2p = 1-póp = 1/3
o In any mixed equilibrium, row player chooses T or B with P(T) = 1/3 and
P(B) = 2/3
– If col chooses L with probability q, the optimal strategies for row are:
o Payoff(T,q) = q x 2 + (1-q) x 0 = 2q
o Payoff(B,q) = q x 0 + (1-q) x 4 = 4-4q – Support theorem:
o Payoff(T,q) = Payoff(B,q)óq = 2-2qóq = 2/3 èMixed NE is P(L) = P(B) = 2/3 and P(T) = P(R)=1/3
Lq
R (1-q)
Tp
2,4
0,0
B (1-p)
0,0
4,2
2. (4 points) The Game of Chicken (featured in movies “Rebel Without a Cause”, and “Charlie’s Angels”.). Two drivers are heading towards each other. Whoever turns away first, loses. A historical example is the Cuba crisis between the USSR and the USA.
a. (2) Find all deterministic Nash Equilibria.
b. (2) Find at least one mixed Nash equilibrium in the Game of Chicken.
Deterministic Nash Equilibria.
(Keep Going, Turn), (Turn, Keep Going)
Mixed Nash Equilibrium:
P(rowàKeep Going) = 3/19, P(colàTurn) = 16/19
NB: full grade if you explained the steps to find a deterministic and mixed NE.
3. (4 points) An issue that arises in technology industries is that an inferior standard may become entrenched even if a better one is available. A historical example is the use of VHS tapes vs. Beta. Or Facebook vs. GooglePlus? This illustrates network effects: users like to use technology used by others. Let’s consider a simple game-theoretic model of this situation.
a. (2) Find all deterministic Nash Equilibria.
b. (2) Find at least one mixed Nash equilibrium in this game.
Deterministic Nash Equilibria: These are cases where neither side randomizes, (Superior, Superior), (Inferior, Inferior)
Mixed Nash Equilibrium: When col randomizes, p = 1/3 When row randomizes, q = 1/3
NB: full grade if you explained the steps to find a deterministic and mixed NE.
Turn
Keep Going
Keep Going
3, 1
-15, -15
Turn
0, 0
1, 3
User 2
User 1
Superior technology
Inferior technology
Superior technology
3, 3
1, 1
Inferior technology
1, 1
2, 2
CMPT 310 Artificial Intelligence Survey
Simon Fraser University Spring 2021
Instructor: Oliver Schulte
Assignment 2: Chapters 4, 3, 5.
(SOLUTIONS)
NB: clarity of your answers is considered in the final grade.
Chapter 4. Local Search in Continuous Spaces.
26 points.
1.
a. (3) Write down the gradient (derivative) of the function you chose. (Hint: this
is probably easier for l.) !l=−(6− 4 )
!# #1−#
b. (10) Try to get close to the minimum in 5 gradient descent steps. Use as your initial guess p=1/2 (the coin is fair), and for the first 3 step sizes, use 0.04, 0.02, 0.01. The last 2 step sizes you can choose for yourself. For your answer fill in the table below.
step
p
step size
0
0.5
0.04
1
0.66
0.02
2
0.607
0.01
3
0.604
0.005
4
0.603
0.0025
5
0.603
Step size of 4 and 5 can be other reasonable values (e.g. both 0.1).
2.
a. (3) Write down the second-order gradient (derivative) of the function you
chose. (Hint: this is probably easier for l.)
!!+ = ( 6 + 4 !#! #! (1−#)!
)
b. (10) Show the results of 5 Newton-Raphson steps. Use as your initial guess p=1/2 (the coin is fair).
step
p
0
0.5
1
0.6
2
0.6
3
0.6
4
0.6
5
0.6
Chapter 5. Adversarial Search. 26 points totals.
1. (10) Draw the complete game tree, using the following conventions.
a. Write each state as (sA, sB), where sA and sb denote the token locations.
b. Put each terminal state in a square box and write its game value in a circle.
(1,4) (2,4) (2,3)
(1,3) (1,2) -1
(4,3)
0
2. (10) Now mark each node with its backed-up minimax value (also in a circle).
0 0 0
(1,3) (1,2)
(1,4) (2,4) (2,3)
-1 -1
(4,3)
0
3. (6) Suppose that we allowed repeated states and otherwise kept the rules the same. a. Describe the optimal strategy for each player (informally but precisely).
For Player A, she should keep herself moving in right direction. For Player B, she should keep herself moving in left direction.
b. Does the standard minimax algorithm terminate with a strategy for each player? If yes, does it find the optimal strategy (from part a)? If not, how could you modify the standard minimax algorithm so that it terminates after finding the optimal strategy for each player in this game? The modification should be general in the sense that the modified algorithm can be applied to any game tree, not just this game.
Standard minimax is depth-first and would go into an infinite loop. It can be fixed by comparing the current state against the stack; and if the state is repeated, then return a “?” value. Propagation of “?” values is handled as above. Although it works in this case, it does not always work because it is not clear how to compare “?” with a drawn position; nor is it clear how to handle the comparison when there are wins of different degrees (as in backgammon). Finally, in games with chance nodes, it is unclear how to compute the average of a number and a “?”. Note that it is not correct to treat repeated states automatically as drawn positions; in this example, both (1,4) and (2,4) repeat in the tree but they are won positions.
What is really happening is that each state has a well-defined but initially unknown value. These unknown values are related by the minimax equation at the bottom of 164. If the game tree is acyclic, then the minimax algorithm solves these equations by propagating from the leaves. If the game tree has cycles, then a dynamic programming method must be used, as explained in Chapter 17. These algorithms can determine whether each node has a well-determined value (as in this example) or is really an infinite loop in that both players prefer to stay in the loop (or have no choice). In such a case, the rules of the game will need to define the value (otherwise the game will never end). In chess, for example, a state that occurs 3 times (and hence is assumed to be desirable for both players) is a draw.
Other modifications, like using a iterative depth first search, are also acceptable.
CMPT 310 Artificial Intelligence Survey
Simon Fraser University Spring 2021
Instructor: Oliver Schulte
Assignment 4: Probabilistic Reasoning and Learning
Instructions: The university policy on academic dishonesty and plagiarism (cheating) will be taken very seriously in this course. Everything submitted should be your own writing or coding. You must not let other students copy your work. On your assignment, put down your name, the number of the assignment and the number of the course. Spelling and grammar count. You should show your work to get the result in order to get the full mark.
Group Work: Discussions of the assignment is okay, for example to understand the concepts involved. If you work in a group, put down the name of all members of your group. There should be no group submissions. Each group member should write up their own solution to show their own understanding.
For the due date please see our course management server https://courses.cs.sfu.ca. The time when you upload your assignment is the official time stamp. If your assignment is late because you did not figure this out soon enough, you will lose marks according to the syllabus policy.
Terminology: The questions are not self-explanatory. Even ordinary English words (e.g., “rationality”) may not have their ordinary meaning in an AI context. Part of your task is to learn the AI terminology required to understand the questions. You will likely not understand the questions if you have not studied the course material.
Getting Help. Check the syllabus for communication policy. You have the textbook, the lecture notes, the discussion forum, and you can ask us in office hours or class sessions. We do not provide individual email support.
Handing in the Assignment. Please use the submission system on courses.cs.sfu.ca. You should post
• a pdf document that contains your written answers, as well as the screenshots and diagrams required.
• A Bayesian network in executable file format (.xml or .bif), for the power station problem.
Probabilistic Reasoning With Bayesian Networks 75 points total.
Go to www.aispace.org and start the “belief and decision network” tool. Load the sample file “File/Load Sample Problem/Simple Diagnostic Example”. We will use this to test some of the basic probability laws. The AIspace tool can do many of these calculations for you, but the purpose of the exercise is to learn the principles behind the calculations. You can use the tool to check your answers, but you should compute them yourself using the probability calculus together with the conditional probabilities from the Bayesian network. If you have difficult running the tool in the browser, try downloading the jar file.
Joint probabilities
1. P(all nodes false)
= P(Influenza = F) * P(Smokes = F) * P(Sore Throat = F | Influenza =
F) * P(Fever = F | Influenza = F) * P(Bronchitis = F | Influenza = F and Smoke = F) * P(Coughing = F | Bronchitis = F) * P(Wheezing = F | Bronchitis = F)
= 0.95 * 0.8 * 0.999 * 0.95 * 0.9999 * 0.93 * 0.999
= 0.670051
2. P(Sore Throat = T, all other nodes false)
= P(Influenza = F) * P(Smokes = F) * P(Sore
Throat = T | Influenza = F) * P(Fever = F | Influenza = F) * P(Bronchitis = F | Influenza =
F and Smoke = F) * P(Coughing = F | Bronchitis = F) * P(Wheezing = F | Bronchitis = F) = 0.95 * 0.8 * 0.001 * 0.95 * 0.9999 * 0.93 * 0.999
= 0.000671
3. P(all nodes others than Sore throat false) = P(Sore Throat = T, all other nodes false) or P(Sore Throat = F, all other nodes false) = P(Sore Throat = T, all other nodes false) + P(all nodes false)
= 0.670051 + 0.000671 = 0.670722
4. P(Sore Throat = F | all other node are false) * P(all other nodes are false) = 0.999 * 0.670722
= 0.670051
= P(all nodes false)
5. P(Sore Throat = T, Fever = T)
= P(Sore Throat = T | Influenza = T) * P(Fever = T | Influenza = T) P(Influenza = T) + P(Sore Throat = T | Influenza = F) * P(Fever = T | influenza = F) * P(Influenza = F)
= 0.3 * 0.9 * 0.05 + 0.001 * 0.05 * 0.95
= 1.35475 * 10^(-2)
Independence
20 points
“If no evidence is observed, Influenza and Smoking are probabilistically independent.”
1. (10) Prove this statement from the numerical semantics, i.e. show that the values of Influenza and Smokes are independent for all possibilities. You may use queries in the tool to do this.
Influenze
TRUE
TRUE FALSE FALSE
Smoking product
TRUE 0.01 FALSE 0.04 TRUE 0.19 FALSE 0.76
joint
0.01 0.04 0.19 0.76
i. Must check all possible values of joint.
Checking the equivalent of P(A)=P(A|B) is also acceptable.
2. (10) Prove this from the topological semantics, i.e. using the Markov condition that given values for its parents, a variable is probabilistically independent of all its nondescendants.
Neither has a parent, so the condition holds vacuously. Neither is a descendant of the other, so they are independent.
Bayesian Networks and Constraints (30 points total)
In a power station, an alarm senses when a temperature gauge exceeds a given threshold. The gauge measures the temperature of the core. Using the AIspace tool, draw a Bayesian network that represents the following information about the plant. You may consider editing your Bayes net in a text editor to facilitate copying of similar entries.
1. (5 points) Create a Bayes net with the following variables (=nodes) and domains. Each domain represents a range of possible locations.
The graph should look like this
2. Draw edges between the nodes and specify conditional probability tables to represent the following information.
a. (6) The alarm works correctly unless it is faulty. If it is faulty, it never sounds.
V ariable
Domain
Meaning
A
{T,F}
alarm sounds
FA
{T,F}
alarm is faulty
FG
{T,F}
gauge is faulty
G
{Normal, High}
gauge reading
T
{Normal, High}
core temperature
b. (6) If the gauge is not faulty, there is a 90% chance that it gives the correct temperature. If the gauge is faulty, there is a 10% chance that it gives the correct temperature.
c. (10) Suppose the alarm and gauge are working correctly and the alarm sounds. Using the probability calculus probability, and the various conditional probabilities in the network, calculate the probability that under these circumstances, the temperature of the core is high. You can make the following assumptions. (i) The temperature is normal 70% of the time, high 30% of the time. (ii) The gauge is faulty 10% of the time, not faulty 90% of the time.
Since the gauge is not faulty, and the alarm is true, we know that the gauge must be high(G=H).
Moreover, given gauge=high, from the Bayes net, we can conlude that alarm and faulty alarm is conditional independent to the temperature and faulty gauge.
P (T= High | A = True, FA = False, FG = False. G = High)
= P (T= High | FG = False, G = High)
= P (T= High, FG = False, G = High) / P (FG = False, Gauge = High)
Now P (FG = False, Gauge = High) =
P (T=High, FG = False, Gauge = High) + P (T= Normal, FG = False, Gauge = High) = ((0.9*0.3*0.9) + (0.7*0.9*0.1)
So P (T= High, FG = False, G = High) / P (FG = False, Gauge = High) = (0.3*0.9*0.9) / ((0.9*0.3*0.9) + (0.7*0.9*0.1)
= 0.243/ (0.243 + 0.063) = 0.243/0.306
P (T=high, FG = False, G = High) = 0.79411764711
d. (3) Use the AIspace query tool to confirm your answer from c.
According to our solution for c), you can use any estimate you like for the
prior P(FA=T), e.g. 50% or 80%. We suggest experimenting with the tool to verify that you get the same result as c) no matter what prior value you use. e.
Difference to textbook 14.11: no edge from T to FG. Extra parameters are specified in the problem.
What to Submit for this question. Everything specified in the problem, including answers and brief explanations. In addition: A loadable .xml or .bif file for your Bayesian network in part 1. A screenshot of your Bayesian network, screenshots of your CP-tables, and a screenshot of your query and the answer from AIspace.