Chapter 4 HEURISTIC SEARCH Contents CSC411 Hill-climbing Dynamic programming Heuristic search algorithm

Admissibility, Monotonicity, and Informedness Using Heuristics In Games Complexity Issues Artificial Intelligence 1 Heuristics Rules for choosing paths in a state space that most likely lead to an acceptable problem solution Purpose Reduce the search space

Reasons May not have exact solutions, need approximations Computational cost is too high CSC411 Artificial Intelligence 2 First three levels of the tic-tac-toe state space reduced by symmetry CSC411

Artificial Intelligence 3 The most wins heuristic applied to the first children in tic-tac-toe CSC411 Artificial Intelligence 4

Heuristically reduced state space for tic-tac-toe CSC411 Artificial Intelligence 5 Hill-Climbing Analog Go uphill along the steepest possible path until no farther up Principle

Expand the current state of the search and evaluate its children Select the best child, ignore its siblings and parent No history for backtracking Problem Local maxima not the best solution CSC411 Artificial Intelligence 6

The local maximum problem for hill-climbing with 3-level look ahead CSC411 Artificial Intelligence 7 Dynamic Programming Forward-backward searching Divide-and-conquer: Divided problems into multiple interacting and related subproblems Address issues of reusing subproblems solutions

An example: Fibonacci series F(0) = 1; F(1)=1; F(n)=F(n-1)+F(n-2) Keep track of the computation F(n-1) and F(n-2), and reuse their results to compute F(n) Compare with recursion, much more efficient Applications: CSC411

String matching Spell checking Nature language processing and understanding planning Artificial Intelligence 8 Global Alignment of Strings Find an optimal global alignment of two character strings Data structure: (n+1)(m+1) array, each element reflects the global alignment success to that point Three possible costs for the current state

If a character is shifted along in the shorter string for better possible alignment, the cost is 1 and recorded in the column score; and If a new character is inserted, cost is 1 and reflected in the row score If the characters to be aligned are different, shift and insert, the cost is 2 If identical, the cost is 0 The initialization stage and first step in completing the array for character alignment using dynamic programming. CSC411

Artificial Intelligence 9 The initialization stage and first step in completing the array for character alignment using dynamic programming. CSC411 Artificial Intelligence 10

The completed array reflecting the maximum alignment information for the strings. CSC411 Artificial Intelligence 11 A completed backward component of the dynamic programming example giving one (of several possible) string alignments. CSC411

Artificial Intelligence 12 Minimum Edit Difference Determine the best approximate words of s misspelling word in spelling checker Specified as the number of character insertion, deletion, and replacements necessary to turn the first string into the second Cost: 1 for insertion and deletion, and 2 for replacement

Determine the minimum cost difference Data structure: array CSC411 Artificial Intelligence 13 Initialization of minimum edit difference matrix between intention and execution CSC411 Artificial Intelligence

14 Array elements are the costs of the minimum editing to that point plus the minimum cost of either an insertion, deletion or replacement Cost(x, y) = min{ Cost(x-1, y) + 1 (insertion cost), Cost(x-1, y-1) + 2 (replacement cost), Cost(x, y-1) + 1 (deletion cost) } CSC411 Artificial Intelligence

15 Complete array of minimum edit difference between intention and execution (of several possible) string alignments. Intention ntention delete I, cost 1 etention cost 2

replace n with e, exention 2 replace t with x, cost exenution insert u, cost 1 execution replace n with c, cost 2 CSC411 Artificial Intelligence 16

The Best-First Search Also heuristic search use heuristic (evaluation) function to select the best state to explore Can be implemented with a priority queue Breadth-first implemented with a queue Depth-first implemented with a stack CSC411 Artificial Intelligence

17 The bestfirst search algorithm CSC411 Artificial Intelligence 18 Heuristic search of a hypothetical state space

CSC411 Artificial Intelligence 19 13 A trace of the execution of best-first-search CSC411 Artificial Intelligence

20 Heuristic search of a hypothetical state space with open and closed states highlighted CSC411 Artificial Intelligence 21 Implement Heuristic Evaluation Function Heuristics can be evaluated in different

ways 8-puzzle problem Heuristic 1: count the tiles out of places compared with the goal state Heuristic 2: sum all the distances by which the tiles are out of pace, one for each square a tile must be moved to reach its position in the goal state Heuristic 3: multiply a small number (say, 2) times each direct tile reversal (where two adjacent tiles must be exchanged to be in the order of the goal)

CSC411 Artificial Intelligence 22 The start state, first moves, and goal state for an example-8 puzzle CSC411 Artificial Intelligence 23

Three heuristics applied to states in the 8puzzle CSC411 Artificial Intelligence 24 Heuristic Design Use the limited information available in a single state to make intelligent choices Empirical, judgment, and intuition Must be its actual performance on problem instances

The solution path consists of two parts: from the starting state to the current state, and from the current state to the goal state The first part can be evaluated using the known information The second part must be estimated using unknown information The total evaluation can be f(n) = g(n) + h(n) g(n) from the starting state to the current state n h(n) from the current state n to the goal state CSC411 Artificial Intelligence

25 The heuristic f applied to states in the 8-puzzle CSC411 Artificial Intelligence 26 State space generated in heuristic

search of the 8-puzzle graph CSC411 Artificial Intelligence 27 The successive stages of open and closed that generate the graph are: CSC411

Artificial Intelligence 28 Open and closed as they appear after the 3rd iteration of heuristic search CSC411 Artificial Intelligence 29

Heuristic Design Summary f(n) is computed as the sum of g(n) and h(n) g(n) is the depth of n in the search space and has the search more of a breadth-first flavor. h(n) is the heuristic estimate of the distance from n to a goal The h value guides search toward heuristically promising states The g value grows to determine h and force search back to a shorter path, and thus prevents search from persisting indefinitely on a fruitless path CSC411

Artificial Intelligence 30 Admissibility, Monotonicity, and Informedness A best-first search algorithm guarantee to find a best path, if exists, if the algorithm is admissible A best-first search algorithm is admissible if its heuristic function h is monotone CSC411

Artificial Intelligence 31 Admissibility and Algorithm A* CSC411 Artificial Intelligence 32 Monotonicity and Informedness

CSC411 Artificial Intelligence 33 Comparison of state space searched using heuristic search with space searched by breadth-first search. The proportion of the graph searched heuristically is shaded. The optimal search selection is in bold. Heuristic used is f(n) = g(n) + h(n) where h(n) is tiles out of place. CSC411

Artificial Intelligence 34 Minimax Procedure Games Two players attempting to win Two opponents are referred to as MAX and MIN A variant of game nim A number of tokens on a table between the 2 opponents Each player divides a pile of tokens into

two nonempty piles of different sizes The player who cannot make division losses CSC411 Artificial Intelligence 35 Exhaustive Search State space for a variant of nim. Each state partitions the

seven matches into one or more piles CSC411 Artificial Intelligence 36 Maxmin Search Principles MAX tries to win by maximizing her score, moves to a state that is best for MAX

MIN, the opponent, tries to minimize the MAXs score, moves to a state that is worst for MAX Both share the same information MIN moves first The terminating state that MAX wins is scored 1, otherwise 0 Other states are valued by propagating the value of terminating states Value propagating rules If the parent state is a MAX node, it is given the maximum value among its children If the parent state is a MIN state, it is given the minimum value of its children

CSC411 Artificial Intelligence 37 Exhaustive minimax for the game of nim. Bold lines indicate forced win for MAX. Each node is

marked with its derived value (0 or 1) under minimax. CSC411 Artificial Intelligence 38 Minmaxing to Fixed Ply Depth If cannot expand the state space to terminating (leaf) nodes (explosive), can

use the fixed ply depth Search to a predefined number, n, of levels from the starting state, n-ply lookahead The problem is how to value the nodes at the predefined level heuristics Propagating values is similar Maximum children for MAX nodes Minimum children for MIN nodes CSC411 Artificial Intelligence 39

Minimax to a hypothetical state space. Leaf states show heuristic values; internal states show backed-up values. CSC411 Artificial Intelligence 40 Heuristic measuring conflict applied to states of tic-tac-toe CSC411

Artificial Intelligence 41 Two-ply minimax applied to the opening move of tic-tac-toe CSC411 Artificial Intelligence 42

Two ply minimax, and one of two possible MAX second moves CSC411 Artificial Intelligence 43 Two-ply minimax applied to Xs move near the end of the game CSC411

Artificial Intelligence 44 Alpha-Beta Procedure Alpha-beta pruning to improve search efficiency Proceeds in a depth-first fashion and creates two values alpha and beta during the search Alpha associated with MAX nodes, and never decreases Beta associated with MIN nodes, never increases To begin, descend to full ply depth in a depth-first search, and apply heuristic evaluation to a state and

all its siblings. The value propagation is the same as minimax procedure Next, descend to other grandchildren and terminate exploration if any of their values is >= this beta value Terminating criteria Below any MIN node having beta <= alpha of any of its MAX ancestors Below any MAX node having alpha >= beta of any of its MIN ancestors CSC411 Artificial Intelligence

45 Alpha-beta pruning applied. States without numbers are not evaluated. CSC411 Artificial Intelligence 46