Playing Sokoban backwards

Last week a post went around with a challenge I couldn’t stop thinking about: make a Sokoban learner that doesn’t need domain-specific priors, then sweep it across everything else.

Sokoban is the box-pushing puzzle. A wrong push can doom a level fifty moves later, so it’s a decent test of planning. DeepMind’s Boxoban set is the standard version: 10×10 rooms, four boxes, and a test split of 1,000 levels that random moves never solve within the usual 120-move limit.

The prior everyone reaches for is partial credit. PufferLib’s shipped Boxoban reward pays +0.25 for each box pushed onto a target, on top of +1 for solving. Take that away and the agent only gets paid when all four boxes land at once. On real levels that never happens by accident.

I wanted to see how far I could get without it, on hardware I already own: an M3 Ultra Mac Studio, and the RTX 3070 in my gaming PC.

Zero wins

The first run was the obvious one. A 0.43M-parameter conv net, trained with PPO on Boxoban’s own training levels, +1 for solving and nothing else.

Twenty million moves later it had won zero games. Not a few. Zero. With nothing to reinforce, it never started learning.

Easy rooms didn’t help

The textbook fix is a curriculum, so I mixed in easy rooms: PufferLib’s own generated levels, open 10×10 rooms with one to four boxes. Half the games on easy rooms, half on real Boxoban. Same win-only reward, PufferLib’s shipped network and settings, 604 million moves on the 3070, about an hour.

The agent got very good at easy rooms: 99.7%. On the real levels it never moved. It won about one game in 1,700 at the start and the same at the end, which is what random play gets.

The amber line is the same pool with PufferLib’s per-box credit. On the held-out test it solved 23.3%, against 0.02%. So the easy rooms weren’t doing the work. The credit was.

Starting at the end

What finally worked is an old idea: a reverse curriculum (Florensa et al., 2017). Start each game near the goal, and move the start further back as the agent gets better.

For Sokoban, near the goal has a clean meaning. Take a real training level, put every box on its target, and play the game backwards: the player walks around and now and then pulls a box behind it. A few pulls back from solved is a position you can solve in a few pushes. Undo the pulls as pushes and you’re done, so every start is solvable. I checked 237 of them with an exact solver, and none needed more pushes than the walk had pulled.

That’s one real training level, walked back ten pulls by the same rule training uses. It took 169 random moves. The finished Mac network then solves it in 19.

The reward stayed the same. +1 for solving, nothing else.

On the Mac, games start one pull from solved and step back whenever the agent solves half of them at the current depth. A fifth of the games still start from the real level. It reached the deepest starts after about 217,000 games.

On PufferLib, the win-only reward was a compile flag I’d already added for the easy-room run. The only new thing was the pool: I swapped the easy rooms for 265,857 backwards-played starts and ran the same 604 million moves.

The run with no credit matched the run with credit. On the held-out test it solved 23.5%, against 23.3%. Medium and hard levels matched too, at 1.5% and about 0.5%.

The Mac learner showed the same shape. Playing straight through, it trails the per-box-credit learner. Then I let each network search a little, guided only by its own move probabilities: first a ban on returning to positions it has already seen, then a beam that keeps its 8 or 32 likeliest lines. With search, it catches up.

Here’s the reverse-curriculum network on a test level it has never seen, playing straight through with no search:

For scale: with per-box credit and a full night on the 3070, 3 billion moves, PufferLib gets to 61%. The run without credit hasn’t had that night yet.

The part I didn’t expect

Twice now, mixing in easy cases did nothing for the hard ones.

The easy rooms were the first time. The second was mazes. I have a small memory agent that only sees an 11×11 window around itself. It solves 99% of 13×13 mazes after nine minutes of training. Trained on 25×25 mazes alone, it solves 37% of 101×101 mazes it has never seen, against 3% for random moves. Here it is on one of them:

So I tried training one agent on a mix of sizes from 13×13 to 47×47, expecting it to do everything. It behaved like the 13×13 agent at every size, and solved only 30% of the 47×47 mazes it had actually trained on.

My guess is that easy cases finish fast and pay often, so they dominate what the network learns, and what they teach doesn’t scale. Starting near the goal is different. Every start is a slightly harder version of something the agent can already do.

A lookup table that helped

DeepSeek’s Engram gives a language model a huge table of learned vectors, looked up by the last few tokens. I tried the board-game version: every cell’s 3×3 neighbourhood of walls, boxes and targets becomes an index into a table of learned vectors, and a gate decides how much of it to use. It adds 8 million parameters but very little arithmetic, though training was still about 1.6 times slower.

On my own generated Sokoban rooms it added 12 to 13 points over the same network without it, on two seeds. Most of the gain was fewer loops, where the agent walks in circles until it runs out of moves.

Is this “no priors”?

Not quite, and I’m not sure where the line is.

The reverse curriculum doesn’t know anything about good play. It doesn’t reward placing boxes or avoiding corners. But it does know the rules well enough to run them backwards, and it needs a way to start a game from any position. Some people will call that a prior. It feels like a different kind of thing than telling the agent which pushes are good, but I can see the argument.

It also doesn’t solve Sokoban. Hard levels are still mostly out of reach for every reinforcement learner I’ve run, and a model that just copies a solver is far ahead on them.

Then I tried the same swap on four of PufferLib’s other games, one run each with PufferLib’s shipped settings: Tower Climb, Pac-Man, 2048, and Zulrah, an Old School RuneScape boss fight. With a reward only for winning, none of them learned anything.

Starting closer to the end rescued one. In Zulrah, half the training fights began with the boss already hurt. From full health, the agent then averaged 3.14 kills per episode, against 2.89 with the shaped reward.

The others didn’t come around. In 2048, my first try started games a few merges short of the 2048 tile, and random moves finished those on their own, so there was nothing to learn. In Pac-Man, with only the pellets near the start left and one setting turned down, it learned to clear those boards but never a full one. Tower Climb has no simple way to start halfway up, so it didn’t get backwards starts.

I’m not sure how far this goes. One game out of four isn’t a recipe. But for Boxoban, at least, the wall wasn’t the reward. It was where the games started.