Game Theory and Strategic AI

The Last Ball of the Over

It is the final ball of a T20 innings. The bowler has two realistic options: a full, fast yorker aimed at the base of the stumps, or a sharp bouncer at the batsman's ribs. The batsman, standing at the crease a fraction of a second earlier, has to commit to a guess — will they get low for a yorker or get up on their toes for a bouncer? Neither player can see the other's choice in advance. Both are choosing under uncertainty, and both know that the other is thinking exactly as hard about outplaying them.

This is not a metaphor for a mathematical idea — it is a mathematical object, and by the end of this chapter you will compute the bowler's and batsman's exact optimal strategies using nothing more than algebra and expected value. The branch of mathematics that studies situations like this is called game theory: the formal study of decision-making when your payoff depends not only on your own choice but on the choices of other rational agents who are simultaneously trying to outmanoeuvre you. It was built by John von Neumann and Oskar Morgenstern in the 1940s, sharpened by John Nash in 1950, and today it sits underneath two things you interact with daily without noticing: the auctions that decide which ad you see on your phone, and the search algorithms that let a chess or Go engine "look ahead" and pick a move no human opponent can trap. That second connection — from human strategic reasoning to the search algorithms inside strategic AI — is the destination of this chapter.

What Exactly Is a "Game," Mathematically?

In everyday speech "game" means something played for fun. In game theory, a game is any formal structure with three ingredients:

• Players — the decision-makers (2 in most examples here; can be more).
• Strategies — the complete set of choices available to each player.
• Payoffs — a number assigned to every player, for every combination of strategies chosen, representing how good that outcome is for that player.

A price war between two companies, a bidding war at an auction, a negotiation, a duel between a chess engine's search and its opponent's — all of these fit the definition. The bowler-batsman situation fits too: two players, two strategies each, and a payoff (probability of success) for every one of the four possible combinations.

Games are further classified by how the payoffs relate to each other. In a zero-sum game (or more generally a constant-sum game), one player's gain is exactly the other player's loss — the payoffs for any outcome add up to the same fixed total. Our cricket example is constant-sum: whatever probability of success goes to the bowler, the rest goes to the batsman, and the two always add to 1. In a non-zero-sum game, players can both gain or both lose together — cooperation and competition can coexist. You will see one of each in this chapter.

Reading a Payoff Matrix: The Yorker-or-Bouncer Game

We represent a two-player, two-strategy game as a table called a payoff matrix. Let the bowler's actual delivery be the row, and the batsman's anticipated delivery be the column. The entry is the bowler's probability of success (a dot ball or wicket) — since this is constant-sum, the batsman's success probability is always 1 minus that number, so one table tells us everything.

Read the matrix carefully — this is the single most important skill in this chapter. When the batsman correctly anticipates the delivery (Yorker/Yorker or Bouncer/Bouncer, the diagonal), the bowler's success probability is low (0.2 and 0.4) because a prepared batsman punishes a delivery they saw coming. When the batsman guesses wrong (the off-diagonal), the bowler's success probability is high (0.8 and 0.6).

First, check whether either player has a dominant strategy — a single choice that is best no matter what the opponent does. Suppose the batsman is somehow known to always anticipate Yorker (column 1): the bowler compares 0.2 (bowling Yorker) against 0.6 (bowling Bouncer) and clearly prefers Bouncer. Now suppose the batsman always anticipates Bouncer (column 2): the bowler compares 0.8 (Yorker) against 0.4 (Bouncer) and prefers Yorker. The bowler's best choice flips depending on what the batsman does — there is no dominant strategy here. This is the signature of a game that has no stable pure-strategy solution: whatever single delivery the bowler commits to, the batsman (if they could predict it) would counter it, and whatever the batsman commits to anticipating, the bowler would exploit it. The only way to be unexploitable is to be unpredictable — which is where mixed strategies come in.

Solving the Game: Mixed Strategies and the Indifference Principle

A mixed strategy is a probability distribution over your pure strategies, rather than a single certain choice. Instead of asking "what should the bowler bowl?", we ask "with what probability should the bowler bowl each delivery, so that no pattern can be detected and exploited over many balls?"

Here is the key insight, due essentially to John von Neumann: at a mixed-strategy equilibrium, each player's mix must make the opponent indifferent between their own options. If the batsman's optimal anticipation-mix made the bowler strictly prefer one delivery over the other, the bowler would just bowl that one every time — but then the batsman, noticing the pattern, would exploit it by always anticipating it. Equilibrium can only hold where neither player can improve by shifting their own mix, which forces the opponent's expected payoff to be flat across their choices.

Let the batsman anticipate Yorker with probability p and Bouncer with probability (1 − p). Compute the bowler's expected success for each of the bowler's two pure deliveries, as a function of p:

E[Bowler bowls Yorker]  = 0.2p + 0.8(1 − p) = 0.8 − 0.6p
E[Bowler bowls Bouncer] = 0.6p + 0.4(1 − p) = 0.4 + 0.2p

For the batsman's mix to be optimal, it must leave the bowler indifferent — otherwise the bowler would abandon the mix and always pick the better row, and the batsman could then punish that predictability. Set the two expressions equal and solve:

0.8 − 0.6p = 0.4 + 0.2p
0.8 − 0.4 = 0.2p + 0.6p
0.4 = 0.8p
p = 0.5

So the batsman's equilibrium mix is 50% anticipate Yorker, 50% anticipate Bouncer — genuinely unpredictable, a mental coin flip weighted exactly evenly. Substituting p = 0.5 back in confirms both expressions equal 0.5: the bowler's expected success rate is 0.5 regardless of which delivery is actually bowled, once the batsman is playing this way.

Now do the same calculation from the bowler's side. Let the bowler bowl Yorker with probability q and Bouncer with probability (1 − q). The batsman's payoff is 1 minus the bowler's, so:

E[Batsman anticipates Yorker]  = q(1 − 0.2) + (1 − q)(1 − 0.6) = 0.4 + 0.4q
E[Batsman anticipates Bouncer] = q(1 − 0.8) + (1 − q)(1 − 0.4) = 0.6 − 0.4q

0.4 + 0.4q = 0.6 − 0.4q
0.8q = 0.2
q = 0.25

The bowler's equilibrium mix is 25% Yorker, 75% Bouncer. This is the pair of mixed strategies at which neither player can do any better by changing their own probabilities, given the other's — a mixed-strategy Nash equilibrium, with a resulting bowler success rate of exactly 0.5 (and hence batsman success rate of exactly 0.5 too, since the game is constant-sum). Notice the equilibrium mix is not 50-50 for the bowler — it is skewed toward Bouncer, because Bouncer is the delivery that punishes a wrong batsman guess less severely (0.6 vs. 0.8), so the bowler needs to lean on it more often to keep the batsman honestly guessing both options. This is exactly the discipline professional bowlers and batsmen train into muscle memory, and it is exactly the discipline a poker-playing or Starcraft-playing AI has to learn: in any competitive setting with hidden simultaneous choices, being predictable — even predictably "optimal" on average — is a losing strategy, because a predictable policy can always be exploited. Reinforcement-learning agents trained against adversaries (poker bots, real-time-strategy bots) are explicitly trained to converge on mixed strategies of exactly this kind.

A Different Kind of Game: The Discounting Trap

Not every strategic situation is zero-sum. Consider two quick-commerce delivery apps — call them App A and App B — each deciding, for the coming quarter, whether to run a heavy discount campaign or hold prices. The numbers below are illustrative, not real reported figures, but the structure is the one companies genuinely face:

Check App A's dominant strategy: if B holds, A gets 50 by holding or 70 by discounting — A prefers discounting. If B discounts, A gets 10 by holding or 20 by discounting — A still prefers discounting. Discounting is a dominant strategy for A regardless of what B does. By the symmetry of the table, discounting is also dominant for B. So both apps discount, both land at (20, 20) — and both are worse off than the (50, 50) they would have shared had they both held prices. This is the classic structure called the Prisoner's Dilemma: individually rational choices (each player doing what is unambiguously best for itself) produce a jointly worse outcome than if both had cooperated. Neither app is being foolish — each is doing exactly what maximizes its own payoff given the other's likely move. The trap is structural, not a mistake either player is making, and it is why competing platforms often end up in prolonged discount wars that shrink everyone's margins even though everyone can see, in principle, that holding prices would leave both of them richer.

Nash Equilibrium, Defined Properly

We have now met two solved games — one where the equilibrium is a pair of mixed strategies (yorker/bouncer), one where it's a pair of pure, dominant strategies (both discount). Both are instances of one unifying idea, due to John Nash (1950): a Nash equilibrium is a set of strategies, one for each player, such that no player can improve their own payoff by unilaterally changing only their own strategy, holding everyone else's strategy fixed.

"Unilaterally" is the operative word. A Nash equilibrium says nothing about whether a different, jointly better outcome exists elsewhere in the game (in the Prisoner's Dilemma, one plainly does — (50,50) beats (20,20) for both players). It only says that from the equilibrium point, no single player, acting alone, can do better by deviating. That is a much weaker and more realistic claim than "the best possible outcome" — and it is precisely what makes it a robust prediction of how self-interested, non-communicating players actually behave, rather than a description of the fairest or most efficient result.

Common Misconception: "A Nash Equilibrium Is the Best Outcome"

Students very often assume that because a Nash equilibrium is the mathematically "stable" or "solved" outcome of a game, it must also be the best outcome for the players. The discounting example refutes this directly: (20, 20) is the Nash equilibrium, but (50, 50) is strictly better for both players and is available on the same payoff table. The equilibrium is stable precisely because no player can improve by deviating alone — but both players deviating together, from discount to hold, would help both of them. The catch is that such joint deviation requires trust or enforceable coordination (a contract, a regulator, or repeated interaction with memory and reputation), which the one-shot game as defined does not provide. Whenever you see a real-world "race to the bottom" — fee wars, arms races, overfishing a shared resource — you are very likely looking at a Prisoner's Dilemma, and the lesson is not "the players are irrational" but "the equilibrium of self-interest and the optimum of joint welfare can be two different points on the same table."

From Human Strategy to Machine Strategy: Minimax Search

Everything so far has been simultaneous-move: both players choose without seeing the other's choice. Many important games — chess, tic-tac-toe, Go, checkers — are instead sequential, perfect-information games: players alternate moves, and each can see the full board before deciding. Game theory handles this case with an algorithm called minimax, and this is the algorithm that sits at the heart of every classical game-playing AI.

The idea: represent the game as a tree. Each node is a board position; each edge is a legal move; each leaf (a finished game) has a numeric value representing how good that final position is for one designated player, call them MAX. It is MAX's job to pick moves that push the outcome as high as possible. Every other player — call them MIN — is assumed to play optimally against MAX, i.e. MIN always picks moves that push the outcome as low as possible. Working from the leaves upward: at every node where it's MAX's turn, the node's value is the maximum of its children's values; at every node where it's MIN's turn, the node's value is the minimum of its children's values. This backward computation is exactly why the algorithm is named minimax.

Trace the diagram: the left MIN node's children are leaves 3 and 5; MIN picks the minimum, so it backs up 3. The right MIN node's children are leaves 2 and 9; MIN backs up 2. At the root, MAX compares its children's backed-up values, 3 and 2, and picks the maximum: 3, via the left branch. Notice something that surprises many students: MAX does not chase the highest leaf on the board (9, sitting under the right branch) — going right would hand MIN the chance to steer play down to the leaf worth only 2. MAX picks the branch with the best guaranteed value against an opponent who is also playing to win, not the branch with the best possible value if the opponent cooperates.

Here is the exact tree from the diagram, expressed in Python, with the recursion traced line by line:

def minimax(node, maximizing):
    if isinstance(node, int):        # leaf node: just return its value
        return node
    if maximizing:
        return max(minimax(child, False) for child in node)
    else:
        return min(minimax(child, True) for child in node)

tree = [[3, 5], [2, 9]]      # root's two MIN children, each with two leaves
print(minimax(tree, True))   # root is a MAX node

Trace: minimax(tree, True) sees a list, so it is not a leaf, and maximizing=True means it evaluates minimax([3,5], False) and minimax([2,9], False) and takes the larger. minimax([3,5], False) is a MIN call, so it evaluates minimax(3, True) and minimax(5, True) — both leaves, returning 3 and 5 unchanged — and takes min(3, 5) = 3. Similarly minimax([2,9], False) returns min(2, 9) = 2. Back at the root, max(3, 2) = 3. The program prints 3, matching the diagram exactly.

Pruning the Tree: Why Chess Engines Don't Search Everything

Minimax, applied naively, is hopeless for real games. Chess has a branching factor of roughly 35 legal moves per position; searching even 8 moves ahead ("8-ply") means evaluating on the order of 35⁸ ≈ 2 × 10¹² leaf positions — computationally far too many to finish in a reasonable time, even on fast hardware. The fix that makes real game-playing AI possible is alpha-beta pruning: while searching, keep track of the best value MAX can already guarantee (alpha) and the best value MIN can already guarantee (beta) from ancestors already explored. If, partway through exploring a node's children, you discover a value that makes alpha >= beta, you can stop exploring that node's remaining children immediately — no matter what they turn out to be, the parent will never let play reach this branch, because a rational opponent higher up the tree already has a strictly better alternative available. This changes nothing about the final answer minimax would have produced; it only skips branches whose exact value can never matter.

def alphabeta(node, alpha, beta, maximizing):
    if isinstance(node, int):
        return node
    if maximizing:
        value = float('-inf')
        for child in node:
            value = max(value, alphabeta(child, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break               # beta cutoff — MIN parent will avoid this branch
        return value
    else:
        value = float('inf')
        for child in node:
            value = min(value, alphabeta(child, alpha, beta, True))
            beta = min(beta, value)
            if alpha >= beta:
                break               # alpha cutoff — MAX parent will avoid this branch
        return value

With good move-ordering (searching the most promising moves first), alpha-beta pruning reduces the effective branching factor from b to roughly √b, which turns that 35⁸ search into something closer to the square root of it — a difference between "impossible" and "runs on a laptop." Every classical chess and checkers engine, and the game-tree-search component inside modern systems, relies on this pruning; it is one of the few places in AI where an exact algorithm (not a learned approximation) is doing all the strategic work.

Strategic AI in the Real World

Minimax assumes you can enumerate the whole tree down to a leaf you know how to evaluate. Go has roughly 10¹⁷⁰ legal board positions — far beyond any tree search, pruned or not. DeepMind's AlphaGo, which defeated top professional Lee Sedol 4 games to 1 in Seoul in March 2016, replaced exhaustive minimax with a Monte Carlo tree search guided by two deep neural networks: a policy network estimating which moves are promising, and a value network estimating who is winning from a given position — both trained initially on human game records and then refined by self-play. Its successor, AlphaZero (2017), discarded the human game records entirely and learned chess, shogi, and Go purely by playing millions of games against itself, using reinforcement learning to improve the same policy-and-value idea. The game-theoretic core — a MAX and a MIN player, an equilibrium each is trying to reach — is unchanged from the minimax tree above; what changed is that a learned function replaces a hand-written evaluation of the leaves, because the tree is too vast to reach the leaves at all.

Game theory also shapes the auctions running behind almost every ad you see online. In a Vickrey auction (a sealed-bid, second-price auction, analysed by William Vickrey, who won the Nobel Memorial Prize in Economic Sciences in 1996 partly for this work), each bidder submits a private bid, the highest bidder wins, but pays only the second-highest bid. This design has an elegant property provable with the same dominant-strategy reasoning used earlier in this chapter: bidding your true valuation is a dominant strategy — you can never do better by lying about how much you value the item, whether you bid higher or lower than your true value. Google's original AdWords mechanism, generalized second-price (GSP) auction, borrows this second-price intuition for a single item but extends it to multiple ad slots on one page; because of that extension it is not perfectly truthful the way a single-item Vickrey auction is — bidders can sometimes gain by shading their bids — which is itself a well-studied example of how game-theoretic guarantees can break when a game's structure is generalized.

A Nod to Competitive Exams: Combinatorial Games and Nim

A different, exam-favourite branch of game theory deals with combinatorial games: two players alternate moves, there is no hidden information and no chance, and the game ends when one player cannot move (that player loses, under the "normal play" convention). The classic example is Nim: several piles of stones; on each turn a player removes any positive number of stones from exactly one pile; whoever takes the last stone wins. Bouton's theorem (1901) gives a complete, clean solution: compute the XOR (bitwise exclusive-or, sometimes called the "nim-sum") of all pile sizes. If the nim-sum is 0 when it becomes your turn, you are in a losing position against optimal play; if it is nonzero, you have a move that returns the nim-sum to 0, and repeating this strategy guarantees you the win. For example, piles of size 3, 4, 5 have nim-sum 3 XOR 4 XOR 5 = 2 (nonzero), so the player to move has a winning move. To find it, try each pile in turn: for pile-of-5, the target size solving 3 XOR 4 XOR x = 0 is x = 3 XOR 4 = 7, which is bigger than 5, so that pile cannot reach it (invalid). For pile-of-4, the target solving 3 XOR x XOR 5 = 0 is x = 3 XOR 5 = 6, again too big (invalid). For pile-of-3, the target solving x XOR 4 XOR 5 = 0 is x = 4 XOR 5 = 1, and since 1 < 3 this move is legal: reduce the pile of 3 down to 1 stone, leaving piles (1, 4, 5) with nim-sum 1 XOR 4 XOR 5 = 0 — exactly the losing position Bouton's theorem says to hand your opponent. This class of problem — reasoning about a position's "Grundy value" via XOR — appears regularly in Olympiad combinatorics and in GATE-level discrete mathematics, and it is a genuinely different tool from the Nash-equilibrium and minimax machinery covered above: it exploits the exact combinatorial structure of games with no randomness and no simultaneous moves, where a single number per position turns out to completely characterize who wins.

Summary

A game, formally, is players plus strategies plus payoffs. Zero-sum (or constant-sum) games split a fixed total between opponents; non-zero-sum games allow mutual gain or mutual loss, which is what makes traps like the Prisoner's Dilemma possible. A dominant strategy is best regardless of the opponent's choice; when no dominant strategy exists in a simultaneous game, the indifference principle finds the mixed-strategy equilibrium by forcing each player's mix to leave the opponent's payoffs equal across their own options. A Nash equilibrium — pure or mixed — is a strategy profile from which no single player can profitably deviate alone; crucially, it need not be the best joint outcome available on the table. For sequential, perfect-information games, minimax computes the value a rational MAX can guarantee against a rational, opposing MIN by backing up maxima and minima from the leaves; alpha-beta pruning gets the identical answer while skipping branches that provably cannot affect it. Real strategic AI systems — from AlphaGo's neural-network-guided search to the second-price logic underneath online ad auctions — are built directly on these ideas, either by using them exactly (minimax, dominant-strategy auctions) or by approximating them where the exact game tree is too large to ever finish searching.

Test Your Strategic Thinking

1. In the yorker/bouncer game, suppose the bowler starts predictably bowling Bouncer 90% of the time instead of the equilibrium 75%. Using the batsman's expected-payoff formulas derived above, is there now an anticipation the batsman should switch to exploiting, and what does the batsman's expected success become if they anticipate Bouncer every time?
2. Redraw the discount-war payoff table so that App A's profit from unilaterally discounting while B holds is only 55 (instead of 70), everything else unchanged. Does App A still have a dominant strategy to discount? Show the comparison explicitly.
3. In the minimax tree [[6, 2], [4, 9]] with the root as a MAX node, compute the backed-up value at each MIN node and the final root value, showing your work the way the worked example did.
4. Explain, in your own words, why a Nash equilibrium is not the same claim as "the best possible outcome for both players" — use the discount-war numbers from this chapter as your evidence.
5. For Nim piles of size 5, 6, 7: compute the nim-sum, state whether the player to move wins or loses under optimal play, and if they win, name the exact move (which pile, reduced to what size) that restores the nim-sum to zero.

Think About It

Think about this: How would you explain game theory and strategic ai to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where game theory and strategic ai is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting game theory and strategic ai to at least 3 other topics you have studied.