DOSELLO is Solved

Abstract

Our independent Rust engine and distributed negamax search establish that perfect play from the standard initial position of DOSELLO gives Black a final disc difference of +2. The optimal openings are f3-f4 and its 180° rotational counterpart c5-c6. The 758-position certificate stores 456 endgame search jobs; legal transitions and interval propagation have been checked. “Solved” refers to the standard initial position, not every reachable position.

We combine exact and null-window bound searches, totaling 6.736 trillion searched nodes. The independent engine, sanitized proof archive, consistency checker and original WebAssembly interface are included. The checker validates legal transitions and interval propagation but trusts saved solver results rather than independently re-solving the leaves.

Initial value: Black +2

1. Introduction

The original DOSELLO — an Othello variant is a third-party game. This research independently implements its rules. Original JavaScript, HTML, CSS, images and favicon are not distributed here.

The board has 8×8 cells, initially four discs of each color arranged as four dominoes. Each move places a same-color domino in two orthogonally adjacent empty cells. As in Othello, opposing discs are captured along straight lines in eight directions. Each directly captured disc’s partner also flips. Partner flips do not trigger further captures. A legal move must directly capture at least one disc.

A player without a legal move passes; play ends when neither player can move. The score is Black discs minus White discs on the board. Empty cells are not awarded to the winner. A position includes domino pairing as well as disc colors.

2. Game size & comparison with Othello

The initial 56 empty cells allow at most 28 placements, excluding passes. We measured 100,000 games with a fixed seed and uniform legal-move selection using the independent Rust move generator. The mean length was 24.86827 placements. Early mean branching factors were 20.00, 12.70, 14.33, 13.13, 15.07, 14.98, 14.99, 15.28, 14.61, 14.92, 13.86, 13.98 and 12.75.

These random-playout lengths and branching factors are descriptive statistics, not counts of positions or game records. A position includes colors, domino pairing and side to move. Ply counts forced passes; terminal positions are not expanded. D4 identifies positions under up to eight board symmetries, without exchanging colors.

Plies 0–7 are exhaustive. For plies 8–11, the unbiased Monte Carlo estimator is N_d = E[W/m(P)]: W is the Knuth forward-sampling weight and m(P) is the exact path multiplicity from retrograde counting. The 4,096-sample shallow dataset is validated against exact shallow counts. Brackets below give empirical normal 95% confidence intervals; heavy tails can impair nominal coverage.

At plies ≥12, only bounds are available: exact multiplicity counting is intractable. The true total of reachable distinct positions across all plies is not pinned down. The exact lower bound is 132,473,902 (≈1.32e8, through ply 7); the proven combinatorial upper bound is 2.2575e21 raw, or 5.6437e20 up to D4. These are bounds on the union across plies, not a sum that double-counts positions reached at different plies.

Knuth sampling of 1,000,000 complete random playouts (seed 20261006) estimates all finite game-record prefixes, including the root, at ≈1.0336e26 [1.0001e26, 1.0672e26], and completed games at ≈3.5573e25 [3.4409e25, 3.6736e25] (95% CI).

Sources: position-counts.json, game-stats.json; methods and limitations.

3. Engine

The Rust engine uses only the standard library. Position keys consist of four 64-bit boards—Black, White, horizontal domino left ends and vertical domino top ends—plus side to move. Bit operations implement two-cell placement, directional captures and partner flips. An independent JavaScript rules implementation supports cross-checking WASM output.

Midgame search uses iterative deepening, PVS and 16-byte transposition entries. The current evaluator, eval3, is an independent linear pattern model: 32 instances of 6-cell patterns, with five cell states encoding color and domino orientation, incremental pattern-state updates, and cheap global terms. It uses the trained eval3-r2.bin weights. Plain eval3 is the chosen configuration: ProbCut and eval-guided move ordering were tested but not adopted because they gave no gain at equal time. Endgame proofs continue to separate heuristic estimates from exhaustive bounds.

Training used 5,999,964 exact labels (22–34 empties) plus approximately 150,000 deep-search labels (36–54 empties): 20 seconds per position at 36–44 empties and 5 seconds at 46–54. Local holdout measurements against exact labels reduced static MAE from 15.8 to 10.9 discs at 30–32 empties and from 14.3 to 10.4 at 34–36. Local search benchmarks measured 2.8–8.5× the speed of the previous learned evaluator; the ratio depends on the position and benchmark conditions. Inference weights are included, but the full training data and journals are not. These are source-project measurements, not experiments rerun for this release.

Parallel search follows the Young Brothers Wait Concept (YBWC): search the first sibling before processing the rest in parallel. Prior measurements reported about 3.7–3.8× speedup at 14 threads, depending on position and load. A representative exact-search position reached about 10.6M nodes/s on one Apple M4 thread. These are prior benchmark reports, not the average speed of the certificate computation.

The same Rust source builds for wasm32-unknown-unknown and analyzes in a browser Worker. Shared memory and special HTTP headers are unnecessary. The Worker loads approximately 1.9 MB of eval3 weights and the TOOL and DISPLAY books (approximately 2.62 MB combined); large sharded books are excluded. If weight loading fails, it quietly retains the previous evaluator. The analyzer distinguishes proven values and bounds from time-limited estimates.

4. Proof method

For side-to-move value V, negamax gives V(s) = max_m −V(s·m). Child intervals [L_i, U_i] propagate to [max(−U_i), max(−L_i)]. We solve the most promising move exactly and use null-window searches to show that alternatives cannot exceed it. Exact values for every move are unnecessary.

The coordinator advances a best-first proof and uses idle slots for speculative candidates. Long jobs split into child positions. All jobs in this saved certificate start three placements from the initial position, with 50 empty cells. Symmetric positions share bounds, which propagate upward.

The coordinator schedules work; remote workers search over SSH. Checkpoints, atomic state saves, job identifiers and retries support resumption. Small local tests exercise recovery and injected failures. Published host settings contain generic host-a/b/c examples only. No SSH or distributed search was started during this revision.

5. Results

The initial interval is [+2, +2]. The two optimal openings, f3-f4 and c5-c6, are related by 180° rotation. Values in the opening and reply tables are the final disc difference from Black’s perspective. White therefore minimizes the value in the reply table.

20 legal opening moves

f3-f4 / c5-c6 have exact value +2; c3-d3 / e6-f6 have exact value −2. The other 16 moves have upper bound ≤ −2 and are not claimed to equal −2.

13 replies to f3-f4

One full perfect-play line

This line has 25 placements and no passes: Black 30, White 28, with six isolated empty cells that can no longer be filled. Black wins by 2, matching the proven value. The first three moves come from the distributed proof; each subsequent move was proven optimal for its mover on 2026-10-06 with analyze --prove-best, 22 threads. Other optimal moves may exist. Per-ply proof results record values and times from the fourth move onward.

Ply is numbered from 1 here; JSONL ply is the number of moves already played. No separate per-move time was recorded for the first three moves. Values in this table are from the mover’s perspective.

5.1 Shortest games and perfect wins

All move sequences from the initial position were enumerated up to four placements. No game ends within one or two placements. The shortest game has 3 placements: there are 26 such sequences (13 up to 180° rotation), and every one is a perfect win for Black (14–0). White's shortest perfect win takes 4 placements: 22 sequences (11 up to rotation), all ending 0–16. Early endings occur only when one side has no discs left.

All 26 three-placement games (Black wins 14–0):

• b2-b3 c2-c3 e6-f6
• b2-b3 c2-c3 f6-g6
• b2-b3 c2-c3 f6-f7
• b3-c3 d2-d3 f3-f4
• b3-b4 c3-d3 f3-f4
• b3-b4 b5-c5 e6-e7
• b3-b4 c5-c6 e6-e7
• a4-b4 b5-c5 e6-e7
• a4-b4 c5-c6 e6-e7
• b4-b5 c5-c6 g4-g5
• b4-b5 c5-c6 g5-h5
• b4-b5 c5-c6 g5-g6
• b4-b5 c5-c6 e6-e7
• g4-g5 f3-f4 d2-d3
• g4-g5 f3-f4 b3-b4
• g4-g5 f3-f4 a4-b4
• g4-g5 f3-f4 b4-b5
• g5-h5 f3-f4 d2-d3
• g5-h5 f4-g4 d2-d3
• g5-g6 f3-f4 d2-d3
• g5-g6 f4-g4 d2-d3
• g5-g6 e6-f6 c5-c6
• f6-g6 e6-e7 c5-c6
• g6-g7 f6-f7 c2-c3
• g6-g7 f6-f7 b3-c3
• g6-g7 f6-f7 c3-d3

All 22 four-placement games (White wins 0–16):

• d2-d3 c1-c2 e6-f6 d7-e7
• d2-d3 b2-c2 e6-f6 d7-e7
• c3-d3 c1-c2 e6-f6 d7-e7
• c3-d3 b2-c2 b3-b4 b5-c5
• c3-d3 c2-d2 e6-f6 d7-e7
• c3-d3 d2-e2 e6-f6 d7-e7
• c3-d3 c7-d7 c5-c6 c2-d2
• f3-f4 e6-f6 g5-g6 g4-h4
• f4-g4 e2-f2 f3-g3 e6-f6
• f4-g4 e6-f6 g5-g6 h3-h4
• f4-g4 e6-f6 g5-g6 h4-h5
• b5-c5 c3-d3 b3-b4 a4-a5
• b5-c5 c3-d3 b3-b4 a5-a6
• b5-c5 c7-d7 b6-c6 c3-d3
• c5-c6 c3-d3 b3-b4 a5-b5
• e6-f6 e2-f2 f3-f4 e7-f7
• e6-f6 d7-e7 c3-d3 d2-e2
• e6-f6 e7-f7 c3-d3 d2-e2
• e6-f6 f7-g7 g5-g6 f4-g4
• e6-f6 f7-f8 c3-d3 d2-e2
• e6-e7 f7-g7 c3-d3 d2-e2
• e6-e7 f7-f8 c3-d3 d2-e2

Data: shortest-games.json.

6. Computation

Computation ran on October 5, 2026, 13:00:14–23:02:58 JST, approximately 10 hours 3 minutes. The three machines below searched while another machine only coordinated. CPU models come from the experiment’s hardware information; jobs, times and nodes were recomputed from the certificate.

Allocated thread-hours sum each job’s elapsed seconds times its assigned threads; they are not measured CPU time. There are more jobs than the 331 distinct positions because positions can receive different threshold and exact-value jobs. See the recomputed measurements.

Split opening books: TOOL and DISPLAY

TOOL contains only proven best moves (DSTOOL01; 15,366 symmetry-canonical positions, 553,188 bytes). AI decision positions were collected from benchmark games and adversarial hardening, then their best moves were proved with prove-best. AI play and hints with Analysis off prioritize TOOL; outside it, the AI searches with eval3 for 3 seconds. Proofs of stored moves do not guarantee perfect play outside the book.

The TOOL book was extended by adversarial hardening: an opponent deviates once within the first 12 plies of the proven perfect line (covering every alternative), the AI's decision positions are proved with prove-best, and positions where the AI's 3 s search missed the proven best move (holes) are added together with the other proven positions. In 100-game rounds with carried-over coverage, holes per 100 AI decisions fell to 2.37, 0.29 and 0.00 in the last three of twelve rounds (mean 0.89). The book was then hardened against a randomized opponent: from a random ply between 2 and 10 (from the first move in the earliest rounds) it deviates up to four times, each time choosing a move proved or estimated to lose at most 4 discs, and otherwise plays the best move. Twenty-five 100-game rounds added 1,017 positions. In later rounds 80–90% of games repeated earlier ones; holes per 100 AI decisions fell from about 6.6 to about 2 in new games, and to 0.24, 0.32 and 0.24 over all games, including repeats, in the last three rounds.

In the supplied local diagnostics, eval3 at 3 seconds missed a best move at these rates by empty cells: 30: 0.3%, 32: 2.3%, 34: 10%, 36: 24%, 38: 28%, 40: 30%, 42: 29%, 44: 25%; reported average loss reached approximately 1.5 discs. These describe the measured positions, not a guaranteed error rate over all reachable positions.

DISPLAY supplies values for the analysis table, board overlay and post-game review (canonical DSBOOK03; 20,355 positions, 2,887,286 bytes). Estimates were recomputed with eval3 at 1 second per position; exact values and proven bounds were retained. Positions proved during adversarial hardening were added with the exact best move and proven upper bounds for the other moves; no new estimates were computed for them. Exact, bound and estimate labels remain distinct. The files load independently: unavailable TOOL falls back to AI search, and unavailable DISPLAY falls back to analysis/review search.

In the supplied benchmark of TOOL's effect, the opponent deviated once at plies 1–8: 400 games against the previous AI at 3 seconds per move. With book: 381 wins, 2 draws, 17 losses (95.5% score); without: 369 wins, 5 draws, 26 losses (92.9%). Score counts a draw as half a win. These are source-project reports, not experiments rerun here or a fresh measurement of the final hardened file shipped here. Results depend on the deviation protocol, selected positions and timing; they neither establish a general win rate nor prove the solved value.

7. Verification & limitations

proof/verify.py uses Rust job --type inspect to enumerate legal moves and compare all saved children and symmetric transitions. It checks job position IDs, types, thresholds and intervals, then reconstructs every interval by repeated negamax propagation from terminal values and saved job intervals. It verifies root [2,2], both optimal openings, the reply table and the first three PV moves.

Verification limits: saved exhaustive leaf results are trusted outputs of this engine; the leaves are not independently re-solved here. Legal-move checks also use the same Rust rules, so this is not an independent third-party proof. There are 374 unsearched leaves with interval [−64,64]; interval propagation confirms they do not affect the root result.

Raw job results are included in proof/initial-proof.json. Host identities were replaced with generic names for privacy, changing the SHA-256 relative to the original archive. Position IDs, intervals, nodes and timestamps are preserved. The verification report records the public file’s hash. Full visited-position traces, large book journals and full training data are excluded.

The analyzer’s estimates do not guarantee perfect play. Outside the book it uses time-limited search. Game-size sampling estimates and cross-machine speed comparisons also depend on their experimental conditions.

8. Playing strength

In local equal-time, paired-color matches without an opening book, plain eval3 scored the following results against the previous AI (400 games per time budget, four random opening plies). Score counts a draw as half a win. These source-project measurements were supplied for this release; timing and random openings affect the results.

Against the original site’s level-5 CPU, eval3 at 500 ms/move recorded 397 wins, 0 draws and 3 losses in 400 games. The experiment owner reports that all three losses were decided by the random opening plies before the AI moved or arose from an already lost position. The opponent was a source-project reimplementation cross-checked against the original CPU; it is not bundled here. The site CPU uses fixed-depth search, so this comparison is not equal-time.

On the solved suite (300 positions per phase), local equal-time best-move accuracy at 3 seconds per position improved from 97% to 99% at 30 empties, 73% to 82% at 34 empties, and 65% to 76% at 38 empties (previous AI → eval3). ProbCut and eval-guided ordering were also tested and not adopted: neither improved equal-time performance. Match results and move accuracy do not establish the initial-position proof.

The analyzer demo remains a time-limited search, not a perfect player. Proven best moves from the bundled book take priority; elsewhere the AI searches for 3000 ms per move and can choose non-optimal moves. Browser speed limits exact endgame solving. The solved value (+2 for Black) rests on the proof in Sections 4–7, not on demo play.

9. Comparison with “Othello is Solved”

Takizawa’s “Othello is Solved” (2023) reports a draw for standard 8×8 Othello. Othello figures below are quoted from that paper (arXiv version).

The supplied Edax reference speed is approximately 1.2×10⁷ nodes/GHz/core/s. Our 10.6M nodes/s is for a particular Apple M4 and position without frequency normalization. Different rules, branching, node work and evaluations prevent inferring relative strength or a speed ratio from these figures.

References

1. DOSELLO — an Othello variant. Original game and source of the rules.
2. Hiroki Takizawa. Othello is Solved. arXiv:2310.19387, 2023. Othello comparison figures use the supplied report of this paper.
3. This repository’s proof/initial-proof.json, proof/verification.txt, random games and opening enumeration, job summary and saved match results.

Reproducibility

Run from the repository root with Rust, Python 3 and Node.js 22 or newer. There are no external Rust crates or npm dependencies.

export CARGO_TARGET_DIR="$PWD/rust/target"
cargo build --release --offline --manifest-path rust/Cargo.toml
cargo test --release --offline --manifest-path rust/Cargo.toml
DOSELLO_OFFLINE=1 npm test
python3 proof/verify.py
rust/target/release/game_stats 100000 5
python3 proof/summarize.py
(cd docs && python3 -m http.server 8000 --bind ::1)

To run locally, open http://localhost:8000/ and /play/. Rebuild WASM with bash rust/tools/build-wasm.sh using an installed wasm32-unknown-unknown target. The published site is wand125.github.io/solving-dosello/.

Users who permit network access can explicitly run DOSELLO_OFFLINE=0 bash rust/tools/crosscheck.sh for optional original-game comparison. Original code is downloaded only into an ignored cache, and unavailable downloads result in SKIP. See README for distributed solving and generic host settings.