COS 3751
ASSIGNMENT 2
SOLUTIONS
2022
1
,Table of Contents
Question 1............................................................................................................4
(1.1) Define the concept of a zero-sum game as we study it in AI..................4
(1.2) Clearly explain what a utility function is, and why it is used during
adversarial searches........................................................................................4
(1.3) Define the utility function for a game of tic-tac-toe. Provide the
algorithm for this utility function and provide an example of the result of
applying your function to a terminal state in the game tree...........................4
(1.4) Explain how forward pruning works. Provide at least one approach to
forward pruning in your explanation, as well as a problem that may be
encountered with forward pruning..................................................................5
(1.5) Does the order in which nodes are examined in minimax matter?
Explain your answer.........................................................................................6
Question 2............................................................................................................7
(2.1) Consider Figure 3 and answer the questions that follow. (The utility
value of the leaf nodes are provided in brackets in the leaf node.)................7
(2.2) Explain what the horizon effect is. Provide an example that clearly
explains this phenomenon. Use diagrams to assist your discussion.............11
Question 3..........................................................................................................12
(3.1) Provide a First-order Logic (FOL) vocabulary for the sentences..........12
(3.2) Using your vocabulary, translate the sentences in FOL........................12
(3.3) Convert the statements obtained in (5.2) into clausal form. Variables
must be standardized.....................................................................................13
(3.4) Use resolution refutation to prove that John is happy...........................13
Question 4..........................................................................................................14
(4.1) Define the Least Constraining Value (LCV) heuristic............................14
(4.2) Explain why establishing strong k-consistency is a problem................14
(4.3) Define the degree heuristic...................................................................15
(4.4) If no legal assignments for a variable remain during a solution to a
CSP, does it mean that the algorithm will be able to find a solution by simply
backtracking? Explain your answer...............................................................15
(4.5) Explain what forward checking for a CSP is.........................................15
Question 5..........................................................................................................16
(5.1) Provide the variables for this problem. Make sure to use the correct
notation..........................................................................................................16
(5.2) Define the domain for the variables, make sure to use the correct
notation, and to use all the information provided. (Hint: Remember that the
number of cells in a box and the number of letters in a word must match.).16
(5.3) Define the constraints for this problem................................................16
(5.4) You are given the following list of words as your dictionary.................17
2
,Question 1
(1.1) Define the concept of a zero-sum game as we study
it in AI.
A zero sum game is a fully observable, deterministic, adversarial
game (turn-based for two-players) in which a win for one player
is a loss for the other. The end value for a game is always equal
but opposite for the players.
(1.2) Clearly explain what a utility function is, and why it is
used during adversarial searches.
A utility function provides an indication of the apparent
numerical value X of a terminal state X s for player p. It is used
to find the best available move for a player X . In the case that
the search tree is too deep, the leaf nodes of the searchable tree
is considered the terminal node.
(1.3) Define the utility function for a game of tic-tac-toe.
Provide the algorithm for this utility function and provide an
example of the result of applying your function to a terminal
state in the game tree.
The simplest utility function will simply add together the number
of tokens for a par-ticular player in a row. If there are 3 in a row,
the utility is +1, if there are 3 of the opponents’ tokens in a row,
the utility is -1. Remember: the principle here is that the search
can consider all the search nodes to a terminal state. If we had
some sort of a limit as to how far we would search, the nodes at
the limit would be considered terminal states (even though those
states may not be the end of the game). There are many ways of
writing this, but what is provided here is elaborate by choice – it
3
, makes it easier to understand what is happening. We provide a
helper algorithm:
input : t the player’s token, S the state to evaluate
output: +1 for a win for token t, 0 otherwise
u ← 0;
for i ← 1 to 3 do
if S1i = t and S2i = t and S3i = t then
u ← 1;
end
end
for j ← 1 to 3 do
if Sj1 = t and Sj2 = t and Sj3 = t then
u ← 1;
end
end
if S11 = t and S22 = t and S33 = t then
u ← 1;
end
if S31 = t and S22 = t and S13 = t then
u ← 1;
end
return u
We can now define a utility function which simply calls the
helper function once for each token. Depending on who we want
the utility for we will return 1 or -1.
4
ASSIGNMENT 2
SOLUTIONS
2022
1
,Table of Contents
Question 1............................................................................................................4
(1.1) Define the concept of a zero-sum game as we study it in AI..................4
(1.2) Clearly explain what a utility function is, and why it is used during
adversarial searches........................................................................................4
(1.3) Define the utility function for a game of tic-tac-toe. Provide the
algorithm for this utility function and provide an example of the result of
applying your function to a terminal state in the game tree...........................4
(1.4) Explain how forward pruning works. Provide at least one approach to
forward pruning in your explanation, as well as a problem that may be
encountered with forward pruning..................................................................5
(1.5) Does the order in which nodes are examined in minimax matter?
Explain your answer.........................................................................................6
Question 2............................................................................................................7
(2.1) Consider Figure 3 and answer the questions that follow. (The utility
value of the leaf nodes are provided in brackets in the leaf node.)................7
(2.2) Explain what the horizon effect is. Provide an example that clearly
explains this phenomenon. Use diagrams to assist your discussion.............11
Question 3..........................................................................................................12
(3.1) Provide a First-order Logic (FOL) vocabulary for the sentences..........12
(3.2) Using your vocabulary, translate the sentences in FOL........................12
(3.3) Convert the statements obtained in (5.2) into clausal form. Variables
must be standardized.....................................................................................13
(3.4) Use resolution refutation to prove that John is happy...........................13
Question 4..........................................................................................................14
(4.1) Define the Least Constraining Value (LCV) heuristic............................14
(4.2) Explain why establishing strong k-consistency is a problem................14
(4.3) Define the degree heuristic...................................................................15
(4.4) If no legal assignments for a variable remain during a solution to a
CSP, does it mean that the algorithm will be able to find a solution by simply
backtracking? Explain your answer...............................................................15
(4.5) Explain what forward checking for a CSP is.........................................15
Question 5..........................................................................................................16
(5.1) Provide the variables for this problem. Make sure to use the correct
notation..........................................................................................................16
(5.2) Define the domain for the variables, make sure to use the correct
notation, and to use all the information provided. (Hint: Remember that the
number of cells in a box and the number of letters in a word must match.).16
(5.3) Define the constraints for this problem................................................16
(5.4) You are given the following list of words as your dictionary.................17
2
,Question 1
(1.1) Define the concept of a zero-sum game as we study
it in AI.
A zero sum game is a fully observable, deterministic, adversarial
game (turn-based for two-players) in which a win for one player
is a loss for the other. The end value for a game is always equal
but opposite for the players.
(1.2) Clearly explain what a utility function is, and why it is
used during adversarial searches.
A utility function provides an indication of the apparent
numerical value X of a terminal state X s for player p. It is used
to find the best available move for a player X . In the case that
the search tree is too deep, the leaf nodes of the searchable tree
is considered the terminal node.
(1.3) Define the utility function for a game of tic-tac-toe.
Provide the algorithm for this utility function and provide an
example of the result of applying your function to a terminal
state in the game tree.
The simplest utility function will simply add together the number
of tokens for a par-ticular player in a row. If there are 3 in a row,
the utility is +1, if there are 3 of the opponents’ tokens in a row,
the utility is -1. Remember: the principle here is that the search
can consider all the search nodes to a terminal state. If we had
some sort of a limit as to how far we would search, the nodes at
the limit would be considered terminal states (even though those
states may not be the end of the game). There are many ways of
writing this, but what is provided here is elaborate by choice – it
3
, makes it easier to understand what is happening. We provide a
helper algorithm:
input : t the player’s token, S the state to evaluate
output: +1 for a win for token t, 0 otherwise
u ← 0;
for i ← 1 to 3 do
if S1i = t and S2i = t and S3i = t then
u ← 1;
end
end
for j ← 1 to 3 do
if Sj1 = t and Sj2 = t and Sj3 = t then
u ← 1;
end
end
if S11 = t and S22 = t and S33 = t then
u ← 1;
end
if S31 = t and S22 = t and S13 = t then
u ← 1;
end
return u
We can now define a utility function which simply calls the
helper function once for each token. Depending on who we want
the utility for we will return 1 or -1.
4
