In the search problems so far, the agent alone determined the sequence of states. In a GAME, an OPPONENT chooses alternate moves, and the opponent is trying to make you lose. THE CONSEQUENCE: you cannot plan a sequence of actions and execute it. You must plan a STRATEGY — a specification of what to do for every possible reply the opponent might make. That changes the output of search from a path to a POLICY. THE GAMES THIS SECTION ADDRESSES are formally: DETERMINISTIC · TURN-TAKING · TWO-PLAYER · ZERO-SUM · PERFECT INFORMATION ZERO-SUM means the players' utilities sum to a constant — what one gains the other loses, so there is no cooperative outcome. (Strictly "constant-sum"; a win/lose/draw game scored 1/0/½ sums to 1.) PERFECT INFORMATION means fully observable — both players see the whole state. Chess, checkers, Go and tic-tac-toe qualify; poker and bridge do not, because cards are hidden. A GAME IS DEFINED AS A SEARCH PROBLEM WITH SIX COMPONENTS: S₀ the INITIAL STATE PLAYER(s) which player has the move in state s ACTIONS(s) the set of legal moves in s RESULT(s, a) the TRANSITION MODEL — the state after move a TERMINAL-TEST(s) true when the game is over; such states are TERMINAL STATES UTILITY(s, p) the UTILITY or PAYOFF FUNCTION, giving a numeric value for terminal state s to player p. Chess: 1 for a win, 0 for a loss, ½ for a draw. Tic-tac-toe: +1, −1, 0. Together S₀, ACTIONS and RESULT define the GAME TREE — nodes are states, edges are moves, and the leaves are terminal states with utilities. THE TWO PLAYERS ARE CONVENTIONALLY CALLED MAX AND MIN: MAX moves first and tries to MAXIMISE the utility MIN tries to MINIMISE it They alternate, so the tree's levels alternate between MAX nodes and MIN nodes — the PLY structure. One PLY is one player's move; a full round of both players is two ply. WHY GAMES ARE HARD — the numbers: game branching factor b game length (ply) ───────────────────────────────────────────────────────── tic-tac-toe ~4 average 9 checkers ~8 ~70 chess ~35 ~80 Go ~250 ~150 ───────────────────────────────────────────────────────── THE SEARCH SPACE FOR CHESS: with b ≈ 35 and 80 ply, the game tree has roughly 35^80 ≈ 10^123 nodes. The number of atoms in the observable universe is about 10^80. THE TREE CANNOT BE SEARCHED, not now and not with any conceivable hardware. (The number of LEGAL POSITIONS is far smaller, around 10^47, because most sequences reach the same positions — but still hopeless.) SO GAME PLAYING IS NOT ABOUT SEARCHING THE TREE. It is about searching a small part of it well, and estimating the value of where you stop. That is the whole content of the next two topics: minimax defines what the right answer would be, and alpha-beta plus evaluation functions make an approximation affordable. THE TIME CONSTRAINT IS PART OF THE PROBLEM, which is unusual. Chess allows roughly 150 seconds per move in tournament play, so the algorithm must return the best move it has found when the clock demands it — an ANYTIME algorithm. This is the semidynamic environment property from ACtE0901: the environment does not change while you think, but your score does.

THE OPTIMAL STRATEGY is found by computing the MINIMAX VALUE of each state — the utility of being in that state, ASSUMING BOTH PLAYERS PLAY OPTIMALLY from there to the end. MINIMAX(s) = UTILITY(s) if TERMINAL-TEST(s) max over a in ACTIONS(s) of MINIMAX(RESULT(s,a)) if PLAYER(s) = MAX min over a in ACTIONS(s) of MINIMAX(RESULT(s,a)) if PLAYER(s) = MIN THE ASSUMPTION MATTERS AND IS OFTEN MISUNDERSTOOD: minimax assumes the opponent plays perfectly. Against an imperfect opponent, a minimax player is SAFE but not necessarily MAXIMALLY EXPLOITATIVE — there may be a risky line that would crush a weak opponent, and minimax will not take it because it loses against a perfect one. Minimax is the pessimistic, guaranteed-worst-case strategy. BECAUSE THE TREE CANNOT BE SEARCHED TO THE END, two changes are required, and Shannon proposed both in 1950: 1. CUT THE SEARCH OFF EARLY at some depth, replacing TERMINAL-TEST with a CUTOFF-TEST. 2. APPLY A HEURISTIC EVALUATION FUNCTION EVAL(s) to the non-terminal states where the search stopped, estimating the utility of the position. H-MINIMAX(s, d) = EVAL(s) if CUTOFF-TEST(s, d) max/min over successors of H-MINIMAX(RESULT(s,a), d+1) DESIGNING AN EVALUATION FUNCTION — the three requirements: · it must ORDER TERMINAL STATES the same way the true utility function does — a win must evaluate above a draw · the computation must not take too long, since it is the point of cutting off the search · for non-terminal states it should be STRONGLY CORRELATED WITH THE ACTUAL CHANCES OF WINNING THE STANDARD FORM is a WEIGHTED LINEAR FUNCTION of FEATURES: EVAL(s) = w₁f₁(s) + w₂f₂(s) + … + wₙfₙ(s) THE CHESS EXAMPLE — material balance with the classical piece values: pawn 1 · knight 3 · bishop 3 · rook 5 · queen 9 f_i(s) = (number of white pieces of type i) − (number of black pieces of type i) EVAL(s) = 1·f_pawn + 3·f_knight + 3·f_bishop + 5·f_rook + 9·f_queen WORKED: white has 8 pawns, 2 knights, 1 bishop, 2 rooks, 1 queen; black has 7 pawns, 1 knight, 2 bishops, 2 rooks, 1 queen. pawns: 8 − 7 = +1 → +1 knights: 2 − 1 = +1 → +3 bishops: 1 − 2 = −1 → −3 rooks: 2 − 2 = 0 → 0 queens: 1 − 1 = 0 → 0 EVAL = 1 + 3 − 3 + 0 + 0 = +1 A one-pawn advantage for white. Note that the extra knight and the missing bishop cancel exactly, which is why the 3-and-3 valuation is a simplification real engines refine. THE LINEAR FORM'S LIMITATION: it assumes the features are INDEPENDENT, and they are not. Two bishops are worth more together than twice one bishop; a knight's value depends sharply on whether the position is open or closed. Real engines add non-linear terms, positional features (king safety, pawn structure, mobility, control of the centre) and values that change between the opening, middlegame and endgame. TWO PROBLEMS THAT ARISE FROM CUTTING OFF, both examinable: THE HORIZON EFFECT A serious threat lies just beyond the search depth, so the program does not see it. Worse, the program may make pointless delaying moves that PUSH THE THREAT OVER THE HORIZON, believing it has been avoided when it has merely been postponed. MITIGATION: SINGULAR EXTENSIONS — search deeper along lines where one move is clearly better than all alternatives. THE NEED FOR QUIESCENCE Cutting off in the middle of an exchange gives a wildly wrong evaluation — count the material after your queen is captured but before you recapture and the position looks lost. A QUIESCENT position is one unlikely to show large swings in value soon. MITIGATION: QUIESCENCE SEARCH — do not stop at a non-quiescent position; continue searching capture sequences until the position is stable. BOTH PROBLEMS COME FROM THE SAME SOURCE: an arbitrary depth limit cuts the tree at positions that are in the middle of something. The fixes are both forms of "search deeper where it matters", which is why real engines search to variable depth rather than a fixed one.

STOCHASTIC GAMES — where chance intervenes. Backgammon has dice, so the game tree contains a third kind of node: CHANCE NODES. The value of a chance node is the EXPECTED value over the possible outcomes: EXPECTIMINIMAX(s) = UTILITY(s) terminal max over a of EXPECTIMINIMAX(RESULT(s,a)) MAX node min over a of EXPECTIMINIMAX(RESULT(s,a)) MIN node Σ over r of P(r) × EXPECTIMINIMAX(RESULT(s,r)) CHANCE node THE COST: backgammon has 21 distinct dice rolls and about 20 legal moves per roll, so the branching factor at a full round is roughly 20 × 21 × 20 ≈ 8,400. The tree grows so fast that depth beyond three ply is impractical, which is why backgammon programs rely on a very strong evaluation function rather than on deep search — the opposite emphasis from chess. AND A SUBTLE POINT WORTH KNOWING: with chance nodes, the EVALUATION FUNCTION'S SCALE MATTERS, not just its ordering. In deterministic minimax any monotonic transformation of EVAL gives the same move choice; with expected values it does not, because averaging is sensitive to the actual magnitudes. An evaluation function must be a positive linear transformation of the probability of winning. IMPERFECT INFORMATION — where part of the state is hidden. Card games hide the opponent's hand, so the state is partially observable. The naive approach — average the minimax value over all possible deals — is wrong in an instructive way: it assumes the world will be revealed before you must act, so it never values INFORMATION-GATHERING moves and never bluffs. Correct play requires reasoning about what the opponent's actions reveal about their hand, and about what your actions reveal about yours. That is why poker needed different techniques entirely and was solved much later than chess. WHERE MODERN GAME AI ACTUALLY LANDED — worth knowing because the syllabus's algorithms are only part of the story: DEEP BLUE (chess, 1997) was the culmination of the approach in this section: alpha-beta search on special-purpose hardware, reaching 12+ ply, with an evaluation function tuned by grandmasters. IT DID NOT LEARN. Brute force plus human knowledge. MONTE CARLO TREE SEARCH (MCTS) changed the picture for games with huge branching factors like Go, where no adequate evaluation function was known. Instead of evaluating a position by a formula, PLAY THOUSANDS OF RANDOM GAMES FROM IT and use the win rate as the estimate. Four steps repeated: SELECTION (walk the tree by a policy balancing exploitation and exploration), EXPANSION, SIMULATION (a random playout), BACKPROPAGATION (push the result up the path). THE INSIGHT: it needs no domain knowledge at all, only the rules — so it works where nobody can write a good EVAL. ALPHAGO (2016) combined MCTS with deep neural networks: a POLICY NETWORK suggesting which moves are worth considering (cutting the branching factor) and a VALUE NETWORK estimating the position (replacing the hand-written EVAL). ALPHAZERO went further and learned both from self-play alone, with no human games — and surpassed the previous programs in chess, shogi and Go. THE HISTORICAL POINT: the search framework of this section survived; what changed is that the EVALUATION FUNCTION AND MOVE ORDERING BECAME LEARNED RATHER THAN HAND-CODED. Which is precisely the symbolic-to-statistical shift the AI concepts topic described, playing out in one domain.