AdministrativiaLast time: search strategiesExercise: Search AlgorithmsDepth-first searchSlide 5Slide 6Slide 7Slide 8Breadth-first searchSlide 10Slide 11Slide 12Slide 13Uniform-cost searchSlide 15Slide 16Slide 17Slide 18Greedy searchSlide 20Slide 21Slide 22Slide 23A* searchSlide 25Slide 26Slide 27Slide 28Last time: Simulated annealing algorithmSlide 30This time: OutlineWhat kind of games?Searching for the next moveTwo-player gamesSlide 35Game vs. search problemExample: Tic-Tac-ToeType of gamesThe minimax algorithmminimax = maximum of the minimumMinimax: Recursive implementationSlide 421. Move evaluation without complete searchEvaluation functionsNote: exact values do not matterMinimax with cutoff: viable algorithm?2. - pruning: search cutoff- pruning: exampleSlide 49Slide 50Slide 51- pruning: general principleProperties of -The - algorithmMore on the - algorithmMore on the - algorithm: start from MinimaxRemember: Minimax: Recursive implementationSlide 58Slide 59Slide 60Slide 61Slide 62Slide 63Another way to understand the algorithmExample- algorithm:SolutionState-of-the-art for deterministic gamesNondeterministic gamesAlgorithm for nondeterministic gamesRemember: Minimax algorithmNondeterministic games: the element of chanceSlide 73Evaluation functions: Exact values DO matterState-of-the-art for nondeterministic gamesSummaryExercise: Game PlayingCS 561, Sessions 8-91Administrativia •Assignment 1 due tuesday 9/24/2002 BEFORE midnight•Midterm exam 10/10/2002CS 561, Sessions 8-92Last time: search strategiesUninformed: Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningInformed: Use heuristics to guide the search•Best first:•Greedy search – queue first nodes that maximize heuristic “desirability” based on estimated path cost from current node to goal;•A* search – queue first nodes that maximize sum of path cost so far and estimated path cost to goal.•Iterative improvement – keep no memory of path; work on a single current state and iteratively improve its “value.”•Hill climbing – select as new current state the successor state which maximizes value.•Simulated annealing – refinement on hill climbing by which “bad moves” are permitted, but with decreasing size and frequency. Will find global extremum.CS 561, Sessions 8-93Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expanded next by each of the following search algorithms?(a)Depth-first search(b)Breadth-first search(c)Uniform-cost search(d)Greedy search(e) A* search 5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-94Depth-first searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 561, Sessions 8-95Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #2 B 1 3 13 C 1 19 14 D 1 5 11 A 0 0 --CS 561, Sessions 8-96Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #5 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 22 B 1 3 13 C 1 19 14 D 1 5 11 A 0 0 --CS 561, Sessions 8-97Depth-first searchNode queue: add successors to queue front; empty queue from top# state depth path cost parent #5 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 22 B 1 3 13 C 1 19 14 D 1 5 11 A 0 0 --CS 561, Sessions 8-98Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expanded next by each of the following search algorithms?(a)Depth-first search(b)Breadth-first search(c)Uniform-cost search(d)Greedy search(e) A* search 5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-99Breadth-first searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 561, Sessions 8-910Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 C 1 19 14 D 1 5 1CS 561, Sessions 8-911Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 C 1 19 14 D 1 5 15 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 2CS 561, Sessions 8-912Breadth-first searchNode queue: add successors to queue end; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 C 1 19 14 D 1 5 15 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 2CS 561, Sessions 8-913Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of the heuristic function, h.Which node (use the node’s letter) will be expanded next by each of the following search algorithms?(a)Depth-first search(b)Breadth-first search(c)Uniform-cost search(d)Greedy search(e) A* search 5D5AC541963h=15BF GEh=8h=12h=10 h=10h=18Hh=20h=14CS 561, Sessions 8-914Uniform-cost searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 561, Sessions 8-915Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 D 1 5 14 C 1 19 1CS 561, Sessions 8-916Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 D 1 5 15 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 24 C 1 19 1CS 561, Sessions 8-917Uniform-cost searchNode queue: add successors to queue so that entire queue is sorted by path cost so far; empty queue from top# state depth path cost parent #1 A 0 0 --2 B 1 3 13 D 1 5 15 E 2 7 26 F 2 8 27 G 2 8 28 H 2 9 24 C 1 19 1CS 561, Sessions 8-918Exercise: Search AlgorithmsThe following figure shows a portion of a partially expanded search tree. Each arc between nodes is labeled with the cost of the corresponding operator, and the leaves are labeled with the value
View Full Document
Unlocking...