latent_sokoban.levels

latent_sokoban.levels

Procedural level generator.

Levels are generated by rejection sampling: place walls, goals, boxes and the player at random, then keep the level only if the BFS solver finds a solution whose length falls inside the requested band. This guarantees every generated level is solvable and gives direct control over difficulty via the solution-length band.

The generator is fully determined by the numpy Generator passed in, which is what makes the hidden-test-set protocol work: freeze this file, agree on the constraints, and generate the final levels from a secret seed.

generate_hidden_set

generate_hidden_set(seed, progress=None)

Generate the full 100-level hidden set from a secret seed.

Deterministic in seed. Takes roughly 70s, nearly all of it in the 4-crate tier, where rejection sampling for a long-solution band is slow.

Source code in latent_sokoban/levels.py

def generate_hidden_set(seed: int, progress=None) -> dict:
    """Generate the full 100-level hidden set from a secret seed.

    Deterministic in `seed`. Takes roughly 70s, nearly all of it in the
    4-crate tier, where rejection sampling for a long-solution band is slow.
    """
    rng = np.random.default_rng(seed)
    levels: list[dict] = []

    for n, n_boxes, density, start, end in HIDDEN_TIERS:
        for i in range(n):
            lo, hi = _tier_band(i, n, start, end)
            # Widen on repeated failure rather than hanging: the measured
            # distributions are noisy at the tails, so a target occasionally
            # lands where sampling is very unlikely.
            for attempt in range(4):
                try:
                    level, solution = generate_level(
                        rng, size=8, n_boxes=n_boxes, wall_density=density,
                        min_solution_len=lo, max_solution_len=hi,
                        max_tries=20000)
                    break
                except RuntimeError:
                    if attempt == 3:
                        raise
                    lo, hi = max(2, lo - 3), hi + 4
            optimal = len(solution)
            levels.append({
                "ascii": level.to_ascii(),
                "optimal_len": optimal,
                "n_crates": n_boxes,
                "max_steps": max(MIN_STEPS, STEP_MULTIPLE * optimal),
            })
            if progress:
                progress(len(levels), n_boxes, optimal)

    return {
        "name": "hidden_public_v2",
        "n_levels": len(levels),
        "ramp": "1-25: 1 crate, 26-50: 2, 51-80: 3, 81-100: 4",
        "levels": levels,
    }

generate_level

generate_level(rng, size=6, n_boxes=1, wall_density=0.12, min_solution_len=2, max_solution_len=30, max_tries=5000)

Generate one solvable level. Returns (level, optimal_solution).

Raises RuntimeError if no valid level is found within max_tries (only happens with contradictory constraints).

Source code in latent_sokoban/levels.py

def generate_level(
    rng: np.random.Generator,
    size: int = 6,
    n_boxes: int = 1,
    wall_density: float = 0.12,
    min_solution_len: int = 2,
    max_solution_len: int = 30,
    max_tries: int = 5000,
) -> tuple[Level, list[int]]:
    """Generate one solvable level. Returns (level, optimal_solution).

    Raises RuntimeError if no valid level is found within max_tries
    (only happens with contradictory constraints).
    """
    for _ in range(max_tries):
        level = _sample_layout(rng, size, n_boxes, wall_density)
        if level is None:
            continue
        solution = bfs_solve(level)
        if solution is None:
            continue
        if min_solution_len <= len(solution) <= max_solution_len:
            return level, solution
    raise RuntimeError(
        f"no solvable level found in {max_tries} tries "
        f"(size={size}, boxes={n_boxes}, band=[{min_solution_len},{max_solution_len}])"
    )

generate_deadlock_level

generate_deadlock_level(rng, size=6, n_boxes=1, wall_density=0.18, min_solution_len=4, max_solution_len=30, max_tries=20000)

Generate a Split-D level: solvable, but at least one available first push leads to an irreversible deadlock. Punishes greedy pushing.

Source code in latent_sokoban/levels.py

def generate_deadlock_level(
    rng: np.random.Generator,
    size: int = 6,
    n_boxes: int = 1,
    wall_density: float = 0.18,
    min_solution_len: int = 4,
    max_solution_len: int = 30,
    max_tries: int = 20000,
) -> tuple[Level, list[int]]:
    """Generate a Split-D level: solvable, but at least one available first
    push leads to an irreversible deadlock. Punishes greedy pushing."""
    from latent_sokoban.env import ACTIONS, SokobanEnv
    from latent_sokoban.solver import state_is_dead

    for _ in range(max_tries):
        level = _sample_layout(rng, size, n_boxes, wall_density)
        if level is None:
            continue
        solution = bfs_solve(level)
        if solution is None or not (min_solution_len <= len(solution) <= max_solution_len):
            continue
        # look for a reachable single push that kills the level
        start = (level.player, level.boxes)
        trap_found = False
        seen = {start}
        frontier = [start]
        # explore only non-pushing moves plus one push
        while frontier and not trap_found:
            key = frontier.pop()
            for action in ACTIONS:
                nxt = SokobanEnv.apply(level, key, action)
                if nxt == key:
                    continue
                if nxt[1] != key[1]:  # this action pushed a box
                    if state_is_dead(level, nxt):
                        trap_found = True
                        break
                elif nxt not in seen:
                    seen.add(nxt)
                    frontier.append(nxt)
        if trap_found:
            return level, solution
    raise RuntimeError("no deadlock-challenge level found; relax constraints")