Other
COS3751 Assignment 2 Solution 2022
- Institution
- University Of South Africa (Unisa)
Solutions for the COS 3751 Assignment 2 - YEAR 2022.
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
Content preview
COS 3751ASSIGNMENT 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller StudyWellNotes. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R200,00. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
57413 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 14 years now