# 利用ASP方法理念制作益智游戏谜题

Gunpoint(from gamesbyangelina.org)

Puzzle(from gamesbyangelina)

《Refraction 2》是一款关于分数的游戏。在游戏中，玩家要在激光束的路径上放小道具，使之转向、分裂、合并等，使激光束最终射进目标飞船，给它充能。游戏设计的谜题要求玩家分裂和合并激光束，如合并两个1/16激光束，给需要1/8能量的飞船充能，以测试玩家的分数算术能力和其他概念。事实上，上文作者已经就此写了另一篇关于使用线束求解法设计谜题的系统的文章。那么，这次他们想说的是什么呢？

Puzzle(from gamesbyangelina)

puzzles(from gamesangelina)

（改良后的求解器制作的谜题。注意右图根本不需要陨石！）

{“飞船需要1/2能量”, 特征2…, 特征X, “玩家必须把1/4和1/4的激光束合并起来才能获胜”}

{“飞船需要1/2能量”, 特征2…, 特征X}

《Gunpoint》的另一张截图(from gamesbyangelina)

“……如果我做的谜题太开放了，玩家会觉得太容易……那么我就提高限制级，使谜题只有一个解决办法，但玩家又抱怨太困难……结果是，我只能把这种谜题放在开放性关卡中。我发现这么做达到了更加平衡的效果。”

The Saturday Paper: Goldilocks And The Three Puzzles

by Mike

Most procedural generators have it pretty easy. Generation techniques for content like dungeon layouts or 3D worlds can’t really fail – they proceed very steadily, laying down content as they go, and if the occasional tree ends up floating in mid-air it’s not going to break the game. This attitude won’t cut it for more critical game content like puzzles or narratives, however. One small mistake might shortcut half of the plot or render a game trivially easy. How can you tell if a puzzle is solvable in the right way, though? This week on The Saturday Paper we look at how procedural generators can intelligently design puzzles with just the features you want – no more, no less.

We’re reading Quantifying over Play: Constraining Undesirable Solutions in Puzzle Design by Adam Smith, Eric Butler and Zoran Popovic. The paper describes their work investigating AI and game design when building a puzzle designer for the game Refraction 2 (you can play the original for free here), an educational maths puzzle game, and the steps they took to make sure the procedural puzzle generator would not only generate puzzles with particular solutions, but puzzles which didn’t inadvertently have additional, unwanted solutions either. The result is a clever procedural design system that can precisely ensure certain goals are met in its output – something that is completely reusable, and could come in handy in all manner of game design projects.

We’re back in the realm of constraint solving here, which we saw recently when reading about populating dungeons with monsters and items a few weeks back. There’s a longer overview there as well as some links to good tutorials, but the upshot is this: constraint solving lets you describe the results you want from a program, rather than writing the instructions to get there like you would with normal ‘imperative’ programming. If you can find a good representation for your problem – which can be tricky at first – then constraint solvers can rapidly build a solution, making and undoing possible design choices as it tries to match the criteria you give it.

Refraction is a game about understanding fractions. Players place pieces in the path of laser beams to redirect, split, combine or change the beams in some way, in order to provide a particular amount of power to some target spaceships. By allowing the player to split up and combine laser streams the game can test fractional arithmetic and other concepts by designing puzzles that require certain kinds of solution – like merging two 1/16 lasers to power up a spaceship needing 1/8 of power. The authors have already written a paper on a system using constraint solving to design puzzles for this purpose, in fact. So what was their next step?

If you look at the picture above, you can see a nice puzzle solution on the left, demonstrating splitting and joining laser beams (with some rather elegantly symmetrical puzzle design to boot), and on the right you can see a nasty shortcut that completely bypasses the whole point of the puzzle. One way to avoid these shortcuts is to generate a puzzle, and then exhaustively test every possible solution to make sure there are no solutions that break the rules you had in mind for this level (such as teaching the player about splitting lasers, as above). This isn’t great for a number of reasons pointed out in the paper – for one thing, this might take ages, especially if the constraints can’t actually be satisfied. Equally importantly, such a system can’t use information about failed designs to stop trying the same idea out for a particular constraint problem.

What if we could express the idea of shortcuts as constraints, just like the rest of the puzzle design system? This would be a huge improvement, because answer set programming (or ASP, the special type of constraint solving used in the paper) improve dramatically over time by using failed solutions to avoid bad designs in future attempts. How do we encode something like that into an ASP, though? The solution uncovered in the paper is initially mind-bending, particularly if you’ve not used ASP before. I’m going to try and give a brief idea here, but I highly recommend reading the paper and contacting the authors to find out more details.

Some puzzles made by the improved solver. Notice how the one on the right doesn’t need rocks at all! It’s all in the elegant placement of the lasers and spaceships.

First, imagine that before we run our solver we give it two things: first, a definition of what we want every solution to include (call it the concept); second, a list of level design features that the solver can define to describe a level. A level design feature might be “Spaceship A needs 1/2 Power” or “There’s a rock at (2,2)”, while a concept might be “The player had to add 1/4 and 1/4 together”. Now suppose our solver comes up with a puzzle-and-solution pair, and through testing it knows it embodies that key concept we want the player to practice. The question is, how do we know if this puzzle has other solutions that pair with it – ones that shortcut our concept?

What we’re looking for (or rather, hoping we don’t find!) is any puzzle-and-solution pair which has exactly the same set of level design features, but that doesn’t have our concept satisfied. If you look at what that means, here’s our initial outcome:

{“Ship needs 1/2 power”, feature2…, featureX, “The player had to add 1/4 and 1/4 together to win”}

And here’s the dastardly shortcut, in which the concept we hoped was required is actually missing:

{“Ship needs 1/2 power”, feature2…, featureX}

In mathematics, the bottom list is a subset of the top list. What Adam and co. do, in just a few lines of ASP, is tell their solver to forbid subsets like this, meaning that if they find them then they know that something about that level design has to change. It’s a little more involved and a lot more clever than I’ve made out, but the principle is the same. And because of the way ASP works, these failures help make the search faster and faster, until a puzzle design is found.

The beauty of this subset checking is that the idea is completely general, and so is the code that Adam and co. have written. As long as you can write down what it means for a concept to be broken or shortcutted for a particular puzzle-and-solution pair, you can use the system developed for Refraction 2 in your own procedural content generator. The paper itself suggests this might be used not just for puzzles, but everything from interactive stories to crafting systems. In essence, it gives developers of procedural generators access to modeling the trickiest problems possible in ASP while staying anchored on the same design task: level design choices and a target concept you wish to see in all player solutions.

Another screen from Gunpoint

The system can produce some really elegant puzzles. As the authors point out, while human designs use things like impassable rocks to block off shortcut solutions (making it much simpler to check the puzzle over visually), the ASP solver is so rigorous it can often satisfy conceptual constraints just by cleverly placing the lasers and their spaceships on the level – and still have a huge diversity of output. I’m really excited to see where this goes next – given that Refraction is a game with education in mind, this could lead to tailored puzzles that teach specific mathematical ideas to people.

I’ve been playing Gunpoint a whole lot since it came out last Monday. In the developer commentary, designer Tom Francis says:

“…if I made the puzzles too open-ended, people found them too easy… then I tried a more restricted version where there was generally only one solution, but people complained it was restrictive … [I ended up with] a puzzle nested within an open-ended level. I found that balance worked much better.”

One of the things I really like about this research – and it’s not exclusive to constraint solving but it’s illustrated so well here – is that with a bit of intelligence in our procedural generators, we could feasibly design puzzles that are perfectly open-ended but where all solutions pass through the same point – exactly as Tom describes his process for Gunpoint worked. Or puzzles where all solutions seem equally feasible (for some definition of ‘feasible’, of course). Or we could design puzzles that explicitly require gadgets the player hasn’t been using very much.

The barrier for many will probably be getting into answer set programming in the first place. The authors here are keen on building better tools, systems and languages that might help developers use the power of ASP without learning a lot of complex new programming ideas though. I originally wrote here, “It’s a barrier worth getting over”, but instead I’ll leave you with a quote from Adam Smith on this very topic, in an email to me about today’s post:

I appreciate your effort in saying “it’s a barrier worth getting over”, but I think I shouldn’t be asking people to cross that particular barrier when I know of not-so-difficult ways to build tunnels through it.

As you can see from the work in their paper, there are some very enticing lights to be seen down the end of this tunnel. I’m looking forward to seeing more of it.(source:gamesbyangelina)