25:["$","title",null,{"children":"Battleship | Visnu Pitiyanuvath | Observable"}] 4c:T1167,// The prediction map is drawn into this slot (by the next cell), which sits beside the board. const mapSlot = document.createElement("div"); mapSlot.className = "map-slot"; mapSlot.style.cssText = "flex:1 1 0;min-width:0;"; const board = view((() => { const root = document.createElement("div"); root.style.cssText = "font: 13px system-ui, sans-serif;"; let history = []; // [{c, out}] in the order fired const make = (tag, text, css = "") => Object.assign(document.createElement(tag), {textContent: text ?? "", style: css}); const btn = (label, onclick) => Object.assign(make("button", label, "margin:0 8px 8px 0;"), {onclick}); const status = make("div", "", "margin:6px 0;color:#444;"); // Select for the reported result (ship length in parentheses). const options = [["-1", "Miss"], ["0", "Hit"], ...shipNames.map((n, k) => [String(k + 1), `Sunk: ${n} (${stdFleet[k]})`])]; const select = make("select", "", "margin:0 0 8px 0;font:inherit;padding:3px;"); const optionEls = options.map(([value, label]) => { const o = Object.assign(document.createElement("option"), {value, textContent: label}); select.append(o); return o; }); const picker = make("label", "", "display:block;"); picker.append(document.createTextNode("Result: "), select); const choice = () => +select.value; const grid = make("div", "", `display:grid;grid-template-columns:20px repeat(${N},34px);gap:2px;align-items:center;justify-items:center;`); grid.append(make("span"), ...[..."ABCDEFGHIJ"].map((l) => make("span", l))); const cellButtons = []; for (let y = 0; y < N; y++) { grid.append(make("span", y + 1)); for (let x = 0; x < N; x++) { const c = y * N + x; const b = make("button", "", "width:33px;height:33px;border:1px solid #888;border-radius:4px;cursor:pointer;padding:0;font-size:13px;"); b.onclick = () => shoot(c); cellButtons[c] = b; grid.append(b); } } const hits = () => history.filter((h) => h.out !== -1).length; const finished = () => hits() === stdHoles; const sunkShips = () => new Set(history.filter((h) => h.out > 0).map((h) => h.out - 1)); function shoot(c) { // Clicking a square that was already entered removes that shot (to fix a mistake). if (history.some((h) => h.c === c)) { history = history.filter((h) => h.c !== c); return update(); } if (finished()) return; history = [...history, {c, out: choice()}]; update(); } function paint() { const byCell = new Map(history.map((h) => [h.c, h.out])); cellButtons.forEach((b, c) => { const out = byCell.get(c); b.textContent = out === undefined ? "" : out === -1 ? "•" : out === 0 ? "✕" : shipCodes[out - 1]; b.title = out === undefined ? "" : "Click again to remove this shot"; b.style.background = out === undefined ? "#fff" : out === -1 ? "#dde6f0" : out === 0 ? "crimson" : "#7a0019"; b.style.color = out >= 0 ? "white" : "black"; }); const done = sunkShips(); optionEls.forEach((o) => { const off = +o.value > 0 && done.has(+o.value - 1); o.disabled = off; const base = options.find(([v]) => v === o.value)[1]; o.textContent = off ? base + " ✓" : base; }); if (optionEls.find((o) => o.value === select.value).disabled) select.value = "0"; status.textContent = `${history.length} shots · ${hits()} of ${stdHoles} holes hit` + (finished() ? " · all ships sunk" : ""); } function update() { paint(); root.value = history; root.dispatchEvent(new Event("input", {bubbles: true})); } const controls = make("div"); controls.append( btn("Undo", () => { history = history.slice(0, -1); update(); }), btn("Clear", () => { history = []; update(); }) ); // Changing the select shouldn't bubble up as a change to the board's value. select.addEventListener("input", (e) => e.stopPropagation()); // Input on the left, prediction map on the right. No wrapping: the map shrinks to fit. const left = make("div", "", "flex:0 0 auto;"); left.append(controls, picker, grid, status); const layout = make("div", "", "display:flex;flex-wrap:nowrap;gap:24px;align-items:flex-start;"); const css = make("style", ".map-slot svg, .map-slot figure {max-width:100%;height:auto;} .map-slot figure {margin:0;}"); layout.append(left, mapSlot); root.append(css, layout); paint(); root.value = history; return root; })());4d:T6da,// Draws the prediction map into mapSlot, beside the board (see the previous cell). function renderBoard(history) { const show = (...nodes) => mapSlot.replaceChildren(...nodes); const mask = new Uint8Array(N * N); history.forEach(({c}) => (mask[c] = 1)); if (history.filter((h) => h.out !== -1).length === stdHoles) { return show(html`

Fleet sunk in ${history.length} shots. Undo or Clear to keep playing.

`); } const rand = d3.randomLcg(1); // fixed seed: the same shots always give the same map let smp = stdSampler.sample(history, 30000, rand); if (smp.ess < 500) smp = stdSampler.sample(history, 240000, rand); // heavily constrained: draw more if (smp.valid === 0) { return show(html`

No layout fits these shots. Check for a contradiction (for example, a ship marked sunk before all its squares were hit, or the wrong ship named).

`); } const est = stdSampler.estimate(smp, mask); const open = d3.range(N * N).filter((c) => !mask[c]); const cells = open.map((c) => ({c, p: est.occ[c] / est.W, tip: `P(ship) ${(100 * est.occ[c] / est.W).toFixed(1)}%`})); const best = d3.least(open, (c) => -est.occ[c]); const alt = d3.least(open, (c) => expectedLeft(est, c, est.W) - 1e-9 * est.occ[c]); show( html`

Most likely square: ${colName(best)} (${(100 * est.occ[best] / est.W).toFixed(1)}% chance of a ship).
Fewest expected layouts left: ${colName(alt)} (${smp.valid.toLocaleString()} sampled layouts, effective size ${Math.round(smp.ess).toLocaleString()}).

`, drawHeat({ cells, shots: history, best, alt: alt !== best ? alt : null, codes: shipCodes, width: 420, legend: false }) ); } renderBoard(board);4e:T537,// For each cell, how many of the surviving layouts give each report if we shoot there. function scoreCells(alive, mask) { const occ = new Int32Array(N * N); // layouts with a ship on the cell const hitOnly = new Int32Array(N * N); // ... where the shot would hit but not sink const sunk = fleet.map(() => new Int32Array(N * N)); // ... where it would sink ship k for (const i of alive) { for (let k = 0; k < fleet.length; k++) { const cells = placementsByShip[k][allConfigs[i][k]]; let rem = 0; for (const d of cells) if (!mask[d]) rem++; for (const d of cells) { if (mask[d]) continue; occ[d]++; if (rem === 1) sunk[k][d]++; else hitOnly[d]++; } } } return {n: alive.length, occ, hitOnly, sunk}; } // Expected number of layouts left after shooting c: sum over reports of (group size)² / total. // Works for exact counts or for weighted sample masses (pass total = W). const expectedLeft = (st, c, total = st.n) => ((total - st.occ[c]) ** 2 + st.hitOnly[c] ** 2 + d3.sum(st.sunk, (s) => s[c] ** 2)) / total; function exactStats(history) { const mask = new Uint8Array(N * N); history.forEach(({c}) => (mask[c] = 1)); const alive = d3.range(allConfigs.length).filter((i) => replayOK(i, history)); return {mask, ...scoreCells(alive, mask)}; }4f:T88f,const colName = (c) => "ABCDEFGHIJ"[c % N] + (Math.floor(c / N) + 1); // Shared heatmap. cells: [{c, p, tip}]; shots: [{c, out}]; best/alt: cells to ring. // domain (optional) fixes the color scale so several maps can be compared. function drawHeat({cells, shots = [], best, alt, title, subtitle, legend = true, width = 320, codes, domain}) { const xy = (c) => ({x: c % N, y: Math.floor(c / N)}); const pts = cells.map((d) => ({...d, ...xy(d.c)})); const dots = shots.map(({c, out}) => ({...xy(c), out, label: out > 0 && codes ? codes[out - 1] : ""})); const ring = (c) => pts.filter((d) => d.c === c); return Plot.plot({ title, subtitle, width, aspectRatio: 1, x: {tickFormat: (i) => "ABCDEFGHIJ"[i], axis: "top", label: null}, y: {tickFormat: (i) => i + 1, label: null, domain: d3.range(N)}, color: {scheme: "blues", legend, label: "P(ship)", domain}, marks: [ Plot.cell(pts, {x: "x", y: "y", fill: "p", inset: 0.5, tip: true, title: "tip"}), Plot.text(pts, {x: "x", y: "y", text: (d) => (d.p * 100).toFixed(0), fontSize: 9, fill: "black", stroke: "white"}), Plot.dot(dots, {x: "x", y: "y", r: 9, stroke: "black", fill: (d) => (d.out === -1 ? "white" : d.out === 0 ? "crimson" : "#7a0019")}), Plot.text(dots.filter((d) => d.label), {x: "x", y: "y", text: "label", fill: "white", fontSize: 8}), best != null && Plot.dot(ring(best), {x: "x", y: "y", r: 14, stroke: "orange", strokeWidth: 3}), alt != null && Plot.dot(ring(alt), {x: "x", y: "y", r: 14, stroke: "orange", strokeWidth: 3, strokeDasharray: "4 3"}) ].filter(Boolean) }); } // Exact heatmap for the two-ship fleet after a shot history. function heatmapExact(history, opts = {}) { const st = exactStats(history); const cells = d3.range(N * N).filter((c) => !st.mask[c]).map((c) => ({ c, p: st.occ[c] / st.n, tip: `P(ship) ${(100 * st.occ[c] / st.n).toFixed(1)}%\nexpected layouts left ${Math.round(expectedLeft(st, c)).toLocaleString()}` })); const best = d3.least(cells, (d) => -d.p).c; return drawHeat({ cells, shots: history, best, subtitle: html`${st.n.toLocaleString()} layouts left.`, ...opts }); }50:T9c9,// Exact shots needed against EVERY layout by a deterministic chooser fn(alive, mask). // Play the chooser as a decision tree: pick a shot for the whole surviving set, split it by the report, recurse. // A lone surviving layout is finished by hitting its remaining squares. function shotsByLayout(fn) { const shots = new Int16Array(allConfigs.length); const mask = new Uint8Array(N * N); (function rec(alive, depth) { if (alive.length === 1) { const i = alive[0]; let remaining = 0; for (let k = 0; k < fleet.length; k++) for (const d of placementsByShip[k][allConfigs[i][k]]) if (!mask[d]) remaining++; shots[i] = depth + remaining; return; } const c = fn(alive, mask); mask[c] = 1; const groups = new Map(); for (const i of alive) { const out = outcomeOf(i, c, mask); if (!groups.has(out)) groups.set(out, []); groups.get(out).push(i); } for (const g of groups.values()) rec(g, depth + 1); mask[c] = 0; })(d3.range(allConfigs.length), 0); return shots; } // Named, cached per-layout shot counts (so each tree is computed once, and the big arrays stay out of the display). const exactShotsFor = (() => { const cache = new Map(); return (name, fn) => { if (!cache.has(name)) cache.set(name, shotsByLayout(fn)); return cache.get(name); }; })(); // Chooser for a player who weights layouts by w (all ones = assumes uniform). const weightedChooser = (w) => (alive, mask) => { const occ = weightedOcc(alive, mask, w); return d3.least(d3.range(N * N).filter((c) => !mask[c]), (c) => -occ[c]); }; // Expected shots against opponents who place with weights w. const expectedShots = (shots, w) => d3.sum(shots, (s, i) => s * w[i]) / d3.sum(w); // Distribution of the number of shots, as a probability for each count 0..N*N, from per-layout counts (uniform opponent). const pmfOfShots = (shots) => { const p = new Float64Array(N * N + 1); for (const s of shots) p[s] += 1 / shots.length; return Array.from(p); }; // Mean, median, 95th percentile (smallest count reaching that share of games), and worst case of a distribution. function summarizePmf(pmf) { let cum = 0, median = null, p95 = null; pmf.forEach((p, t) => { cum += p; if (median === null && cum >= 0.5 - 1e-9) median = t; if (p95 === null && cum >= 0.95 - 1e-9) p95 = t; }); return {mean: d3.sum(pmf, (p, t) => p * t), median, p95, worst: d3.max(d3.range(pmf.length).filter((t) => pmf[t] > 1e-12))}; }51:T578,// Exact results against a uniform opponent, over all 20,336 layouts. const exactGreedy = (() => { const n = N * N, h = totalHoles; // Random shooting: the shots needed are the position of the last ship square in a random order of the n squares. const C = (a, b) => { let r = 1; for (let i = 1; i <= b; i++) r = (r * (a - b + i)) / i; return r; }; const pmfRandom = d3.range(n + 1).map((t) => (t < h ? 0 : C(t - 1, h - 1) / C(n, h))); const shotsProb = exactShotsFor("probability", policies.probability); const shotsInfo = exactShotsFor("information", policies.information); const rules = [ {rule: "random", pmf: pmfRandom}, {rule: "probability", pmf: pmfOfShots(shotsProb)}, {rule: "information", pmf: pmfOfShots(shotsInfo)} ]; const rows = rules.map(({rule, pmf}) => ({rule, ...summarizePmf(pmf)})); const cdf = rules.flatMap(({rule, pmf}) => { let cum = 0; return pmf.map((p, t) => ({rule, t, done: (cum += p)})); }); // Paired comparison of the two greedy rules: same layouts, so the difference is exact for every layout. const diff = Array.from(shotsInfo, (s, i) => s - shotsProb[i]); const paired = { meanDifference: d3.mean(diff), infoFewer: diff.filter((d) => d < 0).length, same: diff.filter((d) => d === 0).length, infoMore: diff.filter((d) => d > 0).length, layouts: diff.length }; return {rows, cdf, paired}; })();52:T462,display(Inputs.table(exactGreedy.rows, {format: {mean: (x) => x.toFixed(2)}})); { const p = exactGreedy.paired, pct = (k) => `${(100 * k / p.layouts).toFixed(0)}%`; display(html`

Over all ${p.layouts.toLocaleString()} layouts, the information rule needs ${p.meanDifference.toFixed(2)} more shots than the probability rule on average. It needs fewer on ${p.infoFewer.toLocaleString()} layouts (${pct(p.infoFewer)}), the same on ${p.same.toLocaleString()} (${pct(p.same)}), and more on ${p.infoMore.toLocaleString()} (${pct(p.infoMore)}).

`); } const cdfPlot = display(Plot.plot({ title: "Two-ship fleet: share of games finished within t shots", subtitle: "Exact, over all 20,336 equally likely layouts; random shooting from the closed-form distribution", x: {label: "Shots fired", domain: [0, N * N]}, y: {label: "Games finished (%)", grid: true, percent: true, domain: [0, 100]}, color: {legend: true, domain: ["random", "information", "probability"]}, marks: [ Plot.lineY(exactGreedy.cdf, {x: "t", y: "done", stroke: "rule", curve: "step-after", tip: true}), Plot.ruleY([0]) ] }));53:T46e,## Five ships: sample, don’t enumerate The standard fleet has at most ${tex`7.7 \times 10^{10}`} layouts (the product of each ship’s placement count, before removing overlaps), too many to list. Instead we **sample** layouts consistent with the shots so far and estimate everything from the samples. **Sequential importance sampling.** Build a layout ship by ship: 1. Place any ships announced as *sunk* first; each has few legal placements. 2. For the first still-uncovered *hit*, choose uniformly among all (ship, placement) pairs that cover it. Repeat until every hit is explained. 3. Place the remaining ships uniformly among their legal placements. A uniform choice among ${tex`n`} options multiplies the sample’s weight by ${tex`n`}. Weighted averages then estimate quantities under the uniform distribution over consistent layouts. “Consistent” means misses are empty, every hit is covered, sunk ships sit exactly where the announcements require, and no unsunk ship is fully hit. **Check.** On the two-ship fleet we can compare against exact enumeration. Differences should be sampling noise (a few thousandths).54:T105e,const stdFleet = [5, 4, 3, 3, 2]; const shipNames = ["Carrier", "Battleship", "Cruiser", "Submarine", "Destroyer"]; const shipCodes = ["Ca", "Ba", "Cr", "Su", "De"]; function makeSampler(fl) { const K = fl.length; const pl = fl.map(shipPlacements); // Turn the shot history into constraints: allowed placements per ship, and which placements cover each hit. function prepare(history) { const shot = new Uint8Array(N * N), miss = new Uint8Array(N * N); const time = new Int16Array(N * N).fill(-1); const hits = []; const sunk = new Array(K).fill(null); history.forEach(({c, out}, t) => { shot[c] = 1; time[c] = t; if (out === -1) miss[c] = 1; else { hits.push(c); if (out > 0) sunk[out - 1] = {c, t}; } }); const allowed = pl.map((list, k) => { const res = []; list.forEach((cells, j) => { let allShot = true; for (const d of cells) { if (miss[d]) return; if (!shot[d]) allShot = false; } if (sunk[k]) { if (!allShot || !cells.includes(sunk[k].c)) return; if (cells.some((d) => time[d] > sunk[k].t)) return; } else if (allShot) return; res.push(j); }); return res; }); const cover = allowed.map((res, k) => new Map(hits.map((h) => [h, res.filter((j) => pl[k][j].includes(h))]))); return {hits, sunk, allowed, cover}; } // Weighted consistent layouts: chosen[v * K + k] = placement index of ship k in sample v. function sample(history, S, rand) { const {hits, sunk, allowed, cover} = prepare(history); const chosen = new Int16Array(S * K), weights = new Float64Array(S); const occ = new Uint8Array(N * N), placed = new Int16Array(K); const candK = new Int16Array(4000), candJ = new Int16Array(4000); const sunkShips = d3.range(K).filter((k) => sunk[k]); const otherShips = d3.range(K).filter((k) => !sunk[k]); const free = (cells) => { for (let i = 0; i < cells.length; i++) if (occ[cells[i]]) return false; return true; }; const put = (k, j) => { placed[k] = j; for (const d of pl[k][j]) occ[d] = 1; }; let valid = 0, sumW = 0, sumW2 = 0; outer: for (let s = 0; s < S; s++) { occ.fill(0); placed.fill(-1); let w = 1; for (const k of sunkShips) { let n = 0; for (const j of allowed[k]) if (free(pl[k][j])) candJ[n++] = j; if (!n) continue outer; w *= n; put(k, candJ[Math.floor(rand() * n)]); } for (const h of hits) { if (occ[h]) continue; let m = 0; for (const k of otherShips) { if (placed[k] >= 0) continue; for (const j of cover[k].get(h)) if (free(pl[k][j])) { candK[m] = k; candJ[m] = j; m++; } } if (!m) continue outer; w *= m; const r = Math.floor(rand() * m); put(candK[r], candJ[r]); } for (const k of otherShips) { if (placed[k] >= 0) continue; let n = 0; for (const j of allowed[k]) if (free(pl[k][j])) candJ[n++] = j; if (!n) continue outer; w *= n; put(k, candJ[Math.floor(rand() * n)]); } chosen.set(placed, valid * K); weights[valid] = w; valid++; sumW += w; sumW2 += w * w; } // ess = effective sample size: how many equally weighted samples the weighted set is worth return {valid, chosen, weights, totalW: sumW, ess: sumW2 ? sumW * sumW / sumW2 : 0}; } // Weighted outcome masses per cell; same shape as scoreCells (with W as the total). function estimate(smp, mask) { const occ = new Float64Array(N * N), hitOnly = new Float64Array(N * N); const sunkM = fl.map(() => new Float64Array(N * N)); for (let v = 0; v < smp.valid; v++) { const w = smp.weights[v]; for (let k = 0; k < K; k++) { const cells = pl[k][smp.chosen[v * K + k]]; let rem = 0; for (const d of cells) if (!mask[d]) rem++; for (const d of cells) { if (mask[d]) continue; occ[d] += w; if (rem === 1) sunkM[k][d] += w; else hitOnly[d] += w; } } } return {W: smp.totalW, occ, hitOnly, sunk: sunkM}; } return {K, pl, sample, estimate}; } const smallSampler = makeSampler(fleet);55:T62c,// Largest difference, over all cells and outcomes, between exact and sampled outcome probabilities. function validate(history, S = 40000) { const exact = exactStats(history); const smp = smallSampler.sample(history, S, d3.randomLcg(11)); const est = smallSampler.estimate(smp, exact.mask); let maxDiff = 0; for (let c = 0; c < N * N; c++) { if (exact.mask[c]) continue; const pairs = [ [exact.occ[c] / exact.n, est.occ[c] / est.W], [exact.hitOnly[c] / exact.n, est.hitOnly[c] / est.W], ...exact.sunk.map((s, k) => [s[c] / exact.n, est.sunk[k][c] / est.W]) ]; for (const [a, b] of pairs) maxDiff = Math.max(maxDiff, Math.abs(a - b)); } return {exactLayouts: exact.n, sampled: smp.valid, effectiveSamples: Math.round(smp.ess), maxDiff: +maxDiff.toFixed(4)}; } const tests = [ {test: "2 hits, 3 misses", history: [{c: 33, out: 0}, {c: 44, out: -1}, {c: 35, out: -1}, {c: 3, out: -1}, {c: 77, out: 0}]}, {test: "3-ship sunk (D4 E4 F4)", history: [{c: 33, out: 0}, {c: 34, out: 0}, {c: 35, out: 2}, {c: 70, out: -1}]}, {test: "hit near a sunk ship", history: [{c: 33, out: 0}, {c: 34, out: 0}, {c: 35, out: 2}, {c: 23, out: 0}]}, {test: "hits E5 and H8, miss A6", history: [{c: 44, out: 0}, {c: 77, out: 0}, {c: 50, out: -1}]}, {test: "adjacent hits E5 F5, miss B2", history: [{c: 44, out: 0}, {c: 45, out: 0}, {c: 11, out: -1}]}, {test: "hits E5 F5, 3-ship sunk at G5", history: [{c: 44, out: 0}, {c: 45, out: 0}, {c: 46, out: 2}]} ]; display(Inputs.table(tests.map(({test, history}) => ({test, ...validate(history)}))));56:Tb49,const stdSampler = makeSampler(stdFleet); const stdHoles = d3.sum(stdFleet); // Uniform random legal configuration, by rejection of overlapping placements. function randomConfig(sampler, rand) { for (;;) { const occ = new Uint8Array(N * N), cfg = []; let ok = true; for (let k = 0; k < sampler.K && ok; k++) { const j = Math.floor(rand() * sampler.pl[k].length); for (const d of sampler.pl[k][j]) { if (occ[d]) ok = false; occ[d] = 1; } cfg.push(j); } if (ok) return cfg; } } // Feedback for shooting c against a true config (mask must already include c). function stdOutcome(sampler, cfg, c, mask) { for (let k = 0; k < sampler.K; k++) { const cells = sampler.pl[k][cfg[k]]; if (!cells.includes(c)) continue; return cells.every((d) => mask[d]) ? k + 1 : 0; } return -1; } // Memoized greedy choices. Each greedy rule is a deterministic function of the shot history, so both // rules (and every game that reaches the same history, e.g. the opening and early misses) share one sample. // The sample's random stream is seeded from the history itself, so results don't depend on run order. const choiceCache = new Map(); const hashString = (s) => { let h = 2166136261; for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 16777619); } return (h >>> 0) + 1; }; function greedyChoices(sampler, history, mask, S) { const key = `${S}|${history.map((h) => `${h.c}:${h.out}`).join(",")}`; let choices = choiceCache.get(key); if (choices) return choices; const rand = d3.randomLcg(hashString(key)); const open = d3.range(N * N).filter((c) => !mask[c]); let smp = sampler.sample(history, S, rand); for (let tries = 0; smp.valid === 0 && tries < 2; tries++) smp = sampler.sample(history, S * 8, rand); const {W, occ, hitOnly, sunk} = sampler.estimate(smp, mask); const score = (c) => (W - occ[c]) ** 2 + hitOnly[c] ** 2 + d3.sum(sunk, (s) => s[c] ** 2); choices = { probability: d3.least(open, (c) => -occ[c]), information: d3.least(open, (c) => score(c) - 1e-9 * occ[c]) }; choiceCache.set(key, choices); return choices; } // Choose the next shot (S posterior samples per new history). function chooseStd(policy, sampler, history, mask, rand, S) { if (policy === "random") { const open = d3.range(N * N).filter((c) => !mask[c]); return open[Math.floor(rand() * open.length)]; } return greedyChoices(sampler, history, mask, S)[policy]; } // Play one full game and return the number of shots. function playStd(policy, cfg, rand, S) { const mask = new Uint8Array(N * N), history = []; let holes = stdHoles; while (holes > 0) { const c = chooseStd(policy, stdSampler, history, mask, rand, S); mask[c] = 1; const out = stdOutcome(stdSampler, cfg, c, mask); history.push({c, out}); if (out !== -1) holes--; } return history.length; }57:T8b3,function renderStd(sim) { const rs = sim.results ?? []; display(sim.started ? html`

${sim.done} of ${sim.total} games per rule (${sim.done >= sim.total ? "done" : "running…"}; ${sim.seconds.toFixed(0)} s of compute)

` : html`

Set the number of games, then click Run.

`); const byPolicy = d3.group(rs, (d) => d.policy); const rows = ["random", "probability", "information"].map((policy) => { const s = (byPolicy.get(policy) ?? []).map((d) => d.shots); return {policy, games: s.length, mean: d3.mean(s), median: d3.median(s), p95: d3.quantile(s, 0.95), worst: d3.max(s)}; }); display(Inputs.table(rows, {format: {mean: (x) => (x == null ? "" : x.toFixed(1))}})); const prob = byPolicy.get("probability") ?? [], info = byPolicy.get("information") ?? []; if (prob.length > 2) { const diffs = info.map((d, i) => d.shots - prob[i].shots); const ci = 1.96 * d3.deviation(diffs) / Math.sqrt(diffs.length); display(html`

Paired difference (information − probability): ${d3.mean(diffs).toFixed(2)} ± ${ci.toFixed(2)} shots (95% CI)

`); } const bin = d3.bin().value((d) => d.shots).domain([0, 105]).thresholds(d3.range(5, 105, 5)); const bins = Array.from(byPolicy, ([policy, ps]) => bin(ps).map((b) => ({policy, x0: b.x0, x1: b.x1, share: b.length / ps.length})) ).flat(); const means = rows.filter((r) => r.mean != null).map(({policy, mean}) => ({policy, mean})); display(Plot.plot({ title: "Standard fleet: greedy play needs less than half the shots of random guessing", subtitle: `Share of games by shots needed to sink all five ships; ${sim.done} games per rule so far. Dashed lines are means.`, x: {label: "Shots to sink the fleet", domain: [0, 105]}, y: {label: "Share of games (%)", percent: true, grid: true, domain: [0, 65]}, // percent: domain in percent units color: {legend: true, domain: ["random", "information", "probability"]}, marks: [ Plot.rectY(bins, {x1: "x0", x2: "x1", y: "share", fill: "policy", fillOpacity: 0.6, tip: true}), Plot.ruleX(means, {x: "mean", stroke: "policy", strokeWidth: 2, strokeDasharray: "4 3"}), Plot.ruleY([0]) ] })); } renderStd(stdSim);58:T48f,// Starts once the Run button has been clicked; each click re-runs this cell and so restarts the simulation. // The game count is read from the slider at that moment (reading the element, not its value, so dragging // the slider doesn't restart anything). All three rules play each layout. const stdSim = (async function* () { let stopped = false; invalidation.then(() => (stopped = true)); const total = stdGamesEl.value; const cfgRand = d3.randomLcg(2027); const results = []; let busy = 0; const snapshot = (done) => ({results: results.slice(), done, total, started: stdRun > 0, seconds: busy / 1000}); yield snapshot(0); if (!stdRun) return; for (let g = 0; g < total && !stopped; g++) { const t = performance.now(); const cfg = randomConfig(stdSampler, cfgRand); for (const policy of ["random", "probability", "information"]) { results.push({policy, shots: playStd(policy, cfg, d3.randomLcg(1000 * g + 7), 1500)}); } busy += performance.now() - t; await new Promise((resolve) => setTimeout(resolve)); // hand control back to the browser yield snapshot(g + 1); } })(); display(md`Run __${stdRun}__ times`);59:T628,// Two-shot lookahead, hits version (small fleet, exact). For each first shot c1, split the surviving layouts by the report // (miss / hit / sunk k), find the best follow-up shot within each group, and add up the expected hits. function lookaheadScores(alive, mask) { const M = N * N, O = fleet.length + 2; // report slot = out + 1: miss 0, hit 1, sunk k -> k + 2 const cnt = new Int32Array(M * O * M); // [c1][slot][c2]: layouts in that group with a ship on c2 const occ = new Int32Array(M); const open = d3.range(M).filter((c) => !mask[c]); for (const i of alive) { const cells = fleet.flatMap((_, k) => placementsByShip[k][allConfigs[i][k]]); for (const c1 of open) { const base = (c1 * O + outcomeOf(i, c1, mask) + 1) * M; for (const d of cells) if (d !== c1 && !mask[d]) cnt[base + d]++; if (shipAt[i][c1] >= 0) occ[c1]++; } } const value = new Float64Array(M).fill(-1); for (const c1 of open) { let v = occ[c1]; // expected hits on the first shot (as a count) for (let s = 0; s < O; s++) { let best = 0; const base = (c1 * O + s) * M; for (let d = 0; d < M; d++) if (cnt[base + d] > best) best = cnt[base + d]; v += best; // best follow-up hits within this report group } value[c1] = v / alive.length; } return {occ, value, open, n: alive.length}; } function lookahead2(alive, mask) { const st = lookaheadScores(alive, mask); return d3.least(st.open, (c) => -st.value[c] - 1e-9 * st.occ[c]); }5a:T669,// Two-shot lookahead, information version: minimize the expected number of layouts left after this shot // and the best follow-up, i.e. sum over report pairs of (group size)² / n. function lookaheadInfo(alive, mask) { const M = N * N, K = fleet.length, O = K + 2; const open = d3.range(M).filter((c) => !mask[c]); const cnt = new Int32Array(M * O * M * O); const occ = new Int32Array(M); const rem = new Int16Array(K), after = new Int16Array(K); for (const i of alive) { const at = shipAt[i]; for (let k = 0; k < K; k++) { rem[k] = 0; for (const d of placementsByShip[k][allConfigs[i][k]]) if (!mask[d]) rem[k]++; } for (const c1 of open) { const k1 = at[c1]; const s1 = k1 < 0 ? 0 : rem[k1] === 1 ? k1 + 2 : 1; if (k1 >= 0) occ[c1]++; for (let k = 0; k < K; k++) after[k] = rem[k] - (k === k1 ? 1 : 0); const base = (c1 * O + s1) * M; for (const c2 of open) { if (c2 === c1) continue; const k2 = at[c2]; cnt[(base + c2) * O + (k2 < 0 ? 0 : after[k2] === 1 ? k2 + 2 : 1)]++; } } } const score = new Float64Array(M).fill(Infinity); for (const c1 of open) { let total = 0; for (let s1 = 0; s1 < O; s1++) { let best = Infinity; for (const c2 of open) { if (c2 === c1) continue; let q = 0; const b = ((c1 * O + s1) * M + c2) * O; for (let s2 = 0; s2 < O; s2++) q += cnt[b + s2] ** 2; if (q < best) best = q; } if (best !== Infinity) total += best; } score[c1] = total / alive.length; } return d3.least(open, (c) => score[c] - 1e-9 * occ[c]); }5b:T670,// Exact results for the one-shot rules and both two-shot lookaheads against a uniform opponent, over all layouts. // Runs only after the button above is clicked (the information lookahead takes about 15 s). const exactLookahead = (async function* () { if (!lookRun) return yield null; yield "running"; await new Promise((resolve) => setTimeout(resolve, 50)); // let the "computing" message paint const t0 = performance.now(); const rules = { "probability": policies.probability, "information": policies.information, "lookahead: hits": lookahead2, "lookahead: information": lookaheadInfo }; const shots = Object.fromEntries(Object.entries(rules).map(([name, fn]) => [name, exactShotsFor(name, fn)])); const base = shots.probability; const rows = Object.entries(shots).map(([rule, s]) => { const diff = Array.from(s, (x, i) => x - base[i]); return { rule, ...summarizePmf(pmfOfShots(s)), vsProbability: d3.mean(diff), fewer: diff.filter((d) => d < 0).length, same: diff.filter((d) => d === 0).length, more: diff.filter((d) => d > 0).length }; }); // Check: the decision tree should match playing games one layout at a time. const rand = d3.randomInt.source(d3.randomLcg(5)); const layouts = d3.range(100).map(() => rand(allConfigs.length)()); const mismatches = Object.fromEntries(Object.entries(rules).map(([name, fn]) => { const cache = new Map(); return [name, layouts.filter((i) => playWith(fn, i, cache).length !== shots[name][i]).length]; })); yield {rows, mismatches, checked: layouts.length, seconds: +((performance.now() - t0) / 1000).toFixed(1)}; })();5c:T459,if (!exactLookahead) display(html`

Click the button above to compute this table.

`); else if (exactLookahead === "running") display(html`

Computing… the page may be unresponsive for about 20 s.

`); else { const signed = (x) => (x > 0 ? "+" : "") + x.toFixed(2); display(Inputs.table(exactLookahead.rows.map((r) => ({ rule: r.rule, "mean shots": r.mean, median: r.median, p95: r.p95, worst: r.worst, "mean vs probability": r.vsProbability, "layouts with fewer shots": r.fewer, "same": r.same, "more": r.more })), {format: {"mean shots": (x) => x.toFixed(2), "mean vs probability": signed}, layout: "auto"})); const bad = d3.sum(Object.values(exactLookahead.mismatches)); display(html`

Two-ship fleet, uniform opponent, exact over all 20,336 layouts. The last four columns compare each rule with the probability rule on the same layout. Check: the decision tree matched game-by-game play on ${exactLookahead.checked} layouts for every rule (${bad} mismatches). Computing this table takes about ${exactLookahead.seconds} s.

`); }5d:T5aa,## When opponents aren't uniform So far the opponent has chosen a layout uniformly at random. Real players probably don't: they may favour the border, and they may avoid placing ships next to each other. To see how much that could matter, we give each layout a weight ${tex.block`\exp(a \cdot \text{edge squares} - b \cdot \text{touching pairs})`} where *edge squares* is the number of ship squares on the border, a *touching pair* is two ships with squares in adjacent cells (diagonals count), and ${tex`a, b \ge 0`} set how strong each habit is. With ${tex`a = b = 0`} every layout has weight 1, which is the uniform opponent used so far. Otherwise the opponent picks a layout with probability proportional to its weight. For scale, ignoring the spacing term, a layout with all seven ship squares on the border gets about 4 times the weight of a layout with none at ${tex`a = 0.2`}, about 33 times at ${tex`a = 0.5`}, and about 1,100 times at ${tex`a = 1`}. These weights are an invented model, not measured from real players. The results describe what would happen if players behaved this way; they are not evidence about how people actually place ships. We stay with the two-ship fleet so that every layout can be listed. Two questions follow. How does the map of ship probabilities change when the opponent has these habits? And how many shots does a player save by knowing the habits, compared with a player who assumes uniform placement?5e:T7b0,// Per-layout features for the human-like prior (two-ship fleet): ship squares on the border, and touching ship pairs. // Computed once on first use. const layoutFeatures = (() => { let cached; return () => cached ??= (() => { const onEdge = (c) => { const x = c % N, y = Math.floor(c / N); return x === 0 || y === 0 || x === N - 1 || y === N - 1; }; const near = (c, d) => Math.abs((c % N) - (d % N)) <= 1 && Math.abs(Math.floor(c / N) - Math.floor(d / N)) <= 1; const edge = new Int16Array(allConfigs.length), touch = new Int16Array(allConfigs.length); allConfigs.forEach((cfg, i) => { const ships = cfg.map((j, k) => placementsByShip[k][j]); edge[i] = d3.sum(ships.flat(), (c) => +onEdge(c)); for (let a = 0; a < ships.length; a++) for (let b = a + 1; b < ships.length; b++) if (ships[a].some((c) => ships[b].some((d) => near(c, d)))) touch[i]++; }); return {edge, touch}; })(); })(); // Weight of every layout under the prior (edgeBias = a, spacing = b). const humanWeights = (edgeBias, spacing) => { const {edge, touch} = layoutFeatures(); return Float64Array.from(edge, (e, i) => Math.exp(edgeBias * e - spacing * touch[i])); }; // Weighted version of P(ship) mass per cell over the surviving layouts. function weightedOcc(alive, mask, w) { const occ = new Float64Array(N * N); for (const i of alive) for (let k = 0; k < fleet.length; k++) for (const d of placementsByShip[k][allConfigs[i][k]]) if (!mask[d]) occ[d] += w[i]; return occ; } const priorCheck = (() => { const all = d3.range(allConfigs.length), w = humanWeights(0.5, 2), flat = humanWeights(0, 0); const {edge, touch} = layoutFeatures(); const share = (ww, f) => d3.sum(all, (i) => ww[i] * f[i]) / d3.sum(ww); return { layouts: allConfigs.length, touching: {uniform: share(flat, touch), human: share(w, touch)}, edgeSquaresOf7: {uniform: share(flat, edge), human: share(w, edge)} }; })();5f:T4a5,{ const all = d3.range(allConfigs.length), noShots = new Uint8Array(N * N); const make = (w, title) => { const occ = weightedOcc(all, noShots, w), W = d3.sum(w); const cells = d3 .range(N * N) .map((c) => ({ c, p: occ[c] / W, tip: `P(ship) ${((100 * occ[c]) / W).toFixed(1)}%` })); const top = d3.max(cells, (d) => d.p); const ties = cells.filter((d) => d.p > top * (1 - 1e-9)).length; // symmetric squares tie exactly return {title, cells, best: d3.least(cells, (d) => -d.p).c, ties, top}; }; const maps = [ make(humanWeights(edgeBias, spacing), "Human-like opponent"), make(humanWeights(0, 0), "Uniform opponent") ]; const domain = [0, d3.max(maps, (m) => m.top)]; display( html`

${maps.map((m) => drawHeat({ cells: m.cells, best: m.best, domain, legend: false, width: 320, title: m.title, subtitle: `Chance each square holds a ship before any shot. Best opening: ${colName(m.best)} (${m.ties} squares tie by symmetry, ${(100 * m.top).toFixed(1)}%)` }) )}

` ); }60:T484,if (!Array.isArray(biasGrid)) display(html`

${biasGrid === "running" ? "Computing… the page may be unresponsive for about 15 s." : "Click the button above to compute this chart."}

`); else { // Change in expected shots for a player who knows the prior, compared with one who assumes uniform placement. const rows = biasGrid.flatMap((r) => [ {a: r.a, b: `b = ${r.b}`, opponent: "Opponent follows the prior", diff: r.knowsVsHuman - r.assumesVsHuman}, {a: r.a, b: `b = ${r.b}`, opponent: "Opponent places uniformly", diff: r.knowsVsUniform - r.assumesVsUniform} ]); const plot = display(Plot.plot({ title: "Change in expected shots from knowing the opponent's placement habits", subtitle: "Two-ship fleet, exact. Player who knows the prior minus player who assumes uniform placement; below zero means knowing the prior saves shots.", width: 820, x: {label: "Edge bias a"}, y: {label: "Shots: knows − assumes", grid: true}, fx: {label: null}, color: {legend: true}, marks: [ Plot.ruleY([0]), Plot.lineY(rows, {x: "a", y: "diff", stroke: "b", fx: "opponent", tip: true}) ] })); }61:T61e,if (!Array.isArray(biasGrid)) display(html`

Available after the grid above has been computed.

`); else { // Exact expected shots as the edge bias grows, at the spacing set by the slider above. const flat = humanWeights(0, 0); const assumes = shotsByLayout(weightedChooser(flat)); const rows = d3.range(16).flatMap((i) => { const a = i / 10, human = humanWeights(a, spacing); const knows = shotsByLayout(weightedChooser(human)); return [ {a, player: "assumes uniform", opponent: "Opponent follows the prior", shots: expectedShots(assumes, human)}, {a, player: "knows the prior", opponent: "Opponent follows the prior", shots: expectedShots(knows, human)}, {a, player: "assumes uniform", opponent: "Opponent places uniformly", shots: expectedShots(assumes, flat)}, {a, player: "knows the prior", opponent: "Opponent places uniformly", shots: expectedShots(knows, flat)} ]; }); const plot = display(Plot.plot({ title: "Expected shots to sink both ships, by edge bias", subtitle: `Two-ship fleet, exact, spacing b = ${spacing} (set by the slider). In the right panel the opponent is uniform, so the line for the player who assumes uniform is flat.`, width: 820, x: {label: "Edge bias a"}, y: {label: "Expected shots", grid: true, domain: [0, 35]}, fx: {label: null}, color: {legend: true, domain: ["assumes uniform", "knows the prior"]}, marks: [ Plot.lineY(rows, {x: "a", y: "shots", stroke: "player", fx: "opponent", tip: true}), Plot.ruleY([0]) ] })); }62:T8db,**Results.** These are for the two-ship fleet. Each number is an average over all 20,336 layouts, so there is no sampling error. Figures are for spacing b = 2 unless stated. *When the opponent follows the prior* - Knowing the prior reduces the expected number of shots by 2.0 at a = 0.2, by 6.7 at a = 0.5 (22.5 versus 29.2), and by 14 at a = 1 (16.9 versus 30.9). - The player who assumes uniform placement needs more shots as the habit strengthens: 25.6 against a uniform opponent, 27.3 at a = 0.2, and about 31 for a ≥ 1. Part of the reason may be its opening shot, D4, in the middle of the board. Under the prior, border squares are more likely to hold a ship than D4: at a = 0.2, 9.4% for D1, G1, A4 and the other squares equivalent by symmetry versus 7.4% for D4, and at a = 0.5, 14% versus 5%. We did not test other explanations. *When the opponent places uniformly* - The player who expects edge placements needs more shots than the one who assumes uniform placement: 1.9 more at a = 0.2, 3.0 more at a = 0.5, and about 5 more for a ≥ 1. - Putting the two cases side by side at b = 2: at a = 0.1 the loss against a uniform opponent is slightly larger than the saving against a prior-following one (1.0 versus 0.9 shots), at a = 0.2 they are about equal (1.9 versus 2.0), and from a = 0.3 the saving is larger. This assumes the player knows which kind of opponent it faces. With real uncertainty, the better assumption depends on how likely each kind of opponent is. *Spacing* - Spacing has a small effect in this model. With a = 0, knowing b = 3 saves 0.8 shots, and costs 0.5 shots if the opponent is uniform. With a strong edge habit (a = 1), the saving is 13.7 shots at b = 0 and 14.1 shots at b = 2. Under uniform placement only about 17% of layouts have touching ships, so there is little for a spacing habit to rule out. *Limits* - The player who knows the prior is given the exact weights. A real player would have to estimate them from experience, so these savings are what this rule achieves in the best case. - The weights are an invented model and the range of a shown here is not calibrated to real play. - The standard five-ship fleet has not been checked. The exact method does not extend to it, because its layouts cannot be listed.63:Tc9c,## What we learned - **Shoot where a ship is most likely to be.** List every ship layout that fits the shots so far, then fire at the square covered by the most of them. At the start that is the middle of the board. After a hit it is the squares next to the hit. (People intuitively do this already.) - **Greedy play needs far fewer shots than random shooting.** On the two-ship fleet, the exact averages are 25.6 shots for the probability rule and 25.8 for the information rule, against 88.4 for random shooting. On the standard fleet, longer sampled runs (300 and 400 paired games) gave about 45 shots for the greedy rules against about 96 for random. - **The two greedy rules are close.** On two ships, the information rule needs 0.22 more shots on average than the probability rule. It needs fewer on 21% of layouts and more on 38%. On the standard fleet, a sampled run put the gap at 1.1 ± 1.1 shots, which is not clearly different from zero; the standard-fleet Run button reproduces it. - **A two-shot lookahead did not help on two ships.** Compared with the probability rule, the hits lookahead needs 0.14 more shots on average and the information lookahead 0.12 more (exact, all layouts). The median, 95th percentile and worst case are the same for all four rules. - **Knowing an opponent's placement habits can save shots, in this model (two ships).** If opponents favour the border, a player who knows this needs 2 fewer shots at a mild habit (a = 0.2), 7 fewer at a = 0.5, and 14 fewer at a = 1 than a player who assumes uniform placement, and the best first shot moves from the middle to the border. If the opponent actually places uniformly, the same assumption costs about 2 to 5 shots. A spacing habit alone has a small effect. The habit model is invented, not measured from real players, and the player is given its exact weights. - **None of these rules is shown to be optimal.** Each is greedy against the exact (or well-sampled) posterior for an assumed opponent, and even the two-shot rules look only a couple of shots ahead. ## Open questions - Does a two-shot lookahead help on the standard fleet? It was tested only on two ships, where exact answers exist. A longer lookahead, or choosing shots to minimize the expected number of shots directly, was not tried; the information lookahead alone takes about 15 s with the exact method on two ships. - Is the information rule worse than the probability rule on the standard fleet, and if so why? The sampled gap (1.1 ± 1.1 shots) is not clearly different from zero. One possible cause is noise: its score sums squares of sampled weights, and 1,500 samples may be too few. - How do real players place ships? Our edge and spacing weights are invented. Measured placements would replace them, and a player could estimate the habit from earlier games instead of being given it. - Do the habit effects carry over to the standard fleet? The exact tree is not feasible there, so the sampler would need to carry the prior weights, and strongly constrained priors will shrink its effective sample size. - The sampler is validated only on the two-ship fleet, where exact answers exist. The standard-fleet numbers rest on the same code, not on an independent check.64:[] 48:{"id":"3ef7d5a2a32c5b4d","slug":"battleship","title":"Battleship","thumbnail":"72fa2525b1c560688ec272fd061984f897cae16143cafa89f68b68f94e0a8749","access_level":"public","create_time":"$D2023-11-23T07:33:08.033Z","update_time":"$D2026-10-21T20:18:01.276Z","view_time":null,"first_public_time":"$D2023-11-29T22:12:04.836Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"31b136fdb993b00a","login":"visnup","name":"Visnu Pitiyanuvath","avatar_url":"https://avatars-next.observableusercontent.com/b847c4c49993b1df7599d355f47dc0ad9c2dcf43439ce9e8f3410e6368b3aac9","tier":"pro_2026","bio":"","followed_by_you":false,"follows_you":false},"version":838,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"dbf69c13a14d2f62","login":"visnup","name":"Visnu Pitiyanuvath","avatar_url":"https://avatars-next.observableusercontent.com/b847c4c49993b1df7599d355f47dc0ad9c2dcf43439ce9e8f3410e6368b3aac9","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"dbf69c13a14d2f62","login":"visnup","name":"Visnu Pitiyanuvath","avatar_url":"https://avatars-next.observableusercontent.com/b847c4c49993b1df7599d355f47dc0ad9c2dcf43439ce9e8f3410e6368b3aac9","tier":null,"role":"editor"}],"comments":[{"id":"889bcc5ca03b1b92","reply_to_id":null,"content":"why is symmetry broken? 🫨","create_time":"$D2023-12-01T08:16:07.225Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}},{"id":"8a592004b165057c","reply_to_id":"889bcc5ca03b1b92","content":"because there's an explicit patrol boat taking up the two pegs at H7 and H8, so the heat map is now everywhere else the 4 peg battleship could fit.","create_time":"$D2023-12-01T09:01:59.594Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"dbf69c13a14d2f62","login":"visnup","name":"Visnu Pitiyanuvath","avatar_url":"https://avatars-next.observableusercontent.com/b847c4c49993b1df7599d355f47dc0ad9c2dcf43439ce9e8f3410e6368b3aac9","tier":null}},{"id":"bafc968fcf3c1552","reply_to_id":"889bcc5ca03b1b92","content":"🫡","create_time":"$D2023-12-01T09:09:45.997Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"6085998240bbe5d6","slug":"games/2","title":"Games","owner":{"id":"31b136fdb993b00a","login":"visnup","name":"Visnu Pitiyanuvath"}},"type":"notebook","body":{"titling":"auto","title":"Battleship","cells":[{"id":383,"value":"# Battleship\n\nWhat does *perfect* play (guessing shots) look like?\n\nThe map on the right shows each square’s chance of holding a ship, estimated from shots input on the left.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"$4c","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":385,"value":"$4d","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"# How it works\n\n**Assumptions**\n\n- 10×10 board. Ships are straight (horizontal or vertical), may touch, and never overlap.\n- The fleet is Hasbro’s 5, 4, 3, 3, 2; we start smaller so we can enumerate everything.\n- Each shot reports *miss*, *hit*, or *sunk* (and which ship).\n- The goal is the fewest shots to sink the fleet. Each shot may depend only on the shots so far.\n- The opponent picks uniformly at random from all legal *whole-fleet* layouts. This is probably the least realistic assumption; a later section relaxes it for the two-ship fleet.\n\nThe map above comes from the method below. We build it up from one ship, then two ships (where every layout can be listed and rules can be compared exactly), then sample layouts for the full fleet (where rules are compared by simulation).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":363,"value":"## One ship\n\nStart with a single 4-hole ship. Count how many of its placements cover each square. Squares near the middle are covered by more placements than squares near the edge, because fewer placements fit against a border.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"const N = 10;\n\n// All placements of a straight ship of length L, as arrays of cell indices (y * N + x).\nfunction shipPlacements(L) {\n const out = [];\n for (const [dx, dy] of [[1, 0], [0, 1]])\n for (let y = 0; y + (L - 1) * dy < N; y++)\n for (let x = 0; x + (L - 1) * dx < N; x++)\n out.push(Array.from({length: L}, (_, i) => (y + dy * i) * N + x + dx * i));\n return out;\n}","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":364,"value":"const onePlacements = shipPlacements(4);\nconst oneCounts = d3.range(N * N).map((c) => ({\n x: c % N, y: Math.floor(c / N), n: onePlacements.filter((p) => p.includes(c)).length\n}));\n\ndisplay(Plot.plot({\n title: \"One 4-hole ship: placements covering each square\",\n subtitle: `${onePlacements.length} placements in all. A corner is covered by ${oneCounts[0].n}, the center by ${d3.max(oneCounts, (d) => d.n)}.`,\n aspectRatio: 1,\n width: 320,\n x: {tickFormat: (i) => \"ABCDEFGHIJ\"[i], axis: \"top\", label: null},\n y: {tickFormat: (i) => i + 1, label: null, domain: d3.range(N)},\n color: {scheme: \"blues\"},\n marks: [\n Plot.cell(oneCounts, {x: \"x\", y: \"y\", fill: \"n\", inset: 0.5}),\n Plot.text(oneCounts, {x: \"x\", y: \"y\", text: \"n\", fill: \"black\", stroke: \"white\"})\n ]\n}));","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"## Two ships, exactly\n\nAdd a 3-hole ship and list every legal *layout* (a placement for each ship, no overlap). A square’s chance of holding a ship is the share of layouts that cover it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"const fleet = [4, 3];\nconst placementsByShip = fleet.map(shipPlacements);\nconst totalHoles = d3.sum(fleet);\n\n// Every legal layout: one placement index per ship, no overlaps.\nconst allConfigs = (() => {\n const out = [];\n const occ = new Uint8Array(N * N);\n const choice = [];\n (function rec(k) {\n if (k === fleet.length) return void out.push(choice.slice());\n placementsByShip[k].forEach((cells, j) => {\n if (cells.some((c) => occ[c])) return;\n cells.forEach((c) => (occ[c] = 1));\n choice.push(j);\n rec(k + 1);\n choice.pop();\n cells.forEach((c) => (occ[c] = 0));\n });\n })(0);\n return out;\n})();\n\n// shipAt[i][c] = index of the ship covering cell c in layout i, or -1.\nconst shipAt = allConfigs.map((cfg) => {\n const a = new Int8Array(N * N).fill(-1);\n cfg.forEach((j, k) => placementsByShip[k][j].forEach((c) => (a[c] = k)));\n return a;\n});\n","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"## Shots are feedback\n\nEach shot reports *miss*, *hit*, or *sunk ship k*. A layout is **consistent** with the shots so far if it would have reported exactly the same. Keep only those.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":367,"value":"// Feedback for shooting cell c in layout i, given the cells already shot (mask):\n// -1 = miss, 0 = hit, k + 1 = hit that sinks ship k.\nfunction outcomeOf(i, c, mask) {\n const k = shipAt[i][c];\n if (k < 0) return -1;\n for (const d of placementsByShip[k][allConfigs[i][k]]) if (d !== c && !mask[d]) return 0;\n return k + 1;\n}\n\n// Does layout i produce exactly the feedback in `history` (a list of {c, out})?\nfunction replayOK(i, history) {\n const mask = new Uint8Array(N * N);\n return history.every(({c, out}) => { mask[c] = 1; return outcomeOf(i, c, mask) === out; });\n}","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":390,"value":"For each square, tally the surviving layouts by what shooting there would report. The share that put a ship there is its **P(ship)**. The tallies also give the **expected layouts left** after the shot, ${tex`\\sum_i n_i^2 / n`} over the report groups (${tex`n_i`} = layouts in group ${tex`i`}, ${tex`n`} = all surviving layouts). It is small when a shot splits the layouts evenly.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"$4e","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":392,"value":"Heatmaps show each square’s P(ship) in percent. A white dot is a miss, a red dot a hit, and the orange ring marks the most likely square.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":393,"value":"$4f","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":368,"value":"const examples = [\n {title: \"No shots yet\", history: []},\n {title: \"After a miss at D4\", history: [{c: 33, out: -1}]},\n {title: \"After a hit at D4\", history: [{c: 33, out: 0}]}\n];\ndisplay(html`

${\n examples.map((e) => heatmapExact(e.history, {title: e.title, legend: false, width: 320}))\n}

`);","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":369,"value":"Each shot just filters the list. D4 lies in 1,880 of the 20,336 layouts (9.2%). A miss discards those and the odds drift to the next most-covered squares; a hit keeps only those and piles probability onto D4’s neighbours.\n\n## Two greedy rules\n\n- **Probability:** shoot the square most likely to hold a ship.\n- **Information:** shoot where the expected layouts left is smallest. Ties go to the likelier hit; otherwise it would happily “test” squares it already knows are ships.\n\nUniformly random shots are the baseline. With hit/miss feedback alone the two rules rank squares almost identically; sunk announcements are what can separate them.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":370,"value":"// A policy picks the next cell from the surviving layouts (indices) and the mask of cells already shot.\n// (Random shooting needs no policy here: its results have a closed form, see \"Which rule wins?\".)\nconst policies = {\n probability(alive, mask) {\n const {occ} = scoreCells(alive, mask);\n return d3.least(d3.range(N * N).filter((c) => !mask[c]), (c) => -occ[c]);\n },\n information(alive, mask) {\n const st = scoreCells(alive, mask);\n let best = -1, bestScore = Infinity, bestOcc = -1;\n for (let c = 0; c < N * N; c++) {\n if (mask[c]) continue;\n const s = expectedLeft(st, c) * st.n; // integer-valued, so ties are exact\n if (s < bestScore || (s === bestScore && st.occ[c] > bestOcc)) { best = c; bestScore = s; bestOcc = st.occ[c]; }\n }\n return best;\n }\n};","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":371,"value":"## Which rule wins?\n\nWe compare the two greedy rules with random shooting on the two-ship fleet, against an opponent who picks a layout uniformly at random. Instead of simulating games, we compute each rule's results exactly.\n\n**Method.** A rule's choice of shot depends only on the shots and reports so far. Playing against every possible layout at once is therefore a decision tree: choose a shot for the whole set of layouts that are still possible, split that set by the report (miss, hit, or sunk ship), and repeat within each group. Each layout ends at a definite number of shots, so the rule's distribution of shots over all 20,336 layouts, and its mean, are exact. One tree takes under a second for the greedy rules. Random shooting has a closed form instead: the shots needed are the position of the last of the seven ship squares in a random order of the 100 squares, and the mean of that position is ${tex`7 \\cdot 101 / 8 = 88.375`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"$50","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"$51","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"$52","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"$53","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":377,"value":"$54","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"$55","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"## The standard fleet: greedy vs. random\n\nSame experiment with the real fleet, using 1,500 posterior samples per shot. Each game is played by all three rules on the same layout. Set the number of games, then click **Run** (clicking again restarts it).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"$56","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":380,"value":"const stdGamesEl = Inputs.range([20, 500], {value: 30, step: 10, label: \"Games per rule\"});\ndisplay(stdGamesEl);\nconst stdRun = view(Inputs.button(\"Run standard-fleet simulation\"));","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":382,"value":"$57","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"$58","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":409,"value":"## Looking two shots ahead\n\nThe greedy rules judge each shot as if it were the last one fired. A **two-shot lookahead** scores a shot together with the best follow-up, taking into account each report the shot could produce (miss, hit, sunk). There are two versions:\n\n- **Hits:** choose the shot that maximizes the expected number of hits over this shot and the best next one.\n- **Information:** choose the shot that minimizes the expected number of layouts left after this shot and the best next one.\n\nBoth are computed exactly on the two-ship fleet with the same decision-tree method, and compared with the one-shot rules against a uniform opponent.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"$59","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"// Play one game with any chooser fn(alive, mask) against layout trueIdx; memoize by shot history (the choice is deterministic).\n// Used to check the exact decision-tree results against ordinary game-by-game play.\nfunction playWith(fn, trueIdx, cache) {\n const mask = new Uint8Array(N * N), history = [];\n let alive = d3.range(allConfigs.length), holes = totalHoles, key = \"\";\n while (holes > 0) {\n let c = cache.get(key);\n if (c === undefined) { c = fn(alive, mask); cache.set(key, c); }\n mask[c] = 1;\n const out = outcomeOf(trueIdx, c, mask);\n history.push({c, out});\n if (out !== -1) holes--;\n key += `${c}:${out},`;\n alive = alive.filter((i) => outcomeOf(i, c, mask) === out);\n }\n return history;\n}","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":407,"value":"$5a","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":434,"value":"const lookRun = view(Inputs.button(\"Compute lookahead comparison (about 20 s)\"));","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"$5b","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":433,"value":"$5c","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":411,"value":"On the two-ship fleet, neither lookahead beats the one-shot probability rule on average. Compared with it, the information lookahead needs 0.12 more shots, the hits lookahead 0.14 more, and the one-shot information rule 0.22 more. These are exact averages over all layouts, not estimates, but they are small next to the spread. Each alternative needs fewer shots than the probability rule on some layouts (3,044 to 5,649 of 20,336) and more on others (6,018 to 7,641). The median, 95th percentile and worst case (25, 41 and 52 shots) are the same for all four rules.\n\nWhy the lookaheads do slightly worse is not clear. Both optimize a proxy for the number of shots (hits within two shots, or layouts remaining after two shots) rather than the number of shots itself, but we did not test whether that explains it. A longer lookahead, or choosing shots to minimize the expected number of shots directly, was not tried. The standard fleet was not tested either, because its layouts cannot be listed.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":412,"value":"$5d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"$5e","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"The sliders set ${tex`a`} (edge bias) and ${tex`b`} (spacing) for the maps below and for the second chart in the results. The maps show each square's chance of holding a ship before any shot is fired, with the same color scale for both opponents.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":414,"value":"// Sliders for the prior. They drive the opening maps below and the spacing used by the second results chart.\nconst edgeEl = Inputs.range([0, 1.5], {value: 0.2, step: 0.1, label: \"Edge bias (a)\"});\nconst spaceEl = Inputs.range([0, 4], {value: 2, step: 0.5, label: \"Spacing (b)\"});\nconst edgeBias = view(edgeEl);\nconst spacing = view(spaceEl);","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":415,"value":"$5f","pinned":false,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":427,"value":"### Exact results over a grid of habit strengths\n\nWe use the exact decision-tree method from \"Which rule wins?\" again, now weighting layouts by the opponent's prior: a player's expected number of shots is the average of its shot counts over all 20,336 layouts, each weighted by its prior weight. There is no sampling error. One tree takes about 0.1 s, so we can compute it for a whole grid of values of ${tex`a`} and ${tex`b`}.\n\nTwo players are compared. Both use the one-shot probability rule from earlier, and they differ only in which layouts they treat as more likely:\n\n- **Assumes uniform** treats every layout that fits the shots so far as equally likely. Its shots do not depend on the opponent's actual habits.\n- **Knows the prior** weights each layout that fits the shots by the opponent's prior weight. It is given the exact weights, which a real player would not have.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":435,"value":"const biasRun = view(Inputs.button(\"Compute exact results over the grid of habits (about 15 s)\"));","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"// Exact expected shots over a grid of priors: edge bias a = 0 to 1.5, spacing b = 0 to 4.\n// Runs only after the button above is clicked.\nconst biasGrid = (async function* () {\n if (!biasRun) return yield null;\n yield \"running\";\n await new Promise((resolve) => setTimeout(resolve, 50));\n const flat = humanWeights(0, 0);\n const assumes = shotsByLayout(weightedChooser(flat));\n const rows = [];\n for (const b of [0, 1, 2, 3, 4]) {\n for (let i = 0; i <= 15; i++) {\n const a = i / 10, human = humanWeights(a, b);\n const knows = shotsByLayout(weightedChooser(human));\n rows.push({\n a, b,\n assumesVsUniform: expectedShots(assumes, flat), assumesVsHuman: expectedShots(assumes, human),\n knowsVsUniform: expectedShots(knows, flat), knowsVsHuman: expectedShots(knows, human)\n });\n }\n }\n yield rows;\n})();","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"$60","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":426,"value":"$61","pinned":true,"hidden":false,"mode":"js","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":421,"value":"$62","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":387,"value":"$63","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W64","stdlib":"2"}} 24:null