Q18Principles of Artificial Intelligence

The standard Minimax algorithm is the absolute mathematical engine for adversarial AI (Chess, Tic-Tac-Toe). It violently generates a massive Game Tree down to the terminal states, scores them, and propagates the numbers up. However, Minimax suffers a catastrophic flaw: its time complexity is $O(b^m)$ (where $b$ is the branching factor). In Chess, this tree is mathematically larger than the number of atoms in the universe. Alpha-Beta Pruning is an aggressive optimization architecture that mathematically proves certain branches of the tree are absolutely useless, violently severing (pruning) them from memory without ever evaluating them, slashing the complexity to $O(b^{m/2})$.

The algorithm utilizes two strict mathematical bounds passed down the tree:

• $\alpha$ (Alpha): The absolute best (highest) value that the MAX player can currently guarantee on the current path or above. Initially set to $-\infty$.
• $\beta$ (Beta): The absolute best (lowest) value that the MIN player can currently guarantee on the current path or above. Initially set to $+\infty$.

The Pruning Condition

The absolute core mathematical rule: If at any node, $\alpha \ge \beta$, the algorithm violently halts evaluation of that node's remaining children and returns.

Why? If MAX knows they can already force a score of $+10$ ($\alpha =10$) in another branch, and they are currently exploring a branch where MIN has just found a move that scores $+5$ ($\beta =5$), MAX will absolutely NEVER choose this branch, because MIN will force the score down to $5$ or worse. Evaluating the rest of MIN's options is a catastrophic waste of CPU cycles.

• 1. Root Node (MAX): Spawns Left Node (MIN) and Right Node (MIN). $\alpha =-\infty$, $\beta =+\infty$.
• 2. Left MIN Node: Spawns two leaf nodes with values 3 and 5.
• - MIN looks at 3. MIN wants the lowest number. MIN's current best is 3. $\beta$ updates to 3.
• - MIN looks at 5. 3 is better. MIN returns 3 to the Root MAX Node.
• 3. Root Update: MAX receives the 3. MAX wants the highest number. MAX's current guaranteed floor ($\alpha$) becomes 3.
• 4. Right MIN Node: The algorithm dives right. It passes down the absolute bounds from the Root: $\alpha =3$, $\beta =+\infty$.
• 5. The Prune: The Right MIN node explores its first leaf, which is a 2. MIN wants the lowest number, so MIN's $\beta$ updates to 2.
• 6. The Mathematical Trigger: At this exact moment, $\alpha =3$ (from the Root) and $\beta =2$ (at the current MIN node). The condition $\alpha \ge \beta$ ($3\ge 2$) is met!
• 7. The Execution: MIN knows it will guarantee a score of 2 or lower. MAX at the root already has a guaranteed score of 3 from the left branch. MAX will absolutely NEVER willingly choose this right branch. Therefore, the algorithm violently PRUNES the remaining unexplored leaves of this Right MIN node. It saves massive computational power.