1. Optimality and Quality of Heuristics

The efficiency, runtime complexity, and memory requirements of heuristic search algorithms such as $A^*$ depend heavily on the quality of the heuristic function employed. While admissibility guarantees that $A^*$ will find an optimal solution, the choice of heuristic dictates how effectively the search space is pruned and how rapidly the search frontier contracts toward the goal state.

1.1 Role of Heuristics in $A^*$ Search

1.1.1 Evaluation Function and Search Guidance

In $A^*$ search, the node evaluation function $f(n)$ determines the priority of node expansion within the frontier queue. The function combines the known exact cost to reach node $n$ from the start state with an estimated cost to reach the goal state:

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

where:

• $g(n)$ represents the exact path cost incurred from the initial start state $n_0$ to node $n$.
• $h(n)$ denotes the heuristic cost-to-go estimate from node $n$ to the nearest goal state $n_g$.

The heuristic function $h(n)$ acts as a search guidance mechanism, providing domain-specific estimates that direct the algorithm toward promising paths. A node $n$ is expanded during $A^*$ search only when its evaluated $f(n)$ value is minimal among all unexpanded nodes in the frontier.

1.1.2 Admissibility and Optimality Guarantees

To guarantee that $A^*$ search returns an optimal (lowest-cost) path, the heuristic function $h(n)$ must be admissible.

A heuristic $h(n)$ is defined as admissible if it never overestimates the true minimal cost to reach the goal state from node $n$. Mathematically, for every state $n$ in the search space:

$$h(n) \le h^*(n)$$

where $h^*(n)$ represents the true, optimal cost-to-go from node $n$ to the goal. Additionally, for any goal state $n_g$, an admissible heuristic satisfies $h(n_g) = 0$.

Under an admissible heuristic, $A^*$ is guaranteed to yield an optimal solution path $C^*$.

1.2 Heuristic Domination

1.2.1 Mathematical Definition of Domination

When choosing between multiple admissible heuristics for a given problem, the concept of domination provides a formal basis for comparison.

Given two admissible heuristics $h_1(n)$ and $h_2(n)$, heuristic $h_2$ dominates heuristic $h_1$ if and only if:

1. For all states $n$ in the search space, $h_2(n) \ge h_1(n)$.
2. For at least one state $n$, $h_2(n) > h_1(n)$ (ensuring that $h_1$ and $h_2$ are not identically equal).

Mathematically, domination establishes a partial ordering over the space of admissible heuristic functions. If both $h_1(n)$ and $h_2(n)$ are admissible and $h_2(n)$ dominates $h_1(n)$, then $h_2(n)$ is tighter (closer to $h^*(n) $) and remains strictly admissible.

1.2.2 Impact on Node Expansions and Memory Frontiers

The primary theoretical and practical advantage of a dominating heuristic lies in node expansion savings and memory reduction:

An $A^*$ implementation utilizing a dominating heuristic $h_2(n)$ will expand no more nodes than an $A^*$ implementation utilizing $h_1(n)$.

The intuition behind this theorem follows directly from the definition of the evaluation function $f(n) = g(n) + h(n)$:

• A larger, more accurate heuristic value $h_2(n)$ increases the total objective value $f(n)$ for non-optimal or off-path nodes.
• Higher $f(n)$ values delay or completely eliminate the expansion of nodes that lie further from the optimal goal path.
• Consequently, a dominating heuristic narrows the search frontier earlier, consumes significantly less memory for open node storage, and shrinks the total explored search tree.

1.2.3 Case Study: Misplaced Tiles vs. Manhattan Distance in the 8-Tile Puzzle

Consider the 8-tile puzzle domain, consisting of a $3 \times 3$ grid with 8 numbered tiles and one blank space.

We evaluate two classic handcrafted heuristics:

1. Misplaced Tiles ($h_1$): The count of non-blank tiles currently not residing in their target goal positions.
2. Manhattan Distance ($h_2$): The sum of horizontal and vertical grid distances (taxicab distance) for each tile from its current position to its goal position.

Let $\overrightarrow{p}_i = (x_i, y_i)^T$ denote the current grid coordinates of tile $i$, and let $\overrightarrow{p}_i^{\text{goal}} = (x_i^{\text{goal}}, y_i^{\text{goal}})^T$ denote its target goal coordinates.

The two heuristics are expressed mathematically as:

$$h_1(n) = \sum\limits_{i=1}^{8} \mathbb{I}\left( \overrightarrow{p}_i(n) \ne \overrightarrow{p}_i^{\text{goal}} \right)$$

$$h_2(n) = \sum\limits_{i=1}^{8} \left( \left| x_i(n) - x_i^{\text{goal}} \right| + \left| y_i(n) - y_i^{\text{goal}} \right| \right)$$

For any single tile $i$ that is misplaced ($\overrightarrow{p}_i(n) \ne \overrightarrow{p}_i^{\text{goal}}$), moving tile $i$ to its goal position requires at least $1$ grid move, but in general requires $\left| x_i(n) - x_i^{\text{goal}} \right| + \left| y_i(n) - y_i^{\text{goal}} \right| \ge 1$ moves.

Thus, for every individual state $n$:

$$\begin{alignat*}{4} && h_2(n) &= \sum\limits_{i=1}^{8} \left( \left| x_i(n) - x_i^{\text{goal}} \right| + \left| y_i(n) - y_i^{\text{goal}} \right| \right) && \ && &\ge \sum\limits_{i=1}^{8} \mathbb{I}\left( \overrightarrow{p}_i(n) \ne \overrightarrow{p}_i^{\text{goal}} \right) && \text{Since grid move count } \ge 1 \text{ for each misplaced tile} \ && &= h_1(n) && \ \end{alignat*}$$

Because $h_2(n) \ge h_1(n)$ across all states $n$ and strictly exceeds $h_1(n)$ whenever any tile is more than one step away from its goal, Manhattan Distance ($h_2$) strictly dominates Misplaced Tiles ($h_1$). In practice, $A^*$ guided by Manhattan Distance expands dramatically fewer nodes than $A^*$ guided by Misplaced Tiles.

1.3 Performance Metrics and Design Trade-Offs

1.3.1 Effective Branching Factor ($b^*$)

To quantify the efficiency gain provided by a heuristic function, AI researchers use the Effective Branching Factor ($b^*$).

If an $A^*$ search expands a total of $N$ nodes to find a goal state located at depth $d$, the effective branching factor $b^*$ is defined as the branching factor that a uniform tree of depth $d$ would require to contain $N + 1$ total nodes.

The mathematical relation governing $b^*$ is given by the geometric series:

$$N + 1 = 1 + b^* + (b^*)^2 + \dots + (b^*)^d = \sum\limits_{k=0}^{d} (b^*)^k$$

If $d$ is large, this relation can be approximated using the closed-form sum of a geometric series:

$$\begin{alignat*}{4} && N + 1 &= \sum\limits_{k=0}^{d} (b^*)^k && \ && &= \dfrac{(b^*)^{d+1} - 1}{b^* - 1} && \text{Applying geometric sum formula } \sum\limits_{k=0}^{d} r^k = \dfrac{r^{d+1}-1}{r-1} \ \end{alignat*}$$

For an unguided brute-force search on a domain like the 8-tile puzzle, the physical branching factor is $b \approx 10$.

• A weak heuristic (such as Misplaced Tiles) may reduce the effective branching factor to $b^* \approx 6$.
• A strong, dominating heuristic (such as Manhattan Distance or pattern databases) can reduce $b^*$ down to $2$ or even $1.5$.

Because total expanded nodes scale exponentially with depth ($O((b^*)^d) $), even a modest reduction in $b^*$ results in exponential time and memory savings during search.

1.3.2 Computational Cost vs. Expansion Savings Trade-Off

Although a dominating heuristic minimizes the number of node expansions, computing a more informed heuristic function at each node often requires additional CPU cycles and memory.

This yields a fundamental design trade-off in intelligent search:

$$\text{Total Search Time} = \underbrace{N}{\text{Total Nodes Expanded}} \times \quad \underbrace{T{\text{eval}}}_{\text{Time to Compute } h(n) \text{ Per Node}}$$

1. Weak Heuristics: Have small $T_{\text{eval}}$, but result in large $N$, leading to high overall runtime and potential memory exhaustion.
2. Complex Dominating Heuristics: Drastically reduce $N$, but require higher $T_{\text{eval}}$ per node.

A heuristic is effective in practice only if the time saved by avoiding node expansions outweighs the time spent calculating the heuristic value.

1.4 Bounded Suboptimality with Weighted $A^*$ Search

1.4.1 Evaluation Function for Weighted $A^*$ Search

In many practical AI applications (such as real-time robotics or large-scale routing), finding a strictly optimal path is less critical than finding a near-optimal path quickly.

Weighted $A^*$ Search modifies the standard $A^*$ evaluation function by introducing a weight parameter $w > 1$ that inflates the heuristic term:

$$f_w(n) = g(n) + w \cdot h(n), \quad \text{where } w > 1$$

By amplifying the influence of $h(n)$, Weighted $A^*$ prioritizes goal-directed exploration, causing the algorithm to behave more like a greedy best-first search and significantly accelerating convergence to a goal state.

1.4.2 Bounded Suboptimality Guarantee ($w$-optimality)

Because $w > 1$, $f_w(n)$ overestimates the true minimum cost, forfeiting strict admissibility. However, Weighted $A^*$ provides a mathematically proven bounded suboptimality guarantee:

If $h(n)$ is an admissible heuristic and $C^*$ is the optimal solution path cost, the cost $C$ of the path found by Weighted $A^*$ is bounded by:

$$C \le w \cdot C^*$$

This property is known as $w$-optimality (or bounded suboptimality). It guarantees that the solution returned will be no worse than $w$ times the optimal cost.

1.4.3 Magnification Effects of Heuristic Quality

Weighted $A^*$ magnifies both the strengths and weaknesses of the underlying heuristic function:

• High-Quality Heuristic: Provides accurate cost estimates close to $h^*(n)$. When paired with Weighted $A^*$, even a small weight $w$ (e.g., $w = 1.2$) yields massive runtime speedups while keeping the solution cost $C$ extremely close to $C^*$.
• Low-Quality Heuristic: Poor guidance requires a large weight $w$ to see meaningful expansion reductions, which drastically increases the bound $w \cdot C^*$ and risks severe solution degradation.

Thus, strong heuristic quality remains essential even when strict optimality is relaxed.

2. Systematic Approaches to Developing Heuristics

2.1 Historical Progression of Heuristic Design

2.1.1 Evolution from Handcrafted to Learned Approaches

The development of heuristics in artificial intelligence has undergone a fundamental paradigm shift over the past several decades. In early AI search frameworks, heuristics were entirely handcrafted, relying on human domain experts to formulate intuitive rules based on qualitative observation (e.g., counting misplaced pieces in tile puzzles). While simple to compute, handcrafted heuristics often suffer from severe underestimation, offering weak search guidance.

As state-space search matured, researchers shifted toward structural derivations, systematically relaxed problem definitions by stripping away constraints to extract admissible distance metrics automatically. This was followed by memory-enhanced methods such as Pattern Databases (PDBs), which trade offline precomputation and storage for near-optimal online search guidance.

In contemporary AI, particularly within complex domain spaces such as high-dimensional robotics, automated planning, and game-playing agents, heuristic design has evolved into a data-driven process. Rather than relying on human design, modern frameworks leverage deep neural networks and reinforcement learning to learn the cost-to-go function $h^*(n)$ directly from state representations and self-play experience.

2.1.2 State Space Scale in Benchmark Domains (8-Tile Puzzle)

To appreciate the necessity of principled heuristic design, consider the classical $8$-tile puzzle benchmark. The environment consists of a $3 \times 3$ grid containing eight numbered tiles ($1$ through $8$) and a single empty space (blank). The objective is to rearrange the tiles from an arbitrary initial state into a designated goal configuration via valid sliding moves.

Despite the structural simplicity of its rules, the state space size of the $8$-tile puzzle is substantial. The total number of valid board permutations is given by:

$$\begin{alignat*}{4} && N_{\text{total}} &= \dfrac{9!}{2} && \text{Permutations divided by 2 due to parity constraints} \ && &= \dfrac{362,880}{2} && \text{Evaluate factorial value} \ && &= 181,440 && \text{Total reachable states} \end{alignat*}$$

Because brute-force uninformed search strategies (e.g., Breadth-First Search or Uniform Cost Search) expand nodes indiscriminately across $181,440$ reachable states, search without informative heuristic guidance is computationally inefficient and scales exponentially worse in larger variants such as the $15$-tile or $24$-tile puzzles.

2.2 Problem Relaxation (Constraint Removal)

2.2.1 Theoretical Framework of Relaxed Problems

A formal method for constructing admissible heuristics is problem relaxation. Given an original search problem $P$, a relaxed problem $P'$ is generated by removing one or more constraints governing valid state transitions in $P$.

Removing constraints expands the set of permissible actions at any state. Consequently, any valid path from state $n$ to goal $g$ in the original problem $P$ remains a valid path in $P'$, but $P'$ may also contain shorter shortcut paths that were illegal in $P$.

Let $h^*(n)$ denote the true optimal cost to reach the goal from state $n$ in problem $P$, and let $h_{\text{relaxed}}^*(n)$ denote the true optimal cost in the relaxed problem $P'$. By construction, the optimal cost in the relaxed problem can never exceed the optimal cost in the original problem:

$$h_{\text{relaxed}}^*(n) \le h^*(n)$$

Therefore, setting the heuristic function equal to the exact optimal cost of the relaxed problem, $h(n) = h_{\text{relaxed}}^*(n)$, guarantees that $h(n)$ is admissible ($h(n) \le h^*(n) $) and consistent.

2.2.2 Formal Rules and Constraints of the 8-Tile Puzzle

In the formal specification of the $8$-tile puzzle, moving a tile from square $A$ to square $B$ is subject to three strict constraints:

1. Adjacency Constraint: Square $A$ must be horizontally or vertically adjacent to square $B$.
2. Blank Constraint: Square $B$ must currently be unoccupied (the blank square).
3. Unit Step Constraint: A tile can only move exactly one grid unit per operation.

2.2.3 Deriving Misplaced Tiles and Manhattan Distance via Relaxation

By systematically removing subsets of these three constraints, classical admissible heuristics are naturally derived:

1. Derivation of Misplaced Tiles Heuristic ($h_{\text{misplaced}}$): Relax the Adjacency Constraint and the Unit Step Constraint, allowing a tile to move from square $A$ to square $B$ in a single move regardless of distance, provided square $B$ is blank. Under this relaxation, any tile not currently in its goal position can be moved directly to its destination in exactly $1$ move. The optimal cost to solve this relaxed problem is simply the total count of misplaced tiles:

   $$h_{\text{misplaced}}(n) = \sum\limits_{i=1}^{8} \mathbb{I}(\overrightarrow{p}_i \neq \overrightarrow{p}_{i, \text{goal}})$$

   where $\mathbb{I}(\cdot)$ is the indicator function, $\overrightarrow{p}_i = (x_i, y_i)^T$ represents the current vector position of tile $i$, and $\overrightarrow{p}_{i, \text{goal}} = (x_{i, \text{goal}}, y_{i, \text{goal}})^T$ represents its goal vector position.

2. Derivation of Manhattan Distance Heuristic ($h_{\text{Manhattan}}$): Relax the Blank Constraint, allowing a tile to slide into square $B$ even if square $B$ is already occupied by another tile. Under this relaxation, tiles can overlap and pass through each other independently along grid lines. The minimum number of horizontal and vertical steps required for tile $i$ to travel from $\overrightarrow{p}_i$ to $\overrightarrow{p}_{i, \text{goal}}$ is its Manhattan distance:

   $$d_{\text{Manhattan}}(\overrightarrow{p}_i, \overrightarrow{p}_{i, \text{goal}}) = |x_i - x_{i, \text{goal}}| + |y_i - y_{i, \text{goal}}|$$

   Summing this relaxed distance over all tiles yields the total Manhattan Distance heuristic:

   $$h_{\text{Manhattan}}(n) = \sum\limits_{i=1}^{8} \left( |x_i - x_{i, \text{goal}}| + |y_i - y_{i, \text{goal}}| \right)$$

Because $h_{\text{Manhattan}}$ accounts for multi-step grid traversal whereas $h_{\text{misplaced}}$ assigns a uniform cost of $1$ to any out-of-place tile, $h_{\text{Manhattan}}(n) \ge h_{\text{misplaced}}(n)$ for all states $n$, proving that Manhattan Distance dominates Misplaced Tiles.

2.3 Pattern Databases

2.3.1 Precomputing Optimal Sub-problem Costs

While relaxed problem heuristics like Manhattan Distance treat each tile independently, they ignore interactions between tiles (such as one tile blocking another). Pattern Databases (PDBs) address this limitation by precomputing exact solution costs for subsets of tiles offline.

A Pattern Database is a lookup table that stores the exact minimum number of moves required to solve a specific sub-problem (pattern) from every possible arrangement of those pattern tiles on the board, ignoring the numbers on all non-pattern tiles.

During $A^*$ search, evaluating $h(n)$ does not require on-the-fly geometric calculation; instead, the state configuration is mapped to an index, and the exact sub-problem cost is retrieved via an $O(1)$ memory lookup.

2.3.2 Non-Overlapping Disjoint Subsets and Additive Admissibility

To combine heuristic values from multiple pattern databases without overestimating the true cost to the goal, the set of all tiles must be partitioned into disjoint (non-overlapping) subsets.

Let $S = {1, 2, 3, 4, 5, 6, 7, 8}$ represent the full set of numbered tiles. Suppose $S$ is partitioned into $K$ disjoint subsets $S_1, S_2, \dots, S_K$ satisfying:

$$\bigcup\limits_{k=1}^{K} S_k = S \quad \text{and} \quad S_i \cap S_j = \emptyset \quad \forall i \neq j$$

When subsets are strictly disjoint, any move made by a tile in subset $S_i$ moves only a tile belonging to $S_i$. Thus, no single physical tile move can simultaneously contribute to reducing the sub-problem cost of $S_i$ and $S_j$. Consequently, the sum of the exact sub-problem costs across disjoint pattern databases is additively admissible:

$$h_{\text{PDB}}(n) = \sum\limits_{k=1}^{K} h_{\text{PDB}, k}(n) \le h^*(n)$$

2.3.3 Numerical Walkthrough and Domination over Manhattan Distance

Consider a disjoint partition of the $8$-tile puzzle into three pattern subsets:

• Subset $S_1 = {1, 2, 3}$
• Subset $S_2 = {4, 5, 6}$
• Subset $S_3 = {7, 8}$ (along with the blank square)

For a given board configuration state $n$, suppose offline Breadth-First Search over each pattern abstraction yields the following exact sub-problem move costs:

• $h_{\text{PDB}, 1}(n) = 9$ moves for pattern tiles ${1, 2, 3}$
• $h_{\text{PDB}, 2}(n) = 7$ moves for pattern tiles ${4, 5, 6}$
• $h_{\text{PDB}, 3}(n) = 3$ moves for pattern tiles ${7, 8}$

The total additive PDB heuristic for state $n$ is calculated as:

$$\begin{alignat*}{4} && h_{\text{PDB}}(n) &= \sum\limits_{k=1}^{3} h_{\text{PDB}, k}(n) && \text{Additive property across disjoint subsets} \ && &= 9 + 7 + 3 && \text{Substitute individual PDB lookup values} \ && &= 19 && \text{Total precomputed sub-problem cost} \end{alignat*}$$

For this same state configuration $n$, the standard Manhattan Distance heuristic might sum to $h_{\text{Manhattan}}(n) = 17$.

Because $h_{\text{PDB}}(n) = 19 > h_{\text{Manhattan}}(n) = 17$, the Pattern Database heuristic provides a strictly higher lower bound to $h^*(n)$ while preserving admissibility. This higher value reduces $A^*$ node expansions compared to Manhattan Distance.

2.4 Machine Learning and Data-Driven Approaches

2.4.1 Approximating the Cost-to-Go Function via Neural Networks

In large-scale or continuous state spaces where constructing pattern databases requires excessive memory, modern AI constructs data-driven heuristics by training parameterized neural networks $h_\theta(\overrightarrow{s}) \approx h^*(n)$, where $\theta$ represents the network weight parameters and $\overrightarrow{s}$ is a vector embedding of state $n$.

The learning objective is formulated as minimizing an empirical loss function (such as Mean Squared Error) over a dataset of $N$ sampled states $\overrightarrow{s}_i$ paired with target cost-to-go labels $y_i$:

$$\mathcal{L}(\theta) = \dfrac{1}{N} \sum\limits_{i=1}^{N} \left( h_\theta(\overrightarrow{s}_i) - y_i \right)^2$$

While neural network heuristics $h_\theta(\overrightarrow{s})$ may occasionally violate strict admissibility ($h_\theta(\overrightarrow{s}) > h^*(\overrightarrow{s})$ for some states), they offer powerful function generalization across complex environments, dramatically outperforming classical handcrafted heuristics in search velocity.

2.4.2 Neural A* Algorithm Paradigm

Neural $A^*$ is an end-to-end data-driven search framework that integrates deep neural networks directly into the node evaluation loop of $A^*$ search.

PyTorch Architectural & Operational Paradigm

In PyTorch, building and utilizing a learned heuristic model $h_\theta(\overrightarrow{s})$ follows a standard object-oriented and functional workflow:

1. Model Architecture Definition (torch.nn.Module): The heuristic network is defined as a class inheriting from torch.nn.Module. Layers such as linear transformations (torch.nn.Linear) or convolutions (torch.nn.Conv2d) are instantiated in __init__, and the forward execution flow is specified in the forward method:

   import torch
   import torch.nn as nn
   
   class HeuristicNetwork(nn.Module):
       def __init__(self, input_dim: int, hidden_dim: int):
           super(HeuristicNetwork, self).__init__()
           self.fc1 = nn.Linear(input_dim, hidden_dim)
           self.relu = nn.ReLU()
           self.fc2 = nn.Linear(hidden_dim, 1)
   
       def forward(self, x: torch.Tensor) -> torch.Tensor:
           out = self.fc1(x)
           out = self.relu(out)
           out = self.fc2(out)
           return out
   

2. Training Loop & Optimization: Model weights $\theta$ are updated iteratively using gradient descent. In each iteration, batch inputs $\mathbf{X}_{\text{batch}}$ pass through the network, prediction loss is computed, gradients are reset using optimizer.zero_grad(), backpropagation is triggered via loss.backward(), and weights are updated using optimizer.step():

   model = HeuristicNetwork(input_dim=9, hidden_dim=64)
   optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
   criterion = nn.MSELoss()
   
   # Forward pass, loss evaluation, and backpropagation
   predictions = model(states_batch)
   loss = criterion(predictions, targets_batch)
   optimizer.zero_grad()
   loss.backward()
   optimizer.step()
   

3. Inference & Search Integration: During search evaluation, the network is set to evaluation mode (model.eval()) with gradient tracking disabled (with torch.no_grad():) to evaluate batched state tensors $\mathbf{S}_{\text{batch}}$ efficiently on GPU hardware, yielding heuristic estimates $h_\theta(\overrightarrow{s})$ for priority queue ordering $f(n) = g(n) + h_\theta(\overrightarrow{s})$.

2.4.3 Self-Play, Reinforcement Learning, and Monte Carlo Tree Search in AlphaZero

AlphaZero exemplifies learned heuristic systems in complex decision-making domains (e.g., Chess, Shogi, Go). It operates completely free of human domain knowledge or predefined opening books, acquiring strategy entirely through self-play reinforcement learning.

AlphaZero utilizes a deep neural network parameterized by weights $\theta$ that takes a board state tensor $\overrightarrow{s}$ as input and outputs two heads:

1. Policy Head $\overrightarrow{P}_\theta(a|\overrightarrow{s})$: A vector of probabilities over all valid actions $a$, providing goal-directed move prioritization.
2. Value Head $V_\theta(\overrightarrow{s})$: A scalar estimate of the expected game outcome from state $\overrightarrow{s}$ (acting as a learned cost-to-go / state-value heuristic).

During move selection, AlphaZero executes Monte Carlo Tree Search (MCTS) guided by $\overrightarrow{P}_\theta$ and $V_\theta$. The MCTS search outputs an improved search policy vector $\overrightarrow{\pi}_i$.

After playing self-play games to completion, outcome $z_i \in {-1, +1}$ is assigned. The neural network weights $\theta$ are trained end-to-end by minimizing a compound loss function balancing value accuracy, policy alignment, and $L_2$ weight regularization:

$$\mathcal{L}(\theta) = \dfrac{1}{N} \sum\limits_{i=1}^{N} \left( (V_\theta(\overrightarrow{s}_i) - z_i)^2 - \overrightarrow{\pi}i^T \log \overrightarrow{P}\theta(\overrightarrow{s}_i) \right) + c |\theta|_2^2$$

Through millions of self-play iterations, this feedback loop enables AlphaZero to learn heuristic evaluations that surpass traditional human-engineered heuristics.