29 Sep How to know these puzzles are right for you
In our past blog posts, we have focused primarily on the puzzle results received from players, and how we use that data to improve this alignment. Today we will be delving into the other half of the process, ensuring we’re producing puzzles which players can solve and contribute meaningful results, while still remaining engaging.
When generating puzzles, we subject each one to a greedy algorithm with a very simple concept. Each turn, determine the highest scoring move by placing a gap in every possible position and calculate the new score. The highest scoring move is implemented, and the process repeats until it can no longer make improvements.
If this sounds extremely tedious, that’s because it is! In a level 1 puzzle we may have at most 30 colored bricks (6×5). If the greedy algorithm manages to add 4 gaps, that entails this one simple puzzle has calculated the total score 120 times. On top of that, when generating new batches we can go through thousands of possible puzzles, only accepting a small handful, thus the process can begin to snowball very quickly. It is essential that we optimize this algorithm as much as possible. Thus, we have focused our code refinement into 3 primary steps.
The first step is to ignore areas where adding a gap is impossible or irrelevant. If a column of colored bricks has already reached the top, no more gaps can be added, thus the column can be ignored. Furthermore, if a gap has been added, it is redundant to try adding a second gap both before and after the existing gap, as it will have the same outcome.
The second step is improving the time required to calculate the score of the puzzle. Rather than looking at each individual brick and determining if it meets the guide, we can retrieve the sum of all bricks in a row which match the guide, and if that sum is equal to the number of columns, we can multiply that with the row bonus.
Lastly, the most critical step is reducing the number of times we need to recalculate the score. By calculating the score of the puzzle prior to adding a new gap, called current_score, then adding a gap at the start of a column, recalculating, and calling that future_score, we already have all the information we need for the given column. If you add a gap to row 3, you would need to recalculate the score of the individual row, but rows 1 and 2 will be equivalent to the rows in current_score, and all rows proceeding will be equivalent to future_score. This results in only calculating the score once per column, and then each potential gap position in the given column is a simple equation of (current_score < row) + row + (future_score > row). This would reduce the number of times calculating the score in our previous level 1 puzzle from 120 times, to 28.
Once this greedy algorithm is complete, we can compare the solution to the acceptance parameters. If the puzzle surpasses the minimum score improvement, and the gaps placed are varied enough, then the puzzle is accepted, and presented to players to derive their own solutions.
Why did you use a greedy algorithm?
While not perfect, the greedy algorithm is a simple and effective method that can resemble a basic player strategy, and handles constant changes based on row bonus. A second solution algorithm is also being used which complements the greedy algorithm’s shortcomings, but that is for a future blog.
This algorithm sounds like it should be scoring higher than the target score?
You are correct! In our April 13 blog we stated that the target score was achieved by a computer. One issue we faced in puzzle design is that we want the target score to be achievable, but not the upper limit. Earlier puzzles used a handicapped version of the greedy algorithm, which could initially only add a gap on the top row, and gradually work down. While effective for target score, it did cause potentially valuable puzzles to fail the acceptance parameters. This handicap has since been removed. The greedy algorithm now runs efficiently, and the target score is the halfway point between the base score, and the score achieved by the greedy algorithm.
Why do we need to solve these puzzles if you already have an algorithm doing it?
The first thing to note is that this algorithm does not guarantee the highest possible score. The greedy algorithm is a good baseline, but will fail to catch areas where more than one gap is required to see improvements. Secondly, algorithms are optimized for one particular task. Relying on a single algorithm chosen by the creator can strongly influence the outcome and result in bias. Finally, while the greedy algorithm returns one result, there may be many viable solutions with equal or similar scores. Player solutions can be incredibly diverse, and there is never one correct solution when it comes to sequence alignments. For more details check out the May 07 blog.