Game playing is the AI topic where almost every question becomes a calculation. If you only memorise definitions, a small game tree can still cost you the full answer. Take one nine-leaf tree: plain minimax reads every leaf to return 3, and alpha-beta returns the same 3 after reading only seven. Evaluation functions, chance nodes and the traps examiners set all hang off that one calculation.
Games as adversarial search: the formal setup
Single-agent search finds a path to a goal. A game has to survive an opponent's counter-moves. Walking the tree is the same skill as in Graph Algorithms: BFS, DFS and Shortest Paths; what changes is that alternate levels of the tree belong to someone who wants your value to come out low.
A formal game description has six elements:
Initial state S0: the starting position.
PLAYER(s): whose turn it is in state s.
ACTIONS(s): the legal moves from s.
RESULT(s, a): the state reached after action a.
TERMINAL-TEST(s): whether the game has ended.
UTILITY(s, p): player p's numerical terminal payoff, such as win +1, loss -1, draw 0.
The standard exam model is zero-sum and perfect-information. One player's gain is the other's loss, so one value suffices, and both see the full state.
Scale explains why smart search matters. Tic-tac-toe has fewer than 9! = 362,880 move sequences and about 255,000 distinct playable games, so brute force works. Chess has roughly 10^40 legal positions and a game tree around 10^120 nodes, the classic Shannon estimate. Enumeration cannot handle that gap.
Minimax, worked end to end
MAX chooses the highest guaranteed value, assuming MIN always selects the lowest reply. Minimax backs values up from terminal leaves to the root.
Root A is MAX. Moves a1, a2, and a3 lead to MIN nodes B, C, and D:
B has leaves 3, 12, 8, so B = min(3, 12, 8) = 3.
C has leaves 2, 4, 6, so C = min(2, 4, 6) = 2.
D has leaves 14, 5, 2, so D = min(14, 5, 2) = 2.
Therefore A = max(3, 2, 2) = 3.
MAX chooses a1 to B, guaranteeing at least 3 against MIN's best replies.
Minimax is optimal against an optimal opponent and complete on finite trees. For branching factor b and depth m, depth-first minimax takes O(b^m) time and O(bm) space. Against a weaker opponent, it never does worse than its guarantee.
Alpha-beta pruning on the same tree
Alpha is MAX's best guarantee on the current path. Beta is MIN's lowest guarantee. Prune at MIN when value <= alpha, and at MAX when value >= beta.
Evaluate the same tree from left to right:
Explore B's leaves 3, 12, 8. B becomes 3, so root alpha becomes 3.
Enter C. Its first leaf is 2, making beta 2. Since beta 2 <= alpha 3, MIN can hold C to at most 2 while MAX already has 3. Prune leaves 4 and 6.
Enter D. Its leaves update beta from 14 to 5 to 2. The cutoff arrives after the last leaf, leaving nothing to prune. D becomes 2.
The root is max(3, at most 2, 2) = 3, and a1 remains the chosen move.
Alpha-beta examined 7 of 9 leaves. Exactly 2 leaves, 4 and 6, were never examined. The value and move are identical to plain minimax because pruning is exact, not an approximation.
With perfect move ordering, alpha-beta examines O(b^(m/2)) nodes. This reduces the effective branching factor to about sqrt(b) and roughly doubles searchable depth. Worst-case ordering degenerates to plain minimax.
Real programs: cutoffs and evaluation functions
Terminal search is impossible near 10^120 nodes. Real programs use a cutoff test and replace terminal utility with EVAL(s).
A weighted linear form is EVAL(s) = w1 f1(s) + w2 f2(s) + .... Classic chess material weights are pawn 1, knight 3, bishop 3, rook 5, and queen 9. Being up one rook after giving up one knight scores 5 - 3 = +2 on material.
The horizon effect makes a delayed bad event look avoided just beyond the cutoff. Quiescence search extends noisy positions, such as pending captures, until they become quiet.
Contemporary engines learn their evaluation function instead of hand-weighting it, but the skeleton the learned evaluation is plugged into is still a depth-limited minimax search with alpha-beta cutoffs.
Chance nodes and other game models
Games with dice add chance nodes and expectiminimax. Values 10 and 2, each with probability 0.5, produce 0.5 x 10 + 0.5 x 2 = 5 + 1 = 6. Here evaluation scale matters, not merely order.
Multiplayer games back up a utility vector, one component per player, allowing alliances to emerge. Imperfect-information games such as card games require different machinery because some state is hidden.
Game-tree backup uses the optimal-substructure reasoning in Dynamic Programming Explained: 0/1 Knapsack. Transposition tables store positions reached by different move sequences, which is memoisation by another name.
Traps that cost marks
Giving MIN a separate utility: in a zero-sum game there is one value. MAX raises it and MIN lowers it. Write min() at every MIN level.
Thinking alpha-beta changes the answer: it changes only the number of examined nodes. Claims that it approximates minimax are bait.
Counting pruned nodes without a visit order: the pruned set depends on move order. Trace alpha and beta using the order stated in the question.
Reversing the cutoff: prune at MIN when value <= alpha, and at MAX when value >= beta. Reversing this would wrongly retain 4 and 6 in our tree and could prune inside D.
Calling O(b^(m/2)) guaranteed: this is the perfect-ordering best case, not the worst case.
How GATE-style papers and interviews test this
Use the worked tree as a compact drill:
NAT: What is the root's minimax value? 3.
NAT: How many leaves are unexamined by left-to-right alpha-beta? 2.
MSQ: Correct statements are that alpha-beta returns the minimax value, depth-first minimax uses O(bm) space, and perfect ordering gives O(b^(m/2)) time. Statements claiming a different returned value or O(b^m) space are wrong.
Game playing sits in the AI portions of GATE-style papers, notably Data Science and AI, and in university, teaching and PSC recruitment papers. Where it falls inside the wider AI paper is mapped in Artificial Intelligence for GATE: Syllabus Areas, Weightage Pattern and Prep Order. Topic weightage and the marks split move from cycle to cycle, so confirm both against the conducting body's official notification before you plan around them.
In AI and ML interviews, implementing tic-tac-toe minimax is a common warm-up. State the terminal test, take max over children on your turn and min on the opponent's, then add alpha-beta and move ordering. If you want that drilled alongside the rest of the interview set, the AI & ML for Placements | Generative AI Placement Course runs the AI topics in interview order.
The short version and the next step
Games are adversarial search problems with six formal elements. Minimax gave the root value 3 through a1. Alpha-beta pruned 2 of the 9 leaves and still returned 3. Practical engines add a cutoff test, an evaluation function and quiescence search. With dice in play, the chance node averaged to 6.
Redraw that tree from memory tonight and run both traces by hand; minimax should touch all 9 leaves and alpha-beta 7, with the root at 3 both times. For a paced revision plan that sequences AI with the rest of the syllabus, there is GATE Guidance by Sanchit Sir.
