CS181 Artificial Intelligence

1. Search

A search problem consists of:

1. A state space
2. A successor function(with actions, costs)
3. A start state and a goal test

A search space keeps only the details needed for planning (abstraction).

DFS

BFS

UCS

Uniform Cost Search is complete and optimal.

1. Explores options in every “direction”
2. No information about goal location

Greedy

Expand a node that you think is closest to a goal state.

A*

Admissible Heuristics

A heuristic h is admissible (optimistic) if:

$$
0\leq h(n)\leq h^*(n)
$$

where $h^*(n)$ is the true cost to a nearest goal.

Consistency

Consistency implies admissibility

$$
\text{cost}(A \rightarrow C) + h( C) \geq h(A)
$$

2. CSP(Constraint satisfaction problems)

• Backtracking
• Backtracking with Forward Checking
• Ordering
  • Least Constraining Value(LCV)

    • Given a choice of variable, choose the least constraining value
    • I.e., the one that rules out the fewest values in the remaining variables
    • Note that it may take some computation to determine this! (E.g., rerunning filtering)

  • Minimum remaining values (MRV)

    • Choose the variable with the fewest legal left values in its domain
    • Also called “most constrained variable”

Arc Consistency
After enforcing arc consistency:

• Can have one solution left
• Can have multiple solutions left
• Can have no solutions left (and not know it)

3. Adversarial Search(Minimax)

• Time: $O(B^m)$
• Space: $O(bm)$

Exactly the same as DFS.
And $m$ represents the depth of the node tree.

Depth-limited search

• Resources limits

Replace terminal utilities with an evaluation function for non-terminal positions.

Evaluation Functions:

• Do not guarantee the optimal play.
• More depth makes a BIG difference.

Adversarial Search $\alpha$-$\beta$ Implementation