CAP 6635 Artificial Intelligence
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].
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].
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]
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]
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]
· 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]
Question 8 [2 pts] The following table lists a number of predicates
x is an apple
x is blue
x is tasty
x is green
x is red
x is people
x is fruit
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]