CSCI4511 Introduction to Artificial Intelligence, Fall 2018

Make-Up Take Home Exam

- The runtime bound of DFS is in terms of maximum branch depth O(b^m), whereas the runtime bound of BFS is in terms of minimum solution depth O(b^d).
*For*__a__*and*__b__*,**consider a problem in which m is significantly larger than d.*- Identify specific conditions of the problem and/or search tree under which DFS finds a solution faster given m >> d.
- Identify specific conditions under which DFS is slower given m >> d.
- Why is it that for Sudoku and KenKen, there is no difference in the worst-case runtime of BFS and DFS? Which would you recommend using for either Sudoku or KenKen and why?

- Run the A* algorithm (graph version) on the following graph to find the shortest path. You start at “D” and the goal is “J”. Show your work by providing the frontier at each time step. The frontier should be in sorted order based on node values (show those values too).
__Is this heuristic admissible? Is it consistent?__

* *

- Throughout the semester, you implemented a variety of problem solving techniques including search and CSP. Explain why using constraint satisfaction (i.e. AC3 with Backtracking Search) to solve KenKen would be preferred over classic search, such as BFS or DFS, discussing both the implementation and the impact on search time and space.

- The ability to evaluate a given state or solution plays a significant role in many problem solving strategies.
__Describe the intent and impact that a good evaluation function can have on a search strategy, contrasting this with a “bad” evaluation function__. Discuss this in the context of two of the following algorithms: A*, Adversarial Search, Hill-Climbing, Genetic Algorithm, Simulated Annealing. Pick TWO of the algorithms to discuss.

* *

- Consider creating AI to compete against a human in a game of checkers (or chess) using adversarial search. Answer the following.
*There is not a right answer to these questions.*

__Give 3 characteristics of a board__in checkers (or chess) that could be used in the evaluation function for CUTOFF search, stating whether each is negatively or positively weighted.__Provide at least one positive and one negative.__

- As the designer of an evaluation function for adversarial search, you have to determine both the relevant factors and the weighting of those factors. If you did not have a lot of experience with evaluating the state of a game, how would you develop and design a “good” evaluation function?

- Four people {Wes, Lula, Viv, Xin} performed {Piano, Dance, Magic, Sing} in some order. What we know:

- Xin sang.
- Wes was 2 acts after the person who performed magic.
- Wes and Lula: one of them was the first act and the other danced.
- The 2
^{nd}act was piano.

Consider framing this for CSP. A variable is a person, and the domain is defined by the set of tuples (act, order). For example, it might be found that Xin was the 2^{nd} person to perform and he sang: Xin = ( Sing, 2^{nd} ).

__Describe the initial domain (generally) for all of the variables. What size is it?____Define a constraint, using lambda notation__, for “Wes was 2 acts after the person who performed magic.”- If you define a constraint for AC3 for the variable pair (Wes, Viv), why do you also need to define one for (Viv, Wes)?

**Using propositional logic**, consider the expression of a person’s act as “Person_Act” and the order as “Person_Order.” For example, Xin singing 2

^{nd}would be expressed as Xin_Sing AND Xin_2.

- Using Xin_Sing, express that Xin singing means that no one else could have been singing.
- Using “Person_Act” and “Person_Order,” express the collection of rules to reflect that “The 2
^{nd}act was piano.” - If you expressed all rules in CNF or in Horn clauses, you could use Resolution or Chaining, respectively. Select one of these inference methods, and describe generally what you would be asking your knowledge base to infer to solve this puzzle. Be sure to
__describe a process__to determine a complete solution, not just the order or act for a single person.

- Reframe this problem using
__first-order logic__. Define the constant and predicate symbols. - State the first-order logic rules that represent:
- Wes was 2 acts after the person who performed magic.
- Wes and Lula: one of them was the first act and the other danced.

- Below is a knowledge base written in propositional logic.

A and F –> E

C –> E

B –> C

D and A –> C

D and B –> A

D.

B.

Draw the AND-OR search tree of a __Backward Chaining__ DFS for **Ask(KB,E).** Be sure to make clear OR versus AND.

**Draw the whole tree**, expanding every possible branch.

**Whenever a literal is inferred (i.e. becomes True)**: 1) circle it on your diagram, 2) number them in order of inference (i.e. put #1 by the first literal that you infer from the tree), and 3) from that point on, assume it has been added to the KB.

You can draw this out on paper, take a picture, and include the image.

SOlution：