IAI Chapter 3 Problem Solving as Search

1. Estimate cost h(n) from current node n to goal state

2. Expand cost minimizing node

3. Completeness (if h unequal 0)

4. Memory and time cost in O(b^h)

1. Combine UCS and GS

2. Estimate cost f(n) the sum from initial node to current node g(n) and from current node n to goal state h(n)

h is called admissible if h(n) \leq h*(n) with h* the cost of the optimal path from current node to goal state

1. Path-max equation can be guaranteed

2. f(n’) = max(f(n) or g(n’)+h(n’)) with n parent of n’

1. Number of successors generated by a "typical" node

2. N+1 = 1+b*+b*²+...+b*^d // No closed form solution for b*

3. Smaller b* is better for h

1. Perform IDS with respect to the heuristic of A*

2. Do not consider an increasing depth (1...d) but the increasing value to the goal node (f(root),...,f(goal))

1. Apply A* on deepest node in Queue with smallest f

2. Assign max(f(parent), g(node)+h(node)) to node or inf if at max depth

3. Update ancestors of node if necessary and add/remove nodes from Queue

1. Find successor node with higher value as current node

2. Current node is solution if no successor has a higher value

1. Choose successor randomly after scheduling index to T

2. If T!=0 AND successor value is greater than current value update current node // Difference deltaE

3. Else update current node only with probability e^(deltaE/T)

4. Theorem “For every search space a schedule exists such that SAS converges to global maximum.”

1. Number of tiles in wrong position // Simplified to placing tiles arbitrary

2. Sum of (Manhattan) distance of tiles to goal location

1. Material value

2. Safety of king, pawn structure

1. Easy to compute

2. Weighted linear functions // Criteria independent from each other

1. Cost of exact solution for simplified problem

2. Pattern databases with maximizing pattern // Sum of pattern is not admissible due to shared moves