Reinforcement Learning · Team project

Sokoban RL

Sokoban is a puzzle where you push boxes onto targets. You can only push, never pull, so one careless move can make a level unsolvable. We trained two reinforcement-learning agents to play it: tabular Q-learning, which keeps a table of every state it has seen, and a deep Q-network (DQN), which learns a neural network that estimates the value of each move.

This work is a project for a graduate-level course with team members Jerum H. and Larry M. I built the multi-level training harness behind every number on this page: the hyperparameter configs, the three level schedules, the results export, and the batch script that ran all 21 runs (about 17 hours).

Train an agent

Pick a level and a set of hyperparameters, then train a fresh Q-learning agent right here in your browser. When it finishes, it replays the level with exploration turned off, so you see only what it learned. Challenge 2 isn’t offered: in testing it never solved, even after 50,000 training episodes.

LevelHyperparameters

One push away from solved. Trains for 500 episodes.

α 0.15 · γ 0.97 · ε decay 0.9995 · ε floor 0.08

Results

Each of the 21 runs trained one agent for 10,000 episodes over all 12 levels then played each level twice with exploration turned off (24 test attempts). Runs differ in hyperparameters and in how episodes were split across levels: equal (an even share), random (a random level each episode) or progressive (more episodes on harder levels).

Best Q-learning run

58%

14 of 24 solved · Baseline, progressive

Best Deep Q-Network run

25%

6 of 24 solved · 3 runs tied

Training per run

10,000

episodes across 12 levels

Tabular Q-learning beat DQN. It’s best run solved 58% of test attempts, against 25% for DQN’s best.
Q-learning handled the two- and three-box levels (Hard 3, Hard 5, Challenge) in most runs. DQN never solved a level with more than one box.
Neither agent solved Challenge 1, Challenge 2 or the generated levels. Those are built fresh every episode, so an agent never sees the same layout twice.

Every training run, ranked

Share of the 24 test attempts each run solved after 10,000 training episodes.

Q-learning
Deep Q-Network

QLBaseline · progressive

58%

QLFast explore · equal

50%

QLBaseline · equal

50%

QLFast explore · random

42%

QLHigh gamma · random

42%

QLHigh gamma · equal

33%

QLBaseline · random

33%

QLHigh gamma · progressive

25%

DQNLarge buffer · random

25%

DQNBaseline · equal

25%

DQNFast sync · equal

25%

QLFast explore · progressive

17%

DQNBaseline · random

17%

DQNLarge buffer · progressive

17%

DQNSingle network · random

17%

DQNLarge buffer · equal

17%

DQNSingle network · equal

DQNBaseline · progressive

DQNSingle network · progressive

DQNFast sync · random

DQNFast sync · progressive

Show as table

Agent	Config	Schedule	Solved	Rate	Avg score
Q-learning	Baseline	progressive	14 / 24	58%	286.1
Q-learning	Fast explore	equal	12 / 24	50%	235.1
Q-learning	Baseline	equal	12 / 24	50%	230.0
Q-learning	Fast explore	random	10 / 24	42%	187.3
Q-learning	High gamma	random	10 / 24	42%	170.6
Q-learning	High gamma	equal	8 / 24	33%	167.5
Q-learning	Baseline	random	8 / 24	33%	139.8
Q-learning	High gamma	progressive	6 / 24	25%	131.1
Deep Q-Network	Large buffer	random	6 / 24	25%	83.4
Deep Q-Network	Baseline	equal	6 / 24	25%	70.5
Deep Q-Network	Fast sync	equal	6 / 24	25%	41.9
Q-learning	Fast explore	progressive	4 / 24	17%	75.3
Deep Q-Network	Baseline	random	4 / 24	17%	37.8
Deep Q-Network	Large buffer	progressive	4 / 24	17%	2.3
Deep Q-Network	Single network	random	4 / 24	17%	-6.3
Deep Q-Network	Large buffer	equal	4 / 24	17%	-19.0
Deep Q-Network	Single network	equal	2 / 24	8%	-18.3
Deep Q-Network	Baseline	progressive	2 / 24	8%	-40.8
Deep Q-Network	Single network	progressive	2 / 24	8%	-52.0
Deep Q-Network	Fast sync	random	2 / 24	8%	-64.5
Deep Q-Network	Fast sync	progressive	2 / 24	8%	-72.5

What each agent learned, level by level

Test attempts solved on each level, pooled across all runs of that agent.

Q-learning
Deep Q-Network

Easy

1 box

89%

92%

Medium

1 box

56%

50%

Hard

1 box

22%

17%

Hard 2

1 box

11%

25%

Hard 3

2 boxes

78%

Hard 4

2 boxes

33%

Hard 5

2 boxes

89%

Challenge

3 boxes

89%

Challenge 1

4 boxes

Challenge 2

6 boxes

Random

1 box · generated

Random (hard)

3 boxes · generated

Show as table

Level	Boxes	Q-learning	Deep Q-Network
Easy	1	89% (16 / 18)	92% (22 / 24)
Medium	1	56% (10 / 18)	50% (12 / 24)
Hard	1	22% (4 / 18)	17% (4 / 24)
Hard 2	1	11% (2 / 18)	25% (6 / 24)
Hard 3	2	78% (14 / 18)	0% (0 / 24)
Hard 4	2	33% (6 / 18)	0% (0 / 24)
Hard 5	2	89% (16 / 18)	0% (0 / 24)
Challenge	3	89% (16 / 18)	0% (0 / 24)
Challenge 1	4	0% (0 / 18)	0% (0 / 24)
Challenge 2	6	0% (0 / 18)	0% (0 / 24)
Random	1	0% (0 / 18)	0% (0 / 24)
Random (hard)	3	0% (0 / 18)	0% (0 / 24)

How moves are scored

Each turn the agent picks one of four moves. The environment also refuses pushes that would trap a box in a corner or against a wall with no target along it, which removes the simplest dead ends before the agent has to learn them.

Solve the level (bonus)	+500
Push a box onto a target	+10
Push a box onto plain floor	+0.5
Take a step	-0.5
Make a blocked move, or a push that would trap a box	-1
Push a box off a target	-10