Module 4 - Classical Search Flashcards
What is the difference between a certain and uncertain world in AI?
A certain world is one where the outcome of each action is known and predictable. It is rule-governed and deterministic. In contrast, an uncertain world is one where actions have multiple possible consequences and are stochastic (not precisely predictable).
How does AI define problem-solving?
AI defines problem-solving as finding the best possible solution given constraints. However, we may not always find the best solution, but we can find the best strategy within given cost constraints.
What are the two core components of AI problem-solving?
AI problem-solving requires:
- Representation – The AI must first structure the problem in a way that it can be processed.
- Search – The AI explores the possible solutions systematically
Why is representation crucial in AI problem-solving?
The way a problem is represented determines the difficulty of solving it. A simple representation often leads to simpler solutions, while a complex representation may make a problem more computationally expensive.
How does representation affect neural network training?
When training a neural network, searching for the lowest error point in a landscape is crucial. A better representation of the problem can lead to faster convergence and improved accuracy.
What is state-space search in AI?
A state-space search involves defining:
- State Representation – What are the different possible conditions of the problem?
- Operators – What actions can be taken to move between states?
- Search Strategy – How does the AI explore the possible states to find the goal?
What is an example of problem-solving using state-space search?
The 8-puzzle problem is a good example. The AI represents the board as a state space, defines valid moves, and then searches for the shortest sequence of moves to reach the goal.
What is the difference between random search and structured search?
- Random search: Tries moves blindly, often leading to inefficiency and infinite loops.
- Structured search: Uses algorithms to find the most efficient path.
How does Breadth-First Search (BFS) work?
BFS explores all possible paths level by level, ensuring that the shortest path to the goal is found.
What is the difference between the open list and closed list in BFS?
- Open list: Keeps track of states that need to be explored.
- Closed list: Stores already explored states to avoid redundant checks.
What are the advantages and disadvantages of BFS?
Advantage: Guarantees finding the shortest path to the solution.
Disadvantage: Memory-intensive because it explores many possibilities
How does Depth-First Search (DFS) differ from BFS?
DFS goes deeper into the search tree first, rather than exploring all nodes at the same level. It can use less memory than BFS but may get stuck in deep searches.
When is DFS preferable over BFS?
DFS is preferable when:
- The solution path is long.
- The branching factor is low (fewer choices at each step).
What is combinatorial explosion in AI?
Combinatorial explosion occurs when the number of possible solutions grows exponentially, making it impossible to explore all options in a reasonable time.
How does AI combat combinatorial explosion?
- Heuristics – Using rules of thumb to guide the search.
- Pruning – Eliminating paths that are unlikely to lead to the goal.
What is an example of combinatorial explosion in AI?
The game of chess. The number of possible moves grows exponentially, requiring strategies like heuristics and pruning to manage complexity.
What is Best-First Search?
Best-First Search prioritizes exploring the most promising paths first based on an evaluation function.
How does a heuristic function work in AI search?
A heuristic function estimates how close a state is to the goal. The lower the evaluation value, the more promising the state.
What is an example of a heuristic in problem-solving?
In the 8-puzzle, one heuristic is counting how many tiles are out of place compared to the goal state.
What is the advantage of Best-First Search over BFS and DFS?
Best-First Search can drastically reduce the number of explored states by focusing on the most promising paths.
What was IBM’s Deep Blue, and why was it significant?
Deep Blue was the first AI to defeat a world chess champion (Garry Kasparov) in 1997.
What made Deep Blue powerful?
- It evaluated 200 million positions per second.
- Used heuristic functions and opening/endgame databases.
How does AI evaluate board positions in chess?
AI uses an evaluation function that assigns a score based on piece values, positioning, and strategy.
What role do game databases play in chess AI?
AI can memorize optimal moves from previous games, reducing the need for real-time calculations.
