CSCI 4511W, Section 1: Introduction to Artificial Intelligence Fall 2022

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI 4511W, Section 1: Introduction to Artificial Intelligence

Fall 2022

Homework 6 – Short Answer/Programming HW3 (100 points possible)

Problems 1 and 2 (Minimax and Alpha-Beta Pruning) – 20 points - 10 points each:

For the following trees, complete the minimax algorithm on for problem 1.  Show the backed up values at each node clearly.  For problem 2, show the alpha and beta at each node and clearly mark the parts of the tree that are pruned. Please mark your pruning very clearly.

 

 

NOTE: Exam 2 Bonus – you will get 1 pointed added to your exam 1 score for each correct solution you submit to the minimax and alpha-beta pruning problems above.  Thus, if your solutions to        Problems 1 and 2 above are both correct, you can earn 2 additional points for Exam 1!

Problem 3:  Constraint Satisfaction Problem (10 points)

You have decided to make some money by writing a classroom scheduling software package.    You have a fixed number of professors and classrooms to use, a whole lot of classes that need to be taught that will be given to use as a list, and the time slots that classes can be taught in.          Classes cannot be taught before 8:00am and after 9:00pm.  Give a precise formulation for this    constraint satisfaction problem.

(Follow the example from the book for the job-shop scheduling discussion on pages 204 and 205.  We are looking for this level of detail.)

Problem 4:  Constraint Satisfaction Problem (15 points)

Solve the cryptarithmetic problem DAYS + TOO = SHORT by hand.  Use the strategy of            backtracking with forward checking; MRV, and least-constraining-values heuristics.  Show all    work to get the full points.  You cannot just give a solution.  You must show the walk through by hand using the heuristics (label the step with the heuristic you used – where they are applicable.

Problem 5:  Logic (15 points)

You are given the following sentence

 

a)  Determine, using enumeration, whether this sentence is valid, satisfiable (but not valid), or unsatisfiable.

b)  Convert the left and right hand sides of the main implication into CNF showing each step and confirm you answer to (a)

c)  Prove your answer using resolution

Programming Portion:  40 points – 10 points each

For this part, you need to use the logic.py code from the aima code. When writing sentences, you need to enclose them in single quotes (') and for the connectors use & (and), | (or), ==> (implication), ~ (negation).

Template file:  student_code_hw3.py (please download this and use)

1.     Check if these sentences are valid using the function tt_true(s) from logic.py.

1.    A ⇒ A

2.    (A ⇒ B) ⇒ (¬ A ⇒ ¬ B)

3.    A ∨ B ∨ ¬ B

4.    (A ⇒ B) ⇒ (B ⇒ C)

5.    (A ⇒ C) ⇒ ((A ^ B) ⇒ C

2.    Check if these sentences are satisfiable using the function dpll_satisfiable(s) which returns False or the      values for the proposition that make the sentence true. When using dpll_satisfiable(s), to avoid errors you  need to use the function expr () in front of the expressions. For instance, for E ⇒ E you need to write (expr ('E ==> E')) instead of 'E ==> E'.

1.    E ⇒ E

2.    E ⇒ F

3.    (E ^ F) ∨ ¬ F

4.    ((G ∨ B) ^ (¬ B ∨ A)) ⇒ (G ∨ A)

5.    (A ⇒ B) ⇒ (B ⇒ C)

3.    You are given the following knowledge:  "If the unicorn is mythical, then it is not mortal but if it is not       mythical then it is a mortal mammal. If the unicorn is either not mortal or a mammal, then it is horned. The unicorn is magical if it is horned."

1.    Write a propositional knowledge base using the function call PropKB() from logic.py software,   using the following propositions: My = mythical, Mo = mortal, Ma = mammal, H = horned, Mag = magical. You do not need to worry about converting the sentences to CNF, the conversion is    done by the software when you add a sentence to the knowledge base. Look at logic.py to find    how to add a sentence to the knowledge base.

2.    Use the function pl_resolution(kb, alpha) from logic.py, where kb is the knowledge base you have created and alpha is the sentence you want to see if it follows from the knowledge base. To avoid  errors you need to use the function expr() in front of the expressions. You need to check if the        sentence "the unicorn is horned" is entailed by the knowledge base.

4.    [ 10 points] You are given these sentences: "If the Joker stole the money, then the Penguin is not guilty. Either the Joker stole the money, or the Joker left town. If the Joker left town, then the Penguin got the car."

1.    Write a propositional knowledge base using PropKB(), and the following propositions: JSM          (Joker stole the money), PG (Penguin is guilty), JLT (Joker left town), PGC (Penguin got the car).

2.    Use the function pl_resolution(kb, alpha), where kb is the knowledge base you have created and  alpha is the sentence you want to see if it follows from the knowledge base. You need to check if the sentence "If the Penguin is guilty then he got the car." is entailed by the knowledge base.


2022-11-07