The Verification Venue · pointed at a game nobody has proved finishes
The Game That May Never End
Beggar-my-neighbour looks like a children's pastime that obviously ends. Nobody has proved that it does, and nobody has found a deal that doesn't. This page states the rules exactly, searches about a hundred million deals across your processor's cores, and shows you the longest deal it finds, replayable move for move from eight bytes.
Every account of this game describes it as harmless. Every implementation anyone plays with runs a few thousand deals and sees nothing longer than a few hundred tricks, and concludes the game always ends. That conclusion is not known to be true. It is not known to be false either. The gap here is not between a rough answer and a precise one; it is between a belief and its actual status. Press Deal below and watch a single seeded deal play itself. Then launch the search, and watch the record climb past anything a kitchen table would ever see.
The rules, stated in full (the claim is void without them)
- Deck and penalties
- One standard 52-card deck. Ace pays 4, King pays 3, Queen pays 2, Jack pays 1; every other rank demands nothing.
- The deal
- A seeded shuffle of all 52 cards, dealt alternately: even positions of the shuffled array to player 0, odd positions to player 1, top card first. Player 0 leads the first trick.
- A trick
- The players strictly alternate playing their top card onto a central pile, except that while a payment obligation stands only the payer plays. When a penalty card of value p appears, the other player owes p cards, and the new card's value replaces any remaining obligation. Each harmless card played while an obligation stands reduces it by one.
- Collecting
- When the obligation is met, the player who laid the last penalty card takes the whole pile, appends it to the bottom of their hand in the order the cards were played, and leads the next trick.
- Losing
- A player who must play a card (leading, following, or paying) and has none loses immediately; the pile is not collected. The game length is the number of resolved tricks, counting the last one.
- The cap
- The search stops any deal at 100,000 tricks. A deal that hit the cap is not a deal that ended; it is counted separately and excluded from the record.
The instrument: one deal, move by move
Trick
0
Card plays
0
Status
press Deal
Seed (8 bytes)
—
Long deals unfold slowly at first and then snowball, as won piles recycle back into play. Step manually if you want to read every play.
The search: your cores against the seed space
The full run partitions 100,663,296 seeds into 256 chunks of 393,216 deals each, farmed out to one Web Worker per core. Every deal is played to completion or to the 100,000-trick cap. The engine counts the card plays it actually executes; nothing below is an estimate.
Deals searched
0
Card plays (counted)
0
Elapsed
—
Workers
—
Longest finished deal
—
Hit the cap / violations
0 / 0
a capped deal is not a finished deal
Nothing here is displayed until the two implementations agree on the battery below.
The check: why a stranger should believe the big number
At full size there is no second implementation to compare against, so the page carries three answers and runs all of them in front of you. First, a slow, obvious second implementation of the same rules in plain JavaScript, compared against the compiled engine on small instances. Second, checks that reach full size. Third, a control that exists to fail.
1 · Two implementations, one contract
| battery row | engine fingerprint | reference fingerprint | |
|---|---|---|---|
| running… | |||
The page refuses to display a headline result unless every row agrees.
2 · The control: watch the check go red on purpose
This button breaks the reference (it removes the Ace's penalty, which changes nearly every deal) and re-runs the battery. The check is supposed to catch it. A control that comes back green means the check itself is decorative.
3 · Planted objects: the engine must measure a known deal
The input data is doctored, never the result list: the unmodified engine is handed a stated deal through its state buffer and must measure it. A search for long games needs to prove it can measure a short one, and a page about non-termination needs a deal that provably never ends. These plants earn their keep: they once caught a turn-order bug that both implementations shared, which the battery alone could never have seen.
4 · Full size: a different decomposition, and the invariants
After the search, the same seed set is searched again with a different chunk count (128 chunks of 786,432 instead of 256 of 393,216). Because a deal is a deterministic function of its seed, the histograms and the record must be identical; any boundary error would show. The engine also checks, on every deal, that cards are conserved, that the deck is a permutation, and that a finished deal ends with one player holding everything. The violation counter must read zero.
5 · The record itself, replayed by the slow implementation
6 · The binary you are running
The reproducible-build check (recompile the committed C and demand identical bytes) runs offline, not in your browser: node research/the-game-that-may-never-end/verify-the-game-that-may-never-end.mjs.
What none of this rules out. Two decompositions agreeing rules out a chunk-boundary error and very little else; the battery catches translation mistakes but not a misunderstanding shared by both implementations; and no finite search says anything certain about whether every deal ends. The record is a property of the search, not of the game.
Layer two: the shape of the search, and pushing the record
Two pictures. The first is the distribution of finished game lengths over every deal searched, bucketed by powers of two. It is long-tailed, with no visible right edge: the record sits wherever the search happens to have looked, which is exactly why the record is a record of the search rather than a property of the game.
The second picture is the difference between looking and searching. Uniform sampling pulls random seeds. Hill climbing takes the current record deal, swaps two cards among the first 26 (perturbing the opening), re-measures the mutant with the same engine, and keeps improvements. Both curves are plotted against deals examined.
Hill climbing perturbs decks, not seeds, so its record is a 52-card deck rather than an eight-byte seed. The page says so rather than pretending otherwise, and the button above replays its best deck in the instrument.
The cost, measured not estimated
Operations performed
—
counted by the engine, one per card play
Wall time
—
Workers used
—
vs main-thread JavaScript
—
The speed factor is measured on a small slice of the job and extrapolated; the slice fraction is printed next to it, because an extrapolation printed without its basis is a boast, not a measurement.
What's exact here, what's a model, and what's open
Exactly true. Every trick count is an exact integer produced by simulating the stated rules. The deal generator is specified step by step (splitmix64 driving Fisher-Yates), so any implementation following it produces the same deal from the same seed. The two planted deals are proved by hand: one ends in exactly five tricks, the other cycles with period four under rule M and can never finish, a fact the offline verifier witnesses by comparing exact ordered states.
Idealised. Seeded pseudo-random deals are not uniform random shuffles in any statistical sense; they are one deterministic family, and conclusions drawn from them are conclusions about that family. The 100,000-trick cap truncates the tail: a deal that hits it is counted, but its true length is unknown. Hill climbing explores deck-space near the record, not seed-space, so its records are not seed-reproducible.
Open, and stated as open. Whether every deal of beggar-my-neighbour terminates is, under these rules, an open problem. This page does not settle it and does not pretend to. It exhibits what a real search finds, shows the checks that make those findings believable, and leaves the question exactly as open as it was.