Overig
COS3751 Assignment 2 Solution 2022
- Vak
- Instelling
- Boek
Solutions for the COS 3751 Assignment 2 - YEAR 2022.
[Meer zien]Voorbeeld 4 van de 15 pagina's
Voorbeeld 4 van de 15 pagina's
In winkelwagen
In winkelwagen
gesponsord bericht van onze partner
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Meer samenvattingen voor studieboek
-
Lecture notes and practical notes - Artifical Intelligence (SET09122) Artificial Intelligence: A Modern Approach, Global Edition, ISBN: 9781292401133
Verkoper
Volgen
StudyWellNotes
Ontvangen beoordelingen
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper StudyWellNotes. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,86. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 56326 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen