engine.js

(function (root) {
  'use strict';

  const SIZE = 15;
  const COUNT = SIZE * SIZE;
  const DIRECTIONS = [[1, 0], [0, 1], [1, 1], [1, -1]];

  const createBoard = () => Array(COUNT).fill(0);
  const rowOf = (index) => Math.floor(index / SIZE);
  const colOf = (index) => index % SIZE;
  const inside = (row, col) => row >= 0 && row < SIZE && col >= 0 && col < SIZE;
  const indexOf = (row, col) => row * SIZE + col;
  const validIndex = (index) => Number.isInteger(index) && index >= 0 && index < COUNT;

  function step(index, dr, dc, distance) {
    const row = rowOf(index) + dr * distance;
    const col = colOf(index) + dc * distance;
    return inside(row, col) ? indexOf(row, col) : -1;
  }

  function contiguousLine(board, index, player, dr, dc) {
    const negative = [];
    const positive = [];
    for (let k = 1; k < SIZE; k++) {
      const cell = step(index, dr, dc, -k);
      if (cell < 0 || board[cell] !== player) break;
      negative.unshift(cell);
    }
    for (let k = 1; k < SIZE; k++) {
      const cell = step(index, dr, dc, k);
      if (cell < 0 || board[cell] !== player) break;
      positive.push(cell);
    }
    return [...negative, index, ...positive];
  }

  function linesAt(board, index, player) {
    return DIRECTIONS.map(([dr, dc]) => contiguousLine(board, index, player, dr, dc));
  }

  function getWinner(board, lastMove, forbidden) {
    if (!validIndex(lastMove)) return { winner: 0, line: [] };
    const player = board[lastMove];
    if (player !== 1 && player !== 2) return { winner: 0, line: [] };
    const lines = linesAt(board, lastMove, player);
    const line = lines.find((part) => forbidden && player === 1 ? part.length === 5 : part.length >= 5);
    return line ? { winner: player, line } : { winner: 0, line: [] };
  }

  function wouldBlackMakeFiveInDirection(board, index, dr, dc) {
    if (index < 0 || board[index] !== 0) return false;
    board[index] = 1;
    const result = contiguousLine(board, index, 1, dr, dc).length === 5;
    board[index] = 0;
    return result;
  }

  function countFours(board, origin) {
    const fours = new Set();
    for (const [dr, dc] of DIRECTIONS) {
      for (let start = -4; start <= 0; start++) {
        const window = [];
        for (let offset = 0; offset < 5; offset++) {
          const cell = step(origin, dr, dc, start + offset);
          if (cell < 0) break;
          window.push(cell);
        }
        if (window.length !== 5) continue;
        const stones = window.filter((cell) => board[cell] === 1);
        const empties = window.filter((cell) => board[cell] === 0);
        if (stones.length !== 4 || empties.length !== 1 || !stones.includes(origin)) continue;
        if (wouldBlackMakeFiveInDirection(board, empties[0], dr, dc)) {
          fours.add(stones.slice().sort((a, b) => a - b).join(','));
        }
      }
    }
    return fours.size;
  }

  function hasOpenFour(board, origin, extension, dr, dc) {
    for (let start = -5; start <= 0; start++) {
      const window = [];
      for (let offset = 0; offset < 6; offset++) {
        const cell = step(origin, dr, dc, start + offset);
        if (cell < 0) break;
        window.push(cell);
      }
      if (window.length !== 6 || board[window[0]] !== 0 || board[window[5]] !== 0) continue;
      const middle = window.slice(1, 5);
      if (!middle.includes(origin) || !middle.includes(extension)) continue;
      if (middle.every((cell) => board[cell] === 1) &&
          wouldBlackMakeFiveInDirection(board, window[0], dr, dc) &&
          wouldBlackMakeFiveInDirection(board, window[5], dr, dc)) return true;
    }
    return false;
  }

  function countThrees(board, origin, depth) {
    let count = 0;
    for (const [dr, dc] of DIRECTIONS) {
      let createsThree = false;
      for (let distance = -4; distance <= 4 && !createsThree; distance++) {
        if (distance === 0) continue;
        const extension = step(origin, dr, dc, distance);
        if (extension < 0 || board[extension] !== 0) continue;
        board[extension] = 1;
        const openFour = hasOpenFour(board, origin, extension, dr, dc);
        board[extension] = 0;
        if (!openFour) continue;
        if (forbiddenReasonInternal(board, extension, depth + 1) === null) createsThree = true;
      }
      if (createsThree && ++count >= 2) return count;
    }
    return count;
  }

  function forbiddenReasonInternal(board, index, depth) {
    if (!validIndex(index) || board[index] !== 0) return '已有棋子';
    board[index] = 1;
    let reason = null;
    const lengths = linesAt(board, index, 1).map((line) => line.length);
    if (lengths.some((length) => length === 5)) reason = null;
    else if (lengths.some((length) => length > 5)) reason = '长连禁手';
    else {
      if (countFours(board, index) >= 2) reason = '四四禁手';
      else if (depth < 3 && countThrees(board, index, depth) >= 2) reason = '三三禁手';
    }
    board[index] = 0;
    return reason;
  }

  function forbiddenReason(board, index) {
    return forbiddenReasonInternal(board, index, 0);
  }

  function isLegalMove(board, index, player, forbidden) {
    if (!validIndex(index) || board[index] !== 0 || (player !== 1 && player !== 2)) return false;
    return !forbidden || player !== 1 || forbiddenReason(board, index) === null;
  }

  function playMove(board, index, player, forbidden) {
    if (!isLegalMove(board, index, player, forbidden)) {
      throw new Error(forbidden && player === 1 ? forbiddenReason(board, index) || '不能落子' : '不能落子');
    }
    const nextBoard = board.slice();
    nextBoard[index] = player;
    const result = getWinner(nextBoard, index, forbidden);
    return { board: nextBoard, nextPlayer: player === 1 ? 2 : 1, winner: result.winner, line: result.line };
  }

  function nearbyCandidates(board, radius = 2) {
    const stones = [];
    for (let index = 0; index < COUNT; index++) if (board[index] !== 0) stones.push(index);
    if (stones.length === 0) return [indexOf(7, 7)];
    const candidates = new Set();
    for (const stone of stones) {
      const row = rowOf(stone);
      const col = colOf(stone);
      for (let dr = -radius; dr <= radius; dr++) {
        for (let dc = -radius; dc <= radius; dc++) {
          const nextRow = row + dr;
          const nextCol = col + dc;
          if (inside(nextRow, nextCol)) {
            const next = indexOf(nextRow, nextCol);
            if (board[next] === 0) candidates.add(next);
          }
        }
      }
    }
    return [...candidates];
  }

  function scorePlacement(board, index, player, forbidden) {
    if (!isLegalMove(board, index, player, forbidden)) return -1;
    board[index] = player;
    if (getWinner(board, index, forbidden).winner === player) {
      board[index] = 0;
      return 10_000_000;
    }
    let score = 0;
    for (const [dr, dc] of DIRECTIONS) {
      const line = contiguousLine(board, index, player, dr, dc);
      const before = step(line[0], dr, dc, -1);
      const after = step(line[line.length - 1], dr, dc, 1);
      const open = Number(before >= 0 && board[before] === 0) + Number(after >= 0 && board[after] === 0);
      if (line.length >= 4) score += open === 2 ? 60_000 : open === 1 ? 16_000 : 100;
      else if (line.length === 3) score += open === 2 ? 3_000 : open === 1 ? 420 : 20;
      else if (line.length === 2) score += open === 2 ? 110 : open === 1 ? 28 : 2;
      else score += open === 2 ? 5 : 1;

      const fourEnds = new Set();
      let threeWindows = 0;
      for (let start = -4; start <= 0; start++) {
        const cells = [];
        for (let offset = 0; offset < 5; offset++) {
          const cell = step(index, dr, dc, start + offset);
          if (cell < 0) break;
          cells.push(cell);
        }
        if (cells.length !== 5 || cells.some((cell) => board[cell] === (player === 1 ? 2 : 1))) continue;
        const own = cells.filter((cell) => board[cell] === player).length;
        if (own === 4) fourEnds.add(cells.find((cell) => board[cell] === 0));
        else if (own === 3) threeWindows++;
      }
      if (fourEnds.size) score += fourEnds.size > 1 ? 34_000 : 11_000;
      else score += Math.min(threeWindows, 2) * 280;
    }
    board[index] = 0;
    return score;
  }

  function rankedMoves(board, player, forbidden, limit = Infinity, radius = 2) {
    const other = player === 1 ? 2 : 1;
    const scored = [];
    for (const index of nearbyCandidates(board, radius)) {
      const attack = scorePlacement(board, index, player, forbidden);
      if (attack < 0) continue;
      const defend = Math.max(0, scorePlacement(board, index, other, forbidden));
      const center = 14 - Math.abs(rowOf(index) - 7) - Math.abs(colOf(index) - 7);
      scored.push({ index, score: attack + defend * 0.94 + center * 0.01, attack, defend });
    }
    scored.sort((a, b) => b.score - a.score || a.index - b.index);
    return scored.slice(0, limit);
  }

  function winningMoves(board, player, forbidden, candidates) {
    const wins = [];
    for (const index of candidates) {
      if (!isLegalMove(board, index, player, forbidden)) continue;
      board[index] = player;
      const won = getWinner(board, index, forbidden).winner === player;
      board[index] = 0;
      if (won) wins.push(index);
    }
    return wins;
  }

  function forcedWinInTwo(board, player, forbidden) {
    const other = player === 1 ? 2 : 1;
    for (const index of nearbyCandidates(board)) {
      if (scorePlacement(board, index, player, forbidden) < 20_000) continue;
      board[index] = player;
      const candidates = nearbyCandidates(board);
      const ownWins = winningMoves(board, player, forbidden, candidates);
      const opponentWins = ownWins.length >= 2 ? winningMoves(board, other, forbidden, candidates) : [];
      board[index] = 0;
      if (ownWins.length >= 2 && opponentWins.length === 0) return index;
    }
    return -1;
  }

  function tacticalOutcome(board, move, player, forbidden) {
    if (!isLegalMove(board, move, player, forbidden)) return null;
    const position = playMove(board, move, player, forbidden);
    if (position.winner === player) return { percent: 100, forced: true, tactic: '直接成五' };
    const other = position.nextPlayer;
    const candidates = nearbyCandidates(position.board);
    if (winningMoves(position.board, other, forbidden, candidates).length) {
      return { percent: 0, forced: true, tactic: '对手下一手可成五' };
    }
    if (winningMoves(position.board, player, forbidden, candidates).length >= 2) {
      return { percent: 100, forced: true, tactic: '两步内必胜' };
    }
    if (forcedWinInTwo(position.board, other, forbidden) >= 0) {
      return { percent: 0, forced: true, tactic: '对手两步内必胜' };
    }
    return null;
  }

  function staticEvaluation(board, player, forbidden, forcedReplies = 2) {
    const other = player === 1 ? 2 : 1;
    const own = rankedMoves(board, player, forbidden, 2);
    // A win available to the side to move takes priority over every opposing threat.
    if (own[0]?.attack === 10_000_000) return 10_000_000;
    const enemy = rankedMoves(board, other, forbidden, 2);
    if (forcedReplies > 0 && enemy[0]?.attack === 10_000_000) {
      if (enemy[1]?.attack === 10_000_000 || !isLegalMove(board, enemy[0].index, player, forbidden)) {
        return -9_999_000;
      }
      board[enemy[0].index] = player;
      const reply = -staticEvaluation(board, other, forbidden, forcedReplies - 1);
      board[enemy[0].index] = 0;
      return reply;
    }
    const ownScore = own[0]?.attack || 0;
    const enemyScore = Math.min(enemy[0]?.attack || 0, 100_000);
    const score = ownScore - enemyScore * 1.08 + (own[1]?.attack || 0) * 0.15 - (enemy[1]?.attack || 0) * 0.15;
    let result = Math.max(-9_999_000, Math.min(9_999_000, score));
    if (forcedReplies > 0 && enemy[0]?.attack >= 60_000 &&
        isLegalMove(board, enemy[0].index, player, forbidden)) {
      board[enemy[0].index] = player;
      result = Math.max(result, -staticEvaluation(board, other, forbidden, forcedReplies - 1));
      board[enemy[0].index] = 0;
    }
    return result;
  }

  function negamax(board, player, forbidden, depth, alpha, beta) {
    if (depth <= 0) return staticEvaluation(board, player, forbidden);
    const other = player === 1 ? 2 : 1;
    const moves = rankedMoves(board, player, forbidden, depth >= 2 ? 7 : 5);
    if (moves.length === 0) return 0;
    let best = -Infinity;
    for (const move of moves) {
      board[move.index] = player;
      const win = getWinner(board, move.index, forbidden).winner === player;
      const value = win ? 10_000_000 + depth : -negamax(board, other, forbidden, depth - 1, -beta, -alpha);
      board[move.index] = 0;
      if (value > best) best = value;
      alpha = Math.max(alpha, value);
      if (alpha >= beta) break;
    }
    return best;
  }

  function chooseVariedMove(board, player, forbidden, choices, bestMove, variety, random) {
    if (variety !== 'moderate' && variety !== 'lively') return bestMove;
    const bestValue = Math.max(...choices.map((choice) => choice.value));
    const tolerance = Math.min(5000, Math.max(variety === 'lively' ? 100 : 25,
      Math.abs(bestValue) * (variety === 'lively' ? 0.12 : 0.04)));
    const other = player === 1 ? 2 : 1;
    const close = choices.filter((choice) => choice.value >= bestValue - tolerance);
    const safe = close.filter(({ index }) => {
      board[index] = player;
      const replyWins = winningMoves(board, other, forbidden, nearbyCandidates(board));
      board[index] = 0;
      return replyWins.length === 0;
    });
    if (safe.length < 2) return bestMove;
    const draw = Math.max(0, Math.min(0.999999999, random()));
    return safe[Math.floor(draw * safe.length)].index;
  }

  function chooseMove(board, player, forbidden, difficulty = 'normal', options = {}) {
    const other = player === 1 ? 2 : 1;
    const nearby = nearbyCandidates(board);
    const ownWins = winningMoves(board, player, forbidden, nearby);
    if (ownWins.length) return ownWins[0];
    const opponentWins = winningMoves(board, other, forbidden, nearby);
    if (opponentWins.length) {
      const blocks = opponentWins.filter((index) => isLegalMove(board, index, player, forbidden));
      if (blocks.length) return blocks[0];
    }
    const forced = forcedWinInTwo(board, player, forbidden);
    if (forced >= 0) return forced;
    const depth = difficulty === 'hard' ? 3 : difficulty === 'easy' ? 1 : 2;
    const moves = rankedMoves(board, player, forbidden, difficulty === 'hard' ? 10 : 8);
    if (moves.length === 0) return -1;
    if (depth === 1) return chooseVariedMove(board, player, forbidden,
      moves.map(({ index, score }) => ({ index, value: score })), moves[0].index,
      options.variety, options.random || Math.random);
    let bestMove = moves[0].index;
    let bestValue = -Infinity;
    let alpha = -Infinity;
    const choices = [];
    for (const move of moves) {
      board[move.index] = player;
      const value = -negamax(board, other, forbidden, depth - 1, -Infinity,
        options.variety === 'moderate' || options.variety === 'lively' ? Infinity : -alpha);
      board[move.index] = 0;
      choices.push({ index: move.index, value });
      if (value > bestValue) {
        bestValue = value;
        bestMove = move.index;
      }
      alpha = Math.max(alpha, value);
    }
    return chooseVariedMove(board, player, forbidden, choices, bestMove,
      options.variety, options.random || Math.random);
  }

  function makeRandom(seed) {
    let state = seed >>> 0 || 1;
    return () => {
      state ^= state << 13;
      state ^= state >>> 17;
      state ^= state << 5;
      return (state >>> 0) / 4_294_967_296;
    };
  }

  function rolloutMove(board, player, forbidden, random, difficulty) {
    const moves = rankedMoves(board, player, forbidden, 3, 1);
    if (!moves.length) return -1;
    if (moves[0].attack >= 10_000_000 || moves[0].defend >= 10_000_000) return moves[0].index;
    const draw = random();
    const first = difficulty === 'hard' ? 0.88 : difficulty === 'easy' ? 0.48 : 0.7;
    const second = difficulty === 'hard' ? 0.98 : difficulty === 'easy' ? 0.78 : 0.93;
    return moves[draw < first ? 0 : draw < second ? Math.min(1, moves.length - 1) : moves.length - 1].index;
  }

  function horizonValue(board, player, forbidden) {
    const other = player === 1 ? 2 : 1;
    const own = rankedMoves(board, player, forbidden, 1, 1)[0]?.attack || 0;
    const enemy = rankedMoves(board, other, forbidden, 1, 1)[0]?.attack || 0;
    return 0.5 + 0.5 * Math.tanh((own - enemy) / 8_000);
  }

  function transformIndex(index, symmetry) {
    const row = rowOf(index);
    const col = colOf(index);
    switch (symmetry) {
      case 1: return indexOf(col, 14 - row);
      case 2: return indexOf(14 - row, 14 - col);
      case 3: return indexOf(14 - col, row);
      case 4: return indexOf(row, 14 - col);
      case 5: return indexOf(14 - row, col);
      case 6: return indexOf(col, row);
      case 7: return indexOf(14 - col, 14 - row);
      default: return index;
    }
  }

  function canonicalPosition(board, move) {
    let bestKey = null;
    let bestBoard = null;
    let bestMove = move;
    for (let symmetry = 0; symmetry < 8; symmetry++) {
      const transformed = createBoard();
      for (let index = 0; index < COUNT; index++) transformed[transformIndex(index, symmetry)] = board[index];
      const target = transformIndex(move, symmetry);
      const key = transformed.join('') + String(target).padStart(3, '0');
      if (bestKey === null || key < bestKey) {
        bestKey = key;
        bestBoard = transformed;
        bestMove = target;
      }
    }
    return { board: bestBoard, move: bestMove };
  }

  function estimateMove(board, move, player, forbidden, difficulty = 'normal', onProgress = null, options = {}) {
    if (!isLegalMove(board, move, player, forbidden)) {
      return { percent: null, samples: 0, forced: false,
        reason: forbidden && player === 1 ? forbiddenReason(board, move) || '不能落子' : '不能落子' };
    }
    const tactical = tacticalOutcome(board, move, player, forbidden);
    if (tactical) return { ...tactical, samples: 0, reason: null };
    const canonical = canonicalPosition(board, move);
    board = canonical.board;
    move = canonical.move;
    const first = playMove(board, move, player, forbidden);
    if (first.winner === player) return { percent: 100, samples: 0, forced: true, reason: null };
    const samples = options.samples || (difficulty === 'hard' ? 128 : difficulty === 'easy' ? 32 : 64);
    const maxPlies = options.maxPlies || (difficulty === 'hard' ? 40 : difficulty === 'easy' ? 28 : 34);
    const progressInterval = Math.max(4, Math.floor(samples / 16));
    let seed = (move + 1) * 2_654_435_761;
    for (let index = 0; index < COUNT; index++) seed = Math.imul(seed ^ (board[index] + index), 1_664_525) >>> 0;
    const random = makeRandom(seed);
    let sum = 0;
    for (let sample = 1; sample <= samples; sample++) {
      const position = first.board.slice();
      let turn = first.nextPlayer;
      let outcome = null;
      for (let ply = 0; ply < maxPlies; ply++) {
        const candidate = rolloutMove(position, turn, forbidden, random, turn === player ? 'normal' : difficulty);
        if (candidate < 0) {
          outcome = 0.5;
          break;
        }
        position[candidate] = turn;
        if (getWinner(position, candidate, forbidden).winner === turn) {
          outcome = turn === player ? 1 : 0;
          break;
        }
        turn = turn === 1 ? 2 : 1;
      }
      sum += outcome === null ? horizonValue(position, player, forbidden) : outcome;
      if (onProgress && (sample % progressInterval === 0 || sample === samples)) {
        onProgress({ percent: Math.round(sum / sample * 1000) / 10, samples: sample, forced: false, reason: null });
      }
    }
    return { percent: Math.round(sum / samples * 1000) / 10, samples, forced: false, reason: null };
  }

  function analysisCandidates(board, player, forbidden, candidateLimit = 10) {
    const candidates = board.every((cell) => cell === 0)
      ? Array.from({ length: 9 }, (_, i) => indexOf(6 + Math.floor(i / 3), 6 + i % 3))
      : (() => {
        const ranked = rankedMoves(board, player, forbidden);
        const cutoff = ranked[Math.min(candidateLimit, ranked.length) - 1]?.score;
        return ranked.filter((move) => move.score >= cutoff).map((move) => move.index);
      })();
    return candidates.filter((index) => isLegalMove(board, index, player, forbidden));
  }

  function estimateTopMoves(board, player, forbidden, difficulty = 'normal', onProgress = null, options = {}) {
    const displayLimit = options.displayLimit || 5;
    const candidates = analysisCandidates(board, player, forbidden, options.candidateLimit || 10);
    const groups = new Map();
    for (const index of candidates) {
      const canonical = canonicalPosition(board, index);
      const key = canonical.board.join('') + ':' + canonical.move;
      if (!groups.has(key)) groups.set(key, []);
      groups.get(key).push(index);
    }
    const total = [...groups.values()].reduce((sum, indices) => sum + indices.length, 0);
    const results = [];
    let evaluated = 0;
    const samples = options.samples || (difficulty === 'hard' ? 24 : difficulty === 'easy' ? 12 : 16);
    const maxPlies = options.maxPlies || (difficulty === 'hard' ? 40 : difficulty === 'easy' ? 28 : 34);
    const snapshot = () => {
      const ranked = results.slice().sort((a, b) => b.percent - a.percent || a.indices[0] - b.indices[0]);
      const best = ranked[0]?.percent || 0;
      const minimum = Math.max(best - 30, best * 0.5, 0.1);
      const points = [];
      for (const group of ranked) {
        if (group.percent < minimum || (points.length && points.length + group.indices.length > displayLimit)) break;
        for (const index of group.indices) points.push({ index, percent: group.percent });
        if (points.length >= displayLimit) break;
      }
      points.sort((a, b) => b.percent - a.percent || a.index - b.index);
      return { points, evaluated, total };
    };
    for (const indices of groups.values()) {
      const result = estimateMove(board, indices[0], player, forbidden, difficulty, null, { samples, maxPlies });
      evaluated += indices.length;
      if (result.percent !== null) results.push({ indices, percent: result.percent });
      if (onProgress) onProgress(snapshot());
    }
    return snapshot();
  }

  const api = { SIZE, COUNT, DIRECTIONS, createBoard, getWinner, forbiddenReason, isLegalMove, playMove,
    chooseMove, estimateMove, estimateTopMoves, analysisCandidates, tacticalOutcome, staticEvaluation };
  if (typeof module !== 'undefined' && module.exports) module.exports = api;
  root.GomokuEngine = api;
})(typeof self !== 'undefined' ? self : globalThis);