CSCE 420 Lecture 10

« previous | Thursday, February 14, 2013 | next »

Happy Feast of St. Valentine!

CSP: Backtracking Search

Recursively and randomly assign values to variables; return up the recursion tree if we run into a problem.

Arc-Consistency Algorithm

for every value in each node, neighboring nodes always have a consistent value choice

Complexity

$n$ variables
domain size $d$
$c\in O(n^{2})$ constraints/edges for each var
$d^{2}$ work to proceess each edge
Total running time: $O(c\,d^{3})=O(n^{2}\,d^{3})$

CSPs are NP-Complete, but AC3 does not solve the problem, it just reduces the domain.

Maintaining Arc Consistency (MAC)

Backtracking with an extra step: perform AC3 before recursing:

function Recursive-Backtracking(assignment, csp, domains) returns domains/failure
  if assignment is complete then return assignment
  var := Select-Unassigned-Variable(Variables[csp], assignment, csp)
  for each value in Order-Domain-Values(var, assignment, csp) do
    if value is consistent with assignment given Constraints[csp] then
      add {var = value} to assignment
      reduced_domains := AC3(assignment, csp)
      result := Recursive-Backtracking(assignment, csp, reduced_domains)
      if result != failure then return result
      remove {var = value} from assignment
    end if
  end for
  return failure

Other CSP Methods

Conflicted-Directed Back-Jumping (c.f. [Chronological] Backtracking)
Inference-Derived Constraints
Max CSP: instead of trying to find a complete and consistent solution, optimize complete variable assignment that satisfies as many constraints as possible

Min-Conflicts

function Min-Conflicts(csp, max_steps) return soln/failure
  current := complete, random initial variable assignment
  for i = 1 to max_steps do
    if current is a solution (satisfies all constraints) then return current
    var := randomly chosen conflicted variable
    val := value that minimizes Conflicts(var, val, current, csp)
    current := current union {var = val}
  end for
  return failure (or best assignment found)

Game Playing

Examples of competetive, multi-agent environments

In all previous examples, the agent had complete control of environment.

In other problems, environment may not be compliant; may even be hostile
Other agents working on their own and/or against other agents

Simplified to Two-player, Zero-sum games

Operators: legal moves
Goal: "win"
Utility function: "payoff" = {1 if win, -1 if lose, 0 if draw}; Notice that $u_{1}(S)=-u_{2}(S)$

Nash Equilibrium Strategies

Decision-Making

Policy: maps states to actions ( $\pi (s_{i})=a_{i}\in A$ )

Minimax Search

Alternating minimum ( $\nabla$ and maximum ( $\Delta$ ) nodes in a tree:

for a state $s$ ,

if $s$ is a max node, then return the maximum child
if $s$ is a min node, then return the minimum child
if $s$ is a terminal node, end the game

function Minimax(state) returns action
  return actions.min_by {|a| Min-Value(result(state, a))}

function Min-Value(state)
  if state is terminal then return u1(s)
  v := INFINITY
  for each action a in A
    v := min(v, Max-Value(result(state, a)))
  end for
  return v
end function

function Max-Value(state)
  if state is terminal then return u1(s)
  v := -INFINITY
  for each action a in A
    v := max(v, Min-Value(result(state, a)))
  end for
  return v
end function