# Lecture 2: Chess, Perfect Information, and Why LLM Games Differ CSCE 631-D: Intelligent Agents, Computational Game Solving. Fall 2026, Texas A&M University. Instructor: Alan Kuhnle. **Accessibility and use note.** These notes are the accessible companion to the Lecture 2 Beamer slide deck. They follow the slide deck in order, with one heading per slide. Every diagram and table on the slides is described in prose. Equations are stated in words alongside their symbolic form. The demo anchor (Slide 28) includes a complete expected scripted transcript of the terminal session so that asynchronous and screen-reader users receive the same content as the live recording. The result is intended to be complete enough to learn from without viewing the Beamer PDF. ### Slide 1 -- Title Lecture 2 of CSCE 631-D, Fall 2026. Title: "Chess, Perfect Information, and Why LLM Games Differ." Instructor: Alan Kuhnle, Texas A&M University. ### Slide 2 -- Today's Plan This lecture begins with chess and the theory of perfect-information games, then asks why the toolkit developed for chess does not transfer to LLM-based agents. The lecture covers game trees, backward induction, Zermelo's theorem, the minimax theorem, alpha-beta pruning, and the computational complexity of chess. A brief history of computer chess leads from Shannon through Deep Blue to AlphaZero. The lecture closes with a new arc: why LLM games require a fundamentally different approach, a live demo of two-agent payoff estimation, and the launch of PA1. ## Chess as a Game-Theoretic Object ### Slide 3 -- Why Chess? Chess is the canonical example of several game-theoretic properties that this lecture introduces. It is a two-player game: one player controls the white pieces and the other controls the black pieces. It is zero-sum, meaning one player's gain is exactly the other player's loss. It is a perfect-information game: both players can see the full state of the board at every point. It is sequential (extensive-form) with alternating moves, so players take turns rather than acting simultaneously. It is deterministic: there are no chance moves such as dice rolls or card draws. Chess motivates the key concepts of this lecture: game trees, backward induction, and the minimax theorem. ### Slide 4 -- Chess: Basic Parameters Chess has two players, White and Black. The set of possible outcomes for White is win, draw, or loss, represented numerically as 1, 1/2, or 0. The average branching factor (the typical number of legal moves from a given position) is approximately 35. The average game length is approximately 40 moves per player, which corresponds to roughly 80 half-moves (called plies). The estimated number of legal board positions is approximately 10 to the 44th power. The game-tree complexity, sometimes called the Shannon number, is approximately 10 to the 120th power. The enormous game tree makes chess computationally intractable to solve exactly. Its perfect-information structure, however, makes the theory tractable. ## Game Trees (Preview) ### Slide 5 -- Game Trees (Preview) A game tree is a rooted tree that represents sequential interaction. Informally, each internal node is labeled with the player whose turn it is to move. Each edge from a node represents one legal action available to the moving player. Each leaf (terminal node) is labeled with a payoff vector giving each player's payoff at that outcome. For chess, the root of the tree is the initial board position, and White moves first. The nodes alternate between White's turn and Black's turn as one descends the tree. The leaves correspond to terminal game states: checkmate, stalemate, or a draw by rule. This is a preview. Formal extensive-form game definitions, including information sets and behavioral strategies, appear in Module 4. ### Slide 6 -- Example: A Tiny Game Tree This slide displays a small game tree used as a running example throughout the lecture. **Alt text:** The figure shows a rooted tree with three levels. At the top (the root), a circular node labeled "1" indicates that Player 1 moves first. Player 1 has two actions, labeled "a" (left branch) and "b" (right branch). Each branch leads to a circular node labeled "2," indicating that Player 2 moves next. From the left Player 2 node, two actions are available: "c" leads to a rectangular leaf with payoff 3, and "d" leads to a rectangular leaf with payoff 1. From the right Player 2 node, action "c" leads to a rectangular leaf with payoff 2, and action "d" leads to a rectangular leaf with payoff 4. All edges are drawn with arrowheads pointing downward from parent to child. This is a two-player zero-sum game. The rectangular leaf labels show Player 1's payoff; Player 2's payoff is the negative of Player 1's payoff. Player 1 chooses between actions a and b at the root. After Player 1's choice, Player 2 chooses between actions c and d at whichever node is reached. ### Slide 7 -- Strategies in Extensive-Form Games (Preview) A pure strategy for player i specifies an action at every decision node belonging to player i, including nodes that might never be reached under that strategy. This is the key idea: a strategy is a complete contingency plan, not just a single move. In the game tree from Slide 6, Player 1 has 2 strategies (choose a or choose b), because Player 1 has only one decision node. Player 2 has 4 strategies, because Player 2 must specify an action at each of two decision nodes (the left node and the right node). These four strategies are written as two-letter codes: cc (play c at both nodes), cd (play c at the left node and d at the right node), dc, and dd. A pure strategy in chess is a complete contingency plan for every possible board position. The number of such strategies is astronomically large, far exceeding 10 to the power 10 to the 50th. The formal treatment of information sets and behavioral strategies appears in Module 4. ## Perfect Information and Backward Induction ### Slide 8 -- Perfect Information A game has perfect information if every player, when making a decision, knows the complete history of all previous moves. Equivalently, every information set is a singleton, meaning each decision node is distinguishable from every other. Examples of perfect-information games include chess, Go, checkers, and tic-tac-toe. Counterexamples include poker, where each player's cards are hidden from the other, and simultaneous-move games such as the Prisoner's Dilemma played simultaneously, where neither player observes the other's choice before acting. ### Slide 9 -- Backward Induction Backward induction is an algorithm that solves finite perfect-information games by working from the leaves of the game tree upward to the root. The algorithm proceeds in three steps. First, start at the leaves of the game tree, where the payoffs are already known. Second, at each internal node where player i moves, assign the node a value: if player i is the maximizing player (Player 1 in a zero-sum game), the node's value equals the maximum of its children's values; if player i is the minimizing player (Player 2), the node's value equals the minimum of its children's values. In notation, v(node) = max over actions a of v(child(a)) for the maximizer, or min over actions a of v(child(a)) for the minimizer. Third, propagate these values upward until the root receives a value. Backward induction yields a subgame-perfect equilibrium (SPE): a strategy profile that constitutes an equilibrium in every subgame of the original game. For zero-sum games, the value computed at the root is the game value, meaning the payoff that results when both players play optimally. The formal induction proof and the theory of subgame-perfect equilibrium are covered in Module 4. ### Slide 10 -- Backward Induction: Example This slide shows the same game tree from Slide 6, now annotated with the backward induction solution. Colors highlight the optimal path and the computed values at each internal node. **Alt text:** The figure shows the same three-level tree as Slide 6, but with colored highlights indicating the backward induction solution. In the left subtree, the leaf with payoff 1 (under action d) is shaded orange, and the left Player 2 node is also shaded orange, now displaying the bold value 1. The leaf with payoff 3 (under action c) is uncolored. In the right subtree, the leaf with payoff 2 (under action c) is shaded green, and the right Player 2 node is shaded green, displaying the bold value 2. The leaf with payoff 4 (under action d) is uncolored. The root node (Player 1) is shaded green and displays the bold value 2. The green shading traces the optimal path: root to right child (action b) to left grandchild (action c). **Step-by-step walkthrough.** Backward induction begins at the leaves. In the left subtree, Player 2 is the minimizing player and chooses between payoffs 3 (action c) and 1 (action d). Player 2 prefers the outcome that is worse for Player 1, so Player 2 chooses d, giving this node a value of 1. In the right subtree, Player 2 chooses between payoffs 2 (action c) and 4 (action d). Player 2 again minimizes, choosing c, which gives this node a value of 2. Now at the root, Player 1 is the maximizing player and chooses between the left subtree (value 1, via action a) and the right subtree (value 2, via action b). Player 1 chooses b (the right branch), which yields the higher value. The game value is 2. Under optimal play, Player 1 chooses action b, and Player 2 responds with action c. ## Zermelo's Theorem ### Slide 11 -- Zermelo's Theorem (1913) Zermelo's theorem (1913) states that in any finite two-player perfect-information game with three possible outcomes (win, lose, or draw), exactly one of the following holds. Either Player 1 has a winning strategy, or Player 2 has a winning strategy, or both players have strategies that guarantee at least a draw. The proof idea applies backward induction to the finite game tree. Because the tree is finite, backward induction terminates and assigns a value from the set {Player 1 wins, Draw, Player 2 wins} to the root. The full proof appears in Module 4. As a corollary, chess is determined: under optimal play by both sides, the outcome is fixed as either a White win, a Black win, or a draw. We do not currently know which of these three holds. ### Slide 12 -- Implications of Zermelo's Theorem Zermelo's theorem is nonconstructive. It guarantees that a winning or drawing strategy exists but does not help find it. The backward-induction proof requires enumerating the entire game tree, which for chess contains roughly 10 to the 120th power nodes. Zermelo's theorem applies to all finite perfect-information games, including Go, checkers, Hex, and Connect Four. For some of these games, the determined outcome is known. Tic-tac-toe has been solved, and the result under optimal play is a draw. Connect Four was solved in 1988, and the first player wins. Checkers was solved in 2007 by Schaeffer et al. through the Chinook project, and the result is a draw. Standard 8 by 8 chess has not been solved; the outcome under optimal play is unknown, though it is widely conjectured to be a draw. Standard 19 by 19 Go has not been solved, and the outcome under optimal play is unknown. ## The Minimax Theorem ### Slide 13 -- Minimax for Game Trees In a two-player zero-sum game tree, the minimax value is defined recursively. At a leaf node, the value equals Player 1's payoff at that leaf. At an internal node where Player 1 moves, the value is the maximum over all actions a of the value of the child reached by action a. At an internal node where Player 2 moves, the value is the minimum over all actions a of the value of the child reached by action a. In notation: v(leaf) = u_1(leaf), and for an internal node n, v(n) equals max_a v(child(n, a)) when Player 1 moves at n, or min_a v(child(n, a)) when Player 2 moves at n. The value at the root, v(root), is the value of the game. Player 1 can guarantee a payoff of at least v(root), and Player 2 can guarantee that Player 1 receives at most v(root). Backward induction computes this value by working from leaves to root; the minimax recursion formalizes the same idea as a single equation. ### Slide 14 -- Von Neumann's Minimax Theorem (1928) Von Neumann's minimax theorem (1928) extends the minimax idea from game trees to the normal-form (matrix) representation of any finite two-player zero-sum game. The theorem states that for any payoff matrix A, the maximum over Player 1's mixed strategies of the minimum over Player 2's mixed strategies of the expected payoff equals the minimum over Player 2's mixed strategies of the maximum over Player 1's mixed strategies of the expected payoff. In notation: max over sigma_1 in Delta(S_1) of min over sigma_2 in Delta(S_2) of (sigma_1 transposed)(A)(sigma_2) equals min over sigma_2 in Delta(S_2) of max over sigma_1 in Delta(S_1) of (sigma_1 transposed)(A)(sigma_2). Here Delta(S_i) denotes the set of all probability distributions (mixed strategies) over player i's pure strategies, and A is the payoff matrix for Player 1. Three consequences follow. First, the order of play does not matter when players use mixed strategies. Second, the common value is the value of the game, denoted v*. Third, for perfect-information games, the minimax theorem specializes to backward induction. The proof via LP duality appears in Lecture 3. The computational treatment using linear programming appears in Module 2, Lecture 7. ### Slide 15 -- Minimax in Normal Form vs. Extensive Form The minimax idea can be expressed in two representations that yield the same game value for perfect-information games. In normal form, the game is represented as a payoff matrix. A strategy is a row choice (for Player 1) or a column choice (for Player 2). Computing the minimax value reduces to a linear program, which is solvable in polynomial time. In extensive form, the game is represented as a game tree. A strategy is a complete contingency plan specifying an action at every decision node. Computing the minimax value uses backward induction, which takes time proportional to the number of nodes in the tree. Because the tree can have exponentially many nodes relative to the depth, backward induction is exponential in tree depth. For perfect-information games, the two representations yield the same game value. The extensive form is exponentially more compact, because it represents the game structure implicitly rather than listing all strategy combinations in a matrix. ## Alpha-Beta Pruning ### Slide 16 -- Alpha-Beta Pruning: Motivation Full minimax search requires visiting every node in the game tree. For chess, with roughly 10 to the 120th power nodes, this is infeasible. The idea behind alpha-beta pruning is that many subtrees cannot affect the value computed at the root. These subtrees can be pruned (skipped) without changing the final result. Alpha-beta pruning maintains two bounds during the search. The value alpha is the best payoff that Player 1 (the maximizer) can guarantee so far; it serves as a lower bound on the game value. The value beta is the best payoff that Player 2 (the minimizer) can guarantee so far; it serves as an upper bound. If at any node the lower bound alpha meets or exceeds the upper bound beta, the remaining children of that node cannot affect the outcome, and the algorithm prunes them. ### Slide 17 -- Alpha-Beta Pruning: Algorithm The alpha-beta algorithm is called as AlphaBeta(root, negative infinity, positive infinity). It works as follows. If the current node n is a leaf, return Player 1's payoff u_1(n). If Player 1 moves at node n, iterate over each child c: update alpha to be the larger of alpha and AlphaBeta(c, alpha, beta); if alpha is greater than or equal to beta, stop iterating (this is called a beta-cutoff) and return alpha. If Player 2 moves at node n, the procedure is symmetric: update beta with the minimum, and stop when beta is less than or equal to alpha (an alpha-cutoff), then return beta. The initial call is AlphaBeta(root, negative infinity, positive infinity). The result is identical to full minimax. Only the amount of search effort changes; the computed game value is the same. ### Slide 18 -- Alpha-Beta: Complexity If the game tree has depth d and branching factor b, the complexity of alpha-beta pruning depends on move ordering. In the worst case, when the move ordering is maximally unhelpful, alpha-beta visits O(b^d) nodes, no improvement over full minimax. In the best case, when moves are ordered optimally (best move examined first at every node), alpha-beta visits only O(b^(d/2)) nodes. The best-case interpretation is that alpha-beta effectively doubles the search depth achievable for the same computational effort. For chess with branching factor approximately 35, this means going from depth 8 to depth 16 with the same number of node evaluations. In practice, good move-ordering heuristics (such as the killer heuristic and transposition tables) bring performance close to the best case. ## Computational Complexity of Chess ### Slide 19 -- How Hard Is Chess? The computational complexity question concerns generalized chess: given an n by n chess position, does White have a winning strategy? Fraenkel and Lichtenstein proved in 1981 that this problem is EXPTIME-complete. No polynomial-time algorithm exists unless P equals EXPTIME, which is considered extremely unlikely. Two facts coexist and must be understood together. First, backward induction runs in time polynomial in the size of the explicit game tree, which has O(b^d) nodes. Second, the game tree of generalized chess is exponential in the board size n. The board position is the succinct representation (polynomial in n), and solving from this succinct representation is EXPTIME-hard. The algorithm is efficient relative to the tree it searches, but the tree itself is exponentially large relative to the input description. As a contrast, standard 8 by 8 checkers was weakly solved by exhaustive search through the Chinook project (Schaeffer et al., 2007), even though generalized n by n checkers is also EXPTIME-complete. ### Slide 20 -- Complexity Landscape of Games The following complexity classifications refer to the generalized version of each game, parameterized by board size as the succinct input. Tic-tac-toe has trivial complexity in its generalized form, and the standard game is solved with result draw. Connect Four has low complexity, and the standard game is solved with result first-player win. Generalized n by n checkers is EXPTIME-complete; standard 8 by 8 checkers is solved with result draw. Generalized n by n chess is EXPTIME-complete; standard 8 by 8 chess is open. Generalized n by n Go is EXPTIME-complete; standard 19 by 19 Go is open. Generalized n by n Hex is PSPACE-complete; the first player wins by a nonconstructive strategy-stealing argument. Backward induction is polynomial in the explicit tree, but the tree is exponential in the board size. This is why the EXPTIME classification and the polynomial-time backward induction algorithm do not contradict each other. ## Computer Chess: A Brief History ### Slide 21 -- From Shannon to Deep Blue The history of computer chess begins with Claude Shannon in 1950, who proposed the basic approach of minimax search combined with a heuristic evaluation function. In 1951, Alan Turing wrote (by hand simulation) the first chess-playing program. In 1958, Newell, Shaw, and Simon first described alpha-beta pruning. The landmark event was 1997, when Deep Blue defeated world champion Garry Kasparov. Deep Blue used special-purpose hardware capable of evaluating 200 million positions per second. It combined alpha-beta search with a handcrafted evaluation function. Its typical search depth was approximately 12 plies, with selective extensions reaching 40 or more plies in tactically sharp lines. Deep Blue was a triumph of search combined with domain knowledge and specialized hardware. ### Slide 22 -- Stockfish and AlphaZero Stockfish is an open-source, community-developed chess engine, under continuous development since 2008. It uses alpha-beta search with NNUE (an efficiently updatable neural network evaluation function, adopted in 2020). Its Elo rating exceeds 3600, far beyond any human player. AlphaZero, developed by DeepMind (Silver et al.), learned chess entirely from scratch via self-play reinforcement learning. It uses Monte Carlo Tree Search (MCTS) guided by a deep neural network, with no handcrafted evaluation function. The 2017 arXiv preprint reported that AlphaZero defeated Stockfish after approximately 4 hours of training on specialized hardware under specific match conditions. The 2018 Science paper reports results under different training and evaluation conditions; the two accounts should not be conflated. AlphaZero demonstrates that game-tree search can be guided by learned value and policy functions rather than handcrafted ones. ### Slide 23 -- Lessons for Algorithmic Game Theory Four lessons emerge from the history of computer chess. First, theory and practice diverge: chess is EXPTIME-complete in the generalized setting, yet practical engines play near-optimally on the standard 8 by 8 board. Second, heuristic search works: alpha-beta search combined with a heuristic evaluation function is a practical approximation to the exact minimax value. Third, learning can replace handcrafting: AlphaZero's self-play is a form of computing equilibrium strategies through repeated interaction. Fourth, perfect information is the comparatively tractable case: the difficult open problems in algorithmic game theory involve imperfect information, including poker, auctions, and mechanism design. ## Preview: Extensive-Form Games ### Slide 24 -- From Chess to General Extensive-Form Games Chess is a special case of extensive-form games: two players, perfect information, deterministic, zero-sum. General extensive-form games introduce three complications. Imperfect information means that players may not observe all previous moves; this is formalized through information sets. Chance nodes mean that nature moves according to a known probability distribution, as in dealing cards in poker. Multiple players means the game may involve more than two participants. Formal definitions of extensive-form games, information sets, and behavioral strategies are the subject of Module 4. ### Slide 25 -- Perfect vs. Imperfect Information The distinction between perfect and imperfect information is where the computational challenges of game theory begin in earnest. In perfect-information games, every information set is a singleton (each decision node is distinguishable). Examples include chess and Go. The solution method is backward induction. The computational complexity of the generalized problem is EXPTIME. In imperfect-information games, information sets are nontrivial (a player cannot distinguish certain nodes from one another). Examples include poker and Kuhn poker. Solution methods include the sequence form and counterfactual regret minimization (CFR). The computational complexity is PPAD-hard or harder. This jump from perfect to imperfect information is the dividing line for the rest of the course. ## Why LLM Games Are Different ### Slide 26 -- LLMs as Game Players The chess toolkit rests on three assumptions. First, there exists a position evaluator that can score any board state. Second, the set of legal moves at each node is finite and enumerable. Third, play is deterministic: the same position always yields the same evaluation. None of these assumptions hold for LLM agents. There is no position evaluator; the "game state" is a conversation history with no compact scoring function. The action space is the set of all possible text outputs, which is not enumerable in any practical sense. LLM policies are stochastic: the same prompt can produce different responses on different calls. The "game" between LLM agents is accessible only through sampled play: run the agents, observe what they do, and record the outcomes. ### Slide 27 -- The Empirical-Game Pipeline In chess, payoffs are computed by exact algorithms such as backward induction, alpha-beta search, or exhaustive enumeration. In LLM games, payoffs are estimated from repeated interaction. The empirical-game pipeline proceeds in four steps. First, fix a finite set of strategies, where each strategy is a prompt, model, or scaffold configuration. Second, query agent pairs repeatedly under each combination of strategies (each cell of the strategy matrix). Third, aggregate the observed outcomes into an estimated payoff matrix with confidence intervals. Fourth, analyze the estimated game by computing Nash equilibria, identifying dominated strategies, or measuring social welfare. This pipeline is called empirical game-theoretic analysis (EGTA). The full treatment appears in Module 2, Lecture 8, and Module 7. ### Slide 28 -- Demo: Two-Agent Payoff Estimation This slide anchors a live instructor demonstration. Two TAMU-API language models play a 2 by 2 Prisoner's Dilemma. Each strategy is a fixed system prompt ("cooperate" or "defect"). The script runs 30 repetitions per cell, then prints the empirical payoff matrix with means and 95% confidence intervals, plus the total token cost against the $5 per day budget. **Alt text:** The slide displays a code listing that first connects to the placeholder course server over SSH, then runs `python run_payoff_estimation.py` with flags for game (pd), strategies (cooperate, defect), model (placeholder), reps per cell (30), and seed (42). Below the listing, a bulleted list requests three outputs: the 4-cell empirical payoff matrix with means and 95% confidence intervals, one raw transcript showing the system prompt, model response, and score, and total token cost against the daily budget. A note at the bottom distinguishes 120 game episodes from 240 agent API calls, because each episode queries two agents, and identifies the demo as the student's PA1 starting point. The following is an *expected scripted transcript*, not evidence that the demo was run. It represents the planned terminal session the instructor will reproduce during the recorded walkthrough. Fields in angle brackets are live-run values the instructor must replace during the actual recording. ``` $ ssh [USER@COURSE_SERVER ~]$ python run_payoff_estimation.py \ --game pd --strategies cooperate defect \ --model \ --reps-per-cell 30 --seed 42 Loading game: Prisoner's Dilemma (2x2) Strategies: [cooperate, defect] Model: Seed: 42 === System prompts === [cooperate]: "You are playing a one-shot Prisoner's Dilemma. You should cooperate with the other player. When asked for your action, respond with exactly one word: COOPERATE or DEFECT." [defect]: "You are playing a one-shot Prisoner's Dilemma. You should defect against the other player. When asked for your action, respond with exactly one word: COOPERATE or DEFECT." Running 4 cells x 30 reps = 120 game episodes... Agent API calls: 120 episodes x 2 agents = 240 calls... === Raw transcript (cell [cooperate, cooperate], rep 1) === Player 1 system prompt: [cooperate] Player 1 user message: "Choose your action in this one-shot Prisoner's Dilemma." >> API call: model=, temperature=1.0 << Response: "COOPERATE" Player 2 system prompt: [cooperate] Player 2 user message: "Choose your action in this one-shot Prisoner's Dilemma." >> API call: model=, temperature=1.0 << Response: "COOPERATE" Outcome: (COOPERATE, COOPERATE) Payoff: Player 1 = 3, Player 2 = 3 [cooperate, cooperate]: 30/30 complete [cooperate, defect]: 30/30 complete [defect, cooperate]: 30/30 complete [defect, defect]: 30/30 complete === Empirical payoff matrix (Player 1), mean +/- 95% CI === P2: cooperate P2: defect P1: cooperate 2.83 +/- 0.24 0.47 +/- 0.30 P1: defect 4.60 +/- 0.31 1.07 +/- 0.12 === Empirical payoff matrix (Player 2), mean +/- 95% CI === P2: cooperate P2: defect P1: cooperate 2.83 +/- 0.24 4.60 +/- 0.31 P1: defect 0.47 +/- 0.30 1.07 +/- 0.12 === Budget === Total game episodes: 120 Total agent API calls: 240 Total tokens: Estimated cost: $ Daily budget remaining: $ of $5.00 ``` **Live-run fields the instructor must replace:** - ``: the exact model identifier used on the TAMU API. - ``: the total number of input and output tokens consumed. - ``: the dollar cost of the API calls in the demo. - ``: the remaining daily budget after the demo. The representative payoff values in the transcript above (such as 2.83 and 4.60) are illustrative. The theoretical Prisoner's Dilemma payoffs are (3, 3) for mutual cooperation, (0, 5) and (5, 0) for one-sided defection, and (1, 1) for mutual defection. The empirical values deviate because the LLM does not follow its system prompt with certainty: a "cooperate"-prompted agent may occasionally defect, and vice versa. The confidence intervals quantify this stochasticity. This is the central methodological point: payoffs for LLM agents must be estimated with measured variance, not assumed to be exact. This demo is the starting point for PA1. ### Slide 29 -- PA1: Empirical Payoff Estimation and Equilibrium Analysis PA1 is due in Week 3. The demo provided two components: a payoff-estimation script for one game (the Prisoner's Dilemma) and an empirical payoff matrix with confidence intervals. PA1 extends the demo in four ways. First, students add a coordination game (such as Battle of the Sexes). Second, students add a negotiation game of their choice. Third, students compute Nash equilibria of their estimated games using provided implementations of the support-enumeration algorithm and the Lemke-Howson algorithm. Fourth, students perform sensitivity analysis: they examine how equilibrium conclusions change when payoffs are perturbed within their confidence intervals. Budget: $5 per day TAMU API limit. Reports must include seeds, model version, sample counts, and confidence intervals for every cell of every estimated payoff matrix. ### Slide 30 -- Summary This lecture covered the following ideas. Chess is a two-player, zero-sum, perfect-information, sequential game. Game trees represent sequential interaction; strategies are complete contingency plans. Backward induction solves finite perfect-information games, and Zermelo's theorem guarantees a determined outcome. Alpha-beta pruning achieves O(b^(d/2)) node evaluations in the best case. Backward induction is polynomial in the explicit tree, but generalized n by n chess is EXPTIME-complete. Computer chess evolved from Deep Blue (search plus handcrafted evaluation) to AlphaZero (MCTS plus learned evaluation via self-play). LLM games lack enumerable moves and deterministic evaluation, so payoffs must be estimated, not computed. Next: Nash equilibria (Lecture 3), then algorithms for the estimated games (Module 2). ## References and forward links **References cited in this lecture:** - Zermelo, E. (1913). "Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels." Proceedings of the Fifth International Congress of Mathematicians. - Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele." Mathematische Annalen, 100(1), 295-320. - Shannon, C. E. (1950). "Programming a Computer for Playing Chess." Philosophical Magazine, 41(314), 256-275. - Newell, A., Shaw, J. C., and Simon, H. A. (1958). "Chess-Playing Programs and the Problem of Complexity." IBM Journal of Research and Development, 2(4), 320-335. - Fraenkel, A. S. and Lichtenstein, D. (1981). "Computing a Perfect Strategy for n x n Chess Requires Time Exponential in n." Journal of Combinatorial Theory, Series A, 31(2), 199-214. - Schaeffer, J. et al. (2007). "Checkers Is Solved." Science, 317(5844), 1518-1522. - Silver, D. et al. (2017). "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm." arXiv:1712.01815. - Silver, D. et al. (2018). "A General Reinforcement Learning Algorithm That Masters Chess, Shogi, and Go Through Self-Play." Science, 362(6419), 1140-1144. - Wellman, M. P. (2006). "Methods for Empirical Game-Theoretic Analysis." Proceedings of AAAI. **Forward links within the course:** - Lecture 3 covers Nash equilibria and proves the minimax theorem via LP duality. - Module 2, Lecture 5 covers support enumeration and Lemke-Howson in full. - Module 2, Lecture 7 covers the computational treatment of zero-sum games via linear programming. - Module 2, Lecture 8 introduces correlated equilibrium, coarse correlated equilibrium, and the full EGTA pipeline. - Module 4 provides the formal definitions of extensive-form games, information sets, behavioral strategies, subgame-perfect equilibrium, and the complete proof of Zermelo's theorem. - Module 7 covers empirical game-theoretic analysis of LLM agent populations at full depth. - PA1 (due Week 3) builds directly on the demo from Slide 28: estimate payoff matrices, compute equilibria, and analyze sensitivity to estimation error.