Algorithm dossier

  • Category: Game AI
  • Worst-case complexity: O(2ⁿ)
  • Approach: Recursive
  • Data structure: Tree
  • First formalised: 1950s

Why this snippet is Minimax with Alpha-Beta Pruning

Why minimax + alpha-beta. Two players alternate (mx flips); the maximiser maximises s.value(), the minimiser minimises it. The a/b window is the pruning trick: if a >= b, the current branch *cannot improve on what the opponent already guarantees*, so abandon it. Speedup. With good move ordering, alpha-beta explores √(branches^depth) instead of branches^depth — turning unplayable depths into reachable ones.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.