My goal for LD is usually to learn something new. I embark on overly ambitious projects, but usually something nice comes out (although not necessarily within the deadline).

This time, I wanted to do something with level generation and reinforcement learning. I did a lot of level generation in the past, mostly using hand-crafted algorithms.

My inspiration was this paper: https://www.youtube.com/watch?v=ml3Y1ljVSQ8 They use Q-learning to train level generation. Q-learning requires a reward function for every state and action, which is in their case based on the solvability of a level. One of their examples is Sokoban, which I think is an interesting game to generate levels for. I wanted to up the ante a little, and decided to try this for Boulderdash. My eventual goal is to be able to generate levels for a larger class of puzzle-action games, such as CellSpace games (this is a tool I created during LD56).

So I created a level solver for a very basic Boulderdash game, based on breadth-first search. It's basically a brute force search, searching the entire state space. It comes up with the shortest path to complete a level. However, it turns out to be very slow. Even after some optimisations, it would slow down to >20 sec and eventually run out of memory for levels larger than about 6x6 tiles. This is because of combinatorial explosion: every step increases the search space up to 4-fold, because there are 4 possible actions (up, down, left, right).

I did not want to add game-specific optimisations to prune the state space. Instead I decided to try and use reinforcement learning to create a more universal (aka "model free") solver for larger levels. Last night, while I was asleep, I had my PC generate a dataset of optimal paths through 2500 random 6x6 levels using the brute force solver, serving to bootstrap my reinforcement learning system. If I can get this to work for larger levels than 6x6, it can generate new training data through self-play and support progressively larger levels (see the figure below).

Today I trained a neural net (a 5-layer Deep Q Network, based on convolution, with 2 million parameters) with part of the dataset, using Tensorflow JS, which I used before for browser games. TFJS support for CUDA sucks though, so I actually train it in the browser because it's the fastest. After some 20mins of training, it manages to find paths 100% of the time for seen levels, and about 60% of unseen (but known solveable) levels. It's clearly overfitted (apparently it has memorised the optimal paths of some 500 levels), but already has usable performance on 6x6 levels. However, on larger levels, it still falls down, with 10% performance on 8x8 levels and near zero for 10x10 levels. However this is still a first attempt, and there are a lot of things to try out, like hyperparameter optimisation and dataset improvement, so I'll be spending the next 24 hours trying to get this to work, and hopefully come up with a game with interesting generated levels!