Heuristics of \(A^\ast\)
Admissability: heuristic cost is less than or equal to the actual cost to the goal.
\begin{equation} h(A) \leq \text{actual cost from A to G} \end{equation}
Consistency: heuristic “arc” cost is less than or equal to the actual cost of each arc.
\begin{equation}
h(A) - h(C) \leq \text{cost}A\text{to}~C
\end{equation}
\(\alpha / \beta\) Pruning
An extension of the Minimax algorithm. It is a depth-first-search which saves time and space by “pruning” branches where there already are established minimums or maximums.
- In the beginning, variables are unknown. As such, \(\alpha = -\infty\) and \(\beta = \infty\)
- \(\alpha\) and \(\beta\) propagate between levels. For the Max player, only the \(\alpha\) gets changed. For the Min player, only the \(\beta\) gets changed.
- Prune any time \(\alpha \geq \beta\)