Many puzzle games incorporate multi-star systems that provide diferent rewards for player performance on each puzzle, with better performance earning more stars. Such puzzles require distinct solutions of increasing dificulty; however, most work in generating puzzles considers just a single solution. In this work, we explore an approach to generating puzzles that have many distinct solutions and could thus lend themselves to being used in a game with a multi-star (in this case, three-star) rating system. Our approach uses a genetic algorithm to search over possible puzzles, and incorporates a fitness function that exhaustively enumerates all possible solutions, rewarding solutions with more distinct solutions. We apply the approach to a game based on a simple lattice protein folding, where puzzles are determined by the a sequence of amino acids, and fitness enumerates all possible conformations with diferent numbers of contacts.
It is not uncommon for puzzles in games to have multiple ways to be solved, with some being considered better than others. This can take form in getting a higher score, making fewer moves, using less time, or taking less common approaches (for example: Angry Birds, Dragon Box, Where’s my Water, and Cut the Rope). In such games, players can be rewarded for better solutions by what we refer to as a three-star system, where a player is given up to three stars for their performance on a puzzle.
A critical aspect of puzzle generation is that a puzzle must be solvable; that is, it must be possible
to reach the solution of the puzzle. There are many approaches to procedural content generation [
Therefore, in this work, we developed an approach to generating three-star puzzles that incorporates
a search over possible puzzles with an exhaustive enumeration of their solutions. More specifically, we
use a genetic algorithm to search over puzzles, in which the fitness function enumerates the solutions
for that puzzle and prefers those that have a larger number of distinct possible scores. Such puzzles may
lend themselves better to gradually rewarding players with increasing stars as they find progressively
better solutions by associating each of the three stars with a score threshold. We apply this approach
to a prototype puzzle game, Foldit Lattice, built around the 2D lattice protein folding problem [
Our findings show that this approach can be used to generate puzzles with a range of diferent scores, and that the genetic algorithm can efectively evolve an initial population of puzzles that contain relatively few high-fitnesses into a larger set of top-fitness puzzles.
PCG for puzzles remains under-explored, as puzzle generation must ensure playability, appropriate
dificulty, and other criteria are often game-specific and more complex than other PCG domains [
There have also been uses of genetic algorithms applied to procedural puzzle generation. For instance,
a variant of FI-2pop was used to generate puzzles that can be described as a sequence of actions. The
optimization functions in the algorithm attempt to adjust the dificulty based on the player and utilize a
simple player model to control this [
The approach to our current game design requires looking at all solutions for a puzzle, building upon
the foundation of exhaustive and semi-exhaustive procedural content generation (EPCG) [
A three-star system is one that is commonly seen in these games with puzzle-like aspects, and has been
found to help increase user engagement and adoption [
Many crowdsourced, citizen-science games engage the public with real scientific data through
puzzlelike mechanics. These include Foldit [
population of puzzles
Fitness Function: prefer puzzles with many possible scores
solutions
scores
scores
puzzle-based games, such as Phylo [
There are also other, more casual crowdsourced games useful for collecting information. For example,
ESP Game [
Genetic algorithms are a search method inspired by natural selection. We used this method to evolve optimal solutions that produce a wide range of solution scores, with the goal of providing more options for 3-star thresholds and ideally more engaging level design.
A flowchart giving an overview of the process is shown in Figure 1. Our genetic algorithm begins with a random population of puzzles. Each puzzle is represented as a string of elements, in which each element corresponds to a diferent character based on the puzzle description. This population is then input into a fitness function, which is used to numerically evaluate the quality of each individual in the population. In this project, puzzles are given preference over when there are a variety of diferent scores, allowing more possibilities to reward the players with stars. The fitness function starts by exhaustively iterating through all possible solutions of the puzzle. The fitness score is found by calculating the total number of distinct scores the puzzle can produce across its valid solutions (i.e., higher diversity of scores indicates a better level).
Based on the fitness score, parents of puzzles are selected randomly with a weighted chance proportional to the score. To these parents, mutation and crossover functions are applied to generate ofspring puzzles. For crossover, a one-point approach is used, where a single random point is chosen, and all elements after that point are swapped between the two parents. Mutation randomly changes individual elements of a puzzle, introducing additional diversity. These ofspring are then inserted back into the population, and the cycle repeats until the set number of generations is complete. As a result, the algorithm yields puzzles with the highest fitness.
The types of application that this algorithm could be applied to consist of those in which it is possible
to enumerate and search through all permutations of a puzzle’s solution, which should have a range of
possible scores. Thus, this framework can be further implemented into games, such as Sokobond [
To test out our approach, we applied it to a prototype game, Foldit Lattice. Foldit Lattice was inspired by
its larger, more complex counterpart, Foldit. It is based on the lattice protein folding problem and uses
the 2D hydrophobic-hydrophilic model [
In this game, players are provided with a protein chain consisting of hydrophobic (orange) and hydrophilic (blue) nodes. Based on the length and the order of this sequence of hydrophobic and hydrophilic nodes, the connected chain can be manipulated by having orthogonal moves (90° or 180°) between each node. An arrangement of a puzzle’s nodes (i.e., a solution) is referred to as a conformation. Players can freely drag the nodes with the mouse using a mass-spring model; the nodes are also pulled to the center of cells in the visualized grid to keep them roughly orthogonal. The player’s goal is to maximize the amount of HH (hydrophobic-hydrophobic) contacts. These contacts happen when two hydrophobic nodes are adjacent to each other on the grid, but not next to each other based on the order of the chain (as seen through the orange dotted lines in Figure 2). In the case of Foldit Lattice, the solution of a puzzle is a protein conformation–essentially the directions from a node to the following one–and the score is the total number of HH contacts.
In the case of Foldit Lattice, to create an optimal puzzle for the game, we began with a random population
of hydrophobic (H) and hydrophilic (P) string sequences of fixed length. Each puzzle is represented as a
linear sequence of the H and P elements, which can be thought of as a 1D array. We then formulated a
iftness function to enumerate all valid conformations that avoid self-intersection for each sequence. Its
representation of each node on the grid would be through a string of directions (up, down, left, right),
avoiding symmetric redundancies. For performance, we implemented enumeration in C, based on the
harmslab/latticeproteins Python package [
The goal of this evaluation is to examine the performance of the genetic algorithm in generating puzzles with diverse fitness scores.
For all experiments, we used a population size of 30, 50 generations, single-point crossover, a pointwise mutation at a rate of 0.1 per element, and 1 elite (the highest-fitness puzzle in each generation is carried over unchanged). For overall GA performance, 25 trials were averaged, and for max fitness count, 15 trials were averaged.
We focused on puzzles of length 16, but ran puzzles of smaller sizes to get rough timing information. Experiments were run on a MacBook Pro (Apple M2, 8-core CPU with 8 GB memory), and we parallelized the evaluation of puzzle solutions in our code to reduce computation time. For puzzles with sequence length 16, the total time was approximately 2.7 hours (162 minutes), with an average of 31.5 minutes per sequence. Each trial took an average of 390 seconds (6.5 minutes), and each generation took approximately 7.8 seconds. For puzzles with sequence length 8, the total time was approximately 54 minutes, with an average of 10.9 minutes per sequence. Each trial took an average of 131 seconds (2.2 2-star solution minutes), and each generation took approximately 2.6 seconds. Finally, for puzzles with sequence length 4, the total computation time was around 47 minutes, with an average of 9.1 minutes per sequence. Each trial took about 109 seconds (1.82 minutes), and each generation took roughly 2.2 seconds.
Based on the genetic algorithm performance plot, we observed a consistent range of high fitness scores throughout the generations.
Figure 3 shows trajectories of the population of the genetic algorithm over the generations. On the left, we see that in fact the first (randomly-generated) population performs quite well, finding solutions with the maximum score found overall. However, on the right, we see that the number of puzzles in the population with that maximum score increases roughly over the generations. This demonstrates that the population is improving over time; finding more of these high-scoring puzzles would be useful for a game, as there are more such puzzles to choose from.
Figure 4 represents levels of the Foldit Lattice, which consists of low and high-fitness 16-length sequences. When mapping this onto a histogram, we can visualize what does and does not classify as an ideal level. For example, the low-fitness histogram only has a total of 3 diferent scores achievable with a similar number of configurations applicable to each score value. On the other hand, the high-fitness histogram provides a much larger range of scores, with a downwards sloping trend where there are very few possible solutions for the highest score, 9, and many more for the lower scores. This distribution could allow for a more stimulating experience for the player as it promotes critical thinking.
Using the distribution seen on these graphs, we can assign the thresholds for the 3-star system for each level. For the Figure 6 puzzle that represents the high-fitness sequence in Figure 4, because the maximum achievable score found is 9, the star threshold is divided by 0-3 as zero stars, 4-7 contacts as 2-star solution 3-star solution one star, 8 contacts as two stars, and 9 contacts as three stars. On the other hand, when determining the score structure for the low fitness sequence shown in Figure 5, a star is obtained with each additional HH-contact, as there are only a maximum of three contacts possible. In this puzzle, we can also observe that the dificulty and subjective visual interest are also low because it is very straightforward to get each contact with the hydrophilic residues positioned right next to each other.
In this work, we were able to successfully generate levels for puzzles with multiple solutions that fit the three-star thresholds. Using a genetic algorithm approach, the number of top-scoring puzzles in the population increased over the generations.
In the future, we would like to adopt a quality-diversity search in place of the genetic algorithm. This approach would provide a variety of puzzles with competitive solutions in the search space, rather than just a singular “best” puzzle.
We also intend to study the spacing of stars among the score thresholds. There are various methods to do this, such as choosing specific percentiles, deciding based on the model of the graph, or by the number of total difering scores. In this work, we only looked at the number of diferent scores in the iftness function; however, the shape of the score histogram may also be interesting to consider (e.g., the relative proportions of each score). There may also be technical scalability issues for larger puzzles whose solutions are increasingly dificult to enumerate.
Specifically, in the context of Foldit Lattice, we would like to incorporate more complex functionality of lattice protein models. This would include factors such as working with a 3D structure instead of a 2D one. It would also involve parts of the genetic algorithm so that it integrates additional attributes to the hydrophobic-hydrophilic model, such as how the score is calculated, rather than simply counting the number of HH contacts. We are also considering conducting a user study to help evaluate the diferences in engagement from the user between low and high fitness puzzles.
Lastly, having only applied this to Foldit Lattice, we propose an extension of this method to other existing games that have the required characteristics of project description, variety of solutions, and score.
This material is based upon work supported by the National Science Foundation under Grant No. 2244288 and the Rosetta Commons REU Program. We would also like to thank Jaden Rodriguez for his contributions.
During the preparation of this work, the author(s) used Grammarly in order to: Grammar and spelling check. After using this tool/service, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content.