This repository contains the implementation of search algorithms discussed in CS50's Introduction to Artificial Intelligence course. The focus is on various search techniques used to solve problems where an agent needs to find a path from an initial state to a goal state.
Watch the interactive pathfinding game in action! This demo shows how you can visualize and compare different search algorithms in real-time.
Watch the Path Finding Game Visualization in action:
Demo.mp4
*Click the image above to watch the full demonstration video for the Path Finding Game
Features demonstrated in the video:
- Interactive grid creation with walls and obstacles
- Real-time visualization of Greedy Best-First Search
- Real-time visualization of A* Search
- Live comparison of algorithm performance
- Step-by-step exploration visualization
Try it yourself:
python pathfinding_game.pyArtificial Intelligence involves creating systems that can perform tasks that typically require human intelligence. In the context of search problems, AI agents must make decisions about which actions to take to reach their objectives efficiently.
Search problems involve:
- Initial State: The starting point of the problem
- Actions: The possible moves available from any given state
- Transition Model: How actions change the current state
- Goal Test: Determines if the current state is the goal
- Path Cost: The cost associated with a particular path
Search algorithms systematically explore the state space to find a solution. They maintain a frontier (set of states to explore) and keep track of explored states to avoid cycles.
- Node: Contains state, parent, action, and path cost
- Frontier: Data structure holding nodes to be explored
- Explored Set: Previously visited states
DFS explores as far as possible along each branch before backtracking. It uses a stack (LIFO) for the frontier.
Characteristics:
- Not optimal (doesn't guarantee shortest path)
- Complete in finite state spaces
- Space complexity: O(bm) where b is branching factor, m is maximum depth
- Time complexity: O(b^m)
BFS explores all nodes at the current depth before moving to nodes at the next depth. It uses a queue (FIFO) for the frontier.
Characteristics:
- Optimal for unweighted graphs
- Complete if branching factor is finite
- Space complexity: O(b^d) where d is depth of solution
- Time complexity: O(b^d)
This algorithm selects the node that appears to be closest to the goal based on a heuristic function h(n).
Characteristics:
- Uses heuristic to guide search
- Not optimal
- More efficient than uninformed search
- Can get stuck in local optima
A* combines the benefits of Dijkstra's algorithm and Greedy Best-First Search. It uses f(n) = g(n) + h(n), where:
- g(n): Cost from start to current node
- h(n): Heuristic estimate from current node to goal
Characteristics:
- Optimal if heuristic is admissible (never overestimates)
- Complete
- Optimally efficient
- Space complexity can be exponential
| Aspect | Greedy Best-First Search | A* Search |
|---|---|---|
| Evaluation Function | f(n) = h(n) | f(n) = g(n) + h(n) |
| Completeness | No¹ | Yes |
| Optimality | No | Yes² |
| Time Complexity | O(b^m) | O(b^d) |
| Space Complexity | O(b^m) | O(b^d) |
| Heuristic Usage | Only h(n) | Both g(n) and h(n) |
| Search Strategy | Always chooses most promising node | Balances path cost and heuristic |
| Memory Efficiency | Medium | Medium |
| Best For | Quick approximate solutions | Optimal pathfinding |
| Worst Case | Can get stuck in local minima | Explores more nodes but finds optimal path |
| Implementation | Simpler | More complex |
| Performance | Fast but may be suboptimal | Slower but guaranteed optimal |
Notes:
- ¹ May not find solution if heuristic leads to dead ends
- ² Optimal when using admissible heuristics (never overestimates true cost)
Greedy Best-First Search:
- Advantage: Very fast, uses minimal memory
- Disadvantage: Not guaranteed to find optimal path, can get stuck
- Use Case: When speed is more important than optimality
A Search:*
- Advantage: Guaranteed to find optimal path, systematic exploration
- Disadvantage: Slower, explores more nodes
- Use Case: When optimal solution is required
In our pathfinding game demo, you can observe:
- Greedy: Explores fewer cells but may find longer paths
- A*: Explores more cells but always finds the shortest path
In adversarial search, multiple agents have conflicting goals. This is common in games where one player's gain is another's loss (zero-sum games).
- Players: The agents in the game
- Initial State: Starting position
- Actions: Legal moves available
- Result: Outcome of an action
- Terminal Test: Determines if game is over
- Utility Function: Assigns numerical value to terminal states
Minimax is a decision-making algorithm for turn-based games. It assumes both players play optimally:
- Maximizing player: Tries to maximize the score
- Minimizing player: Tries to minimize the score
The algorithm recursively evaluates all possible moves and chooses the one with the best outcome.
Characteristics:
- Optimal against optimal opponent
- Time complexity: O(b^m)
- Space complexity: O(bm)
Alpha-Beta pruning optimizes minimax by eliminating branches that won't affect the final decision.
- Alpha: Best value maximizer can guarantee
- Beta: Best value minimizer can guarantee
- Pruning: When alpha ≥ beta, remaining branches can be ignored
Benefits:
- Reduces time complexity (best case: O(b^(m/2)))
- Same result as minimax
- Allows deeper search in same time
For games that are too complex for full minimax search, depth-limited minimax stops at a certain depth and uses an evaluation function to estimate the value of non-terminal states.
Characteristics:
- Practical for complex games
- Uses evaluation function for intermediate states
- Trade-off between search depth and computation time
- Often combined with iterative deepening
# Run DFS (default)
python maze.py maze.txt
# For BFS, change StackFrontier() to QueueFrontier() in maze.py| Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|
 |
 |
| Maze 1 solved using Depth-First Search | Maze 1 solved using Breadth-First Search |
DFS vs BFS Analysis for Maze 1:
- DFS: Explores deeper paths first, may find longer solution but uses less memory
- BFS: Finds optimal (shortest) path, explores more nodes but guarantees shortest solution
- States Explored: BFS typically explores more states but finds optimal path
- Solution Quality: BFS finds shorter path in terms of steps
| Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|
 |
 |
| Maze 2 solved using Depth-First Search | Maze 2 solved using Breadth-First Search |
DFS vs BFS Analysis for Maze 2:
- DFS: May find suboptimal path quickly, explores one branch completely
- BFS: Systematically explores all possibilities at each level, finds optimal solution
- Performance: Significant difference in solution quality for complex mazes
- Memory Usage: DFS uses less memory, BFS requires more space for frontier
| Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|
 |
 |
| Maze 3 solved using Depth-First Search | Maze 3 solved using Breadth-First Search |
DFS vs BFS Analysis for Maze 3:
- DFS: Performance varies greatly depending on maze structure
- BFS: Consistent performance, always finds optimal path
- Scalability: BFS memory requirements grow exponentially with maze size
- Practical Use: DFS better for memory-constrained environments
| Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|
 |
 |
| Maze 4 solved using Depth-First Search | Maze 4 solved using Breadth-First Search |
DFS vs BFS Analysis for Maze 4:
- DFS: Quick exploration but may miss optimal paths
- BFS: Systematic approach ensures shortest solution
- Comparison: Clear visual difference in exploration patterns and solution paths
- Efficiency: Trade-off between memory usage and solution optimality
| Algorithm | Complete | Optimal | Time Complexity | Space Complexity | Pros | Cons |
|---|---|---|---|---|---|---|
| Depth-First Search (DFS) | Yes¹ | No | O(b^m) | O(bm) | Low memory usage Simple implementation Good for deep solutions Fast when solution is deep |
Not optimal Can get stuck in infinite paths Poor performance if solution is shallow May explore irrelevant deep paths |
| Breadth-First Search (BFS) | Yes | Yes² | O(b^d) | O(b^d) | Finds optimal solution Systematic exploration Good for shallow solutions Predictable behavior |
High memory usage Slower for deep solutions Exponential space growth May be overkill for some problems |
Notes:
- ¹ Complete in finite state spaces
- ² Optimal for unit step costs
- b = branching factor, m = maximum depth, d = depth of optimal solution
Use DFS when:
- Memory is limited
- Solution is likely to be deep
- Any solution is acceptable (optimality not required)
- Exploring all paths is needed
Use BFS when:
- Optimal solution is required
- Solution is likely to be shallow
- Memory is not a constraint
- Step costs are uniform
- Choice of Algorithm: Depends on problem constraints (optimality, time, space)
- Heuristics: Can significantly improve search efficiency when admissible
- Trade-offs: Between optimality, completeness, time, and space complexity
- Adversarial Settings: Require different approaches (minimax, alpha-beta pruning)
- Practical Considerations: Depth-limiting and evaluation functions for complex problems
- CS50's Introduction to Artificial Intelligence
- Search
- Harvard University / edX