If you've competed on Codeforces long enough, you've probably seen the aftermath of a plagiarism sweep — ratings quietly rolled back days after a round, a wave of "why did I lose rating?" posts, someone's submission flagged with a red "SKIPPED" or a hack. Ever wondered what's actually happening behind the scenes? Here's a breakdown of how automated code-similarity detection works, and why it's harder to dodge than people think.

The core problem: comparing everyone to everyone

A typical Div. 2 round pulls in tens of thousands of submissions per problem. To catch copied code, you'd naively need to compare every submission against every other submission — that's roughly O(n²) pairs. For 30,000 participants, that's on the order of 450 million comparisons per problem. Even at a blistering 10,000 comparisons per second, that's over 12 hours of raw compute for one problem alone.

This is exactly why plagiarism results don't show up immediately after a contest. Ratings get updated first (people are impatient), and the plagiarism pass runs afterward — often taking a few days, especially since close calls get reviewed by a human rather than auto-banned.

The algorithm: winnowing and fingerprinting

The dominant technique here — used by MOSS (Measure of Software Similarity), the Stanford-built tool that's become the industry standard for this kind of detection — is called winnowing. The idea:

Tokenize the code, stripping away things that don't reflect actual logic: variable names, whitespace, comments, and formatting. Generate k-grams — overlapping sequences of consecutive tokens. Hash each k-gram, then select a representative subset of those hashes (the "fingerprint") using a sliding-window rule that guarantees any shared substring of a minimum length is caught by at least one fingerprint. Compare fingerprint sets between submissions instead of raw text. Two files with a high overlap in fingerprints get flagged.

Because the comparison happens on token structure rather than literal text, this approach is deliberately robust to the "cheap" evasion tricks people try first: renaming variables, reordering independent statements, changing whitespace, adding comments, or swapping for loops for equivalent while loops. None of that changes the underlying token sequence enough to break the fingerprint match.

Why it's hard to reliably evade

A few properties make this genuinely difficult to beat, not just annoying to beat:

Noise suppression: matches on tiny common patterns (like a single for loop skeleton every competitive programmer writes) are filtered out, so the system focuses on large, structurally unusual chunks of matching code — the kind that's actually suspicious. Position independence: code doesn't need to appear in the same order in both files to be flagged, so reordering unrelated blocks doesn't help. Human review on close calls: borderline similarity scores aren't auto-punished; a person looks at them, which catches cases where someone tried to be clever about just barely diffing two files enough to dodge a hard threshold. It's checked against templates: standard boilerplate (fast I/O templates, common headers) gets excluded from scoring specifically so it doesn't cause false positives — meaning the system's signal is concentrated exactly on the parts of your code that are actually yours.

There's actual academic literature on attacking MOSS-style systems (one notable paper is literally called "Mossad: Defeating Software Plagiarism Detection"), and it's telling that the successful attacks involve fairly elaborate automated code transformation pipelines — not the kind of thing you improvise during a contest. Cheap surface-level edits, which is what time-pressured contest cheating usually looks like, don't get anywhere near that level of sophistication.

The bigger picture

The interesting takeaway isn't really "here's how to sneak past it" — it's that the whole design assumes cheating attempts are rushed and superficial, and optimizes detection specifically around that. The system isn't perfect (there are Codeforces blog posts from people who've found edge cases and bugs), but its core design — fingerprint on structure, suppress common noise, flag outliers, let humans adjudicate the gray zone — is why "just rename my variables" hasn't worked as an evasion strategy in over a decade of people trying it.

For anyone curious to dig deeper, the original MOSS paper and the Winnowing algorithm paper (Schleimer, Wilkerson, Aiken, 2003) are both worth reading, and Codeforces' own blog has several posts from the community reverse-engineering how their specific implementation behaves in practice.

Every few months, a new thread pops up on this site demanding that Codeforces "do something" about AI. Ban Copilot. Detect ChatGPT-written solutions. Add a proctoring layer. Lock down every editor into a walled garden.

I think all of that is missing the point, and I want to make an unpopular argument: the problem was never the tool. It's that half the userbase already doesn't believe in the rating system they're grinding for.

The tool panic is a distraction

Every generation of competitive programmers has had a "the tools are ruining this" moment. Calculators. IDE autocomplete. STL and built-in data structures instead of hand-rolled segment trees. Competitive Programmers' Handbook snippets pasted straight into templates. None of these destroyed the sport. They just moved the skill ceiling up a notch — the people who used to spend rating points memorizing implementation details started spending them on recognizing which implementation to use.

Large language models are the same shift, just faster and more visible. The people panicking about AI in Div. 2 rounds are, ninety percent of the time, panicking about something that was already possible with a well-organized template folder and a search engine. The difference isn't capability. It's that watching someone paste a prompt feels more like cheating than watching someone paste from their own notes, even when the effect on the scoreboard is identical.

The real rot: nobody trusts the number anymore

Here's the part that should actually worry you. Scroll through any "congratulations on hitting [rating]" post and count how many top comments are some version of "ratings don't mean anything anymore" or "half of Div. 3 is just template lookup." That sentiment predates every AI tool by years. It's why smurfing threads get more engagement than genuinely good editorial write-ups. It's why "is CF rating still meaningful for internships" gets asked every single month.

If a huge chunk of the community already treats the rating as theater, then arguing about whether an LLM is "unfair" is like arguing about the seating chart on a sinking boat. AI didn't create the trust problem. It just made an existing crack impossible to ignore, because now the fastest way to fake competence is one text box away instead of requiring actual template-building effort.

What would actually fix this — and why it won't happen

The honest fix isn't a ban. It's radical transparency: publish anti-cheat detection rates, publish how many accounts get flagged per division per round, and stop pretending the current system already catches everything. Most of the outrage comes from people assuming enforcement exists and is failing. The truth is closer to: enforcement barely exists, and everyone quietly knows it.

This won't happen, for the same reason it never happens on any platform with a reputation number attached to it: admitting the scale of the problem publicly damages the perceived value of the number more than quietly ignoring it does. Codeforces has every incentive to let this stay a background hum instead of a headline.

So what do you actually do about it

Stop treating your rating as a certificate and start treating it as a training log. If you're using AI tools to solve problems during practice, you're not cheating anyone — you're just choosing a worse way to practice, the same way copying solutions from tutorials during a virtual contest was always a worse way to practice. Nobody needs to ban that from you. You need to decide you don't want to lie to yourself about what "solving" a problem means.

The scoreboard was never the point. If you needed a banned tool to tell you that, you already knew the answer.

Curious where I'm wrong here — genuinely. Is there a fix to the trust problem I'm missing, or is "everyone quietly knows the number is soft" just the permanent state of any rated system at scale?

If you've spent any time on Codeforces, you've probably had this thought at least once:

"Sorting is such a basic operation. Why is O(n log n) the best we can do? Can't someone just be clever enough to sort in O(n)?"

The honest answer is: it depends on what kind of sorting you're doing. For general-purpose comparison-based sorting, O(n log n) isn't just "the best algorithm found so far" — it's a provable mathematical floor. No algorithm, however clever, can beat it. But for special cases, O(n) sorting is not only possible, it's a well-known trick that shows up constantly in competitive programming.

This post explains both halves of that story.

1. The Claim Needs to Be Precise

"You can't sort in O(n)" is only true for a specific class of algorithms: comparison-based sorts. These are algorithms that determine the final order of elements purely by comparing pairs of elements — if a[i] < a[j]), and nothing else. No looking at the actual values, no hashing, no using them as array indices.

Merge sort, quicksort, heapsort, insertion sort — all comparison-based. All bounded below by Ω(n log n) comparisons in the worst case.

The moment you allow yourself to use the actual values of the elements (not just compare them), the rules change completely — more on that in Section 3.

1. The Decision Tree Argument (Why the Bound Is Real)

This is the elegant part, and it's worth understanding fully rather than just memorizing.

Setup: Any comparison-based sorting algorithm can be modeled as a binary decision tree.

Each internal node represents one comparison, like a[i] < a[j]. Depending on the outcome (true/false), the algorithm branches left or right. Each leaf of the tree corresponds to one final, fully-determined ordering of the input.

Key fact: For n distinct elements, there are n! possible orderings. Since the algorithm must be able to produce any of these orderings depending on the input, the decision tree must have at least n! leaves.

Height vs. leaves: A binary tree of height h can have at most 2^h leaves. So we need:

2^h ≥ n! h ≥ log2(n!)

Using Stirling's approximation:

log2(n!) = Θ(n log n)

So the height of the tree — which represents the worst-case number of comparisons — must be at least Ω(n log n). Since every comparison takes at least constant time, any comparison-based sort needs Ω(n log n) time in the worst case.

This is an information-theoretic argument, not an engineering limitation. It's not "we haven't found a faster algorithm yet" — it's a hard mathematical ceiling on how much information a sequence of yes/no comparisons can extract. Merge sort and heapsort, at O(n log n), are actually asymptotically optimal.

1. So How Do Counting Sort, Radix Sort, and Bucket Sort Hit O(n)?

They don't break the lower bound — they step outside the model the bound applies to. They don't compare elements at all.

Counting Sort — O(n + k)

Assumes elements are integers in a small known range [0, k). Instead of comparing, it counts occurrences of each value directly and uses those counts to place elements — essentially using the value itself as an array index.

cppvoid countingSort(vector& a, int maxVal) { vector count(maxVal + 1, 0); for (int x : a) count[x]++; int idx = 0; for (int v = 0; v <= maxVal; v++) while (count[v]--) a[idx++] = v; }

Works great when k = O(n). Falls apart if k is huge (say, values up to 10^9) — then it's not O(n) anymore, it's O(n + k).

Radix Sort — O(d · (n + k))

Sorts numbers digit by digit (or byte by byte), using counting sort as a stable subroutine for each digit position. For d digits, this gives O(d(n+k)) — linear when d is a small constant (e.g., fixed 32-bit or 64-bit integers).

Bucket Sort — O(n) expected

Assumes input is roughly uniformly distributed over a range. Distributes elements into n buckets, sorts each small bucket individually (often with insertion sort), then concatenates. Works well in expectation when the distribution assumption holds; degrades to O(n log n) or worse if it doesn't.

The common thread: all three exploit extra structure in the input — a bounded range, a fixed number of digits, a known distribution — that comparison sort doesn't get to assume. They're solving an easier problem than "sort arbitrary comparable elements," so the Ω(n log n) bound simply doesn't apply to them.

1. The Competitive Programming Angle

Here's the pattern worth internalizing: if you ever submit an O(n) or O(n + k) sort on Codeforces and it passes, it's never because you found a magical general-purpose linear sort. Look at the constraints — you'll almost always find one of these:

Values are bounded by a small range (a[i] ≤ 10^6) → counting sort Values are integers with bounded digit count → radix sort You're sorting into a fixed number of buckets/categories → bucket sort or even just direct placement

A concrete example: if a problem guarantees 1 ≤ a[i] ≤ 2·10^5 and n ≤ 2·10^5, counting sort in O(n + max_val) is often faster in practice than std::sort's O(n log n) — and it's a nice trick to have ready when TLE is close.

1. Takeaway

Ω(n log n) is a provable lower bound for comparison-based sorting — not a limitation of current algorithms, but a mathematical fact about how much information comparisons can extract. Merge sort / heapsort achieve this bound, so they're optimal within their model. Linear-time sorts (counting, radix, bucket) escape the bound by not comparing — they use the actual values of elements, exploiting extra assumptions about the input. On Codeforces, spotting when a problem's constraints quietly permit an O(n) sort is a genuinely useful skill, not just trivia.

Next time you see "why can't we just sort in O(n)?" in a comment section, you'll know the real answer: you can — just not by comparing.

Open your phone right now. Maps, Instagram, Spotify, LinkedIn, Uber — whatever you tap on, there's a good chance a graph is quietly doing the heavy lifting behind the scenes. In competitive programming, graphs are just nodes and edges you traverse with BFS, DFS, or Dijkstra. In the real world, those same nodes and edges represent people, places, songs, and rides — and the algorithms running on them are worth billions of dollars.

Here are 5 apps you probably used today that are secretly graph problems in disguise. **** **** 1. Google Maps / Waze — Shortest Path Algorithms **** The graph: Every intersection is a node. Every road segment is an edge, weighted by distance, speed limit, and live traffic.

The algorithm: A modified version of Dijkstra's algorithm or A* search — the same algorithm you'd use to solve a "shortest path" problem on a competitive programming judge. The twist is that edge weights change in real time based on traffic data from millions of phones, so the graph is being re-weighted constantly, and the shortest path is being recomputed on the fly.

Why it's clever: A full Dijkstra's run on a graph the size of an entire country's road network would be too slow to do from scratch every time. So Maps uses techniques like contraction hierarchies — precomputing "shortcut" edges between important nodes (think highways) so long-distance queries can skip over irrelevant local roads, similar to how you'd precompute a sparse table or use bidirectional search in CP to speed up pathfinding.

2. Instagram / Facebook / LinkedIn — Friend & Connection Suggestions

The graph: Every user is a node. Every friendship, follow, or connection is an edge.

The algorithm: "People You May Know" is a classic graph traversal problem — specifically, it looks a lot like counting common neighbors (friends-of-friends) using BFS up to 2-3 hops, then ranking candidates by the number of mutual connections, shared groups, or interaction frequency.

Why it's clever: Doing a full BFS from every user across billions of people isn't feasible, so these platforms use distributed graph processing frameworks (like Apache Giraph or Pregel, both inspired by BFS-style "supersteps") to compute this efficiently across thousands of machines in parallel — essentially CP graph traversal, scaled to a planet-sized graph.

3. Google Search — PageRank

The graph: Every webpage is a node. Every hyperlink from one page to another is a directed edge.

The algorithm: PageRank, Google's original ranking algorithm, treats the entire internet as a giant directed graph and simulates a "random surfer" who clicks links randomly. Pages that receive links from many other important pages get a higher rank — this is computed iteratively, similar to how you'd propagate values across a graph in a CP problem until the values converge (a fixed-point iteration, related to how you'd compute stationary distributions in a Markov chain).

Why it's clever: Instead of just counting how many links point to a page (which is easy to spam), PageRank weighs whose links you get — a link from a highly-ranked page matters more. This recursive definition (a page's importance depends on the importance of pages linking to it) is exactly the kind of self-referential relationship you'd model with a graph and solve using linear algebra (eigenvector computation) or iterative graph algorithms. **** **** 4. Netflix / Spotify / Amazon — Recommendation Engines

The graph: Users and items (movies, songs, products) form a bipartite graph — users connect to the items they've watched, listened to, or bought.

The algorithm: Collaborative filtering often works by traversing this bipartite graph: "Users who watched X also watched Y" is literally a 2-hop graph traversal

5. Uber / Lyft — Ride Matching (user → item → other users who liked it → other items they liked). More advanced systems build a similarity graph between items or users and use graph embeddings (like Node2Vec) — a technique that turns graph traversal (random walks, similar to DFS with randomness) into vectors that feed into machine learning models.

Why it's clever: Rather than comparing every user to every other user (which is computationally expensive at scale), these systems reduce the graph traversal problem into compact vector representations, so "similar taste" becomes a fast nearest-neighbor lookup instead of a full graph search every time.

The graph: Riders and available drivers form a bipartite graph, with edges weighted by distance, estimated pickup time, and driver rating.

The algorithm: Matching riders to drivers efficiently is a version of the assignment problem, solvable with algorithms like the Hungarian algorithm or min-cost max-flow — both graph algorithms that CP folks will recognize from "matching" and "flow network" problems. The goal is to minimize total wait time (or maximize overall efficiency) across the entire city, not just optimize one match at a time.

Why it's clever: A greedy "match nearest driver" approach seems obvious but is often suboptimal city-wide — it might leave a driver on the other side of town stranded. Batch-matching multiple riders and drivers at once using flow algorithms produces much better overall outcomes, exactly the kind of insight you get from studying flow networks in CP instead of just doing naive greedy matching.

**** The Takeaway

Every time you get directions, see a friend suggestion, search something on Google, get a Spotify recommendation, or book an Uber, there's a graph underneath — and the same BFS, DFS, Dijkstra, and flow algorithms you practice for competitive programming are what make these apps feel instant and "smart" at massive scale.

The difference between a CP problem and one of these real systems isn't really the algorithm — it's scale. The core idea (traverse a graph, find shortest paths, match nodes efficiently) is identical; the engineering challenge is making it work fast across billions of nodes and edges, in real time, across thousands of machines.

So the next time you're grinding a graph problem and wondering "will I ever use this?" — remember, you already are, every time you open your phone.

If you've ever done competitive programming (CP), you know the drill — segment trees at 2 AM, dynamic programming (DP) transitions that make your head spin, graphs that refuse to be traversed efficiently. It's easy to dismiss this as "just contest stuff." But the truth is, almost every algorithm you grind on Codeforces or LeetCode has a real job somewhere in the world — and one of the most fun places to see this is sports.

This post covers two things:

Everyday, real-life uses of classic CP concepts. A deep dive into how algorithms — especially DP — quietly run the show in cricket, tennis, basketball, football, chess, and more.

Part 1: CP Concepts You Already Know, Working in the Real World **** Sorting & Searching **** Every time you sort products by price on Amazon or search for a contact on your phone, you're using variants of merge sort, quicksort, or binary search. Databases use B-trees (a generalization of binary search trees) to fetch records in logarithmic time instead of scanning millions of rows. **** Graph Algorithms

Google Maps / Uber routing — Dijkstra's algorithm and A* search find the shortest path between two points, factoring in live traffic as edge weights. Social networks — "People you may know" and friend recommendations use BFS/DFS traversal and graph community detection. Network routing — the internet itself relies on shortest-path algorithms to move packets efficiently.

**** Greedy Algorithms

Huffman coding compresses files (like ZIP, JPEG, MP3) by giving shorter codes to frequent symbols — a textbook greedy algorithm. Job scheduling in operating systems and cloud computing (like task queues in AWS Lambda) often uses greedy heuristics to maximize throughput.

String Algorithms

Plagiarism detection and spell-checkers use edit distance (a DP classic) and suffix automata/tries. DNA sequencing in bioinformatics uses the same longest common subsequence (LCS) and sequence alignment algorithms you'd use to solve an "edit distance" CP problem.

Backtracking

Sudoku solvers, N-Queens, and even some AI puzzle solvers in games use backtracking with pruning — precisely the technique used in CP for constraint satisfaction problems.

Dynamic Programming

DP shows up in resource allocation, route optimization (like the classic "traveling salesman" approximations used in logistics), text justification in word processors, and — as we're about to see — deciding cricket targets, football fourth-down calls, and F1 pit stops.

**** Part 2: Algorithms in Sports — The Fun Part **** Cricket: The Duckworth-Lewis-Stern (DLS) Method

This is probably the most famous real-world algorithm in sports, and CP folks love it because it's essentially a precomputed table + interpolation problem, similar to how you'd precompute DP states for fast lookup.

The problem it solves: If a rain-interrupted match reduces the number of overs available, what's a fair revised target for the team batting second?

How it works (simplified):

Cricket has two resources: overs remaining and wickets in hand. The DLS model defines a resource percentage table — for any combination of (overs left, wickets lost), it tells you what percentage of "run-scoring resources" a team has left. This table is built from a mathematical exponential decay function, fitted using historical match data. When rain interrupts a match, the system computes: resources lost = R(before interruption) — R(after interruption), and recalculates the target proportionally.

Why CP folks find this interesting: computing and looking up this resource table for every (overs, wickets) pair is conceptually identical to filling a 2D DP table — you're precomputing dp[overs][wickets] = resource% once, then doing O(1) lookups during a live match instead of recalculating from scratch.

** Cricket: Bowler & Over Allocation**

Ever wonder how a captain decides which bowler bowls which over, especially in the death overs (last 5 overs)? Analytics teams model this as a resource allocation / knapsack-style DP problem:

Each bowler has a "cost" (economy rate, current form, matchup against specific batters) for each over. The goal is to minimize expected runs conceded subject to constraints (max overs per bowler, no bowling two overs in a row). This is functionally similar to an assignment problem, solvable via DP or the Hungarian algorithm.

** Tennis & Chess: Seeding and Rankings**

Tournament seeding (making sure the top 2 players don't meet until the final) is essentially a graph/tree construction problem — building a balanced bracket is similar to building a balanced binary tree, ensuring higher seeds are spread across different subtrees.

Chess engines like Stockfish use:

Minimax with alpha-beta pruning (a DFS variant with pruning, exactly like CP's game-tree problems). Endgame tablebases — precomputed DP tables for all positions with very few pieces left, so the engine can look up the perfect move instantly instead of searching.

American Football: Fourth-Down Decisions

Analysts (like those behind ESPN's "Win Probability" models) use dynamic programming over game states — (down, yards to go, field position, time remaining, score difference) — to compute the expected win probability of every possible decision (punt, field goal, go for it). This is precisely a DP problem: each state's value depends on the values of future states, just like a classic "maximize expected value" DP.

** Basketball: Lineup and Rotation Optimization**

NBA teams use combinatorial optimization (often DP or integer programming) to decide which 5-player lineup to put on the court to maximize scoring efficiency and minimize opponent scoring, factoring in fatigue and matchups — essentially a constrained optimization problem over combinations, similar to subset-sum/knapsack style DP.

** Formula 1: Pit Stop Strategy**

Teams simulate thousands of race scenarios to decide when to pit and which tire compound to use. This is modeled as a DP/shortest-path problem: think of each lap and tire state as a node, and the "cost" as time lost. Finding the optimal pit strategy is like finding the shortest path in a graph where nodes are (lap, tire_type, tire_wear).

** Tournament Scheduling (Round-Robin Leagues)**

Ever notice how leagues like the Premier League or IPL create a schedule where every team plays every other team without conflicts? This uses the round-robin scheduling algorithm, a classic application of graph coloring / combinatorics, ensuring no team plays twice in one round and travel constraints are minimized.

The next time someone says "when will I ever use DP in real life?" — you now have cricket's DLS system, NFL's fourth-down calculator, and F1 pit strategy as answers. CP isn't just an academic exercise; it's the same toolkit that:

Decides fair cricket targets in the rain, Tells an NFL coach whether to punt or go for it, Helps an F1 team win a race by seconds.

This kind of "CP meets real life" angle tends to perform well because it appeals both to programmers and casual readers who just love sports — a great combination for shareability.

Chess engines are one of the best case studies in competitive programming for how search and heuristics combine to solve a problem that's too big to brute-force. A chess position has a branching factor of roughly 35, and a full game lasts ~40–80 moves per side — the game tree is astronomically larger than what any computer could ever fully explore. Everything an engine does is about making a huge search space tractable.

This post walks through the algorithms modern engines are built from, roughly in the order you'd add them if you were building one yourself: representation → move generation → search → evaluation → modern neural approaches.

1. Board Representation

Before you can search anything, you need a fast way to represent the board and generate moves.

8x8 array

The simplest approach — a char board[8][8]. Easy to reason about, but slow: move generation and attack detection require scanning rows/columns/diagonals cell by cell.

Bitboards

Almost every serious engine (Stockfish, Leela, etc.) uses bitboards: a uint64_t where each bit represents one of the 64 squares. You keep one bitboard per piece type per color (12 total), plus some derived ones (all white pieces, all black pieces, all occupied squares).

cppuint64_t whitePawns, whiteKnights, whiteBishops, whiteRooks, whiteQueens, whiteKing; uint64_t blackPawns, blackKnights, blackBishops, blackRooks, blackQueens, blackKing; uint64_t occupied = whitePawns | whiteKnights | ... | blackKing;

The magic is that most chess operations become bitwise operations, which are extremely fast:

Is e4 occupied? occupied & (1ULL << E4) All squares a knight on e4 attacks: a precomputed knightAttacks[E4] bitboard. Sliding piece attacks (rook/bishop/queen) use magic bitboards — a perfect-hash technique where you multiply the occupancy mask by a precomputed "magic number" to index directly into a lookup table of attack sets, computed once at startup.

Bitboards make things like "count all squares attacked by black" a single popcount instruction rather than a loop.

1. Move Generation

Move generation must be both fast and correct — a single missed pin or illegal castling rule causes silent bugs deep in search. Key components:

Pseudo-legal move generation: generate all moves ignoring whether your own king ends up in check. Legality filtering: after generating a pseudo-legal move, check if it leaves your king in check (often by checking if the king's square is attacked after making the move, or precomputing pins). Special cases: castling (rights, squares must be empty and not attacked), en passant, and promotion all need dedicated handling.

A common correctness-testing technique is Perft (performance test): count the total number of leaf nodes reachable at a fixed depth from the starting position, and compare against known correct values. If your engine's perft numbers don't match published values at depth 5–6, you have a move generation bug.

1. Search: Exploring the Game Tree

Minimax

The foundational algorithm. Assume both players play optimally: the side to move maximizes the evaluation, the opponent minimizes it.

cppint minimax(Position pos, int depth, bool maximizing) { if (depth == 0 || isGameOver(pos)) return evaluate(pos); if (maximizing) { int best = -INF; for (Move m : generateMoves(pos)) best = max(best, minimax(makeMove(pos, m), depth — 1, false)); return best; } else { int best = INF; for (Move m : generateMoves(pos)) best = min(best, minimax(makeMove(pos, m), depth — 1, true)); return best; } }

This is correct but explores every node — exponential in depth, with base ~35. Depth 4 is already ~1.5 million positions.

Alpha-Beta Pruning

Alpha-beta cuts off branches that can't possibly affect the final decision, without changing the result. It tracks:

alpha: the best score the maximizer can guarantee so far. beta: the best score the minimizer can guarantee so far.

If at any point alpha >= beta, the rest of that branch is irrelevant — prune it.

cppint alphaBeta(Position pos, int depth, int alpha, int beta, bool maximizing) { if (depth == 0) return evaluate(pos); if (maximizing) { int best = -INF; for (Move m : generateMoves(pos)) { best = max(best, alphaBeta(makeMove(pos, m), depth — 1, alpha, beta, false)); alpha = max(alpha, best); if (beta <= alpha) break; // beta cutoff } return best; } else { int best = INF; for (Move m : generateMoves(pos)) { best = min(best, alphaBeta(makeMove(pos, m), depth — 1, alpha, beta, true)); beta = min(beta, best); if (beta <= alpha) break; // alpha cutoff } return best; } }

With a perfect move ordering, alpha-beta reduces the effective branching factor from ~35 to ~√35 ≈ 6 — this is why move ordering (searching the best-looking moves first) is one of the most important optimizations in a chess engine, even more so than raw search speed.

Move Ordering Heuristics

Since alpha-beta's power depends entirely on searching good moves early, engines use several ordering tricks:

Hash move: the best move from a previous search of this position (from the transposition table), tried first. MVV-LVA (Most Valuable Victim – Least Valuable Attacker): try captures of high-value pieces with low-value pieces first (e.g., pawn takes queen before queen takes pawn). Killer moves: quiet moves that caused a beta cutoff at the same depth in a sibling branch — likely to be good again. History heuristic: a table tracking how often a move has historically caused cutoffs, used as a tiebreaker.

Transposition Tables

Different move orders can reach the same position (a "transposition"). A transposition table is a hash table (keyed by a Zobrist hash of the position) storing previously computed evaluations, so the engine never re-searches a position it has already solved to sufficient depth.

Zobrist hashing: assign a random 64-bit number to every (piece, square) combination, plus side-to-move and castling/en-passant state. The position's hash is the XOR of all applicable random numbers — updating it incrementally after a move is O(1).

Iterative Deepening

Rather than searching directly to depth N, the engine searches depth 1, then 2, then 3, ... up to N, using the previous iteration's best move to improve move ordering in the next. This seems wasteful, but because the tree grows exponentially, the cost of all previous shallow searches is small compared to the deepest one — and it gives you an "anytime" algorithm: you can stop at any point (e.g., when your clock runs low) and still have a usable answer.

Quiescence Search

If you stop searching at a fixed depth in the middle of a capture sequence, you get the horizon effect — e.g., you stop right after your queen captures a pawn, without seeing that the opponent recaptures your queen next move. Quiescence search extends the search at leaf nodes, but only considering "noisy" moves (captures, checks, promotions) until the position becomes "quiet," giving a much more stable evaluation.

Other Search Enhancements

Null move pruning: give the opponent a free extra move (skip your turn) and see if you're still winning — if so, the position is so good that you can prune deeply here, since real moves are only better. Late move reductions (LMR): search moves that are ordered late (i.e., probably not good) at reduced depth first, only doing a full-depth re-search if they unexpectedly look promising. Aspiration windows: instead of searching with a full [-INF, INF] window, guess a narrow window around the previous iteration's score — much faster if the guess is close, with a fallback to re-search wider if it fails. Principal Variation Search (PVS): assume the first move searched is best; search all other moves with a minimal [alpha, alpha+1] window just to prove they're worse, and only do a full re-search if one surprisingly beats alpha.

1. Evaluation Function

Search needs a way to score positions where it stops looking further. Classical (hand-crafted) evaluation combines many terms:

Material: sum of piece values (pawn = 1, knight/bishop ≈ 3, rook = 5, queen = 9 — with engines using finer-tuned values). Piece-square tables: bonus/penalty for each piece type based on which square it occupies (e.g., knights are worth more in the center than in the corner). Pawn structure: penalties for doubled, isolated, or backward pawns; bonuses for passed pawns. King safety: pawn shield presence, open files near the king, attacker counts. Mobility: number of legal moves/attacked squares available to each side. Piece coordination: bishop pairs, rooks on open files, control of key outposts.

Classical engines (like older Stockfish versions) hand-tuned these weights, often using automated tuning against large game databases.

NNUE (Efficiently Updatable Neural Network)

Modern top engines (Stockfish since 2020, and others) replaced hand-crafted evaluation with NNUE: a small neural network that takes the position (encoded as sparse features — essentially "which piece is on which square, relative to each king") and outputs an evaluation score.

The "efficiently updatable" part is the key engineering trick: because only a couple of pieces change per move, the network's first-layer activations can be updated incrementally rather than recomputed from scratch, making it fast enough to call millions of times per second on a CPU — no GPU required. This is why Stockfish, a pure alpha-beta engine, could adopt a neural evaluation without losing its search speed advantage.

1. The Other Paradigm: Monte Carlo Tree Search (MCTS)

AlphaZero and its successors (Leela Chess Zero) use a fundamentally different search algorithm: MCTS, guided by a neural network trained through self-play reinforcement learning.

MCTS works by repeating four steps many times per move:

Selection: walk down the tree from the root, picking children according to a formula (like PUCT) that balances exploiting known-good moves and exploring under-tried ones. Expansion: once you reach a node not yet expanded, add its children. Evaluation: instead of a random rollout to the end of the game (as in classic MCTS for other games), AlphaZero-style engines ask a neural network directly for a position evaluation and a policy (probability distribution over promising moves). Backpropagation: propagate that evaluation back up the tree, updating visit counts and average values along the path.

Unlike alpha-beta's fixed-depth, node-by-node exhaustive exploration, MCTS spends its computational budget adaptively — exploring promising lines much more deeply than unpromising ones, guided entirely by the network's judgment.

This is genuinely a different philosophy: alpha-beta engines like Stockfish search narrowly and deep with strong pruning; MCTS engines like Leela search broadly, letting the policy network suggest where to look and the value network judge what it finds.

1. Endgame Tablebases & Opening Books

Two more pieces round out a complete engine:

Opening books: precomputed databases of strong opening moves (from grandmaster games or engine analysis), used instead of searching from scratch in well-known positions. Endgame tablebases (e.g., Syzygy tablebases): for positions with few pieces left (commonly ≤7), the exact outcome (win/loss/draw and moves-to-mate) has been computed exhaustively via retrograde analysis — working backward from checkmate positions. When a search reaches a tablebase position, the engine gets a perfect answer instantly instead of searching further.

Putting It All Together

A modern classical engine's move loop looks roughly like:

for depth = 1 to maxDepth (iterative deepening): run alpha-beta search with: — transposition table lookups/stores — move ordering (hash move, MVV-LVA, killers, history) — null move pruning, LMR, aspiration windows — quiescence search at leaf nodes — NNUE evaluation at leaves — tablebase probes near the endgame if time is up: stop and return best move found so far

Neural MCTS engines swap the entire alpha-beta search out for the four-step MCTS loop, but still rely on the same board representation and move generation machinery underneath.

If you want a rewarding project, building a basic engine that does bitboards + alpha-beta + a simple material/PST evaluation is very achievable, and you can incrementally bolt on transposition tables, quiescence search, and eventually NNUE as separate milestones — each one is individually a fun and self-contained problem to implement and test.

If there's interest, I can follow up with a deeper dive into any single piece here — magic bitboards, NNUE architecture, or MCTS/PUCT in detail.