Search and planning: A* and Monte Carlo tree search

In short: Planning means finding a good one among many possible sequences of actions. Classic search methods such as A* and Monte Carlo tree search do this, and they also sit behind game AI.

A* (A-star)

A* finds the shortest path in a graph, for example on a map. Every node is rated:

f(n) = g(n) + h(n)

• g(n): cost so far from the start.
• h(n): estimated remaining cost to the goal (the heuristic, for example straight-line distance).

A* always expands the node with the smallest f. If the heuristic is never too optimistic, the path found is guaranteed to be shortest. See also Dijkstra’s algorithm (A* without a heuristic).

Monte Carlo tree search (MCTS)

For games with a huge state space full search is impossible. MCTS builds a search tree step by step in four phases:

1. Selection: descend from the start state to a promising leaf (balance of exploring and exploiting, rule UCT).
2. Expansion: add a new move.
3. Simulation: play the game to the end with random or learned moves.
4. Backpropagation: pass the result up along the path.

After many repetitions the most visited move is the best.

With neural networks

Modern systems replace the random simulation and move selection with networks that rate positions. That is the core of AlphaGo, see Game AI: chess, Go and poker.

See also: Breadth-first and depth-first search, Reinforcement learning