6.2 塔防的策略空间

// file: core/genre/tdspace.ts
// tier: P
// verify: node --test 'core/test/gd_proto_06_2_strategy_space.test.ts'
//
// 塔防的**策略空间**分析层：把「塔位 × 塔种 × 升级次序」枚举成空间，算空间熵与结果分布的
// Shannon 熵（×1000，纯整数）。它只 import 内核 towerdefense.ts，同样不碰共享底座。
// 熵 / 支配度都是**代理指标**（proxy），只做相对比较，禁绝对化。

import { rngNext } from "../src/ashdeck/rng.ts";
import { idiv, tdRun, type TdOp, type TdSpec, type TdSnapshot } from "./towerdefense.ts";

export type TdEnumOptions = { slots: number; maxDepth: number; cap: number; seeds: number[] };
export type TdEnumResult = {
  slots: number; maxDepth: number; cap: number; capHit: boolean; size: number; projectedSize: number;
  runs: number; spaceEntropyMilli: number; outcomeEntropyMilli: number; dominantPermille: number;
  dominantMissingPermille: number; distinctOutcomes: number; bestStrategy: TdOp[]; bestPermille: number;
  outcomes: { key: string; count: number }[];
};
export type TdSampleOptions = {
  slots: number; maxDepth: number; draws: number; seed: number; seeds: number[]; structCap: number;
};
export type TdSampleResult = {
  draws: number; runs: number; seed: number; structSize: number; structCapHit: boolean;
  dominantPermille: number; outcomeEntropyMilli: number; distinctOutcomes: number;
  outcomes: { key: string; count: number }[];
};

/** floor(log2(n) * 1000)，纯 BigInt 整数运算，供策略熵使用（禁浮点）。 */
export function log2Milli(n: number): number {
  if (n < 1) return 0;
  const one = 1n << 20n;
  let x = BigInt(n) << 20n;
  let k = 0;
  while (x >= one << 1n) { x >>= 1n; k += 1; }
  let frac = 0;
  for (let i = 0; i < 10; i += 1) {
    x = (x * x) >> 20n;
    frac <<= 1;
    if (x >= one << 1n) { frac += 1; x >>= 1n; }
  }
  return k * 1000 + Math.floor((frac * 1000) / 1024);
}

/** 离散分布的 Shannon 熵 ×1000（比特），整数地板除。 */
export function entropyMilli(counts: number[]): number {
  let total = 0;
  for (const c of counts) total += c;
  if (total <= 1) return 0;
  let s = 0;
  for (const c of counts) if (c > 0) s += c * log2Milli(c);
  return Math.floor((total * log2Milli(total) - s) / total);
}

/** 忽略花费剪枝的序列数上界：1 + A + A^2 + … + A^D，A = 塔位数 × 塔种数 + 塔位数。 */
export function tdProjectedSize(slotCount: number, typeCount: number, maxDepth: number): number {
  const a = slotCount * typeCount + slotCount;
  let sum = 1;
  let term = 1;
  for (let d = 1; d <= maxDepth; d += 1) { term *= a; sum += term; }
  return sum;
}

/** 结果键：先按多数种子是否取胜定 W/L，再按平均剩余基地血量千分比分桶。 */
export function tdOutcomeKey(spec: TdSpec, seq: TdOp[], seeds: number[]): { key: string; avg: number } {
  let sum = 0, wins = 0;
  for (const sd of seeds) {
    const sp = JSON.parse(JSON.stringify(spec)) as TdSpec;
    sp.seed = sd;
    const s: TdSnapshot = tdRun(sp, seq);
    sum += idiv(1000 * s.baseHp, spec.state.baseHp);
    if (s.won) wins += 1;
  }
  const avg = idiv(sum, seeds.length);
  return { key: (wins * 2 >= seeds.length ? "W" : "L") + ":" + avg, avg };
}

/** 精确枚举小规模布防（塔位 × 塔种 × 升级次序），算空间大小与结果分布的 Shannon 熵。 */
export function tdEnumerate(spec: TdSpec, opts: TdEnumOptions): TdEnumResult {
  const slots = spec.rules.slots.slice(0, opts.slots);
  const types = spec.rules.towerTypes;
  const counts = new Map<string, number>();
  const layout: number[] = slots.map(() => -1);
  const level: number[] = slots.map(() => 0);
  const seq: TdOp[] = [];
  let size = 0, runs = 0, capHit = false, bestPermille = -1;
  let bestStrategy: TdOp[] = [];

  const rec = (spent: number): void => {
    size += 1;
    if (size > opts.cap) { capHit = true; return; }
    const o = tdOutcomeKey(spec, seq, opts.seeds);
    runs += opts.seeds.length;
    counts.set(o.key, (counts.get(o.key) ?? 0) + 1);
    if (o.avg > bestPermille) { bestPermille = o.avg; bestStrategy = seq.slice(); }
    if (seq.length >= opts.maxDepth) return;
    for (let s = 0; s < slots.length; s += 1) {
      if (layout[s] < 0) {
        for (let t = 0; t < types.length; t += 1) {
          if (spent + types[t].cost > spec.state.gold) continue;
          layout[s] = t; level[s] = 1;
          seq.push({ w: 1, op: "b", slot: slots[s].id, type: types[t].id });
          rec(spent + types[t].cost);
          seq.pop(); layout[s] = -1; level[s] = 0;
          if (capHit) return;
        }
      } else if (level[s] < spec.rules.upgrade.maxLevel) {
        if (spent + spec.rules.upgrade.cost > spec.state.gold) continue;
        level[s] += 1;
        seq.push({ w: 1, op: "u", slot: slots[s].id });
        rec(spent + spec.rules.upgrade.cost);
        seq.pop(); level[s] -= 1;
        if (capHit) return;
      }
    }
  };
  rec(0);

  const outcomes = [...counts.entries()]
    .map(([key, count]) => ({ key, count }))
    .sort((a, b) => (b.count - a.count) || a.key.localeCompare(b.key));
  const counted = outcomes.reduce((a, o) => a + o.count, 0);
  const dominant = outcomes.length > 0 ? outcomes[0].count : 0;
  const domPermille = counted === 0 ? 0 : idiv(1000 * dominant, counted);
  return {
    slots: slots.length, maxDepth: opts.maxDepth, cap: opts.cap, capHit, size,
    projectedSize: tdProjectedSize(slots.length, types.length, opts.maxDepth), runs,
    spaceEntropyMilli: log2Milli(size),
    outcomeEntropyMilli: entropyMilli(outcomes.map((o) => o.count)),
    dominantPermille: domPermille, dominantMissingPermille: 1000 - domPermille,
    distinctOutcomes: outcomes.length, bestStrategy, bestPermille, outcomes,
  };
}

/** 结构枚举：只生成合法布防序列（不跑仿真），受 structCap 限制，供按索引均匀抽样用。 */
export function tdStructEnum(spec: TdSpec, slotsCount: number, maxDepth: number, structCap: number):
  { all: TdOp[][]; capHit: boolean } {
  const slots = spec.rules.slots.slice(0, slotsCount);
  const types = spec.rules.towerTypes;
  const layout: number[] = slots.map(() => -1);
  const level: number[] = slots.map(() => 0);
  const seq: TdOp[] = [];
  const all: TdOp[][] = [];
  let capHit = false;

  const rec = (spent: number): void => {
    all.push(seq.slice());
    if (all.length >= structCap) { capHit = true; return; }
    if (seq.length >= maxDepth) return;
    for (let s = 0; s < slots.length; s += 1) {
      if (layout[s] < 0) {
        for (let t = 0; t < types.length; t += 1) {
          if (spent + types[t].cost > spec.state.gold) continue;
          layout[s] = t; level[s] = 1;
          seq.push({ w: 1, op: "b", slot: slots[s].id, type: types[t].id });
          rec(spent + types[t].cost);
          seq.pop(); layout[s] = -1; level[s] = 0;
          if (capHit) return;
        }
      } else if (level[s] < spec.rules.upgrade.maxLevel) {
        if (spent + spec.rules.upgrade.cost > spec.state.gold) continue;
        level[s] += 1;
        seq.push({ w: 1, op: "u", slot: slots[s].id });
        rec(spent + spec.rules.upgrade.cost);
        seq.pop(); level[s] -= 1;
        if (capHit) return;
      }
    }
  };
  rec(0);
  return { all, capHit };
}

/** 按索引均匀采样：先结构枚举出索引空间，再用 rngNext 均匀抽 draws 条**只对这 draws 条**跑仿真。 */
export function tdSample(spec: TdSpec, opts: TdSampleOptions): TdSampleResult {
  const { all, capHit } = tdStructEnum(spec, opts.slots, opts.maxDepth, opts.structCap);
  const counts = new Map<string, number>();
  let rngState = opts.seed % 2147483647 || 1;
  let runs = 0;
  for (let d = 0; d < opts.draws; d += 1) {
    rngState = rngNext(rngState);
    const o = tdOutcomeKey(spec, all[rngState % all.length], opts.seeds);
    runs += opts.seeds.length;
    counts.set(o.key, (counts.get(o.key) ?? 0) + 1);
  }
  const outcomes = [...counts.entries()]
    .map(([key, count]) => ({ key, count }))
    .sort((a, b) => (b.count - a.count) || a.key.localeCompare(b.key));
  const counted = outcomes.reduce((a, o) => a + o.count, 0);
  const dominant = outcomes.length > 0 ? outcomes[0].count : 0;
  return {
    draws: opts.draws, runs, seed: opts.seed, structSize: all.length, structCapHit: capHit,
    dominantPermille: counted === 0 ? 0 : idiv(1000 * dominant, counted),
    outcomeEntropyMilli: entropyMilli(outcomes.map((o) => o.count)),
    distinctOutcomes: outcomes.length, outcomes,
  };
}

✔ 整数对数与熵的标定点：log2 与均匀分布熵都对得上
✔ 精确枚举：空间大小与结果分布熵（×1000）
✔ 支配策略缺失度：支配项占 669‰，缺失 331‰
✔ 枚举是确定性的：同一份规格两次枚举逐字相同
✔ 花费剪枝把上界压到千分之二：271453 → 529
✔ 何时改用采样：全配置上界 469070941 远超 cap，子空间 529 在 cap 内
✔ 按索引均匀采样 512 次：支配度与熵都落回精确值容差内
✔ 抽样不足会低估熵：64 次抽样的熵偏差超出容差
✔ 最优布防在单波子空间与六波全配置里都取胜
ℹ tests 9
ℹ pass 9
ℹ fail 0