Procedural Puzzle Generation in The Witness

Spoilers for The Witness

I finally got around to playing The Witness last month, and enjoyed most of it a lot. The vast majority of the puzzles are hand crafted by Jonathan Blow and his team, but near the end is an infamous section, The Challenge. The Challenge is the only timed section in the game. To stop you simply memorising the puzzle answers, all puzzles in this section are randomly generated.

The change of pace and style, coupled with the intense music, and with a few curveballs thrown in, makes it one of the most memorable sections of the game.

I was naturally intensely curious as to how this generation works, and fortunately Blow shared all the key code for this section on stream last year. So I naturally got stuck in.

The answer is: they are all incredibly simple. They rely on generate-and-test. I.e. a relatively unsophisticated random generator randomly places puzzle elements, then the result is checked to see if it has a solution. If not, then you simply retry until you get a good one. There’s little attempt at making puzzles too easy, or too hard, as long as they are solvable. I certainly found playing this section, there was a good chance of running into a puzzle that was too hard, or very quick, but as the whole sequence is only six and a half minutes, it’s not too punishing to have to retry a couple of times.

Let’s dive into each puzzle, and what it does specifically. Each puzzle is named lotus_ as that is the codename for this section.

Continue reading →

Chain of Thought For Humans

These past few weeks, I’ve been conducting interviews, and I often open with “make sure you articulate your thoughts out loud, so I can follow along with your thinking”. This is primarily because I’m not a mind reader, but it does also help ensure candidates avoid freezing up. It’s a very “interviewy” skill though – artificial and unlike real development.

The other thing I’ve been doing is playing The Witness, a 2016 puzzle game centred around solving mazes with increasingly complicated hidden rules. The game has a unexciting presentation, no music or interesting dialog, and no story. At first I found the game fairly dull, you spend a lot of it just wrestling with possibilities and combinatorics. It can get very frustrating when you are not making progress.

But, inspired by my interviews, I’ve started narrating my own thought process out loud to myself. I look like a bit of a loon, but I tell myself I’m just a streamer with an audience of one. And to my surprise, it’s working really well. Not only does it make the game more lively and energetic, but also I find I’m more effective in solving puzzles.

I was initially baffled by this. Common sense says that I can’t articulate my thoughts at remotely the same speed or accuracy as thinking them. Particularly for a puzzle game where the majority of reasoning is geometric, difficult to describe in speech. We know LLMs benefit from this sort of reasoning, but that is due to an architectural limitation – they literally cannot iterate on previous thoughts; they must output tokens to get any true recursion.

But then I remembered rubber duck debugging. It’s often useful in software engineering to explain your problem to someone else. But who you explain to isn’t really an important part of the process – it could be a rubber duck. The value is in forcing you to evaluate all your unstated assumptions, linearly sort your thoughts by priority and dependency, and find good abstractions.

These are also useful skills for real-time problem solving. I think there are some further benefits for this particular use case:

  • It forces you to establish named formal rules and concepts, instead of relying purely on building intuition. In other words, engaging System II, which the puzzles are explicitly designed to require.
  • It forces you to acknowledge when you are making an arbitrary choice. Useful for backtracking or exhaustively searching a possibility space.
  • I think it lets you use echoic memory to slightly augment your working memory.
  • I may well have accidentally triggered the Hawthorne effect

It turns out there’s good evidence that this technique has a moderate benefit, for example this meta-study (n=6000 participants). I’m definitely going to try it in future in more circumstances.

Do You Have Any Ideas?

The Machine Stops (E M Forster, 1909) is an enormously prescient sci-fi dystopia. Everyone lives in isolation, with the titular Machine responsible providing for all their needs, and communication done via video calls. It’s incredibly accurate for predicting some aspects like the internet, social media and AI. But other aspects, like humanity’s total surrender of control to the Machine, have yet to come to pass.

But one aspect that always fascinated seems to be on the verge of becoming true. The citizens of Forster’s story are obsessed with new ideas. They are constantly trading them, and people’s chief activities are “eating, or sleeping, or producing ideas”. The implication is that the omnipotent Machine, which supplies everything needed to the citizens, is sterile. The citizenry still depend on each other to keep life interesting.

Continue reading →

Mesh Welding with Spatial Hashing

Recently I’ve been looking at Mesh Welding algorithms.

Mesh Welding is when you have a a mesh, i.e. a collection of vertices, edges and faces, and you merge any vertices which are close enough together.

This is a common operation in procgen, as it’s often convenient to generate several things completely independently, then join them together afterwards. I’ve had to re-implement it several times.

Continue reading →

Oatmeal Spice

Say you’ve written a little procedural generation program. Say it’s some art, music or level generator. It looks kinda cool, but after a few generations, you are already bored with it. Somehow, for all your careful design, all your generated results look samey, boring. This is Kate Compton’s ten-thousand bowl of oatmeal problem: every bowl of oatmeal is unique, but that does not make them interesting or valuable.

What can you do about it? In this article, I want to talk about how we can improve the interestingness of the results, not by adding more content, but by taking things away.

Continue reading →

Dihedral Subgroups Explained Via Factorio

The dihedral group is the mathematical formalism behind all the rotations and reflections of a regular polygon. For an n sided polygon, there are always n possible rotations, and n reflections, for 2n possible symmetries.

Combining any two symmetries gives another from the same group, that is what makes it a group in the mathematical sense.

The theory of it is useful to know for gamedev. I was reminded of this when seeing this Factorio devlog, where the developer ran into some trouble because he initially forgot to account for all the cases.

Continue reading →

Next Token Prediction is a Misleading Term

I’m fed up of hearing about how LLMs are next token predictors, and therefore they <cannot do some task> <aren’t really doing cognition> <are just guessing>.

There’s lots of philosophical objections, but fundamentally, framing AI as next token predictors in the first places is just misleading and inaccurate. Here’s why LLMs aren’t naive next token predictors.

Continue reading →