Combinatorial search

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Combinatorial search studies algorithms for solving hard problems by exploring the large space of possible solutions. These methods try to be efficient by shrinking the search space or by using heuristics (rules of thumb). Some algorithms can guarantee the best possible solution, while others only guarantee the best solution found within the explored area.

Classic examples include the eight queens puzzle and evaluating moves in big games like chess or Reversi. Computational complexity explains why these problems are hard: many are NP-hard, meaning no fast solution is known for all cases. However, smaller or simpler instances can often be solved quickly and still have real-world importance.

Common techniques include:

- Lookahead: how deeply the algorithm explores the problem’s decision graph. Large problems require limiting lookahead to avoid using too much time or memory; deeper searches grow exponentially.

- Alpha-beta pruning: a smarter approach that cuts away whole parts of the search tree that won’t affect the final result, making search much faster. With these techniques, lookahead is not a fixed depth but depends on how much of the search is explored and the average case.