# How Computers Play Games > How a program plays chess, checkers, Go, and Sudoku: game trees, minimax, alpha-beta pruning, evaluation functions and Stockfish, solved games, Monte Carlo search, AlphaGo and AlphaZero, and constraint solving, with runnable Python at every step. --- # How Computers Play Games You have played the games on this site. Maybe you even lost to the chess opponent and wondered what is going on inside it. The answer is not magic, and it is not "it calculates everything". It is a small set of ideas that fit together, and several of them fit in a dozen lines of Python. This guide is the bridge between playing a game and the computer science underneath it. You will build a tic-tac-toe player that never loses, make it roughly thirty times cheaper by skipping work that cannot matter, and then see why that is still not enough for chess, how Stockfish gets around it, how checkers was proven to be a draw, and how AlphaGo and AlphaZero changed the recipe. The last phase shows a completely different way to think: Sudoku as a puzzle of constraints. ## Prerequisite You should read Python and know what a function and a list are. [Recursion Finally Clicks](/guides/recursion-finally-clicks) matters most, because every search here is a recursive function. [Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) helps with the word "explodes". If you want to feel the games first, play them: [play chess](/games/chess), [play checkers](/games/checkers), [play Sudoku](/games/sudoku). The matching learning guides are [Chess From Zero](/guides/chess-from-zero), [Checkers From Zero](/guides/checkers-from-zero), and [Sudoku From Zero](/guides/sudoku-from-zero). ## How to read this - **Want the code?** Phases 2 and 3 are the heart: minimax, then alpha-beta, both runnable. - **Want the modern story?** Jump to [phase 4](04-evaluation-and-stockfish.md) and [phase 5](05-solving-learning-and-constraints.md). - **Want it to finally make sense?** Read in order. Each phase uses the previous one. Every program runs in your browser using only Python's standard library. Numbers quoted from the real world come from papers and official project pages, linked where they appear. ## The phases 1. **[Game Trees: Every Game as a Branching Map](01-game-trees.md)** - states, moves, branching factor, and why chess and Go cannot be searched to the end. 2. **[Minimax: Playing Perfectly on Tic-Tac-Toe](02-minimax.md)** - assume the opponent plays their best, and get a program that never loses. 3. **[Alpha-Beta Pruning: Skipping Work That Cannot Matter](03-alpha-beta-pruning.md)** - the same answer with a small fraction of the search. 4. **[Evaluation Functions and Stockfish](04-evaluation-and-stockfish.md)** - guessing the value of a position, and how a modern engine does it. 5. **[Solved Games, Learned Games, and Constraints](05-solving-learning-and-constraints.md)** - Chinook and checkers, Monte Carlo search, AlphaGo and AlphaZero, and Sudoku as constraint solving. --- # Game Trees: Every Game as a Branching Map When you plan a chess move, you picture futures: "if I take that pawn, they take my bishop, then I fork their rooks." A computer does the same thing, except it writes the futures down in a data structure. That structure is the **game tree**, and nearly every game-playing program is a way of walking it. This phase gives you the vocabulary and the one number that decides which games a computer can brute-force and which it cannot. ## States and moves A **state** is a complete snapshot of the game: where every piece is, and whose turn it is. A **move** takes one state to another. The rules of the game are exactly the answer to "from this state, which moves are legal?" Draw each state as a dot and each legal move as an arrow to the next state, and you have the **game tree**. The starting position is the **root**. A position where the game is over (a win, a loss, a draw) is a **leaf**. ```mermaid flowchart TD A["Start: empty board, X to move"] --> B["X in corner"] A --> C["X in center"] A --> D["X on edge"] B --> E["O replies"] B --> F["O replies"] C --> G["O replies"] ``` Each level of the tree is one **ply**: a single move by one player. Chess players say "move" for a pair of plies (White then Black), so programmers use "ply" to avoid confusion. > 📝 **Terminology.** The tree is strictly a tree only if you count every path to a position separately. Two different move orders can reach the same board, so the same state can appear many times. Programs that notice this and reuse the answer are using a **transposition table**; you will meet the idea again later. ## The branching factor is the whole story The **branching factor** is the number of legal moves available in a typical state. If every state has about `b` moves and the game lasts about `d` plies, the tree has roughly `b` to the power `d` leaves. The exponent is what hurts: adding one more ply of lookahead multiplies the work by `b`. This is the same explosion that [Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) calls exponential growth. Tic-tac-toe has at most 9 moves at the start and one fewer each turn, so it is small enough to count by machine. Run this: ```python runnable LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for i, j, k in LINES: if b[i] != " " and b[i] == b[j] == b[k]: return b[i] return None def moves(b): return [i for i in range(9) if b[i] == " "] def play(b, i, p): return b[:i] + p + b[i+1:] def count_games(b, p): if winner(b) or not moves(b): return 1 other = "O" if p == "X" else "X" return sum(count_games(play(b, m, p), other) for m in moves(b)) def count_positions(): seen = set() def walk(b, p): if b in seen: return seen.add(b) if winner(b) or not moves(b): return other = "O" if p == "X" else "X" for m in moves(b): walk(play(b, m, p), other) walk(" " * 9, "X") return len(seen) print("distinct games:", count_games(" " * 9, "X")) print("distinct positions:", count_positions()) ``` The board is a 9-character string, `winner` checks the eight lines, and `count_games` walks every path from the empty board to a finished game. When this program ran for this guide it printed: ```console distinct games: 255168 distinct positions: 5478 ``` *What just happened:* there are 255,168 different complete games, but only 5,478 different boards they pass through. The gap is the transposition effect: many move orders arrive at the same board. A computer finishes both counts in a blink, which is why tic-tac-toe is the standard first test for a game-playing program. ## Where brute force stops working Now scale up. In 1950, Claude Shannon wrote the first serious analysis of how a computer could play chess ([Programming a Computer for Playing Chess](https://doi.org/10.1080/14786445008521796), *Philosophical Magazine*). He estimated that a typical position offers on the order of 30 legal moves and a game lasts around 40 moves per side. That gives a game tree with about 10^120 branches, a figure now called the **Shannon number**. It is an estimate of the number of distinct games, not an exact count, and it is a rough order of magnitude, but the lesson does not depend on the exact digits. No computer can list anything near 10^120 items. Go is worse. The Google DeepMind team described Go's search space as more than a googol (10^100) times larger than chess's ([AlphaGo, Google Research blog](https://research.google/blog/alphago-mastering-the-ancient-game-of-go-with-machine-learning/)). A 19-by-19 board offers far more legal moves per turn than chess, and games run long, so both `b` and `d` are big. | Game | Branching factor | Can brute force finish it? | |---|---|---| | Tic-tac-toe | at most 9 | Yes, instantly | | Checkers | modest (jumps are often forced) | Not directly. It took years of work (phase 5) | | Chess | about 30 (Shannon's estimate) | No | | Go | much larger than chess | No, by a huge margin | The table is qualitative for checkers because exact figures depend on how you define a position. The shape is what matters: the bigger `b` is, the faster the tree outgrows any machine. ## So what do programs do instead? They stop trying to see everything. Every technique in the rest of this guide attacks the explosion in one of three ways: 1. **Skip branches that cannot matter** (alpha-beta pruning, [phase 3](03-alpha-beta-pruning.md)). 2. **Stop early and guess** (evaluation functions, [phase 4](04-evaluation-and-stockfish.md)). 3. **Sample instead of enumerate** (Monte Carlo search and learning, [phase 5](05-solving-learning-and-constraints.md)). Check yourself before moving on: ```quiz [ {"q": "A game has about 20 legal moves per position. You add one more ply of lookahead. Roughly how much more work does a full search do?", "choices": ["About 20 times more", "About 20 more nodes", "Twice as much", "The same, because pruning applies"], "answer": 0, "explain": "Each extra ply multiplies the number of leaves by the branching factor, so work grows exponentially with depth."}, {"q": "Why did the tic-tac-toe program count 255,168 games but only 5,478 positions?", "choices": ["Half the games are illegal", "Many different move orders reach the same board", "Positions are counted only for X", "Rotations were removed"], "answer": 1, "explain": "Different sequences of moves can transpose into the same board, so there are far fewer boards than paths."}, {"q": "What did Shannon's 10^120 figure estimate?", "choices": ["The number of legal chess positions exactly", "The number of moves in the longest game", "The number of distinct chess games, roughly", "The speed a computer would need"], "answer": 2, "explain": "It is a rough estimate of the number of distinct games, from about 30 moves per position over about 40 moves per side."} ] ``` ## Recap 1. A game is states connected by legal moves; written out, it is a tree whose leaves are finished games. 2. A ply is one player's move, and the branching factor is the typical number of legal moves. 3. Tree size grows exponentially: roughly `b` to the power `d`. 4. Tic-tac-toe has 255,168 games and 5,478 positions, small enough to enumerate. 5. Shannon estimated chess at around 10^120 games, and Go's search space is vastly larger still. Next up, [Minimax: Playing Perfectly on Tic-Tac-Toe](02-minimax.md): how to pick a move by assuming the opponent plays their best. --- # Minimax: Playing Perfectly on Tic-Tac-Toe You are about to play a move, and you want to know whether it is good. The only reliable answer is: it is good if the opponent cannot punish it. That sentence is the entire minimax algorithm. The rest is bookkeeping, and it fits in one recursive function. ## The mental model Give every finished game a number from the first player's point of view: +1 if X wins, 0 for a draw, -1 if O wins. X wants the number high, so call X the **maximizer**. O wants it low, so O is the **minimizer**. This works for **zero-sum** games, where one player's gain is exactly the other's loss. Now work backwards from the leaves. At a position where O is to move, O will pick the child with the lowest score, so the position's value is the minimum of its children. Where X is to move, the value is the maximum. Repeat up to the root. ```text X to move: value = max(0, -1, +1) = +1 / | \ O to move O to move leaf min(0,+1) min(-1,+1) X wins = 0 = -1 = +1 ``` The value of the root is the result of the game if both sides play perfectly. The best move is the one leading to the child with that value. This is the classic algorithm from the earliest days of game programming, and it is why recursion matters here: "the value of a position is a function of the values of its children" is recursion exactly as in [Recursion Finally Clicks](/guides/recursion-finally-clicks). ## The program ```python runnable LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for i, j, k in LINES: if b[i] != " " and b[i] == b[j] == b[k]: return b[i] return None def moves(b): return [i for i in range(9) if b[i] == " "] def play(b, i, p): return b[:i] + p + b[i+1:] def minimax(b, player): """Score from X's view: +1 X wins, 0 draw, -1 O wins.""" w = winner(b) if w: return 1 if w == "X" else -1 if not moves(b): return 0 other = "O" if player == "X" else "X" scores = [minimax(play(b, m, player), other) for m in moves(b)] return max(scores) if player == "X" else min(scores) def best_move(b, player): other = "O" if player == "X" else "X" pick = max if player == "X" else min return pick(moves(b), key=lambda m: minimax(play(b, m, player), other)) print("Value of the empty board:", minimax(" " * 9, "X")) # Perfect X plays perfect O board, player = " " * 9, "X" while not winner(board) and moves(board): m = best_move(board, player) board = play(board, m, player) player = "O" if player == "X" else "X" for r in range(3): print(" ".join(c if c != " " else "." for c in board[3*r:3*r+3])) print("Winner:", winner(board) or "nobody (draw)") # A position where X must block: O threatens the top row (squares 0, 1 -> 2) b = "OO X X " print("X to move. Score of each move:") for m in moves(b): print(" square", m, "->", minimax(play(b, m, "X"), "O")) print("best move:", best_move(b, "X")) ``` Running it for this guide printed: ```console Value of the empty board: 0 X X O O O X X O X Winner: nobody (draw) X to move. Score of each move: square 2 -> 0 square 3 -> -1 square 5 -> -1 square 6 -> -1 square 8 -> -1 best move: 2 ``` *What just happened:* - **The empty board is worth 0.** Tic-tac-toe is a draw with perfect play, and the program proved it by searching everything. - **Perfect plays perfect and draws.** The exact board shown depends on how ties between equal moves are broken (here, the first best move wins the tie), but a draw is guaranteed. - **The block is found by arithmetic, not by a rule.** O holds squares 0 and 1, threatening 2. Every X move except square 2 scores -1, because minimax finds O's winning reply. Nobody wrote "block the opponent". It falls out of looking ahead. ## Reading the code The pieces map straight onto the theory: - A **base case** handles finished games: a winner, or a full board (a draw). - The **recursive case** asks for the value of every child position, then takes `max` or `min` depending on whose turn it is. - `best_move` is the same search, run one level up, returning the move instead of the value. The 0, +1, -1 numbers have no special meaning, only the order does. Chess programs use scores in "pawns" or "centipawns" and the same max/min logic applies. > ⚠️ **Gotcha.** This version searches roughly half a million positions from the empty board, and it recomputes the same positions many times. That is fine for 9 squares. You will see the exact count in the next phase, and why chess needs smarter tricks. > 💡 **Key point.** Minimax assumes the opponent is perfect. Against a weaker opponent it may pass up a trap that would have won faster, but it never gets a result worse than the value it computed. That safety guarantee is the reason it is the foundation. Check yourself before moving on: ```quiz [ {"q": "At a position where it is O's turn (O is the minimizer), how is the position's value computed?", "choices": ["The maximum of the values of its child positions", "The minimum of the values of its child positions", "The average of the child values", "The value of the first child"], "answer": 1, "explain": "O picks the move that is best for O, which is the lowest score from X's point of view."}, {"q": "Minimax scored the empty tic-tac-toe board 0. What does that tell you?", "choices": ["X always wins if it moves first", "The search found no legal moves", "With perfect play by both sides the game is a draw", "The board is symmetric so scoring failed"], "answer": 2, "explain": "The value of the root is the game-theoretic result when both players play their best."}, {"q": "Why did the program choose square 2 in the blocking position?", "choices": ["A rule says to block the opponent", "Square 2 is the first empty square", "It picks randomly among equal moves", "Every other move led to a score of -1 and square 2 led to 0"], "answer": 3, "explain": "No blocking rule exists. Looking ahead shows that any other move lets O complete the row."} ] ``` ## Recap 1. Score finished games from one player's view and let the two players push the number in opposite directions. 2. A position's value is the max of its children on the maximizer's turn and the min on the minimizer's turn. 3. The whole algorithm is one recursive function with a base case for finished games. 4. The root value is the result under perfect play, and the best move leads to a child with that value. 5. Behaviors like blocking emerge from lookahead; they are not programmed in. Next up, [Alpha-Beta Pruning: Skipping Work That Cannot Matter](03-alpha-beta-pruning.md): the same answer with far fewer positions searched. --- # Alpha-Beta Pruning: Skipping Work That Cannot Matter Minimax is correct and wasteful. It examines moves that a sensible opponent would never allow, and it examines them in full. Alpha-beta pruning is the observation that you can stop looking at a branch the moment you know it cannot affect the final decision. The answer is identical to minimax. Only the work shrinks. ## The idea in one example You are X and you are choosing between two moves, A and B. You have already searched A fully and found it guarantees you a draw (score 0). Now you start searching B. B's first reply from O is a move that wins for O (score -1). You can stop right there. O will pick that reply, so B is worth at most -1, which is already worse than A's 0. It does not matter whether B's other replies are terrible or wonderful for you, because O would choose the refutation. That is a **cutoff**. You skipped the rest of B's subtree without any risk of missing something. To do this in general, each call carries two numbers, as a running record of what is already guaranteed: - **alpha**: the best score the maximizer can already guarantee elsewhere in the tree. - **beta**: the best (lowest) score the minimizer can already guarantee elsewhere. If at some position alpha reaches or passes beta, the player above would never let the game reach this position, so the remaining moves here are skipped. ## The program, with a node counter This runs both searches from the empty board and counts every position each one visits. ```python runnable LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for i, j, k in LINES: if b[i] != " " and b[i] == b[j] == b[k]: return b[i] return None def moves(b): return [i for i in range(9) if b[i] == " "] def play(b, i, p): return b[:i] + p + b[i+1:] nodes = 0 def minimax(b, player): global nodes nodes += 1 w = winner(b) if w: return 1 if w == "X" else -1 if not moves(b): return 0 other = "O" if player == "X" else "X" scores = [minimax(play(b, m, player), other) for m in moves(b)] return max(scores) if player == "X" else min(scores) def alphabeta(b, player, alpha, beta): global nodes nodes += 1 w = winner(b) if w: return 1 if w == "X" else -1 if not moves(b): return 0 other = "O" if player == "X" else "X" if player == "X": best = -2 for m in moves(b): best = max(best, alphabeta(play(b, m, player), other, alpha, beta)) alpha = max(alpha, best) if alpha >= beta: break # O would never allow this line return best best = 2 for m in moves(b): best = min(best, alphabeta(play(b, m, player), other, alpha, beta)) beta = min(beta, best) if alpha >= beta: break # X would never allow this line return best empty = " " * 9 nodes = 0 v1 = minimax(empty, "X") plain = nodes nodes = 0 v2 = alphabeta(empty, "X", -2, 2) pruned = nodes print("minimax value", v1, "nodes", plain) print("alpha-beta value", v2, "nodes", pruned) print("alpha-beta searched %.1f%% as many nodes" % (100 * pruned / plain)) ``` When run for this guide, the output was: ```console minimax value 0 nodes 549946 alpha-beta value 0 nodes 18297 alpha-beta searched 3.3% as many nodes ``` *What just happened:* - **Same value.** Both searches say the empty board is a draw. Pruning never changes the answer. - **About thirty times less work.** 549,946 positions became 18,297. The initial window is `(-2, 2)` because real scores only range from -1 to +1, so no cutoff happens until a real bound is found. - **The saving depends on the tree.** This is one board and one move order. A different order of trying moves gives a different count. ## Move ordering decides how much you save Cutoffs happen sooner when the best moves are tried first. If A is searched before B and A is excellent, B is cut off almost immediately. If the worst move comes first, you learn little and prune little. In the worst case alpha-beta searches as many nodes as minimax; in the best case it searches roughly the square root of the nodes, which lets it look about twice as deep in the same time. This square-root result is a classical analysis of alpha-beta ([Knuth and Moore, 1975](https://doi.org/10.1016/0004-3702%2875%2990019-3)), and it is why real engines work hard at ordering: they try captures, then moves that were good in earlier, shallower searches, and so on. > 💡 **Key point.** Alpha-beta does not make the search approximate. It is an exact shortcut. It is a different thing from the guessing in the next phase. > ⚠️ **Gotcha.** The `break` lines are the whole trick, and the `alpha >= beta` test is a common place to get the direction wrong. A reliable check is to compare your pruned result against plain minimax on many positions. They must always match. ## Where this leaves us Alpha-beta makes chess search tractable to a much deeper depth, but not to the end of the game. The tree is still far too large, as phase 1 showed. Engines therefore stop at a fixed depth and need a way to judge an unfinished position. That is [phase 4](04-evaluation-and-stockfish.md). For a different search that also avoids exploring everything, see [Dijkstra's Shortest Path](/guides/dijkstra-shortest-path): it settles the closest nodes first, so it never revisits paths that cannot be shorter. The problems differ, but the habit is the same, which is to use what you already know to avoid pointless work. Check yourself before moving on: ```quiz [ {"q": "Compared with plain minimax, what does alpha-beta pruning change about the result?", "choices": ["It gives an approximate value", "It only works for draws", "Nothing, the value and best move are the same", "It picks a random best move"], "answer": 2, "explain": "Alpha-beta only skips branches that cannot affect the decision, so its answer is exact."}, {"q": "In the program, alpha-beta visited 18,297 nodes where minimax visited 549,946. What most strongly controls how large that saving is?", "choices": ["The color of the player", "The Python version", "The size of the integer scores", "The order in which moves are tried"], "answer": 3, "explain": "Trying strong moves first produces cutoffs sooner. A bad order prunes little."}, {"q": "You have found that move A guarantees you 0, and while searching move B you find the opponent has a reply worth -1 to you. What should the search do?", "choices": ["Stop searching B, because it is worse than A", "Keep searching all of B to be sure", "Choose B because the search is deeper", "Restart the search"], "answer": 0, "explain": "The opponent will choose the refutation, so B is worth at most -1 no matter what its other replies are."} ] ``` ## Recap 1. Alpha-beta carries two bounds: what the maximizer can already guarantee (alpha) and what the minimizer can (beta). 2. When alpha is greater than or equal to beta, the remaining moves at that position are skipped. 3. The result is exactly minimax's result. On the empty tic-tac-toe board it searched 18,297 nodes instead of 549,946. 4. Good move ordering is what makes pruning powerful; in the best case the search can go about twice as deep for the same work. 5. Even with pruning, chess cannot be searched to the end, so engines need evaluation. Next up, [Evaluation Functions and Stockfish](04-evaluation-and-stockfish.md): what to do when you must stop searching before the game ends. --- # Evaluation Functions and Stockfish Phases 2 and 3 searched until the game ended, because tic-tac-toe is small enough. Chess is not. A chess engine has to stop after some number of plies and say, without seeing the end, "this position looks good for White." The function that says it is the **evaluation function**, and it is where most of an engine's chess knowledge lives. ## The two halves of an engine A real engine is two parts working together: 1. **Search** looks ahead as far as it can, using minimax with alpha-beta pruning from the last phase. 2. **Evaluation** scores the positions at the edge of that lookahead, where search stops. Search without evaluation sees every tactic but cannot tell a good quiet position from a bad one. Evaluation without search judges only what is on the board right now. Together, the search turns a mediocre guess into a good decision by checking many futures. The change to the minimax code is small: add a **depth limit**, and when depth reaches zero, return the evaluation instead of recursing. The scores are no longer the truth about the game. They are estimates, so a deeper search usually (not always) gives a better one. ## A toy evaluation you can run For tic-tac-toe, a reasonable guess is to count the lines that are still open to each player. A line with no O marks is a possibility for X, worth more as X fills it. Score each side that way and subtract. ```python runnable LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for i, j, k in LINES: if b[i] != " " and b[i] == b[j] == b[k]: return b[i] return None def moves(b): return [i for i in range(9) if b[i] == " "] def play(b, i, p): return b[:i] + p + b[i+1:] def evaluate(b): """Guess, from X's view, how good a non-final board looks. A line still open for one side is worth 1, 10 or 100 points depending on how many of that side's marks are already in it.""" score = 0 for line in LINES: cells = [b[i] for i in line] if "O" not in cells: score += (0, 1, 10, 100)[cells.count("X")] if "X" not in cells: score -= (0, 1, 10, 100)[cells.count("O")] return score nodes = 0 def search(b, player, depth): """Minimax that stops after `depth` plies and trusts evaluate().""" global nodes nodes += 1 w = winner(b) if w: return 10000 if w == "X" else -10000 if not moves(b): return 0 if depth == 0: return evaluate(b) other = "O" if player == "X" else "X" scores = [search(play(b, m, player), other, depth - 1) for m in moves(b)] return max(scores) if player == "X" else min(scores) empty = " " * 9 for depth in (1, 2, 3): nodes = 0 scores = {m: search(play(empty, m, "X"), "O", depth - 1) for m in moves(empty)} best = max(scores, key=scores.get) print("depth", depth, "-> opening move", best, "nodes", nodes) ``` The output when run for this guide: ```console depth 1 -> opening move 4 nodes 9 depth 2 -> opening move 4 nodes 81 depth 3 -> opening move 4 nodes 585 ``` *What just happened:* even a one-ply look plus a crude guess picks square 4, the center, which is on the most lines (four of the eight) and is a strong opening in tic-tac-toe. The evaluation encoded that knowledge without a rule saying "take the center." The node counts show the cost: each extra ply multiplies the work, which is the explosion from phase 1. ## Evaluation in chess: material first The oldest and most important chess heuristic is **material**: count the pieces. The conventional point values are pawn 1, knight 3, bishop 3, rook 5, queen 9. These are teaching conventions, not laws, and engines refine them. ```python runnable VALUE = {"p": 1, "n": 3, "b": 3, "r": 5, "q": 9, "k": 0} def material(fen): """Positive means White is ahead. Only reads the piece-placement field.""" total = 0 for ch in fen.split()[0]: if ch.lower() in VALUE: total += VALUE[ch.lower()] if ch.isupper() else -VALUE[ch.lower()] return total start = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" no_queen = "rnb1kbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" print("start position:", material(start)) print("Black has lost its queen:", material(no_queen)) ``` ```console start position: 0 Black has lost its queen: 9 ``` The string is **FEN**, the standard text notation for a chess position (capital letters are White). Material alone is a weak judge, though. Real evaluations add **mobility** (how many moves a side has), king safety, pawn structure, and control of the center. [Chess From Zero](/guides/chess-from-zero) explains why those matter to a human, and the engine cares for the same reasons. ## The horizon problem and quiescence A depth limit creates a trap called the **horizon effect**. Suppose the search stops exactly after your queen captures a pawn. The evaluation sees "up a pawn" and loves it, missing that the queen is captured on the very next ply. The bad news lies past the horizon. The classic fix is **quiescence search**. At the depth limit, instead of evaluating immediately, the engine keeps searching only the "noisy" moves, such as captures, until the position is quiet enough for a material count to mean something. Shannon discussed the need to evaluate only quiet positions in his 1950 paper, and it remains standard practice. ## How Stockfish works today Stockfish is the open-source engine behind the [chess opponent on this site](/games/chess). Its [official project page](https://stockfishchess.org/about/) describes it as one of the strongest engines in the world. Per the Stockfish team's [announcement of NNUE evaluation](https://stockfishchess.org/blog/2020/introducing-nnue-evaluation/), it has two components exactly as above: - **Search:** alpha-beta search (specifically a variant called principal variation search, PVS) finds the best move. - **Evaluation:** a value for each position at the edge of the search. Historically this was a function "handcrafted by experts" from chess concepts. Since Stockfish 12, released in September 2020, it is an **NNUE**, an efficiently updatable neural network. NNUE was first used in the game of shogi and then ported to Stockfish. It computes its score from basic inputs about where the pieces stand, and was trained on millions of positions. The "efficiently updatable" part is the key engineering idea: after one move only a few pieces change, so most of the network's first layer does not need to be recalculated. That lets a neural network run millions of times per second on an ordinary CPU, deep inside the search. Stockfish's own tests at the time of the announcement showed a gain of over 80 Elo points from this change. > 💡 **Key point.** Stockfish did not stop being a search engine when it adopted a neural network. The network replaced the evaluation guess, not the alpha-beta search. This hybrid differs from AlphaZero, which you will meet in the next phase. For background on how a network like this is built, read [How a Neural Network Is Structured](/guides/how-a-neural-network-is-structured), and for how its weights are found, [How a Model Learns](/guides/how-a-model-learns). Check yourself before moving on: ```quiz [ {"q": "Why does a chess engine need an evaluation function at all?", "choices": ["Alpha-beta pruning cannot run without one", "Chess has no winning positions", "To make the search deterministic", "The game tree is too big to search to the end, so it must score unfinished positions"], "answer": 3, "explain": "Search must stop at a depth limit, and the evaluation scores the positions where it stops."}, {"q": "What problem does quiescence search address?", "choices": ["Evaluating a position in the middle of a capture sequence, whose score is misleading", "Slow disk access", "Choosing the opening book", "Reducing the branching factor to 1"], "answer": 0, "explain": "Stopping mid-exchange makes the evaluation look better or worse than it is. Quiescence search continues the noisy moves until the position is calm."}, {"q": "What is true of Stockfish since version 12?", "choices": ["It replaced search with a neural network that plays directly", "It uses alpha-beta search together with an NNUE neural-network evaluation", "It uses only handcrafted evaluation", "It uses Monte Carlo tree search"], "answer": 1, "explain": "The Stockfish project describes NNUE evaluation feeding values into alpha-beta (PVS) search."} ] ``` ## Recap 1. Engines combine a search that looks ahead with an evaluation that scores the positions where it stops. 2. A depth limit turns exact minimax into an estimate, and deeper usually means better. 3. Material is the classic heuristic, joined by mobility, king safety, and structure. 4. The horizon effect is fixed by quiescence search, which keeps resolving captures before scoring. 5. Stockfish pairs alpha-beta search with an NNUE neural-network evaluation that is cheap to update after each move. Next up, [Solved Games, Learned Games, and Constraints](05-solving-learning-and-constraints.md): proving a game is a draw, learning to play without hand-written knowledge, and a different style of problem. --- # Solved Games, Learned Games, and Constraints So far the recipe has been: search the tree as deep as you can, then guess. This phase covers three different directions. One pushes search so far that the game is finished for good. One drops the hand-written guess and uses sampling and learning. The last leaves two-player games altogether, because Sudoku has no opponent and needs a different tool. ## Solving a game: Chinook and checkers To **solve** a game means to know its result under perfect play. There are levels, and the difference matters: - **Ultra-weakly solved:** you know the result from the starting position, maybe by an argument, without knowing how to achieve it. - **Weakly solved:** you know the result and have a strategy that achieves it from the start. - **Strongly solved:** you know the best result from every legal position. In 2007, Jonathan Schaeffer and colleagues published [Checkers Is Solved](https://doi.org/10.1126/science.1144079) in *Science*. They showed that checkers (English draughts) is a **draw** with perfect play, which makes it **weakly solved**. The game has roughly 5 x 10^20 positions, far too many to examine one by one, and the team had been working on the problem since 1989 with their program **Chinook**. They combined a forward search from the opening with endgame databases (precomputed exact results for positions with few pieces left) and a proof-search procedure to avoid examining positions that did not matter. The result is a proof, not a strong opinion: if you never make a mistake as either side, the game is drawn. This is the same alpha-beta thinking from earlier, scaled up with databases and many years of computer time. It worked because checkers' tree, although huge, is small enough to be tamed. Chess and Go are not solved. The checkers opponent on this site is an engine named Marcher, and you can [play checkers](/games/checkers) against it. [Checkers From Zero](/guides/checkers-from-zero) teaches the game itself. > ⚠️ **Gotcha.** "Solved" does not mean the program plays like a human would, or that every game is a draw in practice. It means a flawless player cannot do better than a draw. Humans make mistakes, and so does any engine that is not carrying the full proof. ## Monte Carlo tree search: sample instead of enumerate Go was out of reach for the alpha-beta recipe for two reasons from phase 1: too many moves per turn, and no good hand-written evaluation (a Go position does not reduce to a material count). A different approach, **Monte Carlo tree search** (MCTS), changes the question from "what is the exact value?" to "how often do I win from here?" The simplest form: from the position, try a move, then play the rest of the game out with random moves, many times. A move that wins more of its random games is probably better. Run it on the blocking position from phase 2: ```python runnable import random LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for i, j, k in LINES: if b[i] != " " and b[i] == b[j] == b[k]: return b[i] return None def moves(b): return [i for i in range(9) if b[i] == " "] def play(b, i, p): return b[:i] + p + b[i+1:] def random_playout(b, player): """Finish the game with random moves. Return the winner or None.""" while not winner(b) and moves(b): b = play(b, random.choice(moves(b)), player) player = "O" if player == "X" else "X" return winner(b) def monte_carlo_move(b, player, playouts=300): other = "O" if player == "X" else "X" rates = {} for m in moves(b): wins = 0 for _ in range(playouts): w = random_playout(play(b, m, player), other) wins += 1 if w == player else 0.5 if w is None else 0 rates[m] = wins / playouts return max(rates, key=rates.get), rates random.seed(7) b = "OO X X " # X must block square 2 move, rates = monte_carlo_move(b, "X") print("move chosen:", move) for m, r in rates.items(): print(" square", m, "score", round(r, 2)) ``` With the seed fixed at 7, it printed: ```console move chosen: 2 square 2 score 0.79 square 3 score 0.46 square 5 score 0.37 square 6 score 0.56 square 8 score 0.37 ``` *What just happened:* the program knows no tactics. Random games win more often after the block, so it found the right move through statistics. Other seeds give slightly different percentages, which is the point: results are estimates that sharpen with more playouts. Real MCTS adds the "tree" part. It grows a search tree gradually, repeating four steps: **select** a promising path through the tree built so far, **expand** it by one new position, **simulate** a playout to the end, and **back up** the result along the path. Promising branches get more attention, and weak ones less, so effort concentrates where it matters. ## AlphaGo: networks to guide the search In 2016, the DeepMind team published [Mastering the game of Go with deep neural networks and tree search](https://doi.org/10.1038/nature16961) in *Nature*. AlphaGo combined MCTS with two deep neural networks, as described in the [Google Research summary](https://research.google/blog/alphago-mastering-the-ancient-game-of-go-with-machine-learning/): - A **policy network** predicts which moves a strong player would likely play, so the search examines only those. This cuts the branching factor. - A **value network** estimates who is winning in a position, so the search can stop early instead of playing every game to the end. This cuts the depth. The policy network was first trained on 30 million moves from games between human experts, until it predicted the expert's move 57% of the time, then improved by self-play and reinforcement learning. In the match that followed, AlphaGo beat Fan Hui, the three-time European champion, 5 games to 0, the first time a program had beaten a professional Go player on a full-size board with no handicap. In March 2016 a later version beat Lee Sedol, one of the world's top players, 4 games to 1. Notice the two roles map onto this guide. The value network replaces a hand-written evaluation function from phase 4, and the policy network plays the part that move ordering plays in alpha-beta: spend effort on promising moves first. ## AlphaZero: learning from the rules alone AlphaGo still began with human game records. In 2017 the DeepMind team posted [a general reinforcement learning algorithm](https://arxiv.org/abs/1712.01815), later published in [Science in 2018](https://doi.org/10.1126/science.aar6404), called **AlphaZero**. It starts knowing only the rules and plays against itself. A single neural network, trained from those self-play games, supplies both move preferences and position values to an MCTS. The authors report that, with no domain knowledge beyond the rules, it reached superhuman strength in chess, shogi, and Go within 24 hours of training, and defeated a world-champion program in each: Stockfish in chess and Elmo in shogi. Two caveats help keep the picture clear. Stockfish has changed since that comparison, notably by adopting NNUE (phase 4), and the result depended on the match conditions and hardware, which the paper documents. Also, AlphaZero is a family of ideas: a learned network guiding a search. Engines today often combine learned evaluation with classical search, as Stockfish does. The learning side is the same ideas as [How a Model Learns](/guides/how-a-model-learns) applied to games: the network's weights are adjusted so its predictions match what search and game outcomes show. Self-play creates its own training data. ## A different paradigm: constraint solving Chess and checkers have an opponent. **Sudoku does not.** There is nobody to anticipate, only a set of rules every answer must satisfy. That makes it a **constraint satisfaction problem**: variables (the 81 cells), domains (digits 1 to 9), and constraints (no repeated digit in a row, column, or box). You are not choosing a move to survive a reply. You are searching for any assignment that breaks no constraint. The standard method is **backtracking**: fill a cell, continue, and if you reach a dead end, undo the last choice and try another. It is recursion again, as in [Recursion Finally Clicks](/guides/recursion-finally-clicks). What decides whether it takes microseconds or forever is *which cell you fill next*. Compare two strategies on a well-known example puzzle: ```python runnable PUZZLE = ("530070000600195000098000060800060003400803001700020006060000280000419005000080079") def candidates(grid, r, c): used = set(grid[r]) | {grid[i][c] for i in range(9)} br, bc = 3 * (r // 3), 3 * (c // 3) used |= {grid[i][j] for i in range(br, br + 3) for j in range(bc, bc + 3)} return [d for d in range(1, 10) if d not in used] def solve(grid, smart): """Backtracking search. Returns (solved?, number of digit placements tried).""" tries = 0 def go(): nonlocal tries empties = [(r, c) for r in range(9) for c in range(9) if grid[r][c] == 0] if not empties: return True if smart: # pick the blank with the fewest legal digits r, c = min(empties, key=lambda rc: len(candidates(grid, *rc))) else: # pick the first blank in reading order r, c = empties[0] for d in candidates(grid, r, c): tries += 1 grid[r][c] = d if go(): return True grid[r][c] = 0 return False ok = go() return ok, tries def parse(s): return [[int(s[9 * r + c]) for c in range(9)] for r in range(9)] for name, smart in (("first blank first", False), ("fewest options first", True)): g = parse(PUZZLE) ok, tries = solve(g, smart) print(name, "-> solved:", ok, "placements tried:", tries) print("first row of the answer:", g[0]) ``` ```console first blank first -> solved: True placements tried: 4208 fewest options first -> solved: True placements tried: 51 first row of the answer: [5, 3, 4, 6, 7, 8, 9, 1, 2] ``` *What just happened:* both solvers are exact and find the same grid. The puzzle has 51 blank cells, so 51 placements means the second strategy never backtracked: at each step it chose the most constrained cell, which was always forced or nearly so. This rule, "fewest remaining options first," is a standard heuristic called minimum remaining values. The first solver wasted about eighty times as many placements on guesses it later undid. Compare the two paradigms. In game search you ask what the opponent can do to you, and you handle uncertainty by assuming their best play. In constraint solving you prune by eliminating possibilities that violate a rule, and there is no adversary. Both fight the same enemy, exponential growth, with the same weapon: refusing to explore what cannot lead anywhere. You can try this on a real puzzle with [play Sudoku](/games/sudoku), and [Sudoku From Zero](/guides/sudoku-from-zero) shows the human version of the same elimination logic. > 💡 **Key point.** Choosing the problem's structure matters more than choosing a fast language. Two-player games ask for minimax and its relatives, puzzles with rules ask for constraints, and when no hand-written evaluation exists, learning and sampling fill the gap. Check yourself before moving on: ```quiz [ {"q": "What did Schaeffer and colleagues show about checkers in 2007?", "choices": ["It is a draw with perfect play, so it is weakly solved", "It is a win for the first player", "It is strongly solved from every position", "It cannot be solved by computers"], "answer": 0, "explain": "Checkers Is Solved (Science, 2007) proved the result of the starting position is a draw. Weakly solved means the start is known, not every position."}, {"q": "In AlphaGo, what are the policy network and the value network used for?", "choices": ["Policy stores opening books, value counts stones", "Policy suggests promising moves to search, value estimates who is winning so the search can stop early", "Both only choose the final move without any search", "Policy trains against Stockfish, value runs minimax"], "answer": 1, "explain": "The policy network narrows the branching, and the value network shortens the depth, both inside Monte Carlo tree search."}, {"q": "Why can Sudoku be handled by backtracking with constraints rather than minimax?", "choices": ["It has fewer than nine cells", "Minimax cannot use recursion", "There is no opponent, only rules that a complete answer must satisfy", "Sudoku positions have no legal moves"], "answer": 2, "explain": "Sudoku is a constraint satisfaction problem. You search for any assignment that breaks no rule, rather than anticipating an opponent's replies."} ] ``` ## Recap 1. Solving a game means knowing its result under perfect play; checkers was weakly solved in 2007 and is a draw. 2. Monte Carlo search estimates a move's value from many random playouts and grows a tree around the promising ones. 3. AlphaGo used a policy network to narrow moves and a value network to cut depth, inside MCTS. 4. AlphaZero learned from self-play with only the rules, reaching top strength in chess, shogi, and Go according to its authors. 5. Sudoku is a constraint problem: backtracking plus a good choice of which cell to fill next, with no opponent involved. That is the whole ladder, from a nine-square board to systems that learn a game on their own. To keep going, try changing the tic-tac-toe code to play a different game, or return to [Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) and measure where each of these methods hits its limits.