Final Results
Personal Puzzle Producer
Advisor: David Liben-Nowell
I. Background
I love solving puzzles, from debugging a tricky race condition in a bit of threaded code to figuring out how to get a chicken all the way to the place I need it in order to fly across a canyon to that last heart piece in Zelda, to piecing together an actual classic jigsaw puzzle, to the many available paper & pencil logic puzzles that have a small number of simple rules yet can be almost impossible to solve. However like most people, in order for any puzzle to be enjoyable, it needs to fall in a relatively narrow difficulty range such that the puzzle is challenging enough to maintain my interest but not so difficult that I get stuck for more than a few minutes without making any progress. Finding this sweet spot is of major concern to any puzzle or game makers, especially those that hope to market their game/puzzle to a wide variety of audiences.
The ideal solution would be to dynamically adapt the difficulty level of a puzzle/game to each individual player, both to find the best initial challenge setting for that person and to update the level to match the player's skill as they improve with practice/experience (or perhaps get worse at the end of a long day of compsing and don't want to have to try so hard). How to do this is an open question with lots of active research currently taking place in game theory, artificial intelligence, cognitive/neuro-science, human-computer interaction, and many more areas, as well as at all of the intersections among those fields!
II. The Project
The ultimate goal of this project is to automatically generate puzzles tailored to maximize the enjoyment of each individual puzzle solver, including adapting dynamically over time even for a single user as their skills change. The realistic goal will be to at least automatically generate puzzles of predictable difficulty levels as requested by a user, and attempt to adjust the difficulty/style/type of generated puzzles in some logical way based on analysis of one or more aspects of the individual's past solving history.
This past year I had a comps group do excellent work in building an efficient, fast solver for one particular type of logic puzzle called Slitherlink, and they worked on a generator for this puzzle in the last several weeks of their project. Their initial analysis of many hand-made puzzles as well as the ones they generated brought up many interesting questions as to what exactly is it that makes a puzzle easy vs. difficult, and fun/engaging vs. boring. The project this year will focus on answering those questions in order to generate "good" puzzles. Below are 2 examples of slitherlink puzzles before and after being solved. Though they are both the same size, the first was rated "easy" and took me less than 1 minute to solve, while the 2nd was rated "hard" and required almost 3 minutes for me to finish. If you had asked me a year ago which I thought would be harder I would have had no idea, only because of this past year group's initial analysis can I now say that the abundance of 2's and lack of 0's in the 2nd puzzle are a flag that it is likely to be difficult.
Those numbers, however, are specific to the slitherlink puzzle, and the goal this year is to explore many kinds of puzzles in an attempt to determine some general criteria for what makes any type easy/hard. For example, the reason more 2's means a more difficult slitherlink puzzle is because there are more ways to place 2 lines around a 2 than for example to place 3 lines around a 3, and clearly more than to place 0 lines around a 0, so a 2 gives you less information than a 3 or a 0 in this puzzle. Here are 2 examples of another japanese puzzle that similarly has only a few simple rules but can be difficult to solve, called masyu. The first puzzle is again easy, and the 2nd is labeled medium, and did take me a bit longer to solve. I have no analysis on this type of puzzle yet, but one thing that immediately stands out is that in the easier puzzle there are more dots near the edges, and again it turns out that in this puzzle there are fewer ways to fill in lines for dots on the border of the puzzle. More analysis is needed, however, to say that this is actually a general principle.
The outline of this project will be something like the following:
- Research - there is lots of literature on adaptable game
difficulty, including specifically these kinds of puzzles with a few
simple rules but endless challenges (e.g. sudoku, the examples
above, nonograms, and many more)
- Write code to analyze many hand-written and auto-generated
examples of several types of these puzzles in order to create and
test theories on what characteristics in general may make a puzzle
easy vs. hard, fun vs. boring, etc. Are there detectable differences
between hand-written vs. auto-generated versions of these puzzles?
This seems to currently be a point of contention and hot debate!
- Design and implement a simple puzzle solving environment for at
least one of these types of puzzles that tracks the solver's moves,
time, etc. Collect as much data as possible (we will likely have
some funding to use mechanical turk to get data from many puzzle
solvers of different levels).
- Use what you learn from your data analysis to create a puzzle
generator that can produce puzzles of different levels that are at
least reasonably fun to solve.
- Add dynamic adaptive capability to your puzzle generator using
one or more AI/learning/evolutionary methods.
III. References
Here are some places to get you started, but you will do a thorough literature review in the first few weeks of fall term!- http://ccg.doc.gold.ac.uk/papers/browne_ieeechapter14.pdf
- Game Analytics: Maximizing the Value of Player Data (ed. By Magy Seif El-Nasr, Anders Drachen, Alessandro Canossa)- Ch34 Metrics for Better Puzzles by Cameron Browne
- http://liacs.leidenuniv.nl/assets/Bachelorscripties/18-JohanGroenen.pdf
- https://sourceforge.net/projects/nurikabe-maker/
- Games, Puzzles, and Computation by Robert A. Hearn, Erik D. Demaine
- Light Up is NP-complete. Brandon McPhail, http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf
- Rating Logic Puzzle Difficulty Automatically in a Human Perspective. Hao Wang, Yu-Wen Wang, Chuen-Tsai Sun. http://gamelearninglab.nctu.edu.tw/ctsun/Rating%20Logic%20Puzzle%20Difficulty.pdf
- Evolutionary Algorithm for Generation of Entertaining Shinro Logic Puzzles. David Oranchak. http://www.oranchak.com/evostar-paper.pdf
- http://www.huttar.net/lars-kathy/puzzles/nurikabe.html
- Lots from IEEE Conference on Computational Intelligence and Games (CIG) - e.g. from 2015:
- -- A data-driven approach for online adaptation of game difficulty. Haiyan Yin.
- -- Automated puzzle difficulty estimation. Marc van Kreveld, Maarten Loffler, Paul Mutser
- Generating and Solving Logic Puzzles through Constraint Satisfaction. Barry OSullivan and John Horan. https://www.aaai.org/Papers/AAAI/2007/AAAI07-361.pdf
- Automated Generation and Analysis of Logical Puzzles. T.K. Cocx. Master Thesis 2004. http://www.mountainvistasoft.com/docs/Cocx_Automated_generation_and_analysis_of_logical_puzzles.pdf
IV. Recommended Experience
It would be useful to have taken algorithms and/or computability & complexity. Also any experience with AI, EvoComp, cog-sci, statistics, data-analysis, etc. would be beneficial. This project really though will require a bit of all the things, from designing/coding/user-testing the puzzle interface with user data collection, to performing statistical analysis of data, to implementing AI/learning/evolutionary methods for the adaptable puzzle generator.