August 31, 2005

Lumines: Killing The Fun, Part Two

I've been talking about Lumines. I decided to find out if it was possible to successfully play Lumines deterministically, without looking ahead. The answer, which I've already alluded to, is "yes and no". Read on for a detailed description of how and why.

First, a brief refresher. Lumines is a block-based puzzle game, where you rotate and place blocks that drop vertically onto your game board. Blocks are flagged for deletion when arranged into two-by-two squares of the same colour; they are deleted when the "timeline" sweeps over them. There are two colours. Blocks drop in two-by-two squares.

There are four types of blocks (all other blocks are either rotations or colour-inversions of these types; that's why I count less types of blocks than others - notably gmasterflash - do).

chequer / "deuce"

The Lumines boards is sixteen columns wide, and ten rows tall. The aim is to stay alive by placing these pieces in such a way that you can still place another.

The worst possible arrangement in Lumines is a chequerboard. Since pieces can only be deleted by forming squares, the only way to remove a chequerboard patterns is to slowly work away at it from an exposed location (the top or side). The fundamental tactic to staying alive for a long time is to avoid creating chequerboards in the first place.

The chequer / "deuce" piece is, therefore, a recipe for disaster. It can very quickly destroy a board, and is the hardest piece to place well. In the Lumines FAQ at Gamespot (which I will not link to, as they have a draconian linking policy), the author "gmasterflash" points out that it's possible to deal with deuces in a special way: cordon off a section of the board into which only deuces are placed, in a stable and repeating sequence.

This is a really nice insight. Gmasterflash's solution takes four columns, plus one buffer column to stop the rest of the board interfering, and neatly takes care of all the deuces.

What about the other pieces? Two types are trivial: the solid deletes itself, so requires two columns (plus a buffer). Two pairs delete each other when stacked vertically, so again this requires two columns. Even better, the same space can be used to delete both types together, so these only require a total of three columns.

This leaves the "three", which occurs in both colours. If five columns are needed for deuces, and three for solids+pairs, this leaves eight columns for these two types. If a buffer-zone is to be left between the two types, this leaves seven columns, which must be used as one three-column section and one four-column section. This means that a three-wide solution is needed. Is it possible?

To investigate, I first set up a few extra constraints on the problem. The major complication is the "timeline" and the speed with which pieces drop. For simplification, I am assuming that the timeline moves fast enough (or pieces drop slow enough, or are distributed evenly enough) that all potentially-deletable pieces will be deleted before the next piece is dropped. This is what I call a "slow" game: the board is stable before the next piece is introducted. Real games are not slow, which is one reason why the solutions I'll show you aren't really 100% guaranteed in practice.

This is pretty classic type of computer science problem, that's usually part of "artificial intelligence". You have some start state, and some set of ways of moving from one state to another, and the objective here is to find a cycle within the state-graph. I won't bore you with the details; you can build the graph by expanding iteratively and hashing seen states. You can detect cycles by using a coloured depth-first-search. If you would like to know more, leave a comment and I will happily provide.

To start with, and to let me get a little bit of oneupsmanship out of my system, let's look at deuces in more detail. To look at the gmasterflash loop, click here (link opens in new window). It takes two drops to set up the start of the cycle, and four pieces are dropped in each cycle.

This turns out to be pretty close to optimal for a four-wide deuce-only loop. That's not to say there's not a better solution, of course, and here it is. The only improvement is that now only one piece is dropped before the cycle begins. Not much, but hey! It's a start.

But do you need four columns to make a cycle? It sure looks like it. I had to try, though - by which I mean, I had to make my computer try for me. And it turns out that it is indeed possible to make a three-wide loop composed only of deuces. And what's more, it's shorter, too - only two drops long, with a single setup! I hadn't expected such a good narrow solution, but there you go!

So, deuces are sorted, and in only three columns. Once solids and pairs are dealt with, this now leaves nine columns for the two types of "threes"; that's four columns for each.

Well, let's start with three columns - it was possible for deuces, so what about threes? And it turns out that it is indeed possible to make a three-wide loop composed only of threes. There are, in fact, lots of ways. Including symmetrically identical versions, there are over two-thousand loops within a three-column, eight-row space. The version I've linked to there is the "best", in that it is the shortest cycle (only four drops) and of all equally-short cycles it is the one that requires the least drops to set up. Unfortunately, it still needs thirty moves, including sweeps, to build the right setup for the loop.

This is what I mean when I say that it's technically possible to find a deterministic mechanism for playing Lumines. No-one said it would be easy!

This is the narrowest and fastest that you can build a cycle if you start from scratch and only use threes; it's understandable that, given only one type of piece, it's hard to build the starting position you want. But what if you relax the start-position constraint a little, and allow some pre-building?

To investigate, I tried starting with just a single extra piece added to one column. The results were surprisingly good! Turns out, there's a very good solution that's only four drops long. That's a lot better than before. You still have to get that first priming square there, but that's easier than an elaborate 30-step setup.

There are four-wide patterns for solving threes too. The shortest cycles are ones like this four-wide cycle for threes. It needs a little bit of setup, and then has a four-drop loop. They're not necessary, but it's good to know, anyway.

With the patterns that I've shown so far, there is enough room to deal with each type of block completely separately (except for pairs and solids, which are dealt with together). In fact, there's a little room to spare! So, as long as it is possible to play a "slow" game, Lumines is solved.

Before I found these solutions, I was wondering whether the original game designers had thought about this. My original suspicion, that each cycle would require four columns, would have meant that it was impossible to solve each independently. The PSP screen could have fit more columns, so I was beginning to suspect that the width was chosen especially to stop this deterministic solution. As it turns out, I was wrong: either they didn't think of this, or they didn't think it was an issue.

(In an aside, I don't think anyone tried to work out whether Tetris was NP-complete or not when they were making it, and it's really not important, either. Oh, and it is NP-complete, by the way. So is Minesweeper.)

Now for the caveats: while theoretically possible, I really don't think that it's practical to play the game this way. First, there's the problem of remembering the loops. There's only two loops (one of which is colour-inverted) to remember, but it's still a lot to be doing quickly. Even then, timing becomes a problem. In a given level, it may not be possible to wait for all sweeps in a block-zone before dropping the next piece. It could be possible to build cycles that were "stable" with early-dropped pieces, but I haven't checked that yet.

For all that I've said that I'm "killing the fun", finding this solution hasn't dampened my enthusiasm for the game. I don't intend to play it using this type of pattern; I do intend to beat my current high score of a bit more than three hundred thousand. The score maxes out at 999,999 - if they let it keep going, there wouldn't be a milestone to reach, but as it is, well, there's only one thing I can do....

Posted by Casey at August 31, 2005 02:58 PM