Introduction

Morpion Solitaire is a fast player and solver for the pencil-and-paper puzzle of the same name: a desktop and Web GUI plus a headless CLI, built for hunting records (the 5T world record is 178).

This book covers three things:

• Using it — installing, playing in the GUI, and the command line.
• The MSR format — a self-describing record format (overview, specification) meant to supersede the older Pentasol text format, with a reusable reference library.
• Internals — the architecture, the search algorithms, and the fixed-grid board.

Play online: https://morpion-solitaire.io · Source: https://github.com/sjourdois/morpion-solitaire

The project is a Cargo workspace of three crates — the GPL-3.0-or-later application and two permissively licensed libraries (the MSR format and a record corpus). See Architecture.

Rules and variants

Morpion Solitaire is played on a square grid, starting from a fixed cross of points (36 points for the 5-in-a-line game).

A move:

1. places one new point on a grid intersection, and
2. draws a straight line — horizontal, vertical, or diagonal — through n consecutive points, including the new one. All n − 1 other points of the line must already exist.

The score is the number of moves; play continues until no legal move remains. The goal is the longest possible game.

The touch rule

Two lines in the same direction that lie on the same track may not overlap by more than the allowed amount:

• Touching (T): parallel collinear lines may share one endpoint.
• Disjoint (D): parallel collinear lines must be strictly separate.

(Lines in different directions, or crossing, never conflict by this rule.)

Variants

All four are supported by the application and the MSR format. The exact coordinate frame, the initial cross, and the touch rule as a formula are defined normatively in the MSR specification.

Install

From crates.io

cargo install morpion-solitaire   # the GUI + CLI

From source (native)

Use stable as your default toolchain:

git clone https://github.com/sjourdois/morpion-solitaire
cd morpion-solitaire
cargo run --release            # launches the GUI
cargo run --release -- --help  # the CLI

The web build

The browser build is the only part that needs nightly — it rebuilds std with the WebAssembly atomics feature (-Z build-std) for shared-memory threads. The wasm crate pins nightly and that config itself, so just build from its directory:

cd crates/morpion-solitaire-wasm
trunk serve   # or: trunk build --release

(nightly, rust-src and the wasm target auto-install on first build.)

Threaded WebAssembly needs the page to be cross-origin isolated; the bundled coi-serviceworker.js arranges this on static hosts such as GitHub Pages.

A hosted build is at https://morpion-solitaire.io.

The desktop & web GUI

The GUI (built with egui) runs natively and in the browser. It has two modes:

• Manual — play moves by hand; undo/redo; load a record or paste a game.
• Search — run a solver (see algorithms), watch its best game live, and pause, checkpoint, or stop it.

Playing

• Pick a variant (5T/5D/4T/4D).

• Legal moves are highlighted; click one to play it. When several lines complete at the same point, a small picker toggle on the board chooses how you pick between them:

  • Aim — aim with the cursor and use the scroll wheel to cycle through all collinear candidates (up to five); a click plays.
  • Click — click the point to lock it (the dot turns orange), move the cursor to aim the line among the candidates, then click again to play it (Esc cancels).

  The faint stubs that distinguish touching lines are shown only in the Touching variants.

• You can hide the legal-move markers (they then appear only on hover).

• View controls: rotate (R) / flip (F) the board, recenter (G), zoom with Ctrl/Cmd/Shift + wheel, draw move arrows, number the moves, and a light/dark theme that also restyles the board.

Searching

• Start from an empty cross, a seeded cross, or the loaded position.
• A bundled record game can be loaded from the dropdown (filtered to the current variant) and also used as an NRPA warm-start seed.
• The running search shows a live best-game preview and a node-rate readout; it can be paused, checkpointed and resumed (native).
• For 4D/4T the systematic search can exhaust the whole tree; when it does, a dialog reports the elapsed time and that the best score is the proven optimum.
• Beating the 178 world record (5T) triggers an audible alarm.

Records & metadata

• A collapsible Metadata panel edits the editorial fields (author, source, transcribed-by, description, tags) that are written into your exports and filled in from imported records.
• The first time you export without an author, a one-time prompt asks for your name and can remember it for next time.

Loading & saving

• Import: paste a game (MSR or Pentasol), or drag and drop a .msr/.json/.psol/.png/.svg file onto the window. A PNG or SVG with no embedded record is reported plainly rather than failing.
• Export / copy: MSR, JSON, Pentasol, SVG or PNG. The PNG and SVG embed the record, so the picture is itself a save. Copying a PNG to the clipboard warns that the clipboard image can’t carry the record (use the file export); copying SVG keeps it.
• Keyboard: Ctrl/Cmd + Z/R undo/redo, N new game, S export, C copy, V import. The ? button lists every shortcut.

Persisted between sessions (natively and in the browser): the theme, the line-picker mode, the view toggles (arrows, numbers, legal-move markers), the search configuration (variant, algorithm, NRPA level, start point, export format), the “don’t show the rules” choice, and your default author name.

The command line

With no subcommand, morpion-solitaire launches the GUI. The subcommands below run headless. Use --help on any of them for the full options.

morpion-solitaire --help
morpion-solitaire <command> --help

A global --variant 5T|5D|4T|4D (default 5T) applies where it isn’t read from a file.

search

Run a solver and write the best game found.

morpion-solitaire search --algo nrpa --time 30s -o best.msr

Highlights: --algo nrpa|systematic|perturbation|beam, --level (NRPA), stopping criteria --time/--target-score/--max-nodes, seeding with --from/--warm, --threads, --seed, periodic --checkpoint-interval, --resume, and provenance (--description/--author/--tag). Ctrl-C stops and saves. Output is always an MSR record.

replay

Replay a saved game: it re-derives the game move by move (so replaying is verifying — an illegal game errors with a non-zero exit), then prints its metadata, board and a one-line verdict.

morpion-solitaire replay game.msr            # metadata + board + verdict (--numbers to label)
morpion-solitaire replay game.msr -q         # just the verdict (scriptable; exit code = legality)

convert

Render or convert a game to any format with --to ascii|msr|json|pentasol|svg|png (default ascii). Text formats go to stdout or -o; PNG is binary and requires -o. The SVG and PNG embed the full MSR record (the PNG in a tEXt chunk, the SVG in a <metadata> element), so the picture is itself a save you can reopen or drop onto the app.

morpion-solitaire convert game.msr                       # ASCII board (--numbers to label)
morpion-solitaire convert game.msr --to png -o game.png  # raster image + embedded record
morpion-solitaire convert game.msr --to svg -o game.svg  # vector image + embedded record

# Format conversions
morpion-solitaire convert game.psol --variant 5T --to msr -o game.msr  # Pentasol → MSR
morpion-solitaire convert game.msr  --to json -o game.json             # MSR → JSON (readable)
morpion-solitaire convert game.json --to msr  -o game.msr              # JSON → MSR (compact)
morpion-solitaire convert game.msr  --to pentasol -o game.psol         # MSR → Pentasol (5T/5D)

MS1: ↔ JSON is lossless. Pentasol carries neither the variant nor any metadata, so a round-trip through it drops that information.

records · bench

morpion-solitaire records                  # list saved records by category
morpion-solitaire bench --algo nrpa --time 10s   # nodes/second

The MSR format — overview

MSR (Morpion Solitaire Record) is a small, self-describing interchange format for games: the move list plus optional provenance, in either a compact MS1: envelope or plain JSON. It is designed to supersede the older Pentasol text format.

Why MSR

A record carries who/what/when produced a game (producer, author, method, seed, timestamps, search effort, tags) and a few derived facts, so a file is meaningful on its own.

Reusable library

The format is implemented by the standalone morpion-solitaire-record crate (imported as msr) — a reader, writer and validator with no dependency on any solver, so any tool can adopt it:

#![allow(unused)]
fn main() {
let record = msr::decode(text)?;   // MS1: envelope or raw JSON
msr::validate(&record)?;           // is it a legal game?
let compact = msr::encode(&record)?;
}

The normative definition is the specification and the JSON Schema. A Pentasol bridge is provided for migration.

MSR — Morpion Solitaire Record format, version 0.1

Status: draft · Format version: 0.1 · Media type: application/vnd.morpion-solitaire.record+json · File extension: .msr

Each version of this specification lives at a stable, versioned URL (…/spec/0.1/), so published links never break when a later version appears. 0.1 is the current draft; 1.0 will be the first stable release.

MSR is a self-describing interchange format for Morpion Solitaire games: an ordered list of moves plus optional provenance metadata. It is designed to replace the older Pentasol text format with a lossless, variant-complete, metadata-carrying, and independently verifiable record.

The reference implementation is the morpion-solitaire-record crate (imported as msr).

1. Conformance

The key words MUST, MUST NOT, SHOULD, SHOULD NOT and MAY are to be interpreted as in RFC 2119.

A reader is conformant if it accepts every valid document defined here. A writer is conformant if every document it emits is valid here. A validator additionally checks game legality (§7).

2. The game (informative)

Morpion Solitaire starts from a fixed cross of points on a grid. A move places one new point and draws a straight line of n consecutive collinear points (horizontally, vertically or diagonally) through it; all other n − 1 points of the line must already exist. A touch rule constrains how new lines may overlap earlier parallel lines. The score is the number of moves. Variants differ by n (4 or 5) and by the touch rule (touching or disjoint). The 5T world record is 178 (Rosin, 2011); see the project bibliography.

3. Coordinate system (normative)

Points are integer (x, y) pairs in a single, translation-fixed frame:

• The initial cross occupies the grid 0..=w on both axes, where w = 2n−1 for odd n and w = 2n−2 for even n — so 0..=9 (the classic 36-point cross) for n = 5, and 0..=6 for n = 4. Its members are defined by §3.1.
• Moves MAY use any integer coordinates, including negative ones, as a game grows outward from the cross.

The frame is independent of any grid size: it is an unbounded integer lattice. (Implementations backed by a fixed grid translate this frame by a constant offset; that offset is an implementation detail and is never stored.)

3.1 Initial cross (normative)

For line length n, let arm = n−1, and w = 2n−1 for odd n or w = 2n−2 for even n. Then a = (w − arm + 1) / 2 and b = a + arm − 1, so the arm band [a, b] is centred (a + b = w) and the figure is D4-symmetric — this centring is why even n uses the narrower w = 2n−2 grid. A grid point (x, y) with 0 ≤ x, y ≤ w belongs to the cross iff:

((y = 0 or y = w) and a ≤ x ≤ b)        # top / bottom caps
or ((x = 0 or x = w) and a ≤ y ≤ b)     # left / right caps
or ((x = a or x = b) and (y ≤ a or y ≥ b))   # vertical arm borders
or ((y = a or y = b) and (x ≤ a or x ≥ b))   # horizontal arm borders

This yields the classic 36-point Greek cross for n = 5 (a = 3, b = 6, w = 9) and a centred 24-point cross for n = 4 (a = 2, b = 4, w = 6).

4. Variants (normative)

A variant is encoded as a two-character code, digit first:

Readers MUST accept the canonical code. Readers MAY also accept the reversed spelling (T5) and any letter case; writers MUST emit the canonical digit-first uppercase form.

5. Directions and lines (normative)

A direction has a unit step δ = (dx, dy), oriented so the origin is the smaller-coordinate end:

A move stores the new point (x, y), the direction, and pos — the index of the new point within the line, in 0..n. The line’s origin is therefore (x, y) − pos·δ, and its points are origin + i·δ for i ∈ 0..n.

6. The record (normative)

A record is a JSON object. Field names and value encodings are normative.

¹ A reader MAY default a missing version to "0.1", and SHOULD accept a bare integer (e.g. 1) as its decimal string for backward compatibility; writers MUST emit it as a major.minor string.

Optional fields SHOULD be omitted when empty rather than written as null. Derived fields (score, available_moves, terminal, bbox) SHOULD be computed from the moves by the writer; a reader MUST NOT trust them over the moves themselves and SHOULD recompute when it needs them.

The three provenance fields answer distinct questions: author — who achieved the game; source — where the game comes from; transcribed_by — who put it into MSR form. A human/hand-played/transcribed record carries no solver block.

6.1 The move object (normative)

6.2 The solver object (normative)

Present only when an automated search produced the game. Every field is optional; a writer SHOULD omit the whole object rather than emit it empty.

7. Legality (normative for validators)

A record is legal iff replaying its moves from the initial cross (§3.1) satisfies, for every move with line points P₀…P₍ₙ₋₁₎ and new point N = (x, y) at index pos:

1. 0 ≤ pos < n;
2. N is not currently occupied;
3. every Pᵢ ≠ N is currently occupied;
4. the new line does not break the touch rule (§7.1).

On success the new point becomes occupied and the line is recorded.

7.1 Touch rule (normative)

Two lines conflict only if collinear — same direction and same track:

(track/position are computed from each line’s origin.) Two same-direction lines on the same track conflict iff |position₁ − position₂| ≤ forbid, where forbid = n − 1 − max_overlap (§4). Equivalently: parallel collinear lines may overlap by at most max_overlap points (1 for touching, 0 for disjoint), and a move is illegal if its line conflicts with any earlier line.

8. Encodings (normative)

The same record has two interchangeable serialisations:

• JSON form. The record object as UTF-8 JSON (pretty or compact). This is the readable, diff-friendly form.
• Compact form (MS1:). The string MS1: followed by the unpadded URL-safe Base64 (RFC 4648 §5, no =) of the DEFLATE (RFC 1951) compression of the UTF-8 JSON bytes.

A reader MUST accept both. It detects the compact form by the MS1: prefix (after trimming surrounding whitespace); otherwise it parses JSON. A writer MAY emit either; .msr files SHOULD use the compact form.

9. Versioning & forward compatibility (normative)

• The version field denotes the format version (major.minor); this document specifies "0.1". Each version is published at its own stable URL (…/spec/<version>/).
• Readers MUST ignore unknown object fields (forward compatibility).
• A later minor revision (same major) MUST NOT repurpose an existing field nor change an encoding; it MAY add optional fields. Incompatible changes bump the major version and the MS1 envelope tag (MS2:…).

10. Migration from Pentasol (informative)

Pentasol encodes 5T/5D moves as (col,row)dir centerdist lines, where centerdist = pos − ⌊n/2⌋. A bridge that maps Pentasol moves to §6.1 moves (and back) is provided by the project’s morpion-solitaire tool, so existing Pentasol corpora convert losslessly into MSR (gaining metadata and the other two variants).

11. Examples

Minimal JSON record (empty game):

{ "version": "0.1", "variant": "5T", "score": 0, "moves": [] }

A one-move record, compact form:

MS1:<base64url of deflate of the JSON>

12. Conformance test vectors

The reference implementation ships test vectors, including a real 178-move 5T world-record file that MUST decode and validate. Implementations SHOULD check against the same corpus.

References

• RFC 2119 Key words for use in RFCs.
• RFC 1951 DEFLATE Compressed Data Format.
• RFC 4648 The Base16, Base32, and Base64 Data Encodings.
• Project bibliography: docs/BIBLIOGRAPHY.md.

JSON Schema

The JSON form of an MSR record is described by this JSON Schema (docs/spec/0.1/msr.schema.json). The compact MS1: envelope decompresses to the same JSON.

{
  "$schema": "https://json-schema.org/draft/2020-12/schema",
  "$id": "https://morpion-solitaire.io/spec/0.1/msr.schema.json",
  "title": "MSR 0.1 — Morpion Solitaire Record",
  "description": "Self-describing record for a Morpion Solitaire game. See docs/spec/0.1/msr.md. This schema validates the JSON form (the compact MS1: envelope decompresses to the same JSON).",
  "type": "object",
  "required": ["variant", "score", "moves"],
  "additionalProperties": true,
  "properties": {
    "version": {
      "description": "Format version, major.minor. \"0.1\" for this spec (a bare integer is accepted for backward compatibility).",
      "type": ["string", "integer"],
      "default": "0.1"
    },
    "variant": {
      "description": "Variant code, digit first.",
      "type": "string",
      "enum": ["4T", "4D", "5T", "5D"]
    },
    "score": {
      "description": "Number of moves (equals moves.length).",
      "type": "integer",
      "minimum": 0
    },
    "moves": {
      "description": "Moves in play order.",
      "type": "array",
      "items": { "$ref": "#/$defs/move" }
    },
    "producer": {
      "description": "Program that wrote the file, e.g. \"morpion-solitaire/0.1.0\".",
      "type": "string"
    },
    "available_moves": {
      "description": "Legal moves available at the final position (0 means terminal).",
      "type": "integer",
      "minimum": 0
    },
    "terminal": {
      "description": "Whether the final position is terminal.",
      "type": "boolean"
    },
    "bbox": {
      "description": "Bounding box of all placed points: [min_x, min_y, max_x, max_y].",
      "type": "array",
      "items": { "type": "integer" },
      "minItems": 4,
      "maxItems": 4
    },
    "saved_at": {
      "description": "ISO-8601 UTC save timestamp.",
      "type": "string"
    },
    "description": { "type": "string" },
    "author": {
      "description": "Who set the record (person/team/handle).",
      "type": "string"
    },
    "source": {
      "description": "Where the game originates: a URL or citation (e.g. the original record site or an imported Pentasol file).",
      "type": "string"
    },
    "transcribed_by": {
      "description": "Who transcribed the game into MSR form (curator/project), distinct from source and author.",
      "type": "string"
    },
    "tags": {
      "description": "Free-form labels.",
      "type": "array",
      "items": { "type": "string" }
    },
    "solver": {
      "description": "Automated-search provenance; present only for solver-produced games.",
      "type": "object",
      "additionalProperties": true,
      "properties": {
        "tool": {
          "description": "The search tool/engine that produced the game (name or brand, e.g. \"morpion-solitaire.io\"). Distinct from the file-level producer.",
          "type": "string"
        },
        "method": {
          "description": "Algorithm and parameters, e.g. \"nrpa L3\". Does not restate the seed.",
          "type": "string"
        },
        "seed": {
          "description": "RNG seed, for reproducibility.",
          "type": "integer",
          "minimum": 0
        },
        "nodes_explored": {
          "description": "Search effort in nodes.",
          "type": "integer",
          "minimum": 0
        },
        "elapsed_secs": {
          "description": "Wall-clock seconds of the producing search.",
          "type": "number",
          "minimum": 0
        }
      }
    }
  },
  "$defs": {
    "move": {
      "type": "object",
      "required": ["x", "y", "dir", "pos"],
      "additionalProperties": false,
      "properties": {
        "x": { "description": "X of the new point.", "type": "integer" },
        "y": { "description": "Y of the new point.", "type": "integer" },
        "dir": {
          "description": "Direction code.",
          "type": "string",
          "enum": ["H", "V", "DP", "DN"]
        },
        "pos": {
          "description": "Index of the new point within the line (0..line_len).",
          "type": "integer",
          "minimum": 0,
          "maximum": 4
        }
      }
    }
  }
}

Migrating from Pentasol

Pentasol is the community text format for 5T and 5D games. Each line is (col,row)dir centerdist, where centerdist = pos − ⌊n/2⌋ is the signed offset of the new point from the centre of its line.

The application reads and writes Pentasol, so existing corpora convert losslessly into MSR — gaining provenance metadata and the other two variants:

morpion-solitaire convert game.psol --variant 5T --to msr -o game.msr
morpion-solitaire convert game.msr --to pentasol            # and back

Because Pentasol does not record the variant, you supply it with --variant when reading.

See the specification for the exact mapping.

Architecture

The project is a Cargo virtual workspace under crates/:

Dependencies flow one way — the app depends on the two libraries, which depend on neither each other nor the app:

morpion-solitaire-wasm ─▶ morpion-solitaire ─┬─▶ morpion-solitaire-record (msr)
                                             └─▶ morpion-solitaire-records ─▶ (msr, dev-only)

The permissive libraries are GPLv3-compatible, so the GPL application may depend on them. Keeping the format crate free of the solver’s GameState/bitboard is deliberate: any other tool can read, write and validate MSR records with it standalone.

Inside the application

• game — the core model: a bitboard Board (one Row word per grid row, O(1) contains; see the fixed-grid board), Line/Move, the GameState and rules, and io — conversion to/from msr::Record, the search checkpoint codec (MSC1:), the Pentasol bridge, and the PNG tEXt / SVG <metadata> record embedding shared by the GUI and cli show.
• search — the solvers (see algorithms): NRPA and the perturbation search, the exhaustive systematic search, beam, plus the shared SearchState (atomics for best score / nodes / running / paused / exhausted), symmetry, bounds, and checkpointing.
• render — game → SVG, and via resvg/tiny-skia → PNG; the embed/extract helpers are pure and cross-platform, so the web build can read an embedded record even though it can’t rasterise one.
• ui — the egui board view and side-panel controls (painter-drawn icons, themeable light/dark board).
• i18n — Fluent catalogues (8 locales); app and cli both localise.
• cli — the headless command line (native only).

How a search runs

The solver runs on a background thread (or a rayon pool for the systematic search) and communicates only through the lock-free SearchState. The UI/CLI polls it each tick: it reads the best sequence to show a live preview, the node rate, and the exhausted flag (which, for the systematic search, means the best score is the proven optimum). The move history (Vec<Move>, absolute coordinates) is the single source of truth — the bitboard is a reconstructible projection — so a game survives a grid resize and a search can be checkpointed and resumed.

Search algorithms

The search space is astronomical — a 5T game can run past 170 moves with a wide branching factor — so every solver but one is heuristic. The exception is the systematic search, which is exact but only tractable for the small variants. All of them work on the same GameState (a bitboard position plus the move history) and stream their best game live to the GUI. Full citations are in the bibliography; the GUI’s algorithm selector lists them in the order below, from the exact baseline to the most sophisticated heuristic.

Systematic search

Exhaustive backtracking that is exact and stateless: it visits every reachable position and keeps the best, with memory bounded only by the DFS stack, so a run can continue indefinitely without growing. There is deliberately no transposition table — instead two exact, memory-free layers guarantee each position is reached exactly once:

1. A trace normal form. Moves are kept in a canonical order and a move is explored only if it could not have been played earlier in the sequence. This removes all move-order transpositions with no stored visited-set — the prune is a local test on the candidate move against the trace so far.
2. Structural D4-symmetry pruning. Only one representative per orbit of the position’s current symmetry stabiliser is expanded. The stabiliser starts as the full dihedral group of the cross and collapses to the identity after the first symmetry-breaking move, so the saving is largest near the root where the tree is widest.

A branch-and-bound layer then prunes any branch whose admissible upper bound cannot beat the incumbent; the theoretical length limits [Demaine2006] are the backdrop for those bounds. For 4D and 4T the whole tree can be drained, which proves the optimum (35 and 62 respectively): when the frontier empties on its own, SearchState::exhausted is set and the app reports the elapsed time and that the score is optimal. For 5T/5D the space is far too large to exhaust, so the systematic search confirms small results rather than hunting records.

Beam search

A bounded breadth-first search: at each depth keep only the best width states, expand them all, and repeat. States are scored by their current score plus a weight on the number of remaining legal moves — a crude potential that favours positions which keep their options open. It is deterministic, memory-bounded by the beam width, and never backtracks, which makes it a fast, predictable baseline rather than a record-setter: too narrow a beam commits to a dead end early, while a wide beam costs memory without the policy learning that NRPA brings. The design follows the beam / parallel-NRPA line of work [Cazenave2020].

NRPA

Nested Rollout Policy Adaptation [Rosin2011] — which refines Nested Monte-Carlo Search [Cazenave2009] and generalises as GNRPA [Edelkamp2016] — is the workhorse for the large variants. It learns a policy: a table mapping a symmetry-invariant move code to a real weight. Sampling and learning are nested by level:

• A level-0 playout plays a full game, at each step sampling a legal move with probability softmax(policy) over the candidates’ codes.
• A level-N run performs a fixed number of level-(N−1) runs; after each it adapts the policy toward the moves of the best game seen so far (a gradient step that raises the chosen codes and lowers their alternatives), then recurses.

Because the code is symmetry-invariant, a lesson learned in one orientation transfers to all eight, sharply shrinking what must be learned. Independent island restarts — one per core — supply diversity and are merged by keeping the global best. A warm start can pre-train the policy toward a known strong game (load a bundled record from the dropdown, or pass --warm game.msr to the CLI) so the search begins in a good basin instead of from scratch.

The nesting level trades breadth for depth: level 3 is the responsive default; level 4 and above search far more deeply per run but only pay off over multi-hour sessions.

The adapted policy logits are clamped to a small bound (a Stabilized-NRPA variant, on by default; NRPA_CLAMP=0 disables) so the policy cannot run away and over-commit. This both raises the typical score and cuts its run-to-run variance, and the gain grows with the search budget rather than capping (5T level-4 mean-best went from ~95 unclamped to ~112 clamped in tuning).

Perturbation (large-neighbourhood) search

A destroy-and-repair large-neighbourhood search [Shaw1998, Ropke2006] built on top of NRPA — the solver’s main record-climber. Instead of a single incumbent it keeps a quality-diversity archive [Mouret2015] of high-scoring but structurally diverse games. Each round it:

1. picks a game from the archive,
2. destroys a suffix of it (drops the last moves), and
3. repairs the remainder with a short, warm NRPA search seeded by what was kept.

Improved or novel games re-enter the archive. Diversity is the whole point: a plain hill-climb collapses onto one local optimum, whereas the archive preserves promising-but-different lines so the search can escape and recombine them. It runs its inner NRPA searches across OS threads, so it is native-only — the web build omits it (browsers can’t spawn the same thread pool).

Record-hunting workflow

A practical loop: pick the variant; optionally warm-start from the best bundled record; run NRPA across all cores, or perturbation for a sustained climb; and let the app auto-save every position that beats the best already stored for that algorithm category. Beating the 5T world record (178) raises an audible alarm. Indicative reach per variant is listed in the project README.

Fixed-grid board & overflow handling

Design (fixed grid, resizable by one type alias)

Board occupancy is a fixed GRID×GRID bitset, one Row word per grid row (src/game/board.rs). The grid side length is GRID = Row::BITS, so resizing the grid is a one-line change to a single type alias:

#![allow(unused)]
fn main() {
pub type Row = u128; // 128×128 grid; `u64` → 64×64
}

Everything else (GRID, OFFSET, the line-index tracks, the SWAR move generator’s masks) derives from Row, so nothing else changes. There is no primitive u256; going beyond 128 needs a Row newtype over [u128; k] implementing the handful of bit ops used here (Shl, Shr, BitAnd, BitOr, Not, trailing_zeros, == 0).

A point at internal coordinate (x, y) maps to grid index (x + OFFSET, y + OFFSET), with OFFSET = GRID/2 − 5 centring the initial cross. Board::contains is then an O(1) bit test — no hashing — the single biggest throughput lever for the systematic search.

A margin keeps queries in bounds without a per-query check: no cell may be placed within MARGIN = n − 1 = 4 cells of the edge. Since every window inspected by legal_moves is anchored on an occupied (interior) cell and extends at most n − 1 cells past it, every contains/row query lands in [0, GRID). The margin check is a single comparison in Board::insert, run once per placed move — negligible next to move generation.

Overflow handling (graceful: detect → save → alert, never panic)

With GRID = 128 the interior is ~120 cells per side and a record 5T game (≈178 moves) spans only ~40, so overflow cannot fire for any realistic game on the 128 grid; the realistic candidate is the 64 grid. When it does happen, the engine never crashes:

1. Detection (free). Board::insert is the seam. If a placement falls in the margin it sets the global pub static GRID_OVERFLOW: AtomicBool and returns false without writing — one comparison, no panic, no allocation.
2. Propagation. GameState::apply returns the bool; the search loops check it (NRPA playout/adapt break, systematic explore skips the move). The game so far is left valid.
3. Save + alert. The app (and the CLI’s search) poll GRID_OVERFLOW.swap(false, …) each tick, then stop the search, save the best game to records/overflow/, and show an alert telling the user to widen Row. See MorpionApp::handle_grid_overflow.

Resize & resume

Saves are grid-independent: both the .msr record and the search checkpoint store internal Pos coordinates, never grid indices (the index is computed only at insert time as pos + OFFSET). So enlarging Row grows OFFSET and re-centres the same game with room on every side. The workflow is:

widen Row in board.rs → rebuild → load the records/overflow/… record (or resume the checkpoint) → keep searching past the old boundary.

Possible future: automatic escalation

Today resizing is manual. Because a game’s move history (Vec<Move>, in absolute coordinates) is the sole source of truth — the bitset is a reconstructible projection — overflow could instead be handled automatically: on overflow, enqueue the branch’s history and replay it on a larger-grid Board in a secondary pass, keeping the common path on the small cache-friendly grid. This is not implemented; the cheap GRID_OVERFLOW seam is exactly where it would slot in. During search there are hundreds of live states (one per DFS stack across workers), so escalation would be per-branch, not global.

Records

The historical record progression for the four standard variants, compiled by the community at morpionsolitaire.com (maintained by Christian Boyer — the authoritative source; verify there). A repeated creator is carried down from the row above. 4T and 4D are solved: 62 and 35 are optimal, proven by Quist’s 2008 complete enumeration. 5T and 5D remain open.

5T — five in a line, touching

Bruneau’s 170, found by hand, held the record for 34 years (1976–2010).

5D — five in a line, disjoint

4T — four in a line, touching (solved)

4D — four in a line, disjoint (solved)

Playable grids in this project

These records are shipped, with provenance, in the morpion-solitaire-records corpus crate. Each record’s source links to its original Pentasol file or grid image on morpionsolitaire.com; the 4T and 4D records — which the site publishes only as images — were transcribed and re-verified as legal games.

The source of truth for each record is its JSON file in the repository (linked from the image below). Every other format is generated from it: a rendered board (PNG/SVG with the full record embedded, so the picture is also a save), the compact .msr, and — for 5T/5D — the legacy Pentasol form.

Every format, for every record, is one click away. Each record <id> (the file stem, e.g. rosin178) is published at a stable URL:

https://morpion-solitaire.io/records/<id>.{json, msr, png, svg, psol}

To load any of them, just drag and drop the downloaded file onto the web app (or onto the desktop GUI) — .png, .svg, .msr, .json and .psol are all accepted, and an image that embeds a record loads just like a save. The board numbers each move in play order.

4D — solved (optimal 35)

4T — solved (optimal 62)

5D

5T

There are no downloadable game files for the non-standard variants (5T+, 5T#, infinite, …).

Help wanted: more historical grids

This corpus is far from complete. Many older record grids — the pre-2004 4T/4D progressions, Bartsch’s 5D-102, and assorted hand-drawn grids — aren’t here yet, often because they survive only as photographs of graph-paper grids that resist automatic transcription.

Contributions are very welcome. If you have a record grid — an image, a Pentasol file, or just a move list — please share it (even a photo helps) by opening an issue or pull request on GitHub.

The image-transcription helper (tools/grid_to_msr.py) and the contributing guide describe how a grid becomes a verified .json record.

Bibliography

Research this project builds on. Citation keys (e.g. [Rosin2011]) are used in source-code doc comments to point back here.

Note: entries are being verified for exact venue/year; corrections welcome.

Algorithms

• [Cazenave2009] T. Cazenave. Nested Monte-Carlo Search. IJCAI 2009. — The recursive rollout scheme underlying NRPA.
• [Rosin2011] C. D. Rosin. Nested Rollout Policy Adaptation for Monte Carlo Tree Search. IJCAI 2011. — NRPA, the policy-gradient refinement of nested search; used by Rosin to reach the 5T record of 178. The core of this project’s search::nrpa.
• [Edelkamp2016] S. Edelkamp, T. Cazenave, et al. Generalized Nested Rollout Policy Adaptation (GNRPA). — Feature-weighted policy variants (the beta density bias experimented with here).
• [Cazenave2020] T. Cazenave et al. Work on Beam NRPA / parallel NRPA. — Background for the island and beam variants.
• [Shaw1998] P. Shaw. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. CP 1998. — Large Neighbourhood Search, the destroy/repair idea behind this project’s perturbation search.
• [Ropke2006] S. Ropke, D. Pisinger. An Adaptive Large Neighborhood Search Heuristic … Transportation Science, 2006. — Adaptive LNS.
• [Mouret2015] J.-B. Mouret, J. Clune. Illuminating Search Spaces by Mapping Elites. 2015. — Quality-Diversity / MAP-Elites, the inspiration for the perturbation archive (a diverse pool of high games).

The game: theory, records, community

• [Demaine2006] E. D. Demaine, M. L. Demaine, A. Langerman, S. Langerman. Morpion Solitaire. Theory of Computing Systems, 39(3), 2006. — Upper and lower bounds on game length; the complexity backdrop.
• [Boyer] C. Boyer. morpionsolitaire.com. — The community record registry and the origin of the Pentasol text format that MSR supersedes.
• Records. Rosin (5T 178), Tishchenko, and others; the committed .msr files credit specific record games.

Implementation techniques

• [Hinnant] H. Hinnant. chrono-Compatible Low-Level Date Algorithms (civil_from_days). — Used for dependency-free ISO-8601 date formatting in the record metadata.

API documentation

The crate-level API reference is generated by rustdoc and hosted on docs.rs:

• morpion-solitaire-record — the MSR format library (imported as msr): Record, RecordMove, Solver, Variant, Direction, encode/decode (compact MS1: and JSON), validate, and initial_cross.
• morpion-solitaire-records — the record corpus: RECORDS, a slice of (name, MSR string) pairs.
• morpion-solitaire — the application library: the game model (GameState, Board, Move, io), the search solvers and SearchState, render, and the egui ui.

The format library is the one to depend on if you only need to read, write or validate records — it pulls in none of the solver or rendering machinery.

Build the docs locally with:

cargo doc --workspace --no-deps --open

Contributing

Thanks for your interest in Morpion Solitaire! Contributions of all kinds are welcome — bug reports, fixes, features, docs, and new record games.

By participating you agree to abide by our Code of Conduct.

Project layout

This is a Cargo workspace with two crates under different licenses — this matters for what you contribute and where:

By submitting a change you agree to license your contribution under the license of the crate(s) it touches (GPL-3.0-or-later for the app; MIT OR Apache-2.0 for the format library). No separate CLA is required.

Building

Everything but the web build runs on stable (use it as your default toolchain):

cargo run --release            # GUI
cargo run --release -- --help  # CLI
cargo test --workspace

The only thing that needs nightly is the threaded WebAssembly build (it rebuilds std with the wasm atomics feature via -Z build-std). The wasm crate pins nightly and that config itself (its own rust-toolchain.toml and .cargo/config.toml), so just build from its directory:

cd crates/morpion-solitaire-wasm
trunk serve                    # or: trunk build --release

(nightly, rust-src and the wasm target auto-install on first build.)

Before you open a PR

CI enforces these; please run them locally first:

cargo fmt --all
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace

• Match the surrounding style. Keep comment density and naming consistent with nearby code.
• Add tests for behaviour changes. The format crate ships conformance tests; performance-sensitive engine changes should keep the differential move-gen test passing.
• Touching the MSR format? Update the spec in docs/spec and the JSON Schema in lockstep — the format definition is normative, the crate is its reference implementation.
• Keep the WASM build green if you change shared code (it compiles for wasm32 too; avoid native-only APIs outside #[cfg(not(target_arch = "wasm32"))]).

Commit & PR

• Small, focused commits with clear messages.
• Describe the why, not just the what, in the PR description.
• Reference any issue it closes.

Submitting a record game

Found or verified a strong game? Export it with the CLI and attach the .msr file (it carries provenance — method, author, date):

morpion-solitaire verify your-game.msr   # must pass

Questions

Open a discussion or issue, or email stephane@jourdois.fr.