200 lines
7.3 KiB
JavaScript
200 lines
7.3 KiB
JavaScript
// Server-side Scrabble dictionary + AI move generator.
|
||
//
|
||
// Scoring/extraction is imported from the SAME pure modules the browser uses
|
||
// (no Phaser/DOM deps there) so the AI ranks moves exactly as the client scores
|
||
// them. Move generation is a line-scan DFS over a trie: for every line and every
|
||
// legal word-start we walk the trie, consuming board tiles or placing rack tiles
|
||
// (with cross-checks), recording each terminal word that connects to the board.
|
||
|
||
import { scoreMove } from '../../public/src/games/scrabble/ScrabbleLogic.js';
|
||
import { BOARD_SIZE, RACK_SIZE, BLANK, CENTER } from '../../public/src/games/scrabble/ScrabbleTiles.js';
|
||
|
||
let TRIE = null;
|
||
let WORD_SET = null;
|
||
|
||
export function initScrabbleDictionary(words) {
|
||
WORD_SET = words instanceof Set ? words : new Set(words);
|
||
TRIE = { children: Object.create(null), terminal: false };
|
||
for (const w of WORD_SET) {
|
||
let node = TRIE;
|
||
for (const ch of w) {
|
||
node = node.children[ch] || (node.children[ch] = { children: Object.create(null), terminal: false });
|
||
}
|
||
node.terminal = true;
|
||
}
|
||
}
|
||
|
||
export function isValidWord(word) {
|
||
return WORD_SET?.has(word) ?? false;
|
||
}
|
||
|
||
export function dictionaryReady() {
|
||
return TRIE !== null;
|
||
}
|
||
|
||
// ── Helpers ───────────────────────────────────────────────────────────────────
|
||
|
||
const LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');
|
||
|
||
function rackCounts(rack) {
|
||
const counts = Object.create(null);
|
||
for (const t of rack) counts[t] = (counts[t] ?? 0) + 1;
|
||
return counts;
|
||
}
|
||
|
||
// Take a tile for letter L, preferring a real tile over a blank. Mutates counts.
|
||
function takeTile(counts, L) {
|
||
if (counts[L] > 0) { counts[L]--; return { token: L, blank: false }; }
|
||
if (counts[BLANK] > 0) { counts[BLANK]--; return { token: BLANK, blank: true }; }
|
||
return null;
|
||
}
|
||
function giveTile(counts, t) { counts[t.token]++; }
|
||
|
||
// Perpendicular word constraint at an empty square. null = no constraint
|
||
// (no tiles above/below); otherwise a Set of letters that complete a valid
|
||
// cross word. An empty Set means nothing legal can be placed here.
|
||
function crossCheckSet(board, r, c, cdr, cdc, cache) {
|
||
const key = `${r},${c},${cdr},${cdc}`;
|
||
if (cache.has(key)) return cache.get(key);
|
||
|
||
let pre = '';
|
||
let rr = r - cdr, cc = c - cdc;
|
||
while (board[rr]?.[cc]) { pre = board[rr][cc].letter + pre; rr -= cdr; cc -= cdc; }
|
||
let suf = '';
|
||
rr = r + cdr; cc = c + cdc;
|
||
while (board[rr]?.[cc]) { suf += board[rr][cc].letter; rr += cdr; cc += cdc; }
|
||
|
||
let result;
|
||
if (!pre && !suf) {
|
||
result = null;
|
||
} else {
|
||
result = new Set();
|
||
for (const L of LETTERS) if (WORD_SET.has(pre + L + suf)) result.add(L);
|
||
}
|
||
cache.set(key, result);
|
||
return result;
|
||
}
|
||
|
||
// DFS from (R,C) along (mdr,mdc); cross axis (cdr,cdc). Records every terminal,
|
||
// board-connected word that places ≥1 new tile.
|
||
function dfs(ctx, R, C, node, placed, usedExisting, touchedCross) {
|
||
const { board, counts, mdr, mdc, cdr, cdc, firstMove, moves, cache } = ctx;
|
||
const inBounds = R >= 0 && C >= 0 && R < BOARD_SIZE && C < BOARD_SIZE;
|
||
const cell = inBounds ? board[R][C] : undefined;
|
||
|
||
if (inBounds && cell) { // read an existing tile
|
||
const child = node.children[cell.letter];
|
||
if (child) dfs(ctx, R + mdr, C + mdc, child, placed, true, touchedCross);
|
||
return;
|
||
}
|
||
|
||
// square is empty or off-board → the word may end here
|
||
if (node.terminal && placed.length > 0) {
|
||
const connected = firstMove
|
||
? placed.some(p => p.row === CENTER && p.col === CENTER)
|
||
: (usedExisting || touchedCross);
|
||
if (connected) moves.push(placed.slice());
|
||
}
|
||
|
||
if (!inBounds) return; // cannot place past the edge
|
||
|
||
const cc = crossCheckSet(board, R, C, cdr, cdc, cache);
|
||
for (const L in node.children) {
|
||
if (cc && !cc.has(L)) continue;
|
||
const tile = takeTile(counts, L);
|
||
if (!tile) continue;
|
||
placed.push({ row: R, col: C, letter: L, blank: tile.blank });
|
||
dfs(ctx, R + mdr, C + mdc, node.children[L], placed, usedExisting, touchedCross || cc !== null);
|
||
placed.pop();
|
||
giveTile(counts, tile);
|
||
}
|
||
}
|
||
|
||
function scanLine(ctx, startList) {
|
||
for (const [sr, sc] of startList) {
|
||
const lr = sr - ctx.mdr, lc = sc - ctx.mdc;
|
||
if (ctx.board[lr]?.[lc]) continue; // mid-word start → skip (covered by an earlier start)
|
||
dfs(ctx, sr, sc, TRIE, [], false, false);
|
||
}
|
||
}
|
||
|
||
function generateMoves(board, rack, firstMove) {
|
||
const counts = rackCounts(rack);
|
||
const cache = new Map();
|
||
const moves = [];
|
||
|
||
const directions = firstMove
|
||
? [
|
||
{ mdr: 0, mdc: 1, cdr: 1, cdc: 0, line: Array.from({ length: BOARD_SIZE }, (_, c) => [CENTER, c]) },
|
||
{ mdr: 1, mdc: 0, cdr: 0, cdc: 1, line: Array.from({ length: BOARD_SIZE }, (_, r) => [r, CENTER]) },
|
||
]
|
||
: buildFullScanDirections();
|
||
|
||
for (const d of directions) {
|
||
const ctx = { board, counts, mdr: d.mdr, mdc: d.mdc, cdr: d.cdr, cdc: d.cdc, firstMove, moves, cache };
|
||
scanLine(ctx, d.line);
|
||
}
|
||
return moves;
|
||
}
|
||
|
||
function buildFullScanDirections() {
|
||
const across = { mdr: 0, mdc: 1, cdr: 1, cdc: 0, line: [] };
|
||
const down = { mdr: 1, mdc: 0, cdr: 0, cdc: 1, line: [] };
|
||
for (let r = 0; r < BOARD_SIZE; r++) for (let c = 0; c < BOARD_SIZE; c++) {
|
||
across.line.push([r, c]);
|
||
down.line.push([c, r]);
|
||
}
|
||
return [across, down];
|
||
}
|
||
|
||
// ── Public: choose a move for an AI player ─────────────────────────────────────
|
||
|
||
// board: 15×15 of null | { letter, blank }. rack: array of tokens ('A'…'Z','_').
|
||
// Returns { type:'play', placements, score, word } | { type:'exchange', tiles }
|
||
// | { type:'pass' }.
|
||
export function chooseMove({ board, rack, skill = 3, firstMove, bagCount = 0 }) {
|
||
if (!TRIE) return { type: 'pass' };
|
||
|
||
const rawMoves = generateMoves(board, rack, firstMove);
|
||
if (!rawMoves.length) return fallbackMove(rack, bagCount);
|
||
|
||
const scored = rawMoves
|
||
.map(placements => ({ placements, score: scoreMove(board, placements) }))
|
||
.filter(m => m.score > 0)
|
||
.sort((a, b) => b.score - a.score);
|
||
|
||
if (!scored.length) return fallbackMove(rack, bagCount);
|
||
|
||
const pick = scored[pickIndex(scored.length, skill)];
|
||
return { type: 'play', placements: pick.placements, score: pick.score, word: longestWord(pick.placements) };
|
||
}
|
||
|
||
// Map skill 1–5 onto a slice of the score-ranked move list (0 = best).
|
||
function pickIndex(n, skill) {
|
||
const ranges = {
|
||
5: [0, Math.min(1, n - 1)],
|
||
4: [0, Math.max(0, Math.ceil(n * 0.10) - 1)],
|
||
3: [Math.floor(n * 0.15), Math.ceil(n * 0.45)],
|
||
2: [Math.floor(n * 0.45), Math.ceil(n * 0.75)],
|
||
1: [Math.floor(n * 0.70), n - 1],
|
||
};
|
||
const [lo, hi] = ranges[skill] ?? ranges[3];
|
||
const a = Math.max(0, Math.min(lo, n - 1));
|
||
const b = Math.max(a, Math.min(hi, n - 1));
|
||
return a + Math.floor(Math.random() * (b - a + 1));
|
||
}
|
||
|
||
function longestWord(placements) {
|
||
// The display word: rebuild the main line from the placements alone is enough
|
||
// for a label; the client recomputes the authoritative words when applying.
|
||
return placements.map(p => p.letter).join('');
|
||
}
|
||
|
||
// No legal play: exchange when the bag can support it, otherwise pass.
|
||
function fallbackMove(rack, bagCount) {
|
||
if (bagCount >= RACK_SIZE) {
|
||
return { type: 'exchange', tiles: rack.slice(0, Math.min(rack.length, bagCount)) };
|
||
}
|
||
return { type: 'pass' };
|
||
}
|