1export type GameStatus = "playing" | "won" | "lost";23export type Coordinate = {4 row: number;5 col: number;6};78export type GameState = {9 id: string;10 seed: string;11 width: number;12 height: number;13 mines: Uint8Array;14 revealed: Uint8Array;15 initialRevealed: Uint8Array;16 flags: Uint8Array;17 status: GameStatus;18 revision: number;19 explodedIndex: number | null;20 certifiedNoGuess: boolean;21 createdAt: string;22 updatedAt: string;23 slug?: string;24};2526export type BatchAction = {27 reveal: Coordinate[];28 flag: Coordinate[];29 unflag: Coordinate[];30 intent: string;31};3233export type MoveEvent = {34 revision: number;35 intent: string;36 submittedCount: number;37 revealed: Coordinate[];38 revealedValues: Array<Coordinate & { value: string }>;39 flagged: Coordinate[];40 unflagged: Coordinate[];41 exploded: Coordinate | null;42 status: GameStatus;43 createdAt: string;44};4546export type Observation = {47 game_id: string;48 revision: number;49 status: GameStatus;50 width: number;51 height: number;52 mine_count: number;53 revealed_count: number;54 flagged_count: number;55 remaining_safe_cells: number;56 certified_no_guess: boolean;57 coordinate_system: string;58 legend: Record<string, string>;59 rows: string[];60};6162export type AgentPosition = {63 game_id: string;64 revision: number;65 status: GameStatus;66 width: number;67 height: number;68 mine_count: number;69 flagged_count: number;70 remaining_safe_cells: number;71 certified_no_guess: boolean;72 encoding: {73 cell: string;74 deltas: string;75 clue_code: string;76 };77 frontier_deltas: number[];78 clue_deltas: number[];79 flagged_deltas: number[];80 exploded_cell?: number;81};8283const NEIGHBOR_OFFSETS = [84 [-1, -1],85 [-1, 0],86 [-1, 1],87 [0, -1],88 [0, 1],89 [1, -1],90 [1, 0],91 [1, 1],92] as const;9394function hashSeed(seed: string): number {95 let hash = 2166136261;96 for (let index = 0; index < seed.length; index += 1) {97 hash ^= seed.charCodeAt(index);98 hash = Math.imul(hash, 16777619);99 }100 return hash >>> 0 || 0x9e3779b9;101}102103function createRandom(seed: string): () => number {104 let state = hashSeed(seed);105 return () => {106 state ^= state << 13;107 state ^= state >>> 17;108 state ^= state << 5;109 return (state >>> 0) / 0x1_0000_0000;110 };111}112113export function indexOf(width: number, coordinate: Coordinate): number {114 return coordinate.row * width + coordinate.col;115}116117export function coordinateOf(width: number, index: number): Coordinate {118 return { row: Math.floor(index / width), col: index % width };119}120121function neighbors(width: number, height: number, index: number): number[] {122 const { row, col } = coordinateOf(width, index);123 const values: number[] = [];124 for (const [rowOffset, colOffset] of NEIGHBOR_OFFSETS) {125 const nextRow = row + rowOffset;126 const nextCol = col + colOffset;127 if (nextRow >= 0 && nextRow < height && nextCol >= 0 && nextCol < width) {128 values.push(nextRow * width + nextCol);129 }130 }131 return values;132}133134export function adjacentMineCount(state: Pick<GameState, "width" | "height" | "mines">, index: number): number {135 return neighbors(state.width, state.height, index).reduce(136 (total, neighbor) => total + (state.mines[neighbor] ?? 0),137 0,138 );139}140141function revealFlood(state: GameState, startingIndexes: Iterable<number>): number[] {142 const queue = [...startingIndexes];143 const newlyRevealed: number[] = [];144 const queued = new Uint8Array(state.width * state.height);145 for (const index of queue) queued[index] = 1;146147 for (let cursor = 0; cursor < queue.length; cursor += 1) {148 const index = queue[cursor];149 if (index === undefined || state.revealed[index] === 1 || state.flags[index] === 1 || state.mines[index] === 1) {150 continue;151 }152 state.revealed[index] = 1;153 newlyRevealed.push(index);154 if (adjacentMineCount(state, index) !== 0) continue;155 for (const neighbor of neighbors(state.width, state.height, index)) {156 if (queued[neighbor] === 0) {157 queued[neighbor] = 1;158 queue.push(neighbor);159 }160 }161 }162 return newlyRevealed;163}164165function countBits(values: Uint8Array): number {166 let total = 0;167 for (const value of values) total += value;168 return total;169}170171function validateCoordinates(state: GameState, coordinates: Coordinate[]): void {172 if (coordinates.length > 8192) throw new Error("A batch may contain at most 8192 cells per action type.");173 for (const coordinate of coordinates) {174 if (!Number.isInteger(coordinate.row) || !Number.isInteger(coordinate.col)) {175 throw new Error("Coordinates must use integer row and col values.");176 }177 if (coordinate.row < 0 || coordinate.row >= state.height || coordinate.col < 0 || coordinate.col >= state.width) {178 throw new Error(`Coordinate (${coordinate.row}, ${coordinate.col}) is outside the board.`);179 }180 }181}182183function uniqueIndexes(state: GameState, coordinates: Coordinate[]): number[] {184 return [...new Set(coordinates.map((coordinate) => indexOf(state.width, coordinate)))];185}186187export function countSubmittedTiles(action: BatchAction): number {188 return new Set(189 [...action.reveal, ...action.flag, ...action.unflag].map((coordinate) => `${coordinate.row}:${coordinate.col}`),190 ).size;191}192193export function applyBatch(state: GameState, action: BatchAction, now = new Date().toISOString()): MoveEvent {194 if (state.status !== "playing") throw new Error(`Game is already ${state.status}.`);195 validateCoordinates(state, action.reveal);196 validateCoordinates(state, action.flag);197 validateCoordinates(state, action.unflag);198199 const revealIndexes = uniqueIndexes(state, action.reveal);200 const flagIndexes = uniqueIndexes(state, action.flag);201 const unflagIndexes = uniqueIndexes(state, action.unflag);202 const flagged: number[] = [];203 const unflagged: number[] = [];204 const revealed: number[] = [];205 let explodedIndex: number | null = null;206207 for (const index of unflagIndexes) {208 if (state.flags[index] === 1) {209 state.flags[index] = 0;210 unflagged.push(index);211 }212 }213 for (const index of flagIndexes) {214 if (state.revealed[index] === 0 && state.flags[index] === 0) {215 state.flags[index] = 1;216 flagged.push(index);217 }218 }219 for (const index of revealIndexes) {220 if (state.flags[index] === 1 || state.revealed[index] === 1) continue;221 if (state.mines[index] === 1) {222 explodedIndex = index;223 state.explodedIndex = index;224 state.status = "lost";225 break;226 }227 revealed.push(...revealFlood(state, [index]));228 }229230 if (state.status === "playing") {231 const safeCells = state.width * state.height - countBits(state.mines);232 if (countBits(state.revealed) === safeCells) state.status = "won";233 }234 state.revision += 1;235 state.updatedAt = now;236237 return {238 revision: state.revision,239 intent: action.intent,240 submittedCount: countSubmittedTiles(action),241 revealed: revealed.map((index) => coordinateOf(state.width, index)),242 revealedValues: revealed.map((index) => ({243 ...coordinateOf(state.width, index),244 value: String(adjacentMineCount(state, index)),245 })),246 flagged: flagged.map((index) => coordinateOf(state.width, index)),247 unflagged: unflagged.map((index) => coordinateOf(state.width, index)),248 exploded: explodedIndex === null ? null : coordinateOf(state.width, explodedIndex),249 status: state.status,250 createdAt: now,251 };252}253254function makeCandidate(width: number, height: number, density: number, seed: string, attempt: number): GameState {255 const total = width * height;256 const mines = new Uint8Array(total);257 const random = createRandom(`${seed}:${attempt}`);258 const start = { row: Math.floor(height / 2), col: Math.floor(width / 2) };259 const protectedIndexes = new Set<number>();260 for (let row = start.row - 1; row <= start.row + 1; row += 1) {261 for (let col = start.col - 1; col <= start.col + 1; col += 1) {262 if (row >= 0 && row < height && col >= 0 && col < width) protectedIndexes.add(row * width + col);263 }264 }265 const candidates = Array.from({ length: total }, (_, index) => index).filter((index) => !protectedIndexes.has(index));266 for (let index = candidates.length - 1; index > 0; index -= 1) {267 const swapIndex = Math.floor(random() * (index + 1));268 const current = candidates[index];269 const swap = candidates[swapIndex];270 if (current !== undefined && swap !== undefined) {271 candidates[index] = swap;272 candidates[swapIndex] = current;273 }274 }275 const mineCount = Math.floor(total * density);276 for (let index = 0; index < mineCount; index += 1) {277 const mineIndex = candidates[index];278 if (mineIndex !== undefined) mines[mineIndex] = 1;279 }280 const now = new Date().toISOString();281 const state: GameState = {282 id: "",283 seed,284 width,285 height,286 mines,287 revealed: new Uint8Array(total),288 initialRevealed: new Uint8Array(total),289 flags: new Uint8Array(total),290 status: "playing",291 revision: 0,292 explodedIndex: null,293 certifiedNoGuess: false,294 createdAt: now,295 updatedAt: now,296 };297 revealFlood(state, [indexOf(width, start)]);298 state.initialRevealed = state.revealed.slice();299 return state;300}301302function solveByVisibleDeductions(original: GameState): boolean {303 const state: GameState = {304 ...original,305 mines: original.mines.slice(),306 revealed: original.revealed.slice(),307 flags: new Uint8Array(original.flags.length),308 };309 const totalSafe = state.width * state.height - countBits(state.mines);310311 for (let round = 0; round < state.width * state.height; round += 1) {312 const safe = new Set<number>();313 const mines = new Set<number>();314 for (let index = 0; index < state.revealed.length; index += 1) {315 if (state.revealed[index] !== 1) continue;316 const adjacent = neighbors(state.width, state.height, index);317 const hidden = adjacent.filter((neighbor) => state.revealed[neighbor] === 0 && state.flags[neighbor] === 0);318 const flagged = adjacent.reduce((total, neighbor) => total + (state.flags[neighbor] ?? 0), 0);319 const remaining = adjacentMineCount(state, index) - flagged;320 if (hidden.length > 0 && remaining === 0) hidden.forEach((neighbor) => safe.add(neighbor));321 if (hidden.length > 0 && remaining === hidden.length) hidden.forEach((neighbor) => mines.add(neighbor));322 }323 if (safe.size === 0 && mines.size === 0) break;324 for (const index of mines) state.flags[index] = 1;325 revealFlood(state, safe);326 if (countBits(state.revealed) === totalSafe) return true;327 }328 return countBits(state.revealed) === totalSafe;329}330331export function createNoGuessGame(options: {332 id: string;333 seed: string;334 width: number;335 height: number;336 density: number;337 maxAttempts?: number;338}): GameState {339 const maxAttempts = options.maxAttempts ?? 200;340 for (let attempt = 0; attempt < maxAttempts; attempt += 1) {341 const state = makeCandidate(options.width, options.height, options.density, options.seed, attempt);342 if (solveByVisibleDeductions(state)) {343 state.id = options.id;344 state.certifiedNoGuess = true;345 return state;346 }347 }348 throw new Error(`Unable to generate a no-guess ${options.width}x${options.height} board for this seed.`);349}350351export function toObservation(state: GameState, revealMines = false): Observation {352 const rows: string[] = [];353 for (let row = 0; row < state.height; row += 1) {354 let value = "";355 for (let col = 0; col < state.width; col += 1) {356 const index = row * state.width + col;357 if (state.explodedIndex === index) value += "X";358 else if (state.flags[index] === 1) value += "F";359 else if (state.revealed[index] === 1) value += String(adjacentMineCount(state, index));360 else if (revealMines && state.mines[index] === 1) value += "*";361 else value += "#";362 }363 rows.push(value);364 }365 const mineCount = countBits(state.mines);366 const revealedCount = countBits(state.revealed);367 return {368 game_id: state.id,369 revision: state.revision,370 status: state.status,371 width: state.width,372 height: state.height,373 mine_count: mineCount,374 revealed_count: revealedCount,375 flagged_count: countBits(state.flags),376 remaining_safe_cells: state.width * state.height - mineCount - revealedCount,377 certified_no_guess: state.certifiedNoGuess,378 coordinate_system: "Zero-based rows increase downward; zero-based columns increase rightward.",379 legend: {380 "#": "hidden",381 F: "flagged",382 "0-8": "revealed clue",383 X: "exploded mine",384 "*": "mine revealed after loss",385 },386 rows,387 };388}389390export function toInitialObservation(state: GameState): Observation {391 return toObservation({392 ...state,393 revealed: state.initialRevealed,394 flags: new Uint8Array(state.flags.length),395 status: "playing",396 revision: 0,397 explodedIndex: null,398 });399}400401export function toAgentPosition(state: GameState): AgentPosition {402 const frontier = new Set<number>();403 const clues: Array<{ cell: number; clue: number }> = [];404405 for (let index = 0; index < state.revealed.length; index += 1) {406 if (state.revealed[index] !== 1) continue;407 const adjacent = neighbors(state.width, state.height, index);408 const hidden = adjacent409 .filter((neighbor) => state.revealed[neighbor] === 0 && state.flags[neighbor] === 0)410 .sort((left, right) => left - right);411 if (hidden.length === 0) continue;412 hidden.forEach((cell) => frontier.add(cell));413 clues.push({ cell: index, clue: adjacentMineCount(state, index) });414 }415416 const frontierCells = [...frontier].sort((left, right) => left - right);417 const flaggedCells: number[] = [];418 for (let index = 0; index < state.flags.length; index += 1) {419 if (state.flags[index] === 1) flaggedCells.push(index);420 }421 const observation = toObservation(state);422 const deltaEncode = (cells: number[]): number[] => {423 let previous = 0;424 return cells.map((cell) => {425 const delta = cell - previous;426 previous = cell;427 return delta;428 });429 };430 let previousClueCell = 0;431 const clueDeltas = clues432 .sort((left, right) => left.cell - right.cell)433 .map(({ cell, clue }) => {434 const code = (cell - previousClueCell) * 9 + clue;435 previousClueCell = cell;436 return code;437 });438 return {439 game_id: state.id,440 revision: state.revision,441 status: state.status,442 width: state.width,443 height: state.height,444 mine_count: observation.mine_count,445 flagged_count: observation.flagged_count,446 remaining_safe_cells: observation.remaining_safe_cells,447 certified_no_guess: state.certifiedNoGuess,448 encoding: {449 cell: "cell = row * width + col; row = floor(cell / width); col = cell % width",450 deltas: "decode each *_deltas array by cumulative sum to recover sorted absolute cell IDs",451 clue_code: "for each clue_deltas code: cell += floor(code / 9), clue = code % 9",452 },453 frontier_deltas: deltaEncode(frontierCells),454 clue_deltas: clueDeltas,455 flagged_deltas: deltaEncode(flaggedCells),456 ...(state.explodedIndex === null ? {} : { exploded_cell: state.explodedIndex }),457 };458}459460export function cellsToCoordinates(state: Pick<GameState, "width" | "height">, cells: number[]): Coordinate[] {461 const total = state.width * state.height;462 return cells.map((cell) => {463 if (!Number.isInteger(cell) || cell < 0 || cell >= total) {464 throw new Error(`Cell ${cell} is outside the board.`);465 }466 return coordinateOf(state.width, cell);467 });468}469470export function encodeBits(values: Uint8Array): string {471 let binary = "";472 for (const value of values) binary += String.fromCharCode(value);473 return btoa(binary);474}475476export function decodeBits(value: string): Uint8Array {477 const binary = atob(value);478 const values = new Uint8Array(binary.length);479 for (let index = 0; index < binary.length; index += 1) values[index] = binary.charCodeAt(index);480 return values;481}482483export function countMines(state: GameState): number {484 return countBits(state.mines);485}