CI / test (pull_request) Canceled after 0s
- analysis/tree/build_tree.py -> data/public/tree.json, analysis/reports/TREE.md: every screen the bot has seen, every option, where each led (fixed or dice, with ranges), best known picks per colour chosen cautiously, where any picks end, and the untested options. solver.js screenPick(): least-tried and Thompson picks from the tree. - The bot logs a pick it then overrode as a step: 37 runs were coded with choices they never made. Importer and graph.js now use the played steps only. - runs_clean.csv: the Unofficial Dragon Register's 288 bonded dragons are in the master list as outcome-only rows, flagged (no analysis uses them). - Cycle, refresh and the bot kit rebuild and carry the tree; tests check every generated report is current. Co-Authored-By: Claude Fable 5.2 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014jqCC2LZ4x1WHQ1V57nTsv
320 lines
16 KiB
Python
320 lines
16 KiB
Python
"""The screen tree: every screen the bot has seen, every option on it, and where each option led.
|
|
|
|
python analysis/tree/build_tree.py [--check] -> data/public/tree.json, analysis/reports/TREE.md
|
|
|
|
Built from the bot's logs only (data/bot/), because only the bot records every screen and every pick; the community
|
|
form records a summary of a run. For each option on each screen:
|
|
|
|
n how many times it was played
|
|
to where it led, with counts and a 90% range for each destination
|
|
kind untested never played
|
|
fixed always led to the same place so far
|
|
dice led to more than one place (the game's seeded draws)
|
|
missed for a fixed option: the chance that a second destination with odds of 1 in 20 or better has simply not
|
|
come up yet (0.95 ** n). The developer has said no single event is rarer than 1 in 20
|
|
(planner/knowledge.yaml), so this is how sure "fixed" is.
|
|
|
|
Then, treating a screen's odds as the same whatever came before it (true for the seeded draws; NOT true for the
|
|
shadow, which is a guard on earlier choices), the tree gives for every screen the best known chance of bonding each
|
|
colour and the picks that get it, and for any set of picks where the run ends and how often.
|
|
|
|
What counts as played: a pick the bot logged and then overrode on the same screen is dropped (collection/etl/runs.py
|
|
`played`). A deliberate burn is a real pick with a real result, so it is counted. An aborted run counts up to its
|
|
last screen.
|
|
"""
|
|
import argparse
|
|
import hashlib
|
|
import json
|
|
import math
|
|
import sys
|
|
from pathlib import Path
|
|
|
|
ROOT = Path(__file__).resolve().parents[2]
|
|
sys.path.insert(0, str(ROOT))
|
|
from collection.etl.runs import played # noqa: E402
|
|
|
|
BOT = ROOT / "data/bot"
|
|
OUT = ROOT / "data/public/tree.json"
|
|
REPORT = ROOT / "analysis/reports/TREE.md"
|
|
FLOOR = 0.05 # no single event is rarer than 1 in 20
|
|
DIED = "DIED"
|
|
COLOURS = ["Red", "Orange", "Brown", "Green", "Blue", "Black"]
|
|
|
|
|
|
def wilson(y, n, z=1.645):
|
|
"""A 90% range for a rate (Wilson score)."""
|
|
if not n:
|
|
return None, None
|
|
p = y / n
|
|
d = 1 + z * z / n
|
|
c = (p + z * z / (2 * n)) / d
|
|
h = z * math.sqrt(p * (1 - p) / n + z * z / (4 * n * n)) / d
|
|
return max(0.0, c - h), min(1.0, c + h)
|
|
|
|
|
|
def trajectories(bot_dir=BOT):
|
|
seen, out = set(), []
|
|
for f in sorted(Path(bot_dir).glob("trajectories-*.jsonl")):
|
|
for line in open(f, encoding="utf-8"):
|
|
t = json.loads(line)
|
|
if t["id"] not in seen:
|
|
seen.add(t["id"])
|
|
out.append(t)
|
|
return out
|
|
|
|
|
|
def destination(step, nxt, outcome):
|
|
"""Where a played step led: the next screen, or how the run ended there. None: not known (an aborted run)."""
|
|
if nxt is not None:
|
|
return nxt["scene"]
|
|
to = step.get("to")
|
|
if to and to not in ("BURNED",) and not str(to).startswith("BONDED"):
|
|
return to # the bot saw the next screen but the run was not finished
|
|
kind = (outcome or {}).get("type")
|
|
if kind == "BONDED" or str(to).startswith("BONDED"):
|
|
colour = (outcome or {}).get("colour") or str(to).split(":")[-1]
|
|
return "BONDED:" + str(colour).capitalize()
|
|
if kind == "BURNED" or to == "BURNED":
|
|
return DIED
|
|
return None
|
|
|
|
|
|
def build(trajs=None, scenes=None):
|
|
trajs = trajectories() if trajs is None else trajs
|
|
scenes = json.loads((BOT / "scenes.json").read_text(encoding="utf-8")) if scenes is None else scenes
|
|
screens = {}
|
|
|
|
def screen(sid, step=None):
|
|
if sid not in screens:
|
|
s = scenes.get(sid, {})
|
|
screens[sid] = {"label": s.get("label") or (step or {}).get("stage") or sid, "stage": s.get("stage") or (step or {}).get("stage"),
|
|
"tint": s.get("tint"), "visits": 0, "options": {}}
|
|
for o in s.get("options", []):
|
|
screens[sid]["options"][o["id"]] = {"text": o["text"], "n": 0, "deliberate": 0, "to": {}}
|
|
return screens[sid]
|
|
|
|
for sid in scenes:
|
|
screen(sid)
|
|
stats = {"runs": 0, "steps": 0, "overridden": 0, "unknownEnd": 0, "noSteps": 0}
|
|
starts = {}
|
|
for t in trajs:
|
|
steps = played(t["steps"])
|
|
stats["runs"] += 1
|
|
stats["overridden"] += len(t["steps"]) - len(steps)
|
|
if not steps:
|
|
stats["noSteps"] += 1
|
|
continue
|
|
starts[steps[0]["scene"]] = starts.get(steps[0]["scene"], 0) + 1
|
|
for i, s in enumerate(steps):
|
|
sc = screen(s["scene"], s)
|
|
sc["visits"] += 1
|
|
o = sc["options"].setdefault(s["option"], {"text": s.get("optionText"), "n": 0, "deliberate": 0, "to": {}})
|
|
dest = destination(s, steps[i + 1] if i + 1 < len(steps) else None, t.get("outcome"))
|
|
if dest is None:
|
|
stats["unknownEnd"] += 1
|
|
continue
|
|
stats["steps"] += 1
|
|
o["n"] += 1
|
|
o["deliberate"] += s.get("stage") == "INTENTIONAL_BURN"
|
|
o["to"][dest] = o["to"].get(dest, 0) + 1
|
|
|
|
for sc in screens.values():
|
|
for o in sc["options"].values():
|
|
n = o["n"]
|
|
o["kind"] = "untested" if not n else "fixed" if len(o["to"]) == 1 else "dice"
|
|
if o["kind"] == "fixed":
|
|
o["missed"] = round((1 - FLOOR) ** n, 4)
|
|
o["to"] = {d: {"n": k, "p": round(k / n, 4), "lo": round(wilson(k, n)[0], 4), "hi": round(wilson(k, n)[1], 4)}
|
|
for d, k in sorted(o["to"].items(), key=lambda kv: (-kv[1], kv[0]))}
|
|
if not o["deliberate"]:
|
|
del o["deliberate"]
|
|
|
|
# screens the bot's own labels do not tell apart get the start of their id
|
|
names = {}
|
|
for sid, sc in screens.items():
|
|
names.setdefault(sc["label"], []).append(sid)
|
|
for label, ids in names.items():
|
|
if len(ids) > 1:
|
|
for sid in ids:
|
|
screens[sid]["label"] = f"{label} #{sid[:4]}"
|
|
|
|
tree = {"schema": 1, "floor": FLOOR, "start": max(starts, key=starts.get) if starts else None, "builtFrom": stats,
|
|
"screens": {k: screens[k] for k in sorted(screens)}}
|
|
tree["best"] = {c: best(tree, c) for c in COLOURS}
|
|
tree["coverage"] = coverage(tree)
|
|
tree["id"] = hashlib.sha1(json.dumps(tree, sort_keys=True, separators=(",", ":")).encode()).hexdigest()[:12]
|
|
return tree
|
|
|
|
|
|
# ---------------------------------------------------------------- reading the tree
|
|
|
|
def value(tree, colour, picks=None, cautious=False):
|
|
"""For every screen: the chance of bonding `colour` from there, and the pick that gives it. picks: {screen:
|
|
option id} to follow fixed picks (any screen not in it takes its best tested option). Untested options, and
|
|
screens nobody has played, count as zero: these are chances known so far, not upper limits.
|
|
cautious: every option is given one extra, unseen run that failed (k / (n + 1)), so a step played once counts
|
|
for half and a step played 400 times loses almost nothing. Without it, the best "route" is whichever chain of
|
|
lucky single runs happens to exist."""
|
|
S, memo, choice = tree["screens"], {}, {}
|
|
target = "BONDED:" + colour
|
|
|
|
def v(sid, stack=()):
|
|
if sid == target:
|
|
return 1.0
|
|
if sid == DIED or sid.startswith("BONDED:") or sid not in S or sid in stack:
|
|
return 0.0
|
|
if sid in memo:
|
|
return memo[sid]
|
|
top, arg = 0.0, None
|
|
for oid, o in S[sid]["options"].items():
|
|
if not o["n"] or (picks and sid in picks and picks[sid] != oid):
|
|
continue
|
|
x = sum((d["n"] / (o["n"] + 1) if cautious else d["p"]) * v(dest, stack + (sid,)) for dest, d in o["to"].items())
|
|
if arg is None or x > top + 1e-12:
|
|
top, arg = x, oid
|
|
memo[sid], choice[sid] = top, arg
|
|
return top
|
|
|
|
for sid in S:
|
|
v(sid)
|
|
return memo, choice
|
|
|
|
|
|
def best(tree, colour):
|
|
"""The best known chance of bonding a colour from the start, and the picks on the way (following the likeliest
|
|
result of every dice step that can still reach the colour)."""
|
|
if not tree["start"]:
|
|
return {"p": 0.0, "picks": []}
|
|
careful, choice = value(tree, colour, cautious=True) # choose on the cautious numbers,
|
|
val, _ = value(tree, colour, picks=choice) # report the observed ones for those picks
|
|
S, picks, sid, seen = tree["screens"], [], tree["start"], set()
|
|
while sid in S and sid not in seen and choice.get(sid) and val.get(sid, 0) > 0:
|
|
seen.add(sid)
|
|
o = S[sid]["options"][choice[sid]]
|
|
picks.append({"screen": sid, "label": S[sid]["label"], "option": choice[sid], "text": o["text"], "n": o["n"],
|
|
"kind": o["kind"], "p": round(val[sid], 6)})
|
|
nxt = [d for d in o["to"] if d == "BONDED:" + colour or val.get(d, 0) > 0]
|
|
if not nxt:
|
|
break
|
|
sid = max(nxt, key=lambda d: (d == "BONDED:" + colour, o["to"][d]["p"] * (1 if d.startswith("BONDED") else val.get(d, 0))))
|
|
return {"p": round(val.get(tree["start"], 0.0), 6), "pCautious": round(careful.get(tree["start"], 0.0), 6),
|
|
"picks": picks, "ends": outcomes(tree, choice)}
|
|
|
|
|
|
def outcomes(tree, picks):
|
|
"""Where a run ends when these picks are followed: {ending: chance}. picks: {screen: option id}; a screen
|
|
without one takes the option played most. "not mapped" is the share that reaches an untested option or a
|
|
screen nobody has played."""
|
|
S, out = tree["screens"], {}
|
|
|
|
def walk(sid, p, depth=0):
|
|
if sid == DIED or sid.startswith("BONDED:"):
|
|
out[sid] = out.get(sid, 0) + p
|
|
return
|
|
sc = S.get(sid)
|
|
oid = (picks or {}).get(sid) if sc else None
|
|
if sc and oid is None:
|
|
tried = [k for k, o in sc["options"].items() if o["n"]]
|
|
oid = max(tried, key=lambda k: sc["options"][k]["n"]) if tried else None
|
|
if not sc or oid not in sc["options"] or not sc["options"][oid]["n"] or depth > 200:
|
|
out["not mapped"] = out.get("not mapped", 0) + p
|
|
return
|
|
for dest, d in sc["options"][oid]["to"].items():
|
|
walk(dest, p * d["p"], depth + 1)
|
|
|
|
if tree["start"]:
|
|
walk(tree["start"], 1.0)
|
|
return {k: round(v, 6) for k, v in sorted(out.items(), key=lambda kv: -kv[1])}
|
|
|
|
|
|
def coverage(tree):
|
|
S = tree["screens"]
|
|
opts = [(sid, oid, o) for sid, sc in S.items() for oid, o in sc["options"].items()]
|
|
dests = {d for _, _, o in opts for d in o["to"]}
|
|
untested = sorted(((S[sid]["visits"], sid, oid) for sid, oid, o in opts if not o["n"]), reverse=True)
|
|
return {"screens": len(S), "options": len(opts), "tested": sum(1 for _, _, o in opts if o["n"]),
|
|
"fixed": sum(1 for _, _, o in opts if o["kind"] == "fixed"), "dice": sum(1 for _, _, o in opts if o["kind"] == "dice"),
|
|
"fixedSure": sum(1 for _, _, o in opts if o["kind"] == "fixed" and o["missed"] <= 0.05),
|
|
"endings": sorted(d for d in dests if d == DIED or d.startswith("BONDED:")),
|
|
# the cheapest gaps to fill first: untested options on the screens the bot reaches most often
|
|
"untested": [{"screen": sid, "label": S[sid]["label"], "option": oid, "text": S[sid]["options"][oid]["text"],
|
|
"screenVisits": v} for v, sid, oid in untested]}
|
|
|
|
|
|
# ---------------------------------------------------------------- the report
|
|
|
|
def pct(p):
|
|
return f"{100 * p:.1f}%" if p >= 0.001 or p == 0 else f"{100 * p:.2f}%"
|
|
|
|
|
|
def report(tree):
|
|
S, cov, b = tree["screens"], tree["coverage"], tree["builtFrom"]
|
|
L = ["# The screen tree", "",
|
|
f"Written by `analysis/tree/build_tree.py` from the bot's logs: {b['runs']} runs, {b['steps']} played steps "
|
|
f"({b['overridden']} picks the bot logged and then overrode are left out). Machine-readable: "
|
|
"`data/public/tree.json`.", "",
|
|
"## Coverage", "",
|
|
f"- Screens seen: {cov['screens']}. Options on them: {cov['options']}, of which {cov['tested']} have been played "
|
|
f"and {cov['options'] - cov['tested']} never have.",
|
|
f"- Played options that are dice (led to more than one place): {cov['dice']}. Always the same place so far: "
|
|
f"{cov['fixed']}, of which {cov['fixedSure']} have been played often enough (59 times or more) that a hidden "
|
|
"1-in-20 branch would very likely have shown.",
|
|
f"- Endings reached: {', '.join(cov['endings'])}.", "",
|
|
"A screen only appears here once the bot has stood on it, so screens behind untested options are missing "
|
|
"altogether: the tree is a floor on the size of the game, not its size.", "",
|
|
"## The dice", "", "Every option that has led to more than one place, most played first (90% range).", "",
|
|
"| Screen | Option | Played | Led to |", "|---|---|---|---|"]
|
|
lab = lambda d: d if d == DIED or d.startswith("BONDED:") else S[d]["label"] if d in S else d # noqa: E731
|
|
dice = sorted(((o["n"], sid, oid) for sid, sc in S.items() for oid, o in sc["options"].items() if o["kind"] == "dice"), reverse=True)
|
|
for n, sid, oid in dice:
|
|
o = S[sid]["options"][oid]
|
|
L.append(f"| {S[sid]['label']} | {o['text'][:60]} | {n} | "
|
|
+ "; ".join(f"{lab(d)} {pct(x['p'])} ({pct(x['lo'])}-{pct(x['hi'])})" for d, x in o["to"].items()) + " |")
|
|
L += ["", "## Best known chance of each colour", "",
|
|
"From the first screen, taking the best tested option on every screen. Untested options count as zero, so "
|
|
"these are what is known to be achievable, not limits; a colour the bot has never bonded shows 0. "
|
|
"\"As observed\" multiplies the rates seen. \"Cautious\" adds one unseen failure to every step, which is what "
|
|
"the picks are chosen on: a chain of steps each played once is worth little.", "",
|
|
"| Colour | As observed | Cautious | Weakest step on the way | These picks end in |", "|---|---|---|---|---|"]
|
|
for c in COLOURS:
|
|
r = tree["best"][c]
|
|
weak = min(r["picks"], key=lambda k: k["n"]) if r["picks"] else None
|
|
L.append(f"| {c} | {pct(r['p'])} | {pct(r['pCautious'])} | "
|
|
+ (f"{weak['label']}: \"{weak['text'][:50]}\", played {weak['n']} times" if weak else "no bond logged") + " | "
|
|
+ (", ".join(f"{k} {pct(v)}" for k, v in r["ends"].items()) if weak else "") + " |")
|
|
for c in ("Blue",):
|
|
r = tree["best"][c]
|
|
if r["picks"]:
|
|
L += ["", f"### The picks for {c}", "", "| Screen | Pick | Played | Chance of the bond from here |", "|---|---|---|---|"]
|
|
L += [f"| {k['label']} | {k['text'][:70]} | {k['n']} | {pct(k['p'])} |" for k in r["picks"]]
|
|
L += ["", "## Untested options", "", "On the screens the bot reaches most often first: the cheapest gaps to fill.", "",
|
|
"| Screen | Times on this screen | Option never played |", "|---|---|---|"]
|
|
L += [f"| {u['label']} | {u['screenVisits']} | {u['text'][:90]} |" for u in cov["untested"]]
|
|
return "\n".join(L) + "\n"
|
|
|
|
|
|
def render(tree):
|
|
return json.dumps(tree, indent=1, ensure_ascii=False) + "\n"
|
|
|
|
|
|
def main(argv=None):
|
|
ap = argparse.ArgumentParser(description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter)
|
|
ap.add_argument("--check", action="store_true", help="write nothing; exit 1 if the files are out of date")
|
|
a = ap.parse_args(argv)
|
|
tree = build()
|
|
files = {OUT: render(tree), REPORT: report(tree)}
|
|
if a.check:
|
|
stale = [str(p.relative_to(ROOT)) for p, text in files.items() if not p.exists() or p.read_text(encoding="utf-8") != text]
|
|
if stale:
|
|
print("out of date (run python analysis/tree/build_tree.py): " + ", ".join(stale), file=sys.stderr)
|
|
return 1 if stale else 0
|
|
for p, text in files.items():
|
|
p.write_text(text, encoding="utf-8")
|
|
c = tree["coverage"]
|
|
print(f"tree {tree['id']}: {c['screens']} screens, {c['tested']} of {c['options']} options played, {c['dice']} dice")
|
|
return 0
|
|
|
|
|
|
if __name__ == "__main__":
|
|
sys.exit(main())
|