Беги, Баг, беги! (Run, Bug, Run!)
Беги, Баг, беги! (Run, Bug, Run!)
Platform: bug-makers | Category: Misc | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-05-29 | Status: Solved Techniques: api_submission, engine_port_to_python, first_passage_time_maximization, simulated_annealing_with_seed_chaining
Summary
Task: maze game where a deterministic least-visited-neighbor 'bug' walker is simulated server-side on a submitted 31x21 map; the flag requires the walk to take >=250000 steps. Solution: port the JS engine to Python, recognize score = first-passage time to the exit's unique neighbor, then maximize it via simulated annealing with iterative seed-chaining and light perturbation to build a dense irregular maze (273598 steps).
Беги, Баг, беги! (Run, Bug, Run!) — bug-makers
Description
Беги, Баг, беги! Баг должен пробежать 250 000 шагов, чтобы получить флаг.
English summary: A browser maze game (Express.js backend) at https://bug-run.t1.bug-makers.ru.
The player designs a maze on a fixed 31×21 grid, and a deterministic "bug" walker is
simulated through it. To qualify for the flag, the bug must take at least 250,000 steps
(SCORE_THRESHOLD = 250_000) before it reaches the exit. The simulation engine ships as
client-side JS at /shared/game-engine.js, and the server re-runs the same engine on
submitted maps via POST /api/submit — so this is purely an offline optimization problem:
craft a map string that maximizes the walker's step count.
Analysis
The grid and map encoding
WIDTH = 31,HEIGHT = 21.- Column-major string encoding:
index = x*HEIGHT + y.'1'= wall,'0'= open. START = (1,1),EXIT = (29,19).- The border must be all walls; start and exit cells must be open.
- The server validates that the exit is BFS-reachable from the start, and requires the
walker to actually
reachedExit(not merely hit the step cap of 5,000,000).
The walker ("bug") logic
Each cell carries a weight: wall = 1_000_000_000, open cell starts at 0. The bug is a
deterministic least-visited-neighbor walker. Directions: 0=down, 1=right, 2=up, 3=left.
Each step():
- Read the 4 neighbor weights (down, right, up, left).
currentByDir= weight of the neighbor in the current heading.- Hysteresis: if
currentByDir <= all four neighbors, keep moving in the current direction. - Otherwise move to the minimum-weight neighbor, tie-break priority
down <= right <= up <= left. - Increment the weight of the cell being left by 1, move, increment the step counter.
It stops when it reaches EXIT. The Python reference port (sim.py) reproduces the server
exactly (empty interior map → 46 steps, matching the server's default response).
THE KEY INSIGHT — score is a first-passage time
The exit cell (29,19) keeps weight 0 forever (the bug stops the moment it lands there,
so it is never the cell being "left", and its weight is never incremented). Its only open
neighbor inside the grid is P = (29,18).
Therefore, the instant the bug steps onto P, the exit (weight 0) is the unique minimum among
P's neighbors, so the very next step moves to the exit and the run terminates. Consequently:
SCORE = first-passage time of the least-visited walk to cell
P = (29,18).
This reframes the whole challenge: we are not "solving a maze," we are maximizing how long the walker wanders before it first reaches a single specific cell.
Why naive and regular mazes fail
Because the walker always prefers a weight-0 neighbor, any clean (weight-0) forward path to the exit gets taken on a single pass:
- Empty interior: 46 steps.
- Serpentine / Hamiltonian snake corridor: ~300–550 steps.
- Random spanning-tree (perfect) maze: ~300 steps.
- Rings, combs, ladders, brick-pattern walls: single pass ~300–1100 steps.
To force the walker to revisit cells tens of thousands of times, the maze must be dense and
irregular (~40% interior walls) with no clean forward path. Then the bug oscillates: cell
weights build up like a slowly rising "water level", and only after the level equalizes across
many cells does the walk finally first reach P. There is no closed-form construction — the
landscape is combinatorial and must be searched.
Solution
Step 1 — Recon and engine port
Fetched index.html, /js/app.js, /shared/game-engine.js. Identified the engine and the
250k threshold. The API:
POST /api/session/start {nickname}→ sets a session cookie.POST /api/submit {map}→{score, qualified, flag, bestScore}.GET /api/top50showed real players at 250k–419k, proving a legitimate maze exists.
Ported the engine to Python: sim.py (exact reference) and fastsim.py (optimized flat-array
version). Both agree with the server (default map = 46).
Step 2 — Disprove the "trap" exploit
Attempted to find a BFS-reachable map where the bug never reaches the exit (stable limit cycle
excluding P, hitting the 5M cap). Disproven — no such cycle was found; the bug always
eventually reaches the exit. The server also validates reachability and requires reachedExit,
so a non-terminating map would never qualify. This killed the shortcut; only a genuine
high-step maze works.
Step 3 — Optimization via simulated annealing with seed-chaining
Single-shot annealing from random init plateaus around ~12k–19k steps. The breakthrough was iterative seed-chaining: run several parallel annealers, take the best map, then re-seed the next round of annealers from it with a light perturbation (0–6 wall flips), repeatedly. Heavy perturbation destroyed progress; light perturbation let the search refine the dense structure and climb past the threshold.
Best-score progression across rounds:
6,212 → 11,844 → 18,764 → 54,502 → 90,454 → 130,896 → 164,650 → 273,598
The annealer (anneal2.py) maximizes simulated steps subject to BFS-reachability, accepting
worse maps with a temperature-scaled probability, writing the best map incrementally, and
restarting from the best map after a no-improvement streak.
python read-only • copy allowed# anneal2.py (core of the seed-chaining annealer) import random, sys, time import fastsim as F from fastsim import WIDTH, HEIGHT, START, EXIT EDIT = [(x, y) for x in range(1, WIDTH-1) for y in range(1, HEIGHT-1) if (x, y) != START and (x, y) != EXIT] def grid_to_map(g): return "".join(g[y][x] for x in range(WIDTH) for y in range(HEIGHT)) def map_to_grid(m): return [[m[x*HEIGHT+y] for x in range(WIDTH)] for y in range(HEIGHT)] def score(m): if not F.isExitReachable(m): return -1 s, ok = F.simulate(m) return s if ok else -1 def run(seed, time_budget, start_map, outfile): rng = random.Random(seed) g = map_to_grid(start_map) for _ in range(rng.randint(0, 6)): # LIGHT perturbation x, y = rng.choice(EDIT); g[y][x] = "1" if g[y][x] == "0" else "0" m = grid_to_map(g) while not F.isExitReachable(m): x, y = rng.choice(EDIT); g[y][x] = "0"; m = grid_to_map(g) cur = score(m); best = cur; bestg = [r[:] for r in g] t0 = time.time(); no_imp = 0 while time.time() - t0 < time_budget: k = rng.choice([1, 1, 1, 1, 2, 2, 3]) ch = [] for _ in range(k): x, y = rng.choice(EDIT) old = g[y][x]; g[y][x] = "1" if old == "0" else "0"; ch.append((x, y, old)) sc = score(grid_to_map(g)) accept = sc >= cur if not accept and sc > 0: T = max(80, best*0.02*(1 - (time.time()-t0)/time_budget)) if rng.random() < pow(2.718281828, (sc - cur)/T): accept = True if accept: cur = sc if sc > best: best = sc; bestg = [r[:] for r in g]; no_imp = 0 open(outfile, "w").write(grid_to_map(bestg)) else: no_imp += 1 else: for x, y, old in ch: g[y][x] = old no_imp += 1 if no_imp > 6000: # restart from best g = [r[:] for r in bestg]; cur = best; no_imp = 0 open(outfile, "w").write(grid_to_map(bestg))
Driver (chained rounds): run a batch of seeds, pick the best output map, then feed it as the
seed file for the next batch with the light perturbation built into run().
Step 4 — Final map and submission
The winning map f_87.txt is verified by both Python simulators as 273,598 steps with
reachedExit = True (length 651 = 31×21):
111111111111111111111100000000001000100001101111110101010001011110100011000010101001100000000100001010011100100000010000011001110010000110101110011100101001100000001001100000101000110010011110000011101011110001100010001100100111011100101001001001101001110101001101110000001101000010000110101011100001010101111001111100111110111000011011110000110010101100011110001000101000101111101010101111100000101100001000011011001111101100110100000010011111010100010100111011101000010110101011111110010110100011000001100011110010110000001100001110110010010101100000000011000110011101001010110101001001110011100011010010101100000100111010101101111111111111111111111
Submitted via the authenticated API:
bash read-only • copy allowed# 1) get session cookie curl -s -c cookies.txt -X POST https://bug-run.t1.bug-makers.ru/api/session/start \ -H "Content-Type: application/json" -d '{"nickname":"runner"}' # 2) submit the map curl -s -b cookies.txt -X POST https://bug-run.t1.bug-makers.ru/api/submit \ -H "Content-Type: application/json" \ -d "{\"map\":\"$(cat f_87.txt)\"}"
Server response:
json read-only • copy allowed{"score":273598,"bestScore":273598,"nickname":"runner","threshold":250000, "qualified":true,"flag":"BugCTF{REDACTED}"}