Transcription
This is a random agent exploring the state space of a sliding block puzzle. The puzzle is called Klotssky. These block puzzles are quite common. But aside from just being puzzles, these sliding blocks define graphs modeling convoluted topologies with their local substructure as well as their global superructure.
Often it's a 6x6 grid where the solution is to free this block from the hole on the right. We can't do that yet since this piece is in the way. Let's represent the current position of the puzzle as a node. If we make one move on the puzzle, we arrive at a different node. Since these positions are just one move apart, we draw an edge connecting the two nodes. Each node is connected to a few more forming a labyrinth of paths.
You might start to wonder if we add all the nodes, what would the graph look like? Maybe it has an overarching structure such as a grid. Or maybe it's a total mess. To build some intuition, here's a few contrived puzzles first. With just one block, there's only one degree of freedom. With two, you get the cartisian product of their coordinates, yielding a grid. Each block defines a different axis of motion. Three blocks make a 3D lattice. And with four degrees of freedom, the graph naturally extends to a hyper cube.
But it gets more fun when the pieces can intersect. Taking our two block puzzle, but with blocks opposing each other, a section of the 2D structure is no longer valid, representing overlapping pieces. With the two blocks on the same lane, we get this triangle shape. Wherever the top block is, that serves as a bound for the bottom block. With a puzzle like this, we implicitly create an imaginary counterpart structure corresponding to the valid states which are unreachable without one block passing through the other. Three intersecting pieces still form a cube. There's just some excavated areas.
But as the piece number gets higher, the graph's dimensionality has less to do with the number of pieces and more to do with the number of empty spaces. As an example, this puzzle has some cool behavior. If I expand it out entirely, notice that it has some overall superructure, but also in a small portion of the graph, the local behavior is quite nicely patterned as well. It's like a cute little local uklitian manifold with two dimensions, two degrees of freedom. That's because on the puzzle, there are two holes allowing movement. One axis characterized by moving the top hole, one axis for the bottom. In the extreme case, it's not the pieces moving, but rather the empty spaces which define the degrees of freedom. So somewhere between a full board and an empty one, we get complex structures of tangled intersections between pieces.
Here's one of the puzzles we started with. Its superructure is quite simple. Pause for a moment to think through what it might look like. You might be able to guess its form from the arrangement of the pieces. Ready? From this perspective, the puzzle is almost symmetrical. The key is recognizing that these two pieces stay latched in one of two spots. They can either be to the left of the vertical red bar or they can be to the right of it. Only one can transition at a time. When the red bar is up, the orange block can transition, but when it's down, the green block can transition. This is the defining characteristic of the graph's superructure. It's a square connecting four corners.
We can color the nodes on the graph in correspondence with the position of the puzzle. Nodes in this half have the green block right of the bar and nodes in this half have the orange block right of the bar. Let's take a tour around this graph. Now from here we can highlight all the solutions where the green block is by the hole. Unsurprisingly, they all live in the corners with the green block right of the bar. Can you figure out why the graph has a higher dimensionality near the corners?
Here's Klotssky again. The goal is to get this big piece out of the bottom. It's slightly different since the intersections don't have pins, so blocks are free to move laterally. Compared to the last puzzle, it's much harder. I showed it to a co-orker after work, but he wouldn't leave until he solved it. He finally got it at 11 p.m. He thought the hardest part was getting the box under the horizontal bar. Instead of solving it myself, I was more interested to see how it works under the hood. Is getting the box under the bar actually the hardest part? The structure defined by this puzzle. What is this for?
[Music] That's 25,955 nodes. The puzzle is symmetrical. So the graph is two. For example, if we take this position, the board is a mirror reflection of this note on the opposite side. Turning 90°, we see a rough division into two halves. This red node right here is the starting position. And these are all the solutions where the square is at the bottom. All the solution nodes are on the opposite half of the graph as the starting position.
By making random moves. Unless we get lucky, we're probably going to crash into this dense pit. Going back to the start, the only alternative is to walk one of these very fine lines to the other side. This line is the shortest path to a solution. Let's follow it.
[Music] Interestingly, this is not the path used by the Guinness World Record speed solver, who instead takes this line. Let's see if my friend was right that getting the horizontal bar unstuck is the hardest challenge. Let's highlight every node. Red when the block is above the bar, orange when they're side by side, yellow when the block is almost under, and green when the block is finally below the bar. Now, once again, take a peek at the solution set. There's an extremely close overlap. So, my friend's intuition was right.
What else can we learn? Remember how this puzzle has unreachable positions? So does Klotssky. You might notice that although the graph is horizontally symmetrical, why not vertically, too? Although in theory you could rearrange all the pieces upside down, it's not actually possible unless you take a piece out and put it back in. Adding the flipped board and all the other positions reachable, we get our doubly symmetric graph. Are there any other disconnected islands? It turns out quite a lot. Here's the biggest one with only 248 nodes. It's primarily oriented as a long path with occasional branching.
So, what makes this puzzle hard? We could say, for example, that it's hard because getting the block under the bar is hard, or that it's hard because crossing between the two halves is hard. But I think there's something more fundamental going on here. Let's peek at a far away land and select a small region of nodes. Now I'm going to show you the boards for all of these nodes, but blurred together so that we can only see the shared patterns. All the boards in this substructure have one thing in common. The block and bar are in the center. This local structure is formed by two holes similar to the 2D grid before. But if we align the holes just right, we can break out into a different substructure with its own rules and organization.
[Music] In other words, this graph can be thought of not as a single unified topology, a single overarching framework of rules which govern the puzzle as a whole, but rather a collection of local subpuzzles which have their own logic and form loosely stitched together into one large puzzle.
But what's the point? Who even cares? It's just some toy. Allow me to draw a parallel diagramming a map of phenomena in the natural world. We see biological superructures at the highest level built loftily at top of physical substructure through several layers of abstraction. The point is the differentiation of resolutions of phenomena isn't unique to physics. Even the most mundane domestic toy is no exception. Rather, such form emerges from the mere computational exploration of a system of rules.
I love using computer science to shine a fresh light on systems we otherwise wouldn't think twice about. Complicated topics, slidy puzzles, and programming alike, when viewed from the right perspective, can become much more clear. That's why Brilliance lessons are so effective. Their games and clear examples make all those hard subjects infinitely more digestible. Learn to think like a programmer by breaking down complex problems into manageable chunks of code. Or dive right into Python and start building programs on day one. Brilliant helps you get smarter everyday with thousands of interactive lessons in math, science, programming, data analysis, and AI. These topics don't have to be intimidating. Uncover their mystery with Brilliant.
To try everything Brilliant has to offer for free for 30 days and get 20% off an annual subscription, visit brilliant.org/twap in the description or scan the QR code on screen. This has been twos swap with music by 6884.