Exploring EPCG in The Witness Nathan R. Sturtevant Department of Computing Science University of Alberta Edmonton, AB, CANADA nathanst@ualberta.ca Abstract While in traditional PCG it is important to evaluate the This paper provides an examination of how Exhaustive Pro- output of content generators (Shaker, Smith, and Yannakakis cedural Content Generation (EPCG) can be used to explore 2016), in EPCG all content is potentially generated. Thus, it the creation of new content for games. We study the puzzles is also important to focus on the questions that can be asked in the game The Witness along with an aesthetic for game de- about content, as these questions will determine the breadth sign proposed by Jonathan Blow and Marc ten Bosch, show- of content that is generated. ing how EPCG is well-suited to answering game design ques- We use a design aesthetic from Jonathan Blow and Marc tions and for helping designers find unique content for their ten Bosch to help focus the questions we ask about the avail- games. able content. Introduction A Matching Aesthetic Procedural content generation (PCG) in games seems to In a 2011 IndieCade presentation,2 Jonathan Blow and Marc have great potential. One could imagine a never-ending ten Bosch presented an aesthetic for game design which stream of deep and interesting games produced at little or aims to, in their words, “show a lot of truth, with minimum no cost. But, games like No Man’s Sky have shown that bil- contrivance.” They suggest that in this aesthetic the role of lions of combinations of content can still lead to repetitive a designer is to explore and reveal the truths about the uni- and uninteresting play, and that it is easy for expectations to verse more than to create a fun gameplay experience. They outstrip current technologies. That isn’t to say that PCG will outlined eight pieces of this aesthetic as follows: not one day deliver, but, similar to how updates to No Man’s Sky have improved the game, more research is needed to 1. Richness better understand how to deliver compelling and interesting 2. Completeness experiences. 3. Surprise One suggestion to improve PCG has been to involve a de- 4. Lightest Contrivance signer in the process, called mixed-initiative content creation (Liapis, Smith, and Shaker 2016). There are many ways that 5. Strength of Boundary a computer can assist human designers, such as by ensur- 6. Compatibility of Mechanics ing that design constraints are enforced and that all areas 7. Orthogonality in levels are reachable. This effort is primary supported by 8. Generosity computer-aided design (CAD) tools. Recent research (Sturtevant and Ota 2018) proposed a The goal is to (1) aim for the richest space of game de- subfield of PCG called Exhaustive PCG, or EPCG. In sign, where there is significant room to explore the space of this sub-area content is generated exhaustively or semi- possible interactions between mechanics. Once that space is exhaustively to fully explore a design space. In this paper identified, the designer must (2) completely explore the in- we use a mixed-initiative form of EPCG to explore and an- teractions within the game before (3) editing and pruning swer questions about game design. By answering questions the interactions to be left with a set that are interesting and about all available content, an EPCG system is able to sug- surprising for the players. This aesthetic prefers mechanics gest meaningful content that can be selected for use in a that are (4) simple (with unnecessary complications) and (7) game.1 For instance, we might ask to see all puzzles of a orthogonal (without overlapping functionality). At a broader certain size that have a single solution. level, the total set of mechanics explored should not overlap or be unbalanced, forming an interesting boundary between 1 Taken broadly, EPCG includes some generic constraint pro- gramming or answer-set programming solvers, as such solvers may in games, such as the region constraints we discuss in this paper. In perform an exhaustive search with pruning (making them semi- these situations, a custom solver may be more efficient and flexible. 2 exhaustive) over variables and values. However, these generic lan- http://the-witness.net/news/2011/11/designing-to-reveal-the- guages do not easily support many types of constraints that are used nature-of-the-universe/ (a) (b) (c) Figure 1: A sample puzzle with two types of constraints (a), the natural solution a player might try first (b), and the solution to the puzzle (c). different puzzles (5), and each new mechanic should inter- act cleanly with existing mechanics (6). For the remainder Table 1: Number of paths through a grid of the paper we refer to the aesthetic as a whole as the BtB height width count (Blow and ten Bosch) design aesthetic, and when referring 2 2 12 specific aesthetic points, we will refer to them as (BtBN ), 2 3 38 where N is the aesthetic we are referring to. 3 3 184 In the BtB aesthetic, the goal isn’t to explicitly make hard 3 4 976 puzzles, but instead to look for truth about the design conse- 4 4 8,512 4 5 79,384 quences in the space being explored and to illustrate it with 5 5 1,262,816 a selection of puzzles, although the aesthetic is not limited to puzzles. This can be done in many ways; one such way would be to present a set of puzzles that follow a pattern and then to break that pattern to help the player to learn about The large rounded squares are spatial constraints. In the the interactions of the mechanics. final solution, the puzzle is divided into one or more regions EPCG broadly speaking is designed to exhaustively ex- by the solution path. No two spatial constraints of different plore design spaces in ways that other more selective tech- colors can be in the same region in the final puzzle. This par- niques do not. Thus, EPCG is well suited for the BtB aes- ticular puzzle has black and white spatial constraints which thetic. For instance, due to its exhaustive nature, EPCG can must be separated by the path. The solution path splits the explore the full consequences of different design decisions puzzle into two parts, with each part having one of the two (BtB2). It can also explore how orthogonal constraints fit spatial constraints. together (BtB6 and BtB7). But, EPCG does this best in a This puzzle is interesting because visually the spatial con- mixed-initiative process with a designer that is evaluating straints are grouped with the lowest must-cross constraint. and editing content to maximize surprise and to minimize Additionally, the spatial constraints are larger than the must- contrivance (BtB3 and BtB4). cross constraints, so one might focus on finding a path that satisfies these first. Thus, a natural first path to follow is what Design in The Witness is shown in Figure 1(b). But, this path does not lead to a In previous work we explored a single puzzle type from solution. So, this puzzle subverts the natural inclination of The Witness (Sturtevant and Ota 2018), a 2016 game by someone who is used to solving such puzzles and thus con- Jonathan Blow and Thekla Inc. In this paper we continue tains surprise (BtB3). that exploration by looking at different puzzle constraints The number of self avoiding paths for a given table size and how their mechanics can be put together using an EPCG is shown in Table 1. This grows exponentially, but there are approach. efficient algorithms for computing the number of possible To begin, we explain the basic mechanics of the puzzles paths. The exponential growth is useful, because it elimi- in the game. A sample puzzle for game is shown in Figure nates the possibility of someone using brute-force to find a 1, with the puzzle in part (a) and the solution in part (c). The solution and suggests that there might be a rich space of so- goal of each puzzle is to trace a self-avoiding walk (Knuth lutions to explore (BtB1). 1976) from the start (the circle in the lower-level corner) to We employ a few general strategies when searching for in- the goal (the notch in the upper-right corner) that obeys the teresting puzzles that lend themselves to the BtB aesthetic. constraints of the puzzle. Symbols are placed on the puz- First, since we are using EPCG, we fundamentally get a zle to indicate constraints on the path. This puzzle contains measure of completeness (BtB2). Within each portion of both types of constraints we study in this paper. The small the space we explore, our search will be exhaustive. Sec- hexagons are ‘must cross’ constraints, which indicate that ond, related to using the lightest contrivance (BtB4), we will the final solution path for the puzzle must cross that point. look for puzzles with as few constraints as possible. Plac- Hexagons can be placed on vertices or edges. ing more constraints on the board than is needed or using (a) (b) (c) (d) (e) Figure 2: Sample 3 × 4 and 4 × 4 puzzles. The solution to (b) is in (d), and the solution to (c) is in (e). a larger board than is needed adds complexity but, for the 3×3 board with 3 constraints we look at 9,880 possible puz- puzzles analyzed here, does not significantly increase the zles. For each possible puzzle we look at 184 actual paths. quality of the puzzles. Finally, we prefer puzzles with fewer So in the code we analyze 9, 880 · 184 = 1, 817, 920 puzzle solutions, preferably only one. With fewer solutions play- and path combinations together on a 3 × 3 board with 3 con- ers must demonstrate that they exactly understand the con- straints. The min column is the minimum number of unique straints given, which seems to give more opportunities for solutions for any puzzle that is generated, and the time col- surprise (BtB3), although this may be specific to the partic- umn is the total time required to generate all puzzles and ular puzzles studied here. count the number of solutions. For the work in this paper, the time required to implement and test more efficient code Must-Cross Constraints would be larger than the time spent finding the solutions. Our exploration revealed that 3 × 3 puzzles were too sim- To begin, we explore the must-cross constraints. First, how ple to be interesting. On the 3 × 4 board we found a few many constraints are there? In a puzzle width w and height interesting puzzles, and these were not improved on signif- h, where the puzzle in Figure 1 is 3 × 3, there are w × (h + icantly when moving to the 4 × 4 board. In Figure 2(b) we 1) + (w + 1) × h must-cross constraints that can be placed show one interesting puzzle with the solution in (d). The on edges (the right two constraints). An additional (w +1)× puzzle is interesting because the natural tendency is to draw (h + 1) can be placed on vertices (the upper left constraint). a path directly towards the constraints, but the solution ini- Thus, the total number of positions where a constraint can be tially winds around the outside. When solving for 4 × 4 puz- placed is 3wh+2w+2h+1. If we then want to place k must- zles with 5 constraints on the board, there were no puzzles cross constraints onto a board with n possible constraints, with unique solutions. With 6 constraints on the board we there are nk ways to do so.  found the smaller puzzle from Figure 2(b) repeated with a Our procedure for finding interesting puzzles works as single additional constraint, shown in Figure 2(c). As this follows. For each possible arrangement of constraints, we does not bring significant new depth to the understanding of count how many legal solutions there are for a given puz- this puzzle and solution lengths were already maximal for zle. We then keep all puzzles with the minimum number the board size, we did not explore further, although for com- of solutions. Initially we stored all such paths, but later we pleteness it would be worthwhile to study puzzles with 7 switched to only storing the longest paths. Longer paths may constraints. seem more contrived, but that piece of the aesthetic is point- If we were to continue to explore these puzzles we would ing more towards mechanics, and we found that the longer consider what happens when the board is filled with must- paths tend to contain elements of surprise (BtB3) not found cross constraints with very few open locations. (The com- in shorter paths. For instance, consider the puzzle in Figure 2(a). Here the constraints are uninteresting as they only al- low a single simple path to the goal. In the search process we gain some efficiency by throwing Table 2: Number of must-cross constraints out a puzzle once we know that it is worse than the best puz- zle found thus far. While significantly better performance height width max # total min sol. time could be achieved, our simple code was sufficient for our 3 3 40 3 9,880 4 0.01s purposes – we able to explore all 4 × 4 boards with up to 3 3 40 5 658,008 1 1.51s 6 constraints on each board in less than 1000 seconds, as 3 4 51 3 20,825 16 0.20s 3 4 51 5 2,349,060 1 5.42s shown in Table 2. In this table, the max column is the number 4 4 65 3 43,680 190 0.59s of locations where constraints can be placed. The # column 4 4 65 4 677,040 27 6.01s is the number of ways to place constraints. Note that for each 4 4 65 5 8,259,888 2 73.41s possible placement, all combinations in Table 1 must be con- 4 4 65 6 82,598,880 1 969.74s sidered to compute the number of valid paths. That is, on a (a) (b) (c) (d) Figure 3: One interesting set of separability constraint puzzles plexity of putting must-cross constraints in all but k loca- tions is the same as placing them in k locations.) In this case Table 3: Number of region constraints the constraints at the intersections of paths should be primar- height width max # total min time ily used, as they give more options for movement. We could 3 3 9 3 336 14 0.01s also explore the use of cannot-cross constraints, which are 3 3 9 5 2,016 1 0.08s just broken lines in the game that cannot be crossed. There 3 4 12 3 880 87 0.24s are several optional puzzles in The Witness that explore these 3 4 12 4 7920 20 0.59s together. Beyond this, there does not seem to be significant 3 4 12 5 12,672 2 1.38s additional depth that can be found in must-cross constraints 4 4 16 3 4,480 820 6.25s 4 4 16 4 29,120 218 24.56s alone. 4 4 16 5 69,888 74 74.36s 4 4 16 6 256,256 2 219.36s Region Constraints As a second piece of exploration we look at the region con- straints in a similar manner to our study of must-cross con- colors or the use of even larger boards. Most puzzles gen- straints. In a w × h puzzle there are whk 2 k−1 ways to place erated with three colors can be simplified to use only two k pieces onto the board, assuming two colors. For symme- colors, so further filtering is needed to find the interesting try reduction the first piece placed is always black, and the three-color puzzles. We have seen larger user-generated puz- remaining pieces can be any color. zles with just region constraints that are difficult to solve, so As before, to get a sense of the size of the problem we there is still room to explore region constraints on their own. show the number of combinations and minimum number One way to quickly reduce computational times on much of paths for solving a puzzle in Table 3. Although there larger boards is to only build puzzles with symmetric piece are fewer puzzles for each board size, it is more expensive placement. to compute whether a solution is valid because it involves dividing the board into regions; pre-computing the regions would speed up this calculation. Joint Must-Cross and Region Constraints One interesting set of puzzles were found on the 3 × 4 One point of the BtB aesthetic is that mechanics in games board size, shown in Figure 3. The puzzle in (a) with 6 pieces should have orthogonal design (BTB7). In the case of the has a natural beauty because of the placement of the pieces constraints we are looking at in this paper, the constraints and their colors. Puzzles (b)-(d) have pieces in the same lo- are physically placed in different locations on the puzzle - cation in each puzzle, but the change in colors means that must-cross constraints are on paths, while region constraints the solution used to solve each puzzle is completely differ- are in the spaces between paths. This means that both types ent. (The solutions are in Figure 5 in the appendix.) of constraints can be placed in the same puzzle, effectively When describing the BtB aesthetic, Blow uses puzzles combining the mechanics together. We previously discov- with the region constraints to illustrate several design points ered that small puzzles require too many constraints to pro- in the puzzles. The one point of completeness that is de- duce puzzles with a single solution, and when a single so- scribed and used in the game that we do not explore here lution is produced the solution tends to be trivial. Here we is varying the location of the exit. Blow keeps the puzzles look at the impact of joining together the two mechanics. almost fixed and varies the exit to produce different paths; We find more interesting puzzles with the combination of we do this with different colored constraints while keeping constraints; it is an open question whether an interesting the constraint locations fixed. It would not be difficult to add phase-transition occurs as the number of types of constraints start/goal locations as part of the EPCG exploration proce- is added to a puzzle (Gent and Walsh 1994). dure. Even adding a single must-cross constraint to a region For this paper we did not deeply explore more than two constrained puzzle can make a puzzle significantly more (a) (b) (c) (d) Figure 4: Puzzles with joint must-cross and region constraints complicated. Our previous work (Sturtevant and Ota 2018) Given further exploration, it would be worth deeply ex- studied how multiple puzzles can be combined together to ploring larger puzzles with as few constraints as possible to create a triple puzzle where one solution solves all three sub- see if the use of two types of constraints is able to reduce puzzles. That work did not take advantage of the orthogonal- the total number of constraints required to make interest- ity of constraints to use only a single puzzle with different ing problems. It is also worth exploring together some of types of constraints. But, it did suggest that when combin- the many other constraints available in the game to see what ing puzzles, it is useful to look for individual puzzles with new and interesting things can be learned through the EPCG the maximum number of solutions that, when combined to- process. gether, only have a single solution. Although we did not use As a preliminary test of the value of these puzzles we up- this metric directly when building puzzles, we were able to loaded the puzzles in Figure 4(a) and (b) to a popular site for verify that it held for many puzzles. The Witness puzzles3 . The site keeps track of the most pop- There are 10,098,000 combinations of ways to place 2 ular puzzles by ‘likes’, and within two days Figure 4(b) was must-cross and 4 region constraints on the 3 × 4 board. This tied for the most popular puzzle of the previous two weeks takes 173.04s and leads to 485 unique puzzles (with max- and Figure 4(a) was just one ‘like’ shy of Figure 4(b). While imum length and a single solution – there are 945 puzzles further user studies are needed, this provides preliminary ev- when including the shorter solutions). We illustrate one such idence that users find these puzzles interesting to solve. puzzle in Figure 4(a). As with previous puzzles, this one is interesting because the natural first actions do not lead to- Summary wards the solution. We would summarize the process we describe in this paper On a 4x4 board there are 195,686,400 combinations of as one of exploring the nature of the constraints in The Wit- ways to place 3 must-cross and 3 region constraints on a ness to see what puzzles arise from these constraints. This is 4 × 4 board. This takes 5721.52s and leads to 72 puzzles a mixed-initiative process, with a designer asking questions (with maximum length and two solutions each – there are about the size of the board, the number of solutions, etc, and 3020 puzzles when including the shorter solutions). We se- then analyzing the results to look for interesting content and lected a few of these puzzles and placed them in Figure 4(b)- new questions to ask. (d). All of these puzzles would be trivial to solve with just From this process we make a few generalizations about the region constraints, because there are so few region con- puzzle design. First, puzzles with many solutions are less straints. Similarly, they would be trivial to solve with just interesting because they are less likely to test specific un- the must-cross constraints. But, when combined together, derstanding. Thus, a common EPCG question seems to be the resulting puzzles are non-trivial to solve. There are of- to ask for puzzles with a single solution, or with as few so- ten many puzzles with the same solution but slightly differ- lutions as possible. Second, puzzles with fewer constraints ent configurations of constraints. Part of the editing process seem to be more interesting than those with more con- that is needed after exploring puzzles is removing puzzles straints. Fewer constraints seem to reduce the contrivance where the combinations of constraints do not seem to work of the puzzles and ensure that the puzzles do not overwhelm well together. The puzzle in Figure 4(c) is a strong puzzle the reasoning capacity of the player solving the puzzles. In- because the must-cross constraints interact closely with the stead they directly test the understanding of the constraints region constraints. But, the puzzle in in Figure 4(d) is poor in the game. Thus, a common EPCG process will likely because the must-cross constraints are placed independently involve iterating over small board with small numbers of from the region constraints, making it feel like two separate constraints to find the threshold where interesting problems puzzles instead of a single integrated puzzle. (The solution emerge. This is beneficial for EPCG because of its limited can also be pieced together more independently.) Because ability to scale to very large problem instances. Finally, we both of these puzzles have the same solutions, we would 3 only want one of them in practice. https://windmill.thefifthmatt.com observe that, in this domain, avoiding very short paths in- herently produces puzzles that have interesting interactions, even without directly optimizing for these interactions. In many of the puzzles shown in this paper there is a simple so- lution that can be achieved if a single constraint is removed. This minimalism pushes the player directly up against the constraints in each puzzle, forcing the player to analyze puz- zle in new ways. The work in this paper relied on writing custom code to answer the EPCG questions that arose. Future work will need to look at more accessible ways of using EPCG to ex- plore game design that do not require as much code. This will allow more users to engage with EPCG methods and use them to explore their own design spaces. References Gent, I. P., and Walsh, T. 1994. The SAT phase transition. In ECAI, 105–109. Knuth, D. E. 1976. Mathematics and computer science: Coping with finiteness. Science 194(4271):1235–1242. Liapis, A.; Smith, G.; and Shaker, N. 2016. Mixed-initiative content creation. In Shaker, N.; Togelius, J.; and Nelson, M. J., eds., Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer. 195–214. Shaker, N.; Smith, G.; and Yannakakis, G. N. 2016. Evaluat- ing content generators. In Shaker, N.; Togelius, J.; and Nel- son, M. J., eds., Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer. 215–224. Sturtevant, N. R., and Ota, M. J. 2018. Algorithms for ex- haustive and semi-exhaustive procedural content generation. In Artificial Intelligence and Interactive Digital Entertain- ment (AIIDE). Figure 6: Solutions to puzzles in Figure 4 Appendix: Puzzle Solutions For completeness, in this section we provide the solutions to any puzzles in the paper that did not already appear. Figure 5: Solutions to puzzles in Figure 3