ACI — Formula Sheet (CS1–CS8, mid-sem)

Every formula you need for the CS1–CS8 mid-sem, on one page — each with its name, the equation, and a one-line "what each symbol means / when to use it." Learn the equation and the trigger. For the full derivation behind any line, open the slides explained.

Symbol key

Symbol	Meaning
\(b,\; d,\; m\)	branching factor, depth of shallowest goal, max tree depth
\(g(n)\)	cost of the path from start to node \(n\) (so far)
\(h(n),\; h^*(n)\)	heuristic estimate to goal; true cost to goal
\(f(n)\)	evaluation function used to order the frontier
\(\tau,\; \eta\)	pheromone on an edge; visibility \(\eta = 1/\text{distance}\)
\(\alpha,\; \beta,\; \rho,\; Q\)	ACO: pheromone weight, visibility weight, evaporation, deposit constant (\(\alpha/\beta\) also = pruning bounds in CS8)
\(T,\; \Delta E\)	temperature; change in objective/energy (simulated annealing)

Search & heuristics (CS2–CS4)

Agent function

\[ f : P^* \to A \]

Maps a percept history \(P^*\) to an action \(A\). The whole job of an agent is to realise a good \(f\).

A* evaluation

\[ f(n) = g(n) + h(n) \]

Order the frontier by cost-so-far + estimate-to-go. Greedy Best-First uses \(f = h\) only; UCS uses \(f = g\) only (i.e. \(h = 0\)).

Admissibility

\[ h(n) \leq h^*(n) \]

Never overestimate the true cost. Guarantees A* (tree search) returns an optimal path.

Consistency (monotonicity)

\[ h(n) \leq c(n,\, n') + h(n') \]

For every successor \(n'\) reached by step cost \(c\). Consistent ⇒ admissible (not the reverse); needed for optimal A* graph search.

Effective branching factor

\[ N + 1 = 1 + b^* + (b^*)^2 + \cdots + (b^*)^d \]

If A* expands \(N\) nodes to depth \(d\), \(b^*\) solves this. \(b^* \to 1\) means a sharp, informative heuristic.

8-puzzle heuristics

\[ h_1 = \#\text{ misplaced tiles} \qquad h_2 = \sum \text{Manhattan distances} \]

Both come from relaxed problems (so both admissible). \(h_2 \geq h_1\) always ⇒ \(h_2\) dominates and expands no more nodes.

Search complexity (CS3)

Algorithm	Time	Space	Optimal?
BFS	\(O(b^d)\)	\(O(b^d)\)	If equal step costs
DFS	\(O(b^m)\)	\(O(bm)\)	No
UCS	\(O\!\left(b^{1+\lfloor C^*/\varepsilon \rfloor}\right)\)	\(O\!\left(b^{1+\lfloor C^*/\varepsilon \rfloor}\right)\)	Yes
IDS	\(O(b^d)\)	\(O(bd)\)	Like BFS

Local search & optimization (CS4–CS5)

Simulated annealing — acceptance probability

\[ P(\text{accept worse move}) = e^{-\Delta E \,/\, T} \]

When a neighbour is worse by \(\Delta E\), still accept it with this probability. High \(T\) (hot) → explore freely; \(T \to 0\) (cooled) → behaves like greedy hill climbing.

Genetic algorithm — roulette-wheel selection

\[ P(\text{select } i) = \frac{\text{fitness}_i}{\displaystyle\sum_j \text{fitness}_j} \]

Probability of picking individual \(i\) as a parent is its share of total fitness. Fitter individuals breed more often (exploitation); mutation supplies exploration.

8-queens fitness

\[ \text{fitness} = \text{number of non-attacking pairs of queens} \]

Maximise it; for 8 queens the goal is 28 pairs (the slide demo uses \(k=4\) with threshold 6). Drives the GA / hill-climbing search.

Ant Colony Optimization (CS5–CS6)

Transition probability (next city)

\[ P_{ij} = \frac{(\tau_{ij})^\alpha\,(\eta_{ij})^\beta}{\displaystyle\sum_{h\,\in\,\text{allowed}} (\tau_{ih})^\alpha\,(\eta_{ih})^\beta} \]

An ant at \(i\) picks next city \(j\) by balancing pheromone \(\tau\) (collective memory, weight \(\alpha\)) and visibility \(\eta = 1/\text{dist}\) (greedy "shorter is better", weight \(\beta\)); denominator normalises over unvisited cities.

Pheromone update (evaporation + deposit)

\[ \tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \Delta\tau_{ij}, \qquad \Delta\tau_{ij} = \frac{Q}{f_k} \text{ (edges used by ant } k\text{, else } 0) \]

Every edge first evaporates by fraction \(\rho\) (exploration); edges on a tour gain \(Q / \text{tour-cost}\) (shorter tour ⇒ bigger deposit ⇒ exploitation). Repeat to converge on short routes.

Game playing (CS7–CS8)

Minimax value

\[ \text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal} \\ \displaystyle\max_a\; \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if PLAYER}(s) = \text{MAX} \\ \displaystyle\min_a\; \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if PLAYER}(s) = \text{MIN} \end{cases} \]

Back values up the tree: take the max at MAX nodes, the min at MIN nodes. MAX maximises its guaranteed (worst-case) outcome.

Static evaluation (when you can't reach leaves)

\[ \text{Eval} = w_1 f_1 + w_2 f_2 + \cdots \qquad \text{simple: } (\text{MAX pieces}) - (\text{MIN pieces}) \]

A fast weighted sum of board features estimating utility of a non-terminal state at the depth cutoff. Higher = better for MAX.

Alpha-beta cutoff

\[ \text{prune when } \beta \leq \alpha \qquad \alpha = \text{best for MAX (init } {-\infty}\text{)}, \quad \beta = \text{best for MIN (init } {+\infty}\text{)} \]

Stop expanding a node's remaining children once \(\beta \leq \alpha\) — they can't change the result. Same answer as minimax; best-case nodes \(\approx O(b^{d/2})\) with good move ordering (doubles reachable depth).

UCB — MCTS selection

\[ \text{UCB1} = \frac{w_i}{n_i} + c\,\sqrt{\frac{\ln N}{n_i}} \]

Pick the child maximising this: first term = exploitation (win rate \(w/n\)), second = exploration (grows when node \(n_i\) is under-visited vs parent visits \(N\)). \(c\) tunes the balance.

Neural building blocks (CS6)

ReLU activation

\[ f(x) = \max(0,\, x) \]

Drops negative activations; cheap non-linearity used between conv/dense layers in the evolved CNNs.

Softmax (class probabilities)

\[ P(y_i) = \frac{e^{z_i}}{\displaystyle\sum_j e^{z_j}} \]

Turns the output logits \(z\) into a probability distribution over classes (e.g. Cat = 0.92, Dog = 0.08). Largest logit wins.

How to revise this. Cover the right column and recall what each symbol means; then cover the equation and re-derive it from the name. You should be able to reproduce A* (f=g+h), the two heuristic inequalities, simulated annealing, both ACO equations, minimax, the alpha-beta cutoff, and softmax from memory.