2

CAP 6635 Artificial Intelligence

Homework 3

Question 1 [1 pt] Figure 1 shows the cu

ent layout of a tic-tac-toe game board, and Max (“X”) is going to make the next move. Please draw the remaining states of the game tree [0.5 pt], and explain what is the best move for Max [0.5 pt].

Figure 1

Question 2 [1 pt] Given a two-player game tree in Figure 2, starting from the root node, please list the nodes in the order they are visited by α-β pruning (0.25 pt). Please show the utility values of every node [0.25 pt], and report nodes pruned by α-β pruning [0.5 pt].

Figure 2

Question 3 [1 pt]. Given a two-player game tree in Figure 3, please list co

ect α value for each Max node, and co

ect β value for each Min node [0.5 pt] (no need to report α, β values for nodes pruned by α-β pruning). Mark all nodes which are pruned by α-β pruning [0.5 pt]

Figure 3

Question 4 [1 pt]: Figure 4 shows a portion of an imperfect tic-tac-toe game tree using evaluation function. Assume X is the Max player and O is the Min player. Assume a heuristic function is defined as the number of X’s winning position subtract the number of O’s winning position. For example, for board layout, X has 6 winning positions, and O has 5 winning positions. Therefore, the heuristic value of this board layout is 6-5=1.

· Using defined heuristic function, list the heuristic values for all leaf nodes. [0.25 pt]

· Assume X is the root player, applying α-β pruning to the game tree in Figure 4, determine α value for Max node, and β value for Min nodes. [0.25]

· Determine nodes which are pruned by α-β pruning, and also specify the best move for X. [0.5 pt]

Figure 4

Question 5 [1 pt]: What is the semantic (meaning) of the following sentence? [0.5 pt] Show detailed steps to decompose sentence into CNF format [0.5 pt]

B1,3 ( (P1,2 ( P1,4( P2,3)

Question 6 [1 pt]: Figure 5 shows the Wumpus world game, where the agent starts from location [4,1], and does not sense

eeze or stench.

· Please use propositional logics to write sentences to describe the observations and rules & backgrounds (after agent enters location [4,1], and only consider Pit). [0.5 pt]

· Given above settings, please use model checking to validate that location [3,1] is safe (or KB ╞ (P3,1). Please list all models as a table (only consider Pit), and mark model(s) of KB and model(s) of (. Explain why KB ╞ (P3,1 [0.5 pt]

Figure 5

· Question 7 [2.5 pts] Figure 6 shows the Wumpus world game, where the agent starts from location [1,1], and does not sense

eeze or stench. After that, the agent moves to location [1,2] and sense a Breeze (B). Then the agent moved back to [1,1], and further moved to location [2,1] and senses a Stench (S). Based on the above observations and the Wumpus world game rules, please use resolution algorithm to prove following entailment.

· KB╞ (W1,3 (There is no Wumpus at location [1,3]) [0.5 pt]

· KB ╞ W3,1 (There is a Wumpus at location [3,1]) [0.5 pt]

· KB ╞ P1,3 (There is a Pit at location [1,3]) [0.5 pt]

· KB ╞ ( P2,2 (There is no Pit at location [2,2]) [0.5 pt]

· KB ╞ ( W2,2 (There is a no Wumpus at location [2,2]) [0.5 pt]

Figure 6

Question 8 [2 pts] The following table lists a number of predicates

A(x)

x is an apple

B(x)

x is blue

T(x)

x is tasty

G(x)

x is green

R(x)

x is red

P(x)

x is people

F(x)

x is fruit

L(x,y)

x like y

Using first order logic to express following sentences

· Apples are fruit [0.25 pt]

· Some apples are red [0.25 pt]

· No apple is blue [0.25 pt]

· Green apples are tasty [0.25 pt]

· Some people do not like apple [0.25 pt]

· Not all apples are green [0.25 pt]

· Some people like fruit, except apples [0.25 pt]

· No fruit is liked by every people [0.25]

Question 9 [1 pt] The following sentences describe interesting behaviors of a Hoffer club members.

· Tony, Shi-Kuo and Ellen belong to the Hoofers Club.

· Every member of the Hoofers Club is either a skier or a mountain climber or both.

· No mountain climber likes rain, and all skiers like snow.

· Ellen dislikes whatever Tony likes and likes whatever Tony dislikes.

· Tony likes rain and snow.

Query: Does Hoffer club has a member who is a mountain climber but not a skier?

(1) Define predicates and relations of the Hoffer using first order logic [0.25 pt]

(2) Using first order logic to express each sentence (including query) [0.25 pt]

(3) Converting each sentence to clause format [0.25 pt]

(4) Using Unification to answer the query [0.25]

For all programming tasks, please submit the Notebook as html or pdf files for grading (your submission must include scrips/code and the results of the script).

For each subtask, please use task description (requirement) as comments, and report your coding and results in following format:

Question 10 [1.5 pts] The Minmax Decision Playing Tictactoe [Notebook, html] and Alphabeta Pruning Playing Tictactoe [Notebook, html] posted on Canvas show two programs playing Tic-Tac-Toe game against a computer agent. Use Notebook as the skeleton code, validate and compare following settings and results.

a. Play Tic Tac Toe Minmax for 10 times. Report average computer thinking time (which is the time required for Minmax algorithm to find solutions) [0.25 pt]. Report number of times you have won/lost/tied [0.25 pt]. Explain why it is hard to win the game against computer [0.25 pt]

. Play Tic Tac Toe Alphabeta for five time. Report average computer thinking time (which is the time required for Alpha Beta Pruning to find solutions) [0.25 pt]. Compare time required for Minmax and Alphabeta pruning, explain why Alphabeta pruning is quicker [0.25 pt].

c. What is the maximum depth of the game tree for Tic tac toe [0.25 pt]

Answered 2 days AfterMar 16, 2022

2

CAP 6635 Artificial Intelligence

Homework 3

Question 1 [1 pt] Figure 1 shows the cu

ent layout of a tic-tac-toe game board, and Max (“X”) is going to make the next move. Please draw the remaining states of the game tree [0.5 pt],

Answer:

Explain what is the best move for Max [0.5 pt].

Answer:

Figure 1

The next best move for the Max X’s turn is 7th place and the game is over.

Question 2 [1 pt] Given a two-player game tree in Figure 2, starting from the root node, please list the nodes in the order they are visited by α-β pruning (0.25 pt). Please show the utility values of every node [0.25 pt], and report nodes pruned by α-β pruning [0.5 pt].

??

Figure 2

Answer:

list of nodes in the order they are visited by α-β pruning:

a-b-d-h-t-x-y-z-t-h-i-j-d-b-a

The utility values of every node:

a= 2 g=

4

m=2

s=7

y=5

E=6

= 2

h=

2

n=7

t=2

z=2

F=11

c=4

i=

6

o=-5

u=5

A=5

G=7

d=-9

j=

-9

p=13

v=-5

B=12

H=12

e=2

k=

5

q=4

w=7

C=6

I=8

f= -5

l=

3

=9

x=3

D=-5

Pruned by α-β pruning :

A,B,C,D,E,F,G,H,I,u,v,w,k,l,m,n,o,p,q,r,s,e,f,g,c

Question 3 [1 pt]. Given a two-player game tree in Figure 3, please list co

ect α value for each Max node, and co

ect β value for each Min node [0.5 pt] (no need to report α, β values for nodes pruned by α-β pruning). Mark all nodes which are pruned by α-β pruning [0.5 pt]

Figure 3

Answer:

Pruned node is denoted by circle.

Question 4 [1 pt]: Figure 4 shows a portion of an imperfect tic-tac-toe game tree using evaluation function. Assume X is the Max player and O is the Min player. Assume a heuristic function is defined as the number of X’s winning position subtract the number of O’s winning position. For example, for board layout, X has 6 winning positions, and O has 5 winning positions. Therefore, the heuristic value of this board layout is 6-5=1.

· Using defined heuristic function, list the heuristic values for all leaf nodes. [0.25 pt]

ANSWER:

· Assume X is the root player, applying α-β pruning to the game tree in Figure 4, determine α value for Max node, and β value for Min nodes. [0.25]

Answer:

Max Node a has alpha=0

Min nodes beta values: b=0,i=-2,c=0

· Determine nodes which are pruned by α-β pruning, and also specify the best move for X. [0.5 pt]

Answer:

f-g-h,m,n,o,p,I,j,k,c

Figure 4

Question 5 [1 pt]: What is the semantic (meaning) of the following sentence? [0.5 pt]

Answer:

Observations

– Let Pi,j be true if there is a pit in [i, j]....

CAP 6635 Artificial Intelligence

Homework 3

Question 1 [1 pt] Figure 1 shows the cu

ent layout of a tic-tac-toe game board, and Max (“X”) is going to make the next move. Please draw the remaining states of the game tree [0.5 pt],

Answer:

Explain what is the best move for Max [0.5 pt].

Answer:

Figure 1

The next best move for the Max X’s turn is 7th place and the game is over.

Question 2 [1 pt] Given a two-player game tree in Figure 2, starting from the root node, please list the nodes in the order they are visited by α-β pruning (0.25 pt). Please show the utility values of every node [0.25 pt], and report nodes pruned by α-β pruning [0.5 pt].

??

Figure 2

Answer:

list of nodes in the order they are visited by α-β pruning:

a-b-d-h-t-x-y-z-t-h-i-j-d-b-a

The utility values of every node:

a= 2 g=

4

m=2

s=7

y=5

E=6

= 2

h=

2

n=7

t=2

z=2

F=11

c=4

i=

6

o=-5

u=5

A=5

G=7

d=-9

j=

-9

p=13

v=-5

B=12

H=12

e=2

k=

5

q=4

w=7

C=6

I=8

f= -5

l=

3

=9

x=3

D=-5

Pruned by α-β pruning :

A,B,C,D,E,F,G,H,I,u,v,w,k,l,m,n,o,p,q,r,s,e,f,g,c

Question 3 [1 pt]. Given a two-player game tree in Figure 3, please list co

ect α value for each Max node, and co

ect β value for each Min node [0.5 pt] (no need to report α, β values for nodes pruned by α-β pruning). Mark all nodes which are pruned by α-β pruning [0.5 pt]

Figure 3

Answer:

Pruned node is denoted by circle.

Question 4 [1 pt]: Figure 4 shows a portion of an imperfect tic-tac-toe game tree using evaluation function. Assume X is the Max player and O is the Min player. Assume a heuristic function is defined as the number of X’s winning position subtract the number of O’s winning position. For example, for board layout, X has 6 winning positions, and O has 5 winning positions. Therefore, the heuristic value of this board layout is 6-5=1.

· Using defined heuristic function, list the heuristic values for all leaf nodes. [0.25 pt]

ANSWER:

· Assume X is the root player, applying α-β pruning to the game tree in Figure 4, determine α value for Max node, and β value for Min nodes. [0.25]

Answer:

Max Node a has alpha=0

Min nodes beta values: b=0,i=-2,c=0

· Determine nodes which are pruned by α-β pruning, and also specify the best move for X. [0.5 pt]

Answer:

f-g-h,m,n,o,p,I,j,k,c

Figure 4

Question 5 [1 pt]: What is the semantic (meaning) of the following sentence? [0.5 pt]

Answer:

Observations

– Let Pi,j be true if there is a pit in [i, j]....

SOLUTION.PDF## Answer To This Question Is Available To Download

- class Calculator():def __init__(self):XXXXXXXXXXself.operation_map = {'add' : self.add}def get_input(self):XXXXXXXXXXpassdef execute_operation(self, operation):XXXXXXXXXXpass...SolvedMar 15, 2022
- Assignment: Using your flowchart and pseudocode developed last week for the larval bloater model in the Rice et al 1993 paper, create python code to simulate the results observed in the paper, except...SolvedMar 14, 2022
- Using Python, perform data analysis on the attached csv file regarding alzheimers. Then Study and analyze the dataset to find correlations between the average age of patients, average race of...SolvedMar 14, 2022
- IT 140 Design Document TemplateIT 140 Design Kyiesha Butler Storyboard (Description and Map)You are a wizard that’s been invited to a wizard’s symposium. Every wizard and sorcerer in the...SolvedMar 14, 2022
- Pizza Servings Calculator GUI AssignmentWrite a GUI to calculate the number of servings that a circular pizza of a certain diameter will make. The GUI will have the following appearance:It must...SolvedMar 13, 2022
- Load the JSON file below into Jupyter notebook Python as a dictionary; convert to a list and calculate the minimum velocity and maximum height using recursion. Introduce the space mission to the user...SolvedMar 09, 2022
- DESCRIPTIONBackground of Problem Statement :The US Census Bureau has published California Census Data which has 10 types of metrics such as the population, median income, median housing price, and so...SolvedMar 07, 2022
- In checking writing systems, it's crucial to prevent the alteration of check amounts. One common security method requires that the amount be written in numbers and spelled out in words as well. Create...SolvedMar 06, 2022
- creating a Python program that builds on the assignments for weeks 3 and 4. In addition to the house cleaning service from the previous assignments, the company will now offer yard service. Yard...SolvedMar 06, 2022
- COMP 2152 – Assignment 1 – Winter 2022 Important: ● This is an individual assignment (complete the requirements on your own). ● Do not share the assignment requirements with any former or...SolvedMar 05, 2022

Copy and Paste Your Assignment Here

Disclaimer: The reference papers provided by TAE serve as model papers for students and are not to be submitted as it is. These papers are intended to be used for research and reference purposes only.

Copyright © 2023. All rights reserved.