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 gamesSlide 39The minimax algorithmGenerate Game TreeSlide 42Slide 43Slide 44A subtreeWhat is a good move?MinimaxSlide 48Slide 49Slide 50minimax = maximum of the minimumMinimax: Recursive implementationSlide 53Do We Have To Do All That Work?Slide 55Slide 56Slide 571. Move evaluation without complete searchEvaluation functionsNote: exact values do not matterMinimax with cutoff: viable algorithm?2. - pruning: search cutoff- pruning: exampleSlide 64Slide 65Slide 66- pruning: general principleProperties of -The - algorithm:More on the - algorithmMore on the - algorithm: start from MinimaxRemember: Minimax: Recursive implementationSlide 73Slide 74Slide 75Slide 76Slide 77Slide 78Another way to understand the algorithmExample- algorithm:SolutionState-of-the-art for deterministic gamesNondeterministic gamesAlgorithm for nondeterministic gamesRemember: Minimax algorithmNondeterministic games: the element of chanceSlide 88Evaluation functions: Exact values DO matterState-of-the-art for nondeterministic gamesSummaryExercise: Game PlayingCS 460, Sessions 8-91Administrativia •Assignment 1 due thursday 9/25/2003 BEFORE midnight•Midterm exam 10/09/2003 in classCS 460, 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 460, 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 460, Sessions 8-94Depth-first searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 460, 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 460, 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 460, 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 460, 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 460, Sessions 8-99Breadth-first searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 460, 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 460, 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 460, 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 460, 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 460, Sessions 8-914Uniform-cost searchNode queue: initialization# state depth path cost parent #1 A 0 0 --CS 460, 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 460, 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 460, 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 460, Sessions 8-918Exercise: Search AlgorithmsThe following