Define game. Write the benefits and limitations of depth limited search.

## Definition of a Game
A **game** in the context of Artificial Intelligence (AI) is a structured form of problem-solving between two or more intelligent entities (players, agents, or programs) who take turns moving in a well-defined environment. It consists of the following key components:

1. **Players**: Two or more decision-makers (e.g., human players, AI agents).
2. **Initial State**: The starting configuration of the game (e.g., chessboard with pieces in their initial positions).
3. **Rules**: A set of constraints and legal moves that define how the game progresses (e.g., pawns move forward in chess).
4. **State Space**: The set of all possible configurations (states) the game can be in.
5. **Terminal States**: States where the game ends (e.g., checkmate in chess or a player winning in tic-tac-toe).
6. **Objective**: The goal of each player (e.g., winning, minimizing/maximizing a score).
7. **Moves/Transitions**: Actions that change the state of the game (e.g., moving a piece in chess).
8. **Utility Function**: A function that assigns a value to terminal states (e.g., +1 for win, -1 for loss, 0 for draw).

Games can be classified based on:
- **Number of players** (two-player vs. multiplayer).
- **Information availability** (perfect information like chess vs. imperfect like poker).
- **Determinism** (deterministic like checkers vs. probabilistic like backgammon).
- **Turn order** (sequential like chess vs. simultaneous like Go).

---

## Depth-Limited Search: Benefits and Limitations

### **Benefits of Depth-Limited Search**
Depth-limited search is a variant of depth-first search (DFS) that restricts the search to a predefined depth limit (`d`) to avoid excessive computation. Its advantages include:

1. **Computational Efficiency**
   - Limits the search to a fixed depth, reducing the number of nodes explored compared to unconstrained DFS.
   - Prevents infinite loops in cyclic games (e.g., chess) by avoiding revisiting states.

2. **Practicality for Real-World Games**
   - Many games (e.g., chess, Go) have branching factors too large for exhaustive search. Depth-limited search provides a trade-off between solution quality and computational cost.
   - Useful in time-constrained environments (e.g., competitive AI where moves must be made quickly).

3. **Simplicity and Ease of Implementation**
   - Easy to implement compared to more complex algorithms like alpha-beta pruning or iterative deepening.
   - Requires minimal additional logic beyond standard DFS.

4. **Avoids Infinite Search in Cyclic Games**
   - By enforcing a depth limit, it prevents the algorithm from getting stuck in loops (e.g., repeatedly moving a pawn back and forth in chess).

5. **Works Well with Heuristics**
   - Can be combined with evaluation functions to estimate the utility of states at the depth limit, improving decision-making.

---

### **Limitations of Depth-Limited Search**
Despite its benefits, depth-limited search has significant drawbacks:

1. **Shallow Search May Miss Optimal Solutions**
   - If the depth limit (`d`) is too small, the algorithm may not reach the optimal solution (e.g., a winning move might be deeper than `d`).
   - Example: In chess, a forced mate in 5 moves might be overlooked if `d = 3`.

2. **Incomplete Search**
   - The search is not exhaustive; it may terminate without exploring all possible moves, leading to suboptimal decisions.
   - Guarantees no solution only if the depth limit is sufficient to reach a terminal state.

3. **Sensitivity to Depth Limit Choice**
   - The performance heavily depends on the choice of `d`. A poorly chosen `d` can lead to either:
     - **Overly shallow search**: Missing critical moves.
     - **Overly deep search**: Approaching the computational limits of exhaustive search.

4. **No Guarantee of Optimality**
   - Unlike minimax or alpha-beta pruning, depth-limited search does not guarantee finding the best possible move within the search tree.
   - The quality of the solution depends on the evaluation function used at the depth limit.

5. **Wasted Computation at Shallow Depths**
   - If the depth limit is too high, the algorithm may spend excessive time exploring irrelevant branches before reaching the limit.
   - Example: In a game with a branching factor of 30 (like chess), even `d = 4` explores \(30^4 = 810,000\) nodes, which can be computationally expensive.

6. **No Handling of Variable-Depth Solutions**
   - Some games have solutions at varying depths (e.g., a quick win vs. a long-term strategy). Depth-limited search cannot adapt dynamically to such scenarios without prior knowledge.

7. **Requires Backtracking**
   - Like DFS, it requires backtracking to explore all paths up to depth `d`, which can be memory-intensive for large `d`.

---

### **Comparison with Other Search Algorithms**
| Feature                     | Depth-Limited Search       | Breadth-First Search (BFS) | Depth-First Search (DFS) | Iterative Deepening DFS (IDDFS) | Alpha-Beta Pruning |
|-----------------------------|----------------------------|----------------------------|--------------------------|----------------------------------|--------------------|
| **Completeness**            | No (unless `d` is sufficient) | Yes                        | No (unless limited)      | Yes                              | Yes                |
| **Optimality**              | No                         | Yes (with uniform cost)    | No                       | Yes                              | Yes                |
| **Time Complexity**         | \(O(b^d)\)                 | \(O(b^d)\)                 | \(O(b^m)\) (where \(m\) is max depth) | \(O(b^d)\) (amortized) | \(O(b^{d/2})\) (pruned) |
| **Space Complexity**        | \(O(bd)\)                  | \(O(bd)\)                  | \(O(bm)\)                | \(O(bd)\)                        | \(O(bd)\)          |
| **Handles Cyclic Games**    | Yes (with depth limit)     | No (unless modified)       | No (unless modified)    | Yes                              | Yes                |
| **Guarantees Best Move**    | No                         | Yes (with uniform cost)    | No                       | Yes                              | Yes                |
| **Adaptability**            | Poor (fixed `d`)           | Poor (fixed depth)         | Poor (fixed depth)       | Good (adjusts `d`)              | Good (prunes branches) |
| **Implementation Complexity** | Low                     | Low                        | Low                      | Moderate                         | Moderate           |

---
```figure
{
  "type": "tree",
  "root": {
    "v": "Root",
    "children": [
      {
        "v": "Depth 1",
        "children": [
          {"v": "Depth 2 (A)"},
          {"v": "Depth 2 (B)"},
          {"v": "Depth 2 (C)"}
        ]
      },
      {
        "v": "Depth 1 (Limited to d=2)",
        "children": [
          {"v": "Depth 2 (X)"},
          {"v": "Depth 2 (Y)"}
        ]
      }
    ]
  },
  "highlight": ["Depth 2 (A)", "Depth 2 (B)", "Depth 2 (C)"],
  "caption": "Depth-limited search (d=2) explores only up to depth 2, ignoring deeper branches."
}

---

Example: Depth-Limited Search in Tic-Tac-Toe

Consider a tic-tac-toe game where the AI (X) is searching for the best move with a depth limit of d = 3. The search tree might look like this (simplified):

1. Root Node: Current board state.
2. Depth 1: All possible moves for X (e.g., top-left, top-center, etc.).
3. Depth 2: Opponent’s (O) responses to each of X’s moves.
4. Depth 3: X’s counter-moves to O’s responses.
5. Evaluation: At depth 3, the algorithm evaluates terminal states or uses a heuristic (e.g., count lines with two X’s and one empty space).

If d = 3 is insufficient to reach a terminal state (e.g., a win), the algorithm may return a suboptimal move. Increasing d improves accuracy but increases computation time.

---

def depth_limited_search(node, depth_limit):
    """
    Perform depth-limited search up to a given depth limit.
    Returns the best move found within the limit.
    """
    if depth_limit == 0:
        return evaluate(node)  # Heuristic evaluation

    best_value = float('-inf')
    best_move = None

    for move in legal_moves(node):
        child = make_move(node, move)
        value = minimax(child, depth_limit - 1, False)  # Alternate players
        if value > best_value:
            best_value = value
            best_move = move

    return best_move

def minimax(node, depth, is_maximizing):
    """Minimax with depth limit (helper function)."""
    if depth == 0 or is_terminal(node):
        return evaluate(node)

    if is_maximizing:
        best_value = float('-inf')
        for move in legal_moves(node):
            child = make_move(node, move)
            best_value = max(best_value, minimax(child, depth - 1, False))
        return best_value
    else:
        best_value = float('inf')
        for move in legal_moves(node):
            child = make_move(node, move)
            best_value = min(best_value, minimax(child, depth - 1, True))
        return best_value

How it works:

• depth_limited_search explores all possible moves up to the specified depth_limit.
• minimax recursively evaluates the game tree, alternating between maximizing (AI) and minimizing (opponent) players.
• The search terminates when depth_limit is reached or a terminal state is found. The best move is chosen based on the highest/minimum evaluation score.