Module 2:
Heuristic Search Techniques and Game
Playing
Heuristic Search Techniques: AI and Search Process
A heuristic is a problem-solving technique that improves the efficiency of finding solutions
by guiding the search process toward the most promising paths. In AI, heuristic search
techniques use rules of thumb or educated guesses to speed up the search for solutions in
complex problems. This helps avoid the exhaustive search over all possibilities.
1. AI and Search Process:
In AI, search is a systematic process of navigating through a problem space to find a goal
state (solution) from an initial state.
AI search can be broadly divided into two categories:
• Uninformed Search (Brute Force Search): These methods don't use any
domain-specific information (heuristics) to guide the search.
• Informed Search (Heuristic Search): These methods use heuristics to guide the
search more efficiently by focusing on the most promising paths.
2. Brute Force Search:
Brute force search explores all possible solutions without any domain knowledge. It
guarantees finding the correct solution but is inefficient for large problem spaces.
3. Depth-First Search (DFS):
Process: DFS explores as deep as possible down one path before backtracking. Uses a
stack (LIFO).
- Advantages: Requires less memory than BFS.
- Disadvantages: Can get stuck in irrelevant paths.
- Time Complexity: O(b^m), where b is branching factor, m is max depth.
- Space Complexity: O(b*m).
4. Breadth-First Search (BFS):
Process: Explores all nodes at present depth level before moving to next. Uses a queue
(FIFO).
- Advantages: Guarantees the shortest path.
- Disadvantages: Requires a lot of memory.
- Time Complexity: O(b^d), where d is depth of the shallowest solution.
- Space Complexity: O(b^d).
5. Heuristic Search:
In contrast to brute force searches, heuristic search uses knowledge about the problem
domain to make decisions. A heuristic function evaluates each node and estimates the
cost of reaching the goal from that node.
6. Hill Climbing:
Hill climbing is a local search algorithm that iteratively moves towards the most
promising neighbor (one with a higher evaluation score). It is greedy and does not
look ahead.
Types:
1. Simple Hill Climbing: Evaluates each neighbor and moves to the first better
state.
2. Steepest-Ascent Hill Climbing: Evaluates all neighbors and selects the best one.
Problems:
1. Local Maxima: The algorithm may get stuck at a peak that is lower than the
global maximum.
2. Plateau: A flat region with no better moves.
3. Ridges: Requires moving in several directions to continue improving.
Time and Space Complexities: Dependent on the number of neighbors evaluated.
Generally O(n), where n is the number of neighbors.
7. Best-First Search:
Process: Best-first search evaluates all neighbors and chooses the one closest to the
goal. It uses a priority queue to always expand the most promising node.
- Time Complexity: O(b^d).
- Space Complexity: O(b^d).
8. A* Algorithm:
Process: A* is a combination of the Best-First Search and Dijkstra’s Algorithm. It uses
a heuristic function. Uses f(n) = g(n) + h(n),
where g(n) is cost to node, h(n) heuristic, f(n) estimates the total cost of the path
through n.
- Optimality: A* is optimal if the heuristic is admissible .(i.e., it never overestimates the
cost to reach the goal).
- Time and Space Complexity: O(b^d).
- Space Complexity: It stores all generated nodes, making it memory-intensive.
9. Beam Search:
Process: A variant of best-first search that only keeps a fixed number of the most
promising nodes (the "beam width") at each level, discarding less promising nodes.
- Advantages: Less memory-intensive than Best-First Search.
- Disadvantages: Might miss the optimal solution if it prunes important paths.
- Time Complexity: O(w*d).
- Space Complexity: O(w), where w is the beam width.
10. AO* Search:
Process: AO* is used in AND-OR graphs, which involve combining partial solutions. It
recursively selects nodes, expands them, and combines the results of subproblems.-
Time and Space Complexities: Similar to A*.
11. Constraint Satisfaction Problems (CSPs):
Process: CSPs involve finding solutions that satisfy a set of constraints. Examples
include Sudoku, scheduling problems, and graph coloring.
Example: In Sudoku, each cell must satisfy the constraints that no row, column, or
subgrid can have duplicate numbers.
- Types:
Backtracking: Tries partial solutions and backtracks when a constraint is violated.
Constraint Propagation: Narrows down the possibilities for each variable by enforcing
constraints (e.g., arc consistency).
Local Search: Involves iterative improvement, moving to neighboring solutions that
violate fewer constraints.
Game Playing in AI
Game Playing in AI:
In AI, game playing is an important application of search algorithms. The goal is to create
systems that can play games intelligently, often against a human or another computer. Game
playing involves making decisions by searching through possible game states (moves) and
choosing the best course of action to maximize the chance of winning.
1. AI and Game Playing:
AI uses search techniques to play games. A typical game-playing AI simulates potential
future moves and their consequences before choosing the best move. Classic examples of
games where AI has been applied include chess, checkers, and tic-tac-toe.
Two-player games (like chess) are typically adversarial, where one player’s gain is another
player’s loss. These are called zero-sum games.
AI needs to handle large decision trees efficiently and anticipate the opponent's moves.
2. Plausible Move Generator:
Plausible Move Generation is the process of generating a set of "reasonable" or promising
moves from the current game state. Instead of evaluating every possible move (which can
be computationally expensive), AI focuses on moves that are likely to lead to a good
outcome.
In complex games, generating all possible moves is impractical due to the combinatorial
explosion of possibilities. For example, chess has approximately 10^120 possible game
states.
Examples:
- In chess, plausible moves might include capturing an opponent's piece or moving a piece
to control more of the board.
- AI can prune moves that are unlikely to be useful (such as moving a piece back to its
original position without a tactical reason).
3. Static Evaluation Function:
The static evaluation function estimates the value of a game position without having to
search all the way to the end of the game. It is typically used when the search depth is
limited (e.g., in time-constrained environments).
It assigns a numerical score to a game position. The higher the score, the better the position
for the player. In chess, this might consider factors like material advantage (pieces), control
of the center, king safety, and piece mobility.
Example:
- In chess, a static evaluation function might give 9 points for a queen, 5 for a rook, and 1 for
a pawn. The function would then sum the material on the board and combine it with other
factors to evaluate the position.
4. Move Generator:
A move generator is responsible for generating all legal moves for a player at any point in
the game.
It is the part of the game-playing AI that generates new game states based on the current
position. This includes moves like placing a piece in chess, moving a token in checkers, or
discarding a card in a card game.
Efficiency is important, so good move generators prune or ignore moves that are unlikely to
be beneficial. They only generate moves that are worth exploring based on game knowledge
or heuristics.
5. Game Playing Strategies:
Several strategies are employed by AI in games. The two most famous are the minimax
algorithm and alpha-beta pruning:
- Minimax Algorithm:
- Goal: In a two-player game, the minimax algorithm aims to minimize the possible loss for
a worst-case scenario.
- Process: The AI simulates all possible moves for both itself and its opponent. It assumes
the opponent will play optimally and make moves that minimize the AI’s chances of
winning.
- Min: The opponent tries to minimize the AI’s score.
- Max: The AI tries to maximize its own score.
Example: In a game like chess, the minimax algorithm examines all possible moves by both
players to find the move that leads to the best worst-case outcome (hence, the name
minimax).
Time Complexity: O(b^d), where b is the branching factor and d is the depth of the tree
being explored.
- Alpha-Beta Pruning:
- Goal: Alpha-beta pruning is an optimization technique for the minimax algorithm. It
reduces the number of nodes evaluated in the game tree.
- Process: It "prunes" branches of the search tree that don’t need to be explored because
they won’t affect the final decision.
- Alpha: The best score the maximizing player can guarantee so far.
- Beta: The best score the minimizing player can guarantee so far.
Example: In chess, if the AI already found a move leading to a strong position (high alpha),
it can prune (skip) certain branches that lead to worse positions than that threshold,
speeding up the decision-making process.
6. Problems in Game Playing:
Game-playing AI faces several key challenges:
- Computational Complexity:
- Large Search Space: Some games, like chess or Go, have a vast number of possible game
states (chess has around 10^120 possible positions). Searching through all of them is
computationally infeasible.
- Time Constraints: In real-time or turn-based games, AI must make decisions within a
limited time frame, requiring fast and efficient algorithms.
- Opponent Modeling:
- AI must anticipate the opponent’s strategies, which can be difficult if the opponent
behaves unpredictably or doesn’t follow optimal strategies.
- Resource Management:
- The AI may need to manage resources, such as memory or computational power, to
ensure it doesn’t run out while searching through game states.
- Uncertainty:
- In games with hidden information or chance elements (like poker or dice games), the AI
must deal with uncertainty and make decisions based on incomplete knowledge.
- Imperfect Evaluation:
- The static evaluation function can be imperfect, especially in complex positions where
long-term strategies are difficult to assess. For example, a position might appear poor in the
short term but lead to a strong strategic advantage later in the game.