Search formulas

Uniform tree with branching factor $b$, goal at depth $d$, the last iteration generating every node to depth $d$, root counted in every iteration. Nodes at depth $i$ are generated $d+1-i$ times.

From the sum above with $k=d-i$: $N_{\text{IDS}}=b^d{\sum }_{k=0}^d(k+1)b^{-k}<b^d(1-1/b{)}^{-2}$. For $b=2$ the factor is 4; for $b=10$ it is about 1.23.

A* always expands the frontier node with the smallest $f$. Greedy best-first search uses $f(n)=h(n)$ alone; uniform-cost search is A* with $h\equiv 0$.

Never overestimates the true remaining cost. Enough for A* to be optimal in tree search, and in graph search when cheaper paths re-open expanded nodes.

A triangle inequality on estimates. Every consistent heuristic is admissible; the converse is false. Along any path $f$ never decreases when $h$ is consistent.

Two-player zero-sum game, perfect information, finite tree. The value is computed bottom-up.

$m$ is the maximum depth of the game tree. Minimax is complete on a finite tree and optimal against an optimal opponent.

Updates: at a MAX node $\alpha \leftarrow \max (\alpha ,v)$; at a MIN node $\beta \leftarrow \min (\beta ,v)$, where $v$ is the best child value so far. Pruning when $\alpha =\beta$ is safe because it cannot change the root value. Some sources prune only when $\alpha >\beta$; that can change the number of pruned leaves but never the root value. These notes use $\alpha \ge \beta$.

With perfect ordering alpha-beta can look about twice as deep as minimax in the same time; with random ordering the cost is roughly $b^{3m/4}$. The root value is the same for every ordering; only the number of pruned leaves changes.

Uniform game tree with branching factor $b$, all leaves at depth $m$, distinct leaf values, children ordered best-first for the player to move. Example: $b=3$, $m=2$ gives $3+3-1=5$ leaves (all three under the first MIN child, then one under each other child).