UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.3 Free with a free account
Blind and Competitive Search Strategies
Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.3 · lesson 25 of 6913 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Heuristic Approaches: Guided Problem Solving →← Applying Bayes' Rule to AI DecisionsNext lesson: Heuristic Approaches: Guided Problem Solving →
In this lesson
Uninformed search strategies and minimax for two-player games.
- Formulate a problem with an initial state, actions, transitions, a goal test, and path cost
- Trace breadth-first, depth-first, uniform-cost, depth-limited, and iterative deepening search
- Compare search strategies on completeness, optimality, time, and space
- Apply minimax to choose the best move in a two-player zero-sum game tree
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,940 words). Read along, or search it.
Opening Question
Hunting for a Lost Key
Imagine hunting for a lost key in a huge building, with no clue where it is. You could check every room on the ground floor before going upstairs. Or follow one corridor as far as it goes, then turn back. Or always try the room that's cheapest to reach next. Each plan finds the key. But they differ in time, in memory, and in how good a route they find. Which plan should a computer use? And what changes when an opponent fights back?
Problem Formulation
Five Parts of a State Space
Before any search can run, the problem must be written down precisely. A state-space formulation has five parts. For finding a route: the initial state is where you start, town S. The actions are what you can do: drive along a road leaving your town. The transition says where an action leaves you: driving from S along a road to A leaves you at A. The goal test asks, are we done: am I at town G? And the path cost adds up along the way: total kilometers driven. A sliding-tile puzzle has the same five parts, with one slide as each step.
Key Terms
State Space, Solutions, and Path Cost
The states, with the actions joining them, form the state space. A solution is a sequence of actions from the start to a goal. And the best solution is the one with the lowest total path cost. A good formulation keeps only what matters. For a route, the state is the town, not the weather.
Search Trees
Frontier, Explored Set, b, d, and m
Search explores the state space by growing a search tree. The start state is the root. Expanding a node means applying every action, to produce its children. Nodes generated but not yet expanded form the frontier. Since a state can be reached by different paths, a careful search keeps an explored set, so it never repeats work. Three numbers size a tree. b, the branching factor, is how many children a node typically has. d is the depth of the shallowest goal: the fewest actions to reach one. And m is the maximum depth, which can be far larger, or even endless.
The Common Loop
One Choice Separates Blind Strategies
Every blind strategy runs the same loop. Put the start on the frontier. If the frontier is ever empty, there's no solution. Otherwise, choose a frontier node. If it passes the goal test, return its path. If not, expand it, and go around again. The strategies differ in only one choice: which frontier node comes next.
Overview
Queue, Stack, and Priority Queue
Breadth-first search takes the shallowest node, using a queue: first in, first out. Depth-first takes the deepest, using a stack: last in, first out. Uniform-cost search takes the node with the lowest path cost so far, using a priority queue. Depth-limited search is depth-first that never goes below a set depth. And iterative deepening reruns it with limits 0, 1, 2, and so on.
Running Example
A Road Map From S to G
Here's the running example. Search starts at S, and must reach G. Lines are roads, and the numbers are step costs. S connects to A, at cost 1, and to C, at cost 4. A connects to D for 2, and to B for 4. D connects to B for 1. B reaches G for 3, and C reaches G for 6.
Breadth-First Search
Fewest Actions at Cost 10
On the running example, BFS expands the start, then all its children, then all its grandchildren. Here, the goal test happens when a node is chosen, and children join in alphabetical order. BFS expands S, A, C, B, D, and then G. The first path to reach G is S, C, G: only 2 actions, but it costs 4 plus 6, which is 10. BFS always finds the fewest actions. That's the best path only when every action costs the same.
Depth-First Search
Diving Down One Branch at Cost 8
Depth-first search dives down one branch instead. From S it goes to A, then B, then D. D is a dead end, so DFS backs up, and tries G from B. The path it finds is S, A, B, G, costing 1 plus 4 plus 3: 8. That's neither the fewest actions nor the cheapest. DFS needs very little memory. But where paths are endless or loop around, it can wander forever.
Uniform-Cost Search
Cheapest Path First at Cost 7
Uniform-cost search, UCS, ignores the number of actions. It keeps the frontier ordered by g, the path cost so far, and expands the cheapest node first. Expand S at cost 0. The frontier holds A at 1, and C at 4. Expand A at 1. Now D is at 3, C at 4, and B at 5. Expand D at 3. Through D, B costs only 4, so B improves from 5 to 4. B and C tie at 4. Ties go alphabetically, so expand B, which puts G on the frontier at 7. Expand C. Its road to G would cost 10, worse than 7, so that route is dropped. Finally G comes off at 7. The path is S, A, D, B, G, the cheapest of all.
Depth Limits
Depth-Limited Search and Iterative Deepening
To stop DFS from wandering forever, depth-limited search caps it. Nodes at the limit are not expanded. With a limit of 2, it visits S, A, B, D, then C and G, and finds S, C, G. With a limit of 1, it finds nothing: G is 2 actions away. But the right limit is usually unknown. Iterative deepening, IDS, tries limits 0, 1, 2, and so on, until a solution appears.
Cost Check
Repeating Shallow Levels Costs Little
Repeating the shallow levels looks wasteful. But most of a tree's nodes sit at the bottom level. With b equal to 10 and d equal to 5, BFS generates 111,111 nodes. Iterative deepening generates 123,456: only about 11 percent more.
Comparison
Four Strategies, Three Answers
Put the four side by side. Breadth-first found S, C, G, at cost 10. Depth-first found S, A, B, G, at cost 8. Uniform-cost found S, A, D, B, G, at cost 7. Iterative deepening found the same answer as breadth-first. Four strategies, three different answers. Only uniform-cost search found the cheapest route.
Quick Check
Tracing Uniform-Cost Search on a New Map
Quick check, on a new map. S connects to A for 2, and to B for 5. A connects to B for 1. A reaches G for 9, and B reaches G for 3. Which path does uniform-cost search return? Pause, and decide. C: S, A, B, G, at cost 6. UCS expands S, then A at 2. Through A, B costs 3, better than 5, and G costs 11. Next it expands B at 3, which improves G to 6. G then comes off at 6. S, B, G costs 8. And S, A, G ties for the fewest actions, and BFS would return it, but it costs 11.
Evaluation Criteria
Completeness, Optimality, Time, and Space
Strategies are compared on four questions. Completeness: if a solution exists, is it sure to find one? Optimality: is the one it finds sure to be the cheapest? Time: how many nodes does it generate? And space: how many must it hold in memory at once? BFS is complete when b is finite, and optimal when all steps cost the same. But its time and space both grow like b to the d. UCS is complete and optimal if every step costs at least some small epsilon above zero. Its cost grows with the paths cheaper than the best one, C star. DFS is not complete in endless spaces, and never optimal, but needs only about b times m memory. Depth-limited search fails if the limit is below d. And IDS matches BFS's guarantees, with only b times d memory.
Scaling
How b to the d Explodes
What does b to the d mean in practice? Say b is 10, a computer checks a million nodes a second, and each node takes 100 bytes. At depth 6, BFS takes about a second, and 111 megabytes. At depth 8, about 2 minutes, and 11 gigabytes. At depth 10, about 3 hours, and 1.1 terabytes. At 12, 13 days. At 14, three and a half years, and 11 petabytes. Each extra level multiplies the cost by b, and memory runs out long before patience does. That's why depth-first methods and iterative deepening are attractive.
Choosing a Strategy
Matching Strategy to Situation
So match the strategy to the situation. If every step costs the same, and the tree fits in memory, use BFS. If steps cost different amounts, and the cheapest route matters, use uniform-cost search. If memory is tight and any solution will do, use DFS, or depth-limited search. And if memory is tight, but you want the shallowest solution at an unknown depth, use iterative deepening.
Adversarial Search
Two-Player Zero-Sum Games
So far the world stood still while the agent searched. In a game, another player moves too, and wants the opposite outcome. Take the simplest case: two players taking turns, nothing hidden, and no dice. Such games are often zero-sum: whatever one player gains, the other loses. A game needs an initial state, like an empty tic-tac-toe grid, and whose turn it is. Then the legal actions, and the transition to each new position. A terminal test asks if the game is over. And a utility scores each ending: plus 1 if X wins, 0 for a draw, minus 1 if O wins.
Minimax
MAX, MIN, and Backed-Up Values
The two players are MAX, who wants the utility high, and MIN, who wants it low. Each level of the game tree is one player's turn, called a ply. Here, MAX has three moves, and MIN can answer each in three ways. The leaves are payoffs to MAX. Move 1 leads to 5, 8, or 6. Move 2 to 4, 7, or 9. Move 3 to 2, 10, or 12. Work upward. Where MIN moves, the value is the smallest child. So the moves are worth 5, 4, and 2. Where MAX moves, the value is the largest child: 5. MAX picks Move 1. Move 3 is tempting, with 10 and 12. But MIN decides which leaf appears, and MIN would choose the 2. Minimax is optimal against a perfect opponent: its move guarantees MAX at least the minimax value, whatever MIN does. It's complete for finite game trees. It runs depth-first, so memory stays modest, about b times m. But time is huge: about b to the m. And it doesn't exploit weak opponents. Assuming perfect play, it may miss a chance to do even better. Even small games are big. Tic-tac-toe has 255,168 possible games. Chess has about 35 moves per position, over about 80 plies: more than 10 to the 120th lines of play. So real programs search a few plies ahead, and estimate how good the unfinished positions look. Notice the shift. Alone, an agent searches for the best path. Against an opponent, it needs the best strategy: a plan that holds up against every reply.
Quick Check
Picking MAX's Move in a New Tree
Quick check, with a new tree. The left move leads to 7, 3, or 9. The middle move leads to 6, 5, or 8. The right move leads to 1, 15, or 11. MIN replies to each move. Which move should MAX pick? Pause, and decide. B: the middle move. MIN answers each move with its smallest leaf. So the left move is worth 3, the middle move 5, and the right move only 1. MAX takes the largest, 5. The right move is tempting, with 15 and 11, but MIN would answer it with the 1.
Key Takeaways
Blind Search and Minimax Summed Up
To sum up. A problem becomes searchable once it has states, actions, a goal test and a path cost. Blind strategies differ only in which frontier node they expand next. BFS finds the fewest actions, UCS the lowest cost, and DFS saves memory, but guarantees neither. Iterative deepening gives BFS results with DFS memory. And minimax picks the move that survives the best reply.
Reflection
When Breadth-First Still Wins
Something to think about. Iterative deepening repeats work, yet it's often preferred. When would you still choose breadth-first search? And what might minimax miss, if a real opponent isn't a perfect player?
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Blind and Competitive Search Strategies
What is the difference between breadth-first search and depth-first search?
How does uniform-cost search find the cheapest path?
Why use iterative deepening search instead of breadth-first search?
How does the minimax algorithm choose a move?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →