AI-Search

AI-Search: Search

CS Core:

1. State space representation of a problem
   1. Specifying states, goals, and operators
   2. Factoring states into representations (hypothesis spaces)
   3. Problem solving by graph search
      1.         e.g., Graphs as a space, and tree traversals as exploration of that space
      2.         Dynamic construction of the graph (not given upfront)
2. Uninformed graph search for problem solving (See also: AL-Foundational)
   1. Breadth-first search
   2. Depth-first search
      1.         With iterative deepening
   3. Uniform cost search
3. Heuristic graph search for problem solving (See also: AL-Strategies)
   1. Heuristic construction and admissibility
   2. Hill-climbing
   3. Local minima and the search landscape
      1.         Local vs global solutions
   4. Greedy best-first search
   5. A* search
4. Space and time complexities of graph search algorithms

KA Core:

5. Bidirectional search
6. Beam search
7. Two-player adversarial games
   5. Minimax search
   6. Alpha-beta pruning
      5.         Ply cutoff
8. Implementation of A* search
9. Constraint satisfaction

Non-core:

10. Understanding the search space
    10. Constructing search trees
    11. Dynamic search spaces
    12. Combinatorial explosion of search space
    13. Search space topology (e.g., ridges, saddle points, local minima)
11. Local search
12. Tabu search
13. Variations on A* (IDA*, SMA*, RBFS)
14. Two-player adversarial games
    10. The horizon effect
    11. Opening playbooks/endgame solutions
    12. What it means to “solve” a game (e.g., checkers)
15. Implementation of minimax search, beam search
16. Expectimax search (MDP-solving) and chance nodes
17. Stochastic search
    10. Simulated annealing
    11. Genetic algorithms
    12. Monte-Carlo tree search

Illustrative Learning Outcomes:

1. Design the state space representation for a puzzle (e.g., N-queens or 3-jug problem)
2. Select and implement an appropriate uninformed search algorithm for a problem (e.g., tic-tac-toe), and characterize its time and space complexities.
3. Select and implement an appropriate informed search algorithm for a problem after designing a helpful heuristic function (e.g., a robot navigating a 2D gridworld).
4. Evaluate whether a heuristic for a given problem is admissible/can guarantee an optimal solution.
5. Apply minimax search in a two-player adversarial game (e.g., connect four), using heuristic evaluation at a particular depth to compute the scores to back up. [KA Core]
6. Design and implement a genetic algorithm solution to a problem.
7. Design and implement a simulated annealing schedule to avoid local minima in a problem.
8. Design and implement A*/beam search to solve a problem, and compare it against other search algorithms in terms of the solution cost, number of nodes expanded, etc.
9. Apply minimax search with alpha-beta pruning to prune search space in a two-player adversarial game (e.g., connect four).
10. Compare and contrast genetic algorithms with classic search techniques, explaining when it is most appropriate to use a genetic algorithm to learn a model versus other forms of optimization (e.g., gradient descent).
11. Compare and contrast various heuristic searches vis-a-vis applicability to a given problem.
12. ​​Model a logic or Sudoku puzzle as a constraint satisfaction problem, solve it with backtrack search, and determine how much arc consistency can reduce the search space.

Suggestions Accepted for consideration for the next Edition:

1. Time complexity of search algorithms

Please provide your suggestions about this knowledge unit. All submitted comments will be reviewed at the end of the month. Comments accepted for inclusion will be listed above.