Generating 2D Lego Compatible Puzzles Using Reinforcement Learning

Abstract

We present a framework that generates a 2D Lego-compatible puzzle layout of greater than thousands pieces of bricks using a reinforcement learning technique. Many existing 2D legorization strategies have limitations in producing a Lego layout, which is composed of more than thousands of pieces. We attack this problem by employing a reinforcement learning technique, which accelerates the progress of various game strategies. We represent the legorization process as a game tree search problem, where each leaf node of the tree corresponds to a Lego layout. The goal of legorization is to find an optimal Lego layout that achieves maximum reward. To efficiently find a leaf node for the maximum reward layout, we reduce the search space using a dueling deep Q-Network (DQN), which is a widely used reinforcement learning model. Our framework is composed of a learning stage and a legorization stage. In the learning stage, we design a dueling DQN model and train this model using three heuristics for legorization strategies. In the legorization stage, we efficiently generate a large-scaled 2D Lego-compatible puzzle layout by reducing the search space using the trained dueling DQN. This approach enables us to produce a puzzle layout of more than a thousand of pieces, which has not been feasible for existing legorization schemes.

Keywords

• Lego
• reinforcement learning
• deep Q-network
• legorization
• heuristic