<script id="mcts-worker-source" type="javascript/worker">
  'use strict';

  const LINES = [
    [0, 1, 4],
    [0, 2, 6],
    [4, 5, 6],
    [0, 3, 5],
    [1, 3, 6],
    [2, 3, 4],
    [1, 2, 5]
  ];

  const CELL_COUNT = 49;
  const SIDE_SIZE = 7;
  const MOVE_BASE = 49;

  /*
   * 島內與島群線形的評估權重。
   * 島群中已有兩個己方控制島且第三格未被敵方控制，
   * 是最重要的非終局特徵。
   */
  const LOCAL_WEIGHTS = [0, 0.35, 3.4, 14];
  const META_WEIGHTS = [0.1, 2.8, 20, 200];

  const PROFILES = {
    easy: {
      rolloutDepth: 16,
      policySamples: 5,
      rolloutEpsilon: 0.24,
      rolloutNoise: 5,
      rolloutTop: 4,
      rolloutRankPower: 1.5,
      rolloutSafetyDepth: 1,
      rolloutSafetyChecks: 1,
      priorTemperature: 58,
      replySamples: 3,
      replyWeight: 0.12,
      maxThreatCount: 3,
      lateTreeSafetyPly: 99,
      lateTreeSafetyDepth: 0,
      rootWidening: 4.8,
      widening: 1.9,
      wideningExponent: 0.5,
      cpuctMultiplier: 1.15,
      batchSize: 12
    },

    hard: {
      rolloutDepth: 24,
      policySamples: 10,
      rolloutEpsilon: 0.09,
      rolloutNoise: 1.6,
      rolloutTop: 4,
      rolloutRankPower: 2.1,
      rolloutSafetyDepth: 4,
      rolloutSafetyChecks: 2,
      priorTemperature: 46,
      replySamples: 5,
      replyWeight: 0.22,
      maxThreatCount: 4,
      lateTreeSafetyPly: 38,
      lateTreeSafetyDepth: 1,
      rootWidening: 4.2,
      widening: 1.65,
      wideningExponent: 0.5,
      cpuctMultiplier: 1.05,
      batchSize: 8
    },

    expert: {
      rolloutDepth: 32,
      policySamples: 16,
      rolloutEpsilon: 0.02,
      rolloutNoise: 0.45,
      rolloutTop: 3,
      rolloutRankPower: 3,
      rolloutSafetyDepth: 8,
      rolloutSafetyChecks: 3,
      priorTemperature: 36,
      replySamples: 7,
      replyWeight: 0.34,
      maxThreatCount: 6,
      lateTreeSafetyPly: 32,
      lateTreeSafetyDepth: 2,
      rootWidening: 3.8,
      widening: 1.5,
      wideningExponent: 0.5,
      cpuctMultiplier: 1,
      batchSize: 6
    },

    custom: {
      rolloutDepth: 38,
      policySamples: 24,
      rolloutEpsilon: 0.006,
      rolloutNoise: 0.16,
      rolloutTop: 3,
      rolloutRankPower: 3.6,
      rolloutSafetyDepth: 12,
      rolloutSafetyChecks: 4,
      priorTemperature: 31,
      replySamples: 9,
      replyWeight: 0.42,
      maxThreatCount: 8,
      lateTreeSafetyPly: 28,
      lateTreeSafetyDepth: 3,
      rootWidening: 3.6,
      widening: 1.45,
      wideningExponent: 0.5,
      cpuctMultiplier: 0.95,
      batchSize: 4
    }
  };

  let rngState = 0x9e3779b9;

  function seedRandom(seed) {
    rngState = seed >>> 0;
    if (!rngState) rngState = 0x9e3779b9;
  }

  function random() {
    let value = rngState | 0;
    value ^= value << 13;
    value ^= value >>> 17;
    value ^= value << 5;
    rngState = value >>> 0;
    return rngState / 4294967296;
  }

  function randomInt(limit) {
    return (random() * limit) | 0;
  }

  function clamp(value, minimum, maximum) {
    return Math.max(minimum, Math.min(maximum, value));
  }

  function hashState(state) {
    let hash = 2166136261 >>> 0;

    for (let i = 0; i < CELL_COUNT; i++) {
      hash ^= (state.board[i] + 2 + i * 3) & 255;
      hash = Math.imul(hash, 16777619);
    }

    for (let i = 0; i < SIDE_SIZE; i++) {
      hash ^= (state.claims[i] + 2 + i * 11) & 255;
      hash = Math.imul(hash, 16777619);
    }

    hash ^= state.turn === 1 ? 0x51ed270b : 0x7f4a7c15;
    hash = Math.imul(hash, 16777619);
    hash ^= state.ply >>> 0;

    return hash >>> 0;
  }

  function encodeMove(from, to) {
    return from * MOVE_BASE + to;
  }

  function moveFrom(move) {
    return (move / MOVE_BASE) | 0;
  }

  function moveTo(move) {
    const from = moveFrom(move);
    return move - from * MOVE_BASE;
  }

  function publicMove(move) {
    if (!Number.isInteger(move) || move < 0) return null;

    return {
      from: moveFrom(move),
      to: moveTo(move)
    };
  }

  function hasIslandLine(board, island, player) {
    const base = island * SIDE_SIZE;

    for (const line of LINES) {
      if (
        board[base + line[0]] === player &&
        board[base + line[1]] === player &&
        board[base + line[2]] === player
      ) {
        return true;
      }
    }

    return false;
  }

  function islandOwner(board, island) {
    const fire = hasIslandLine(board, island, 1);
    const ice = hasIslandLine(board, island, -1);

    if (fire && !ice) return 1;
    if (ice && !fire) return -1;
    return 0;
  }

  function hasMetaLine(claims, player) {
    for (const line of LINES) {
      if (
        claims[line[0]] === player &&
        claims[line[1]] === player &&
        claims[line[2]] === player
      ) {
        return true;
      }
    }

    return false;
  }

  function generateMoves(state) {
    const board = state.board;
    const player = state.turn;
    const result = [];

    for (let from = 0; from < CELL_COUNT; from++) {
      if (board[from] !== player) continue;

      const island = (from / SIDE_SIZE) | 0;
      const point = from % SIDE_SIZE;
      const base = island * SIDE_SIZE;

      for (let nextPoint = 0; nextPoint < SIDE_SIZE; nextPoint++) {
        if (nextPoint === point) continue;

        const to = base + nextPoint;
        if (board[to] === 0) {
          result.push(encodeMove(from, to));
        }
      }

      for (let nextIsland = 0; nextIsland < SIDE_SIZE; nextIsland++) {
        if (nextIsland === island) continue;

        const to = nextIsland * SIDE_SIZE + point;
        if (board[to] === 0) {
          result.push(encodeMove(from, to));
        }
      }
    }

    return result;
  }

  function cloneState(state) {
    return {
      board: state.board.slice(),
      claims: state.claims.slice(),
      turn: state.turn,
      winner: state.winner,
      ply: state.ply
    };
  }

  function applyMoveInPlace(state, move) {
    const from = moveFrom(move);
    const to = moveTo(move);
    const player = state.turn;

    state.board[to] = player;
    state.board[from] = -player;

    const originIsland = (from / SIDE_SIZE) | 0;
    const destinationIsland = (to / SIDE_SIZE) | 0;

    state.claims[originIsland] = islandOwner(state.board, originIsland);

    if (destinationIsland !== originIsland) {
      state.claims[destinationIsland] = islandOwner(state.board, destinationIsland);
    }

    let winner = 0;

    /*
     * 與主執行緒的規則一致：
     * 先檢查行動方，再檢查對手。
     */
    if (hasMetaLine(state.claims, player)) {
      winner = player;
    } else if (hasMetaLine(state.claims, -player)) {
      winner = -player;
    }

    state.turn = -player;
    state.winner = winner;
    state.ply++;

    return state;
  }

  function applyMove(state, move) {
    const next = cloneState(state);
    return applyMoveInPlace(next, move);
  }

  function terminalReward(state, rootPlayer) {
    if (state.winner === rootPlayer) return 1;
    if (state.winner === -rootPlayer) return 0;
    if (state.winner === 2) return 0.5;
    return -1;
  }

  function ownerBalance(owner, player) {
    if (owner === player) return 1;
    if (owner === -player) return -1;
    return 0;
  }

  function claimBalance(claims, player) {
    let score = 0;

    for (let i = 0; i < SIDE_SIZE; i++) {
      score += ownerBalance(claims[i], player);
    }

    return score;
  }

  function metaPotential(claims, player) {
    let score = 0;

    for (const line of LINES) {
      let own = 0;
      let enemy = 0;

      for (const island of line) {
        if (claims[island] === player) own++;
        else if (claims[island] === -player) enemy++;
      }

      if (enemy === 0) {
        score += META_WEIGHTS[own];
      }
    }

    return score;
  }

  function metaBalance(claims, player) {
    return metaPotential(claims, player) - metaPotential(claims, -player);
  }

  function localPotential(board, island, player) {
    const base = island * SIDE_SIZE;
    let score = 0;

    for (const line of LINES) {
      let own = 0;
      let enemy = 0;

      for (const point of line) {
        const occupant = board[base + point];

        if (occupant === player) own++;
        else if (occupant === -player) enemy++;
      }

      if (enemy === 0) {
        score += LOCAL_WEIGHTS[own];
      }
    }

    return score;
  }

  function localBalance(board, island, player) {
    return localPotential(board, island, player) - localPotential(board, island, -player);
  }

  function mobilityBalance(state, player) {
    const emptyByIsland = new Int8Array(SIDE_SIZE);
    const emptyByPoint = new Int8Array(SIDE_SIZE);

    for (let index = 0; index < CELL_COUNT; index++) {
      if (state.board[index] !== 0) continue;

      const island = (index / SIDE_SIZE) | 0;
      const point = index % SIDE_SIZE;

      emptyByIsland[island]++;
      emptyByPoint[point]++;
    }

    let score = 0;

    for (let index = 0; index < CELL_COUNT; index++) {
      const occupant = state.board[index];
      if (!occupant) continue;

      const island = (index / SIDE_SIZE) | 0;
      const point = index % SIDE_SIZE;
      const mobility = emptyByIsland[island] + emptyByPoint[point];

      if (occupant === player) score += mobility;
      else score -= mobility;
    }

    return score;
  }

  /*
   * 暫時在原棋盤上走一步，再完整恢復。
   * withScore=false 時只檢查勝負，供 rollout 的快速戰術掃描使用。
   */
  function inspectMove(state, move, withScore = true) {
    const from = moveFrom(move);
    const to = moveTo(move);
    const player = state.turn;

    const originIsland = (from / SIDE_SIZE) | 0;
    const destinationIsland = (to / SIDE_SIZE) | 0;

    const oldFrom = state.board[from];
    const oldTo = state.board[to];
    const oldOriginClaim = state.claims[originIsland];
    const oldDestinationClaim = state.claims[destinationIsland];

    let beforeClaim = 0;
    let beforeMeta = 0;
    let beforeLocal = 0;

    if (withScore) {
      beforeClaim = ownerBalance(oldOriginClaim, player);

      if (destinationIsland !== originIsland) {
        beforeClaim += ownerBalance(oldDestinationClaim, player);
      }

      beforeMeta = metaBalance(state.claims, player);
      beforeLocal = localBalance(state.board, originIsland, player);

      if (destinationIsland !== originIsland) {
        beforeLocal += localBalance(state.board, destinationIsland, player);
      }
    }

    state.board[to] = player;
    state.board[from] = -player;

    state.claims[originIsland] = islandOwner(state.board, originIsland);

    if (destinationIsland !== originIsland) {
      state.claims[destinationIsland] = islandOwner(state.board, destinationIsland);
    }

    let winner = 0;

    if (hasMetaLine(state.claims, player)) {
      winner = player;
    } else if (hasMetaLine(state.claims, -player)) {
      winner = -player;
    }

    let score = 0;

    if (withScore) {
      let afterClaim = ownerBalance(state.claims[originIsland], player);

      if (destinationIsland !== originIsland) {
        afterClaim += ownerBalance(state.claims[destinationIsland], player);
      }

      const afterMeta = metaBalance(state.claims, player);
      let afterLocal = localBalance(state.board, originIsland, player);

      if (destinationIsland !== originIsland) {
        afterLocal += localBalance(state.board, destinationIsland, player);
      }

      score =
        (afterClaim - beforeClaim) * 90 +
        (afterMeta - beforeMeta) * 13 +
        (afterLocal - beforeLocal) * 4.5;

      if (winner === player) {
        score = 1000000000;
      } else if (winner === -player) {
        score = -1000000000;
      }
    }

    state.board[from] = oldFrom;
    state.board[to] = oldTo;
    state.claims[originIsland] = oldOriginClaim;

    if (destinationIsland !== originIsland) {
      state.claims[destinationIsland] = oldDestinationClaim;
    }

    return {
      winner,
      score
    };
  }

  function evaluateRaw(state, player) {
    let local = 0;

    for (let island = 0; island < SIDE_SIZE; island++) {
      local += localBalance(state.board, island, player);
    }

    return (
      claimBalance(state.claims, player) * 70 +
      metaBalance(state.claims, player) * 14 +
      local * 4 +
      mobilityBalance(state, player) * 0.18 +
      (state.turn === player ? 2 : -2)
    );
  }

  function findImmediateWinningMove(state, moves = null) {
    const candidates = moves || generateMoves(state);
    const player = state.turn;

    for (const move of candidates) {
      if (inspectMove(state, move, false).winner === player) {
        return move;
      }
    }

    return -1;
  }

  function heuristicReward(state, rootPlayer) {
    const terminal = terminalReward(state, rootPlayer);
    if (terminal >= 0) return terminal;

    const moves = generateMoves(state);
    if (!moves.length) return 0.5;

    /*
     * 輪到的一方已有立即勝利著時，不應由一般靜態評估掩蓋。
     */
    if (findImmediateWinningMove(state, moves) !== -1) {
      return state.turn === rootPlayer ? 0.99 : 0.01;
    }

    const raw = evaluateRaw(state, rootPlayer);
    const scaled = clamp(raw / 110, -8, 8);
    const probability = 1 / (1 + Math.exp(-scaled));

    /*
     * 靜態評估不返回絕對 0/1，以便真正終局始終比估值更可信。
     */
    return 0.02 + probability * 0.96;
  }

  function analyseReplies(state, config) {
    if (state.winner) {
      return {
        replyCount: 0,
        immediateWins: 0,
        bestScore: 0
      };
    }

    const moves = generateMoves(state);

    if (!moves.length) {
      state.winner = 2;

      return {
        replyCount: 0,
        immediateWins: 0,
        bestScore: 0
      };
    }

    const player = state.turn;
    let immediateWins = 0;

    /*
     * 完整掃描所有回應，檢查對手是否下一手即可獲勝。
     * 數量只需計到上限，超過後已足以判定此著非常危險。
     */
    for (const move of moves) {
      if (inspectMove(state, move, false).winner === player) {
        immediateWins++;

        if (immediateWins >= config.maxThreatCount) {
          break;
        }
      }
    }

    /*
     * 額外抽樣少量對手回應，作為兩層戰術排序。
     */
    let bestScore = 0;
    const samples = Math.min(config.replySamples, moves.length);

    for (let index = 0; index < samples; index++) {
      const move = moves[randomInt(moves.length)];
      const score = inspectMove(state, move, true).score;

      if (score > bestScore) {
        bestScore = score;
      }
    }

    return {
      replyCount: moves.length,
      immediateWins,
      bestScore
    };
  }

  class Node {
    constructor(state, parent = null, move = -1, prior = 1, depth = 0) {
      this.state = state;
      this.parent = parent;
      this.move = move;
      this.prior = prior;
      this.depth = depth;

      this.children = [];
      this.actions = null;
      this.nextAction = 0;
      this.originalMoveCount = 0;

      this.visits = 0;
      this.valueSum = 0;
      this.wins = 0;
    }
  }

  function assignPriors(actions, config) {
    if (!actions.length) return;

    actions.forEach(action => {
      action.tie = random();
    });

    actions.sort((left, right) => {
      if (right.score !== left.score) return right.score - left.score;
      return right.tie - left.tie;
    });

    const maximum = actions[0].score;
    let total = 0;

    for (const action of actions) {
      const scaled = clamp(
        (action.score - maximum) / config.priorTemperature,
        -14,
        0
      );

      action.weight = Math.exp(scaled) + 0.001;
      total += action.weight;
    }

    for (const action of actions) {
      action.prior = action.weight / total;
      delete action.weight;
      delete action.tie;
    }
  }

  function buildActions(node, config) {
    const state = node.state;

    if (state.winner) {
      node.actions = [];
      node.originalMoveCount = 0;
      return;
    }

    const moves = generateMoves(state);
    node.originalMoveCount = moves.length;

    if (!moves.length) {
      state.winner = 2;
      node.actions = [];
      return;
    }

    const player = state.turn;
    const all = [];
    const winning = [];
    const nonLosing = [];

    for (const move of moves) {
      const inspected = inspectMove(state, move, true);

      const action = {
        move,
        score: inspected.score,
        winner: inspected.winner,
        danger: 0,
        prior: 0,
        cachedState: null
      };

      all.push(action);

      if (inspected.winner === player) {
        winning.push(action);
      }

      if (inspected.winner !== -player) {
        nonLosing.push(action);
      }
    }

    /*
     * 有立即勝利著時，只保留勝利著。
     * 沒有立即勝利時，只要存在不會當場送勝的著法，
     * 就排除直接令對手獲勝的著法。
     */
    let actions = winning.length
      ? winning
      : nonLosing.length
        ? nonLosing
        : all;

    const useSafetyScreen =
      node.depth === 0 ||
      (
        state.ply >= config.lateTreeSafetyPly &&
        node.depth <= config.lateTreeSafetyDepth
      );

    /*
     * 根節點一定做一手防敗檢查；
     * 後盤分支下降後，也在較淺的樹節點進行同樣檢查。
     */
    if (!winning.length && useSafetyScreen && actions.length > 1) {
      for (const action of actions) {
        const next = applyMove(state, action.move);
        action.cachedState = next;

        if (next.winner) {
          action.danger =
            next.winner === player
              ? 0
              : config.maxThreatCount + 1;

          continue;
        }

        const replyAnalysis = analyseReplies(next, config);
        action.danger = replyAnalysis.immediateWins;

        /*
         * 對手下一手的局部戰術收益也會影響此著的先驗排序。
         */
        action.score -=
          clamp(replyAnalysis.bestScore, 0, 320) *
          config.replyWeight;
      }

      const safeActions = actions.filter(action => action.danger === 0);

      if (safeActions.length) {
        /*
         * 存在不會被下一手直接擊敗的著法時，
         * 不再浪費搜尋量於立即送勝的著法。
         */
        actions = safeActions;
      } else {
        /*
         * 如果所有著法都會遭遇立即威脅，
         * 優先選擇讓對手必勝回應較少的著法。
         */
        for (const action of actions) {
          action.score -= action.danger * 5000;
        }
      }
    }

    assignPriors(actions, config);

    node.actions = actions;
    node.nextAction = 0;
  }

  function ensureActions(node, config) {
    if (node.actions === null) {
      buildActions(node, config);
    }
  }

  function allowedChildren(node, config) {
    const factor = node.depth === 0
      ? config.rootWidening
      : config.widening;

    return Math.max(
      1,
      Math.floor(
        factor *
        Math.pow(node.visits + 1, config.wideningExponent)
      )
    );
  }

  function shouldExpand(node, config) {
    if (!node.actions || node.nextAction >= node.actions.length) {
      return false;
    }

    if (!node.children.length) {
      return true;
    }

    return node.children.length < allowedChildren(node, config);
  }

  function selectChild(node, rootPlayer, config) {
    const rootToMove = node.state.turn === rootPlayer;
    const parentScale = Math.sqrt(node.visits + 1);
    const cpuct = config.exploration * config.cpuctMultiplier;

    let best = null;
    let bestScore = -Infinity;

    for (const child of node.children) {
      const rootMean = child.visits
        ? child.valueSum / child.visits
        : 0.5;

      /*
       * 所有 value 都以根玩家視角儲存。
       * 對手節點則最大化 1-rootMean，相當於最小化根玩家收益。
       */
      const exploitation = rootToMove
        ? rootMean
        : 1 - rootMean;

      const exploration =
        cpuct *
        child.prior *
        parentScale /
        (1 + child.visits);

      const score =
        exploitation +
        exploration +
        random() * 1e-10;

      if (score > bestScore) {
        bestScore = score;
        best = child;
      }
    }

    return best;
  }

  function chooseRolloutMove(state, moves, config, rolloutDepth) {
    const player = state.turn;
    const allMoves = [];
    const nonLosingMoves = [];

    /*
     * 先用較便宜的勝負檢查完整掃描：
     * 1. 有立即勝利著就直接走。
     * 2. 只要有其他選擇，就不走立即送勝著。
     */
    for (const move of moves) {
      const winner = inspectMove(state, move, false).winner;

      if (winner === player) {
        return move;
      }

      allMoves.push(move);

      if (winner !== -player) {
        nonLosingMoves.push(move);
      }
    }

    const pool = nonLosingMoves.length
      ? nonLosingMoves
      : allMoves;

    if (random() < config.rolloutEpsilon) {
      return pool[randomInt(pool.length)];
    }

    /*
     * 不放回抽樣，避免舊版同一著被重複抽到、
     * 實際只評估兩三個不同著法的問題。
     */
    const shuffled = pool.slice();
    const sampleCount = Math.min(config.policySamples, shuffled.length);
    const candidates = [];

    for (let index = 0; index < sampleCount; index++) {
      const swapIndex =
        index +
        randomInt(shuffled.length - index);

      const temporary = shuffled[index];
      shuffled[index] = shuffled[swapIndex];
      shuffled[swapIndex] = temporary;

      const move = shuffled[index];
      const inspected = inspectMove(state, move, true);

      candidates.push({
        move,
        score:
          inspected.score +
          (random() - 0.5) * config.rolloutNoise
      });
    }

    candidates.sort((left, right) => right.score - left.score);

    const shortlistLength = Math.min(
      candidates.length,
      Math.max(
        config.rolloutTop,
        config.rolloutSafetyChecks
      )
    );

    let shortlist = candidates.slice(0, shortlistLength);

    /*
     * rollout 前幾層對候選著法做一手防敗檢查，
     * 大幅減少隨機模擬中的低級送勝。
     */
    if (
      rolloutDepth < config.rolloutSafetyDepth &&
      config.rolloutSafetyChecks > 0
    ) {
      const safeCandidates = [];
      const checks = Math.min(
        config.rolloutSafetyChecks,
        shortlist.length
      );

      for (let index = 0; index < checks; index++) {
        const candidate = shortlist[index];
        const next = applyMove(state, candidate.move);

        if (next.winner === player) {
          return candidate.move;
        }

        if (next.winner === -player) {
          continue;
        }

        const replies = generateMoves(next);

        if (!replies.length) {
          next.winner = 2;
          safeCandidates.push(candidate);
          continue;
        }

        if (findImmediateWinningMove(next, replies) === -1) {
          safeCandidates.push(candidate);
        }
      }

      if (safeCandidates.length) {
        shortlist = safeCandidates;
      }
    }

    const topCount = Math.min(
      config.rolloutTop,
      shortlist.length
    );

    /*
     * 從前幾名中抽取，強度越高越偏向第一名，
     * 但仍保留少量變化，避免 rollout 完全同質化。
     */
    const rank = Math.min(
      topCount - 1,
      Math.floor(
        Math.pow(random(), config.rolloutRankPower) *
        topCount
      )
    );

    return shortlist[rank].move;
  }

  function rollout(startState, rootPlayer, config) {
    const simulation = cloneState(startState);

    const remainingMoves = Math.max(
      1,
      CELL_COUNT - 1 - simulation.ply
    );

    const depthLimit = Math.min(
      config.rolloutDepth,
      remainingMoves
    );

    for (let depth = 0; depth < depthLimit; depth++) {
      const terminal = terminalReward(simulation, rootPlayer);

      if (terminal >= 0) {
        return terminal;
      }

      const moves = generateMoves(simulation);

      if (!moves.length) {
        return 0.5;
      }

      const move = chooseRolloutMove(
        simulation,
        moves,
        config,
        depth
      );

      applyMoveInPlace(simulation, move);
    }

    return heuristicReward(simulation, rootPlayer);
  }

  function runIteration(root, rootPlayer, config) {
    let node = root;
    let reward = -1;

    while (true) {
      const terminal = terminalReward(node.state, rootPlayer);

      if (terminal >= 0) {
        reward = terminal;
        break;
      }

      ensureActions(node, config);

      if (!node.actions.length) {
        reward = terminalReward(node.state, rootPlayer);

        if (reward < 0) {
          reward = 0.5;
        }

        break;
      }

      if (shouldExpand(node, config)) {
        const action = node.actions[node.nextAction++];
        const nextState =
          action.cachedState ||
          applyMove(node.state, action.move);

        action.cachedState = null;

        const child = new Node(
          nextState,
          node,
          action.move,
          action.prior,
          node.depth + 1
        );

        node.children.push(child);
        node = child;
        break;
      }

      const selected = selectChild(
        node,
        rootPlayer,
        config
      );

      if (!selected) {
        break;
      }

      node = selected;
    }

    if (reward < 0) {
      reward = rollout(node.state, rootPlayer, config);
    }

    while (node) {
      node.visits++;
      node.valueSum += reward;

      if (reward >= 0.999999) {
        node.wins++;
      }

      node = node.parent;
    }
  }

  function bestRootChild(root) {
    let best = null;

    for (const child of root.children) {
      if (
        !best ||
        child.visits > best.visits ||
        (
          child.visits === best.visits &&
          child.valueSum / child.visits >
            best.valueSum / best.visits
        )
      ) {
        best = child;
      }
    }

    return best;
  }

  self.onmessage = function (event) {
    const data = event.data;

    if (!data || data.type !== 'start') {
      return;
    }

    const level = PROFILES[data.level]
      ? data.level
      : 'hard';

    const config = {
      ...PROFILES[level]
    };

    const suppliedExploration = Number(data.exploration);

    config.exploration = Number.isFinite(suppliedExploration)
      ? clamp(suppliedExploration, 0.1, 4)
      : 1.2;

    const limit = Math.max(
      50,
      Number(data.limitMs) || 6000
    );

    const rootState = {
      board: Int8Array.from(data.state.board),
      claims: Int8Array.from(data.state.claims),
      turn: data.state.turn,
      winner: data.state.winner,
      ply: data.state.ply
    };

    const token = data.token;
    const rootPlayer = rootState.turn;

    seedRandom(
      hashState(rootState) ^
      (Number(token) || 0) ^
      (Date.now() >>> 0)
    );

    const root = new Node(rootState);
    const start = performance.now();
    const deadline = start + limit;

    let iterations = 0;
    let nextUpdate = 100;

    const initialTerminal = terminalReward(
      rootState,
      rootPlayer
    );

    if (initialTerminal >= 0) {
      self.postMessage({
        type: 'done',
        token,
        elapsed: performance.now() - start,
        iterations: 0,
        move: null,
        expected: initialTerminal,
        winRate: initialTerminal === 1 ? 1 : 0
      });

      return;
    }

    /*
     * 先完成根節點戰術篩選。
     * 這一步能保證 AI 不會漏掉當前立即勝利著。
     */
    ensureActions(root, config);

    if (!root.actions.length) {
      self.postMessage({
        type: 'done',
        token,
        elapsed: performance.now() - start,
        iterations: 0,
        move: null,
        expected: 0.5,
        winRate: 0
      });

      return;
    }

    const immediateWin = root.actions.find(
      action => action.winner === rootPlayer
    );

    if (immediateWin) {
      self.postMessage({
        type: 'done',
        token,
        elapsed: performance.now() - start,
        iterations: 0,
        move: publicMove(immediateWin.move),
        expected: 1,
        winRate: 1
      });

      return;
    }

    while (performance.now() < deadline) {
      for (
        let batch = 0;
        batch < config.batchSize;
        batch++
      ) {
        runIteration(root, rootPlayer, config);
        iterations++;

        if (
          (batch & 3) === 3 &&
          performance.now() >= deadline
        ) {
          break;
        }
      }

      const elapsed = performance.now() - start;

      if (elapsed >= nextUpdate) {
        self.postMessage({
          type: 'progress',
          token,
          elapsed,
          iterations
        });

        nextUpdate += 100;

        if (nextUpdate < elapsed) {
          nextUpdate =
            Math.floor(elapsed / 100) * 100 + 100;
        }
      }
    }

    const best = bestRootChild(root);

    let selectedMove = -1;
    let expected = 0.5;
    let winRate = 0;

    if (best && best.visits) {
      selectedMove = best.move;
      expected = best.valueSum / best.visits;
      winRate = best.wins / best.visits;
    } else {
      /*
       * 即使時間全花在根節點戰術分析，
       * 也能使用排序第一的合法著，而不是隨機著。
       */
      const fallbackAction = root.actions[0];
      selectedMove = fallbackAction.move;

      const next =
        fallbackAction.cachedState ||
        applyMove(rootState, selectedMove);

      const terminal = terminalReward(next, rootPlayer);

      expected = terminal >= 0
        ? terminal
        : heuristicReward(next, rootPlayer);

      winRate = terminal === 1 ? 1 : 0;
    }

    self.postMessage({
      type: 'done',
      token,
      elapsed: performance.now() - start,
      iterations,
      move: publicMove(selectedMove),
      expected,
      winRate
    });
  };
</script>

const AI_LEVELS = {
  easy: {
    ms: DEFAULT_AI_SECONDS.easy * 1000,
    exploration: 1.55
  },

  hard: {
    ms: DEFAULT_AI_SECONDS.hard * 1000,
    exploration: 1.25
  },

  expert: {
    ms: DEFAULT_AI_SECONDS.expert * 1000,
    exploration: 1.05
  },

  custom: {
    ms: DEFAULT_AI_SECONDS.custom * 1000,
    exploration: 1.15
  }
};

function runFallbackAI(token, started) {
  if (token !== aiToken) return;

  const rootPlayer = state.turn;
  const level = controllers[rootPlayer];
  const moves = getLegalMoves(state);

  thinking = false;

  if (!moves.length) {
    state.winner = 2;
    history[historyIndex].state = cloneState(state);
    renderAll();
    return;
  }

  const localWeights = [0, 0.4, 3, 12];
  const metaWeights = [0, 3, 22, 1000];

  function fallbackPositionScore(position) {
    if (position.winner === rootPlayer) return 1000000;
    if (position.winner === -rootPlayer) return -1000000;
    if (position.winner === 2) return 0;

    let score = 0;

    /*
     * 已控制島嶼的價值。
     */
    for (let island = 0; island < 7; island++) {
      if (position.claims[island] === rootPlayer) {
        score += 80;
      } else if (position.claims[island] === -rootPlayer) {
        score -= 80;
      }
    }

    /*
     * 整個群島上的成線潛力。
     */
    for (const line of LOCAL_LINES) {
      let own = 0;
      let enemy = 0;

      for (const island of line) {
        if (position.claims[island] === rootPlayer) {
          own++;
        } else if (position.claims[island] === -rootPlayer) {
          enemy++;
        }
      }

      if (enemy === 0) {
        score += metaWeights[own];
      }

      if (own === 0) {
        score -= metaWeights[enemy];
      }
    }

    /*
     * 各島內的局部成線潛力。
     */
    for (let island = 0; island < 7; island++) {
      const base = island * 7;

      for (const line of LOCAL_LINES) {
        let own = 0;
        let enemy = 0;

        for (const point of line) {
          const occupant = position.board[base + point];

          if (occupant === rootPlayer) {
            own++;
          } else if (occupant === -rootPlayer) {
            enemy++;
          }
        }

        if (enemy === 0) {
          score += localWeights[own] * 4;
        }

        if (own === 0) {
          score -= localWeights[enemy] * 4;
        }
      }
    }

    return score;
  }

  let bestMove = null;
  let bestNext = null;
  let bestScore = -Infinity;

  for (const move of moves) {
    const next = applyMove(state, move);
    if (!next) continue;

    let score = fallbackPositionScore(next);

    if (next.winner === rootPlayer) {
      score = 1000000;
    } else if (next.winner === -rootPlayer) {
      score = -1000000;
    } else if (next.winner !== 2) {
      /*
       * 排除會讓對手下一手立即勝利的著法。
       */
      const replies = getLegalMoves(next);
      let opponentCanWinImmediately = false;

      for (const reply of replies) {
        const afterReply = applyMove(next, reply);

        if (afterReply?.winner === -rootPlayer) {
          opponentCanWinImmediately = true;
          break;
        }
      }

      if (opponentCanWinImmediately) {
        score -= 500000;
      }
    }

    /*
     * 只用極小亂數打破完全同分，不影響戰術排序。
     */
    score += Math.random() * 1e-7;

    if (score > bestScore) {
      bestScore = score;
      bestMove = move;
      bestNext = next;
    }
  }

  if (!bestMove) {
    bestMove = moves[0];
    bestNext = applyMove(state, bestMove);
    bestScore = bestNext
      ? fallbackPositionScore(bestNext)
      : 0;
  }

  let expected;

  if (bestNext?.winner === rootPlayer) {
    expected = 1;
  } else if (bestNext?.winner === -rootPlayer) {
    expected = 0;
  } else if (bestNext?.winner === 2) {
    expected = 0.5;
  } else {
    const bounded = Math.max(-500, Math.min(500, bestScore));
    expected = 1 / (1 + Math.exp(-bounded / 110));
  }

  commitMove(bestMove, 'ai', {
    elapsed: performance.now() - started,
    iterations: 0,
    expected,
    winRate: bestNext?.winner === rootPlayer ? 1 : 0,
    level
  });
}

aiWorker.onerror = event => {
  if (token !== aiToken) return;

  console.error(
    'MCTS Worker 執行失敗，改用戰術後備 AI：',
    event.message || event
  );

  aiWorker?.terminate();
  aiWorker = null;
  runFallbackAI(token, started);
};