No rulebook, no tells

No rules. No rule book. Ever. I had reverse-engineered rules from 100 shipped levels and had constructed an agent to generate levels based on my best guesses. The studio’s sole level designer had sorted 20 generated levels into those he thought had been written by a machine and those that he thought had been written by a human. He had done well, identifying 14 of the 20 generated levels, but described the levels that he had correctly identified as being nearly indistinguishable from his human-written work. Five days later, with three new physics models under my belt, he’s no better than guessing at identifying the generated levels (which were now shipping at 90% acceptance).

A studio with a live puzzle game on the web agreed to let us use 100 production levels as a basis for a challenge: could we get an AI agent to write levels for the campaign that the AI wrote, and would a designer be able to tell the difference? The only evaluation that we set up before writing a line of code was a blind test: we would write 20 levels and the studio would pick from those plus 20 real levels, without knowing which were which. The designer’s picks had to be no better than random.

This set up is actually 90% of the work to create an acceptable test. Because your acceptance test is actually a human, trying to catch your AI, you will make all kinds of decisions along the way that bend to the one question: What can he see that you can’t measure yet?

No Rulebook, No Tells

But we didn’t get a rulebook. No design document, no style guide, no list of shippable level criteria. The studio designer had 3+ years of ‘taste’ in their level design, but all we got was a folder of levels and a deadline. Every rule listed in this article (e.g. levels oriented this way, devices have this many tokens per type, levels in this corpus band, etc.) was reverse engineered from the levels themselves or else we lost a round to not implementing it.

This shot was taken almost blind, just relying on the simplest 3D models for the player agents and on several intuitions about what would be hard to recognize, and hit way closer than we expected.

Level Design in Practice

The puzzles are of type drag-and-collect. In a drag-and-collect game colored polyomino containers are placed in a grid on which also lie same-colored tokens, scattered around. In drag-and-collect games a container is moved across the grid by dragging it with the mouse and all tokens of the same color as the dragged container which are reached by it are filled (boarded) by it. The container which contains tokens is removed from the grid after it is full. The studio in addition to these basic elements of the game also uses spawners (which can be placed on the border of the grid) which stream tokens of a certain color one after another in order, hidden second layers of containers (which double the capacity of a container for a certain token type after this container has been filled for the first time for that token type), locks, obstacles and axis constraints. A good level is shaped in a certain way rather than simply being hard.

Deconstructing the studio's hand

First, we reverse-engineered the already generated levels in the 100-level corpus (eight different schemata realized in 100 levels), and searched for an exact per-color conservation invariant holding in the levels. After that, we reversed-engineered the game’s dynamics, that is, how levels are played, by frame-stepping through the game’s gameplay footage, figuring out the queue order, lock semantics, and movement rules, by inspecting the pixels on the screen, as opposed to the studio people telling us how to realize the levels.

The key figure here is the positional corpus window which compares a generated level candidate for a campaign slot N against a band of levels for the same slot N. The studio’s hand changes across the campaign. The levels in the game grow in size, the headroom between the playing field and the top and bottom of the screen decreases and the number of devices in the game increases. Thus, a level for a campaign slot N has to be within a band for each of the ~20 features for a level of that slot N.

First, the baseline is perfect on paper – 20 generated levels, all solvable, all valid within their respective corpus windows, and five golden evals all green. I shipped the first set of the “blind pack” set of levels with some confidence.

There was nothing wrong with the basic approach of making 20 levels. The levels looked great, the solvability was guaranteed, the corpus windows all fit. All 5 gold test cases passed for all 20 levels. We shipped the first blind pack of our Level Generation Studio with great confidence.

Round 1: caught in twenty minutes, and praised anyway

During round 1 our designer even managed to score 14/20 (p = 0.013) while only superficially looking at the generated compositions. And indeed, one single distributional property by far dominated the designer’s scoring: the board orientation. The reason for this, of course, is that the studio never had managed to ship a landscape level before, but we had managed to ship 7 out of 20 test levels.

Another important point from Round 1 that initially went unobserved is illustrated in Figure 8 below. How did the level designer feel after the studio designer had sorted the 94 levels by their quality? Clearly, the designer was very impressed with the results. In particular, he felt that, aside from the obvious errors in the studio levels, the generator levels looked as if they were designed by a human.

“If it weren’t for the obvious mistakes, it is nearly impossible to distinguish this from a level designed by a human.” — the studio’s level designer for round 1.

— the studio’s level designer, round 1

This was also surprisingly good at replicating human composition (see Fig. 7). The onlythings it got wrong were obvious (i.e. mistakes that would be immediately obvious to a human designer). Some of these mistakes are enumerable (e.g. the studio used a ‘landscape’ board a number of times; it used a ‘Device Rate’ that was way too high to ever be shipped). Others are not (yet). As mentioned, the designer felt that the ‘obvious mistakes’ in the compositions were the easiest things to spot, and so the entire project was redirected towards closing off the list of tells that the studio had come up with for the ‘obvious mistakes’ rather than starting from scratch to teach the agent to have taste.

Expert feedback must be verified. Of the mistakes the designer said the system wasn’t able to spot that he listed out, one of them was actual (orientation), one of them was false that we were able to very quickly prove false (the designer had incorrectly stated a movement-constraint rule for the system and we were able to very quickly disprove 3 ways with designer-level content), and one of the ‘flaws’ that the designer said the system wasn’t able to spot for a level, actually pointed out a flaw in one of the studio’s own levels.

Round 2: Guessing at the Physics & Losing Twice

The follow-up round involved us bringing our levels into the live game and having the designer play through them to identify the generated levels. He correctly identified all 6 machine levels in the set of 12 created (6 human + 6 generated). Interestingly, the reasons for the designer’s identification of the generated levels as not being human created was because none of the machine generated levels could actually be completed. His reasons for this were found to stem from an error in our rules model for how collection works, an error which would later be found and corrected in two subsequent physics models.

I will present to you what the level might look like and how it certifies under each of the physics models and then dies to under the evidence found in each respective model’s flaws.

All 100 corpus levels were solvable under v1 physics (a perfect score for the solver). However, in truth, all those levels were unsolvable under the strictest model and had to be hand-tuned to be solvable. Initially, the solver could solve only 75 of 94 usable corpus levels under v2 physics. But, with sufficient search, this was upgraded in turn to 81 of 94 levels.

Round 3: reaching chance

All twenty levels were re-generated for the new physics rules model. This can be witnessed in the journey of one single campaign slot in Fig. 09.

For this test the designer took a more refined approach, and flagged 4 of the 6 “real” levels, allowing 2 of them to be published in their normal state. The designer was also very quick to finger-print a single level as being “machine-generated” and even provided solid reasoning for the levels slight asymmetry. The detection rate for this test was a rather underwhelming p ≈ 0.12 (or in simple terms: he basically guessed correctly).

In our later review calls of the levels the designer of one of the machine-made levels of "Hard" difficulty stated that "It was a good level — it challenged me, its balance was right. Had it been submitted to me, I would have approved it."

"It was a good level — it challenged me, its balance was right. Had it been submitted to me, I would have approved it."

However, during that same call, knowledge of the “unwritten house rules” for critique were revealed, including the most important one: that colors in a hidden-layer container must never be used in other hidden-layer containers. This was an important rule for the studio as it prevented the “dead-end” state that had once caused them so much pain. 87 of 94 levels in the studio’s corpus comply with this rule (see fig. 11).

Each failure found in reviewing levels further solidified the hard checks in our critic. The first blind test’s critical remarks became house style, even with the bands between the different types of statistics sometimes varying significantly. Each of these checks was also calibrated against the entire corpus before being added to the critic.

The regression that taught us the most

Then a quality regression creeped in. Swapping in a newer base model meant that we’d certified a new set of levels. And this set of levels used zero optional devices. In other words, there were no hidden layers, no obstacles. Just twelve open and airy levels to play. This was in stark contrast to our own earlier sets, where we used a device in about 1 in 4 levels on average. (As an aside, the designer had previously pointed out that sets are more meaningful than levels.)

The most obvious hypothesis is that this new model is just afraid to be creative, but, after some wresting with this idea, I came up with an A/B test: take the exact same 12 briefs, run them through the previous model in the exact same codebase, but with the setting to “use devices at the studio’s rate”. What happens? The entire generation collapses to produce the barest minimum of scenes, every single one of them failing for the same reason.

So the real mechanism for the flops in both cases was a victim of the generator's own acceptance gate. We had assumed the solvability certificate (a solvability certificate is a semi-decision procedure — i.e. it may fail to confirm a solvable level but never claim an unsolvable level is solvable) was something that was exercised by the solver’s search parameters. But in practice it was simply a different view on the same problem, and the problem the generator was trying to solve (create an acceptable level) was the same set of views that the solver was trying to solve (solve the level). As such the generator had learned the same lessons as the solver. And the verifier’s blind spots had been quietly inherited by the generator. Even the designer of the new model had commented that the levels generated by it looked “flat” — ie they had the solver’s fingerprint on them, not the model’s.

By the time I even considered these potential fixes I had cheaply confirmed or rejected them. Making search width larger did nothing for 13/14 of the levels, and a short amount of trial and error setting the device requirement for the brief within a campaign slot, and verifying that the studio had introduced that device to the player in the relevant level, confirmed that in the cases where a model did indeed try to solve a level that required a device in a brief, saving such a level would drop to 50% (since the level is a “corpus” level that the gate cannot verify for solvability). And further, I found a self-inflicted bug in the case where a brief required a device for a campaign slot level: the brief would fail to be accepted by the agent in those cases (because there was no device introduced by the studio for that level yet).

To solve the problem, we invert the problem. Instead of generating levels and then solving them, the generator can produce proof of solvability for a level, and the verifier can replay the solution to verify that the level can be solved. That’s to say, instead of scattering tokens until a level is solvable, we search backwards from a solution to a level to populate the board with tokens that solve the level. Every level would then come with a solution witness for the level, which could be replayed for verification rather than re-searching for a solution, and the length of the solution witness could be a way to vary difficulty for the studio, which is the next thing they want.

What transferred

1. Put the ground truth outside the code. This blind test of our story using a human as an expert found all the issues with our internal test metrics that we had failed to find before. It also provided a clear answer to ‘done’.
2. ** Rules are hypotheses.** Three physics models. Two of them were killed by evidence when put to the test. A validator who relies on unchallenged assumptions flatters himself to think he is validating.
3. Distributions are the tell, not instances. Every detection round was won or lost on set-level statistics — e.g. the numbers of orientable cavities, amount of devices to be placed of various types — none of which can be derived from any individual level’s features.
4. Verify the expert. Feedback is only encoded if it survives contact with the data (i.e. is true): one of the designer’s assertions was treated as gold, one was false, and one attributed a level to the wrong studio.
5. Your acceptance gate shapes your generator. Any learned or searching producer will drift to what your verifier rewards. Therefore the bias in your output will look like a model problem until you A/B the environment.
6. When verification is the bottleneck, generate certificates. All generated levels are solvable. The hardest check is then no longer a problematic search but a simple replay of a solution.