How to Beat Threes (and 2048)

Threes is a terrifically simple, yet tremendously intriguing game from the creative team of Asher Vollmer and Greg Wohlwend, known for their work on indie games such as Puzzlejuice and Ridiculous Fishing. While each of them have created tons of great indie games, I don’t think it’s an exaggeration to say that Threes could well be their best game yet.

The rules are very simple: every time you swipe across the screen, all of the tiles try to move in the direction you swiped. Two tiles can combine if their values add up to 3, or if the tiles are equal and both integer multiples of 3. If you try to combine two tiles (by squishing one against the wall) and they can’t, then they act as a barrier, and that particular column or row doesn’t budge. Finally, there’s the part which makes it tricky: Every time you move the tiles, another tile is introduced. The goal is to reach the elusive 6144 tile, or more realistically, to last as long as you can without running out of possible moves.

For reasons which are yet to be fully understood, this game has attracted a stunningly large audience of players. Perhaps it’s because the game’s aesthetically appealing, or perhaps it’s because it’s apparently (and initially) easy to get past the first few stages, and yet nearly impossible to reach the final goal. It’s also a game which encourages study from just about everyone who’s played it (in the same way as Chess does), but also lacks any sort of threat of failure- a cheerful sound plays, and you get to see how many points you wound up with without losing in any sort of public way. In any case, even though it’s been around for only 2 and one-third months, there’s been an enormous amount of public interest and quite a few successful attempts to work out how the game works internally. Unfortunately, quite a few clones, some of which have offered notable modifications to the game, have also been created.

One of the most notable clones is Gabriel Cirulli’s 2048, which is almost identical to Threes, except for a few differences:

  • The tiles are the powers of 2 (2,4,8…) instead of three times the powers of two along with 1 and 2 (1,2,3,6,12,24…)
  • Only tiles reading 2 and 4 are ever inserted, as opposed to the 1,2,3, and sometimes 6 or more of Threes
  • The tiles slide as far as possible instead of moving at most one space
  • The tiles are placed randomly on the board (in Threes, they only ever enter from the edge you swiped from)
  • The goal is to get to 2048 instead of 6144, which makes the game a bit easier, since there are two types of tiles you never have to deal with, and
  • 2048 is free and open-source, and this, more than anything else, has probably led to its popularity and the number of subsequent clones.

If you’ve never played Threes or 2048 before, I highly recommend giving them a try, if only so that you can develop your own intuition for these games.

One of the few things that everyone who’s played Threes or 2048 agrees about is that these games are really difficult. As it turns out, people have discovered quite a few strategies for playing these games which make them a bit easier, but usually not by very much. However, there is a complicated and arcane algorithm for 2048, known as the Corner Strategy, that will allow you to match or surpass scores you may have spent hours achieving in just a few minutes, using only a few very simple calculations.

The Corner Strategy

Tap Right and Down in alternating order until you can’t move. Then press Up. Repeat.

This works ridiculously well, given the amount of thought necessary to run this algorithm.

(This isn’t sped up or time-lapsed in any way)

Of course, the standard corner strategy rarely gets you to the 2048 tile, though it sometimes does. There are other methods, such as the so-called Mancini technique (keep the largest number in a corner, construct chains, never press Left), but almost all are versions of the Corner Strategy.

What we’d really like to know, though, is how to play 2048 or Threes optimally; that is, what is an algorithm that will play a game so as to gain the highest score? While this is almost certainly extraordinarily computationally intensive, a number of programmers have developed algorithms which play 2048 extraordinarily well. There was actually a bit of a competition on StackExchange not very long ago to design the best AI for the game, and many of the submissions were able to attain the 2048 tile almost all of the time! In particular, the best AI, developed by nneonneo, uses a surprisingly simple technique known as expectimax optimization, which works something like this:

  • Consider the game tree of 2048: We move in one direction, then the computer places a piece randomly, then we move in another direction, the computer places another piece randomly, and so on until we can’t move anymore.
  • Suppose we can assign a “score” to each state of the board, which tells us roughly how good a position is, without actually looking into the future for possible moves or anything like that. The function used to calculate the score can be as simple as counting the number of empty spaces on the board, to complicated heuristics (such as ovolve’s combination of monotonicity, smoothness, and free tiles) It’s a bit like looking at a chessboard and guessing how much one side is winning.
  • That said, we can get a better idea of how good a particular state is if we can look a few moves ahead, and measure the approximate score of each of those positions, assuming we played optimally up to each one.
  • Now, suppose we’re at a particular state, and we want to determine how good a move such as, say, moving right is. It’s actually fairly easy to compute the expected score of the computer‘s move- just add up the score times the probability of a particular move for each move the computer could make. For instance, if there were a probability of 0.9 that the computer would place a 2 (say) resulting in a state with a score of 5, and a probability of 0.1 that the computer would place a 4, resulting in a state with a score of 2, then the expected score would be

0.9*5 + 0.1*2 = an expected score of 4.7

  • If we know how good each move we could make is, then we should just play the best move (obviously).
  • Expectimax optimization starts by asking “What is the best move I can make?” at the current state. To do that, it has to compute the score of each of the moves it could make, which it does by first branching over each of the moves the computer could make, and then measuring the score of each of the resulting positions by asking “What is the score of the best move I can make?” for each of those. Theoretically, this could go on forever, so expectimax just uses the base heuristic once it’s sufficiently far down the game tree (that is, once it’s thinking a particular number of moves ahead). Once it has decided on an accurate score for each of the possible moves it could make, it simply plays the one with the best score.

Not only is this algorithm very good at playing the game when equipped with a good base heuristic- nneoneo’s implementation achieved 4096 in 97 of 100 trials, and gets to 16384 about once in every eight attempts – it’s also very fast!

(this is also not sped up in any way- it really is doing 30 moves per second!)

Of course, if you have an AI that play the game, it’s not difficult to create an AI that can always place the new tile in the worst possible place for the player, making the game more or less impossible. (For instance, see Stephen B. Beevan’s Hatetris) This is exactly what Zsolt Sz. Sztupák has done with 2048-Hard, based off of Matt Overlan’s solver. Interestingly enough, the “Impossible” mode isn’t entirely impossible- I actually managed to get the 64 tile, with a final score of 540, while the embedded AI solver often gets to the 128 tile.

It’s Not Just You; Threes is Difficult for Computers as Well!

Unfortunately, if you try the Corner Strategy on Threes, you’ll probably get the lowest score you’ve ever gotten. In fact, the designers of Threes found out about the corner strategy fairly early on, and modified the game a bit to make braindead strategies like it ineffective. This has the side effect of making the game much more difficult. Continue reading

Images from “Marble Runs and Turing Machines”

I just returned from this year’s G4G11, where I presented my work on the computability of marble runs (with some success- while I did finish my slides, I went almost 2 and a half minutes over time despite editing and practicing my talk. PROTIP: Don’t go on a two-day vacation 4 days before a conference whose third major theme was sleep deprivation!) I promised I would post the full construction for a marble-run computer here, which not only shows that the double-switch marble run halting problem is PSPACE-Complete, but also should enable simple proofs of universal computability for many other systems. But enough with the jargon; this is going to be more of a slideshow-style post, although I’ll soon post a more in-depth explanation of my talk. (The original slides are also available here, which also includes notes on the script.)

But first, some acknowledgements. The very first image, an example of a marble machine, was taken directly from denha’s fantastic video, “Marble machine chronicle“. While denha’s Youtube channel focuses primarily on marble machines, the electronics videos are certainly interesting as well, so definitely check it out. I used Blender for most of the non-schematic animations, so thanks to the people behind the animation engine and Cycles Render. And finally, the proof would undoubtedly have been much more difficult without the ideas of Demaine, Hearn, and Demaine (choose your own ordering), not to mention the many other people who’ve done work on computational complexity theory and all the things that led up to the field. (I’m sure some would prefer I name-checked everybody involved, but then I’d have to include my kindergarten teacher and the crew behind the Broome Bridge and, well, this would be a lot longer.)

So, without further ado, here are the various images and videos from my talk, presented in substantially more than 6 minutes.

This is, as mentioned above, denha’s “Marble machine chronicle”, for those who have never heard of marble runs under that particular name before.

 

I made (with assistance from Peter Bickford) a short video demonstrating a few recurring elements in marble machines- specifically, the ones I would be analyzing later in the talk. The original marble machine, from the Tech Museum of Innovation,  also contains a few other elements (such as loop-de-loops, chimes, and randomized switches), some of which do nothing to the computational ability of the machine, others which actually do change the problem a bit. Additionally, I consider problems with exactly one marble or pool ball, although Hilarie Orman suggested that it might be possible to simplify the construction using two or more pool balls.

 

This is a decoy that looks like a duck, used for a quick gag and counterexample to the Duck test. This was actually the shortest clip and the longest render for the entire project; the good news was, it rendered at 24 times the speed of a Pixar film. The bad news was that it rendered at only 24 times the speed of a Pixar film.

 

pvpcA short slide made to demonstrate the proof that single-switch marble machines cannot emulate a computer (unless NP=PSPACE, which is really unlikely). Up top, we have the problem we’re trying to solve, while on the lower-left is a randomly generate marble run with edges annotated and on the right is a system of equations representing said marble run. (Click through to see the rest of the images)

Continue reading

Sliding Block Puzzles, Part 4 of 3

And you thought it was over! 1 2 3

I was originally planning to finish the series of articles on SBPs at this post, concluding with the announcement of the optimal puzzles for a 4×4 grid. Partially, this was because the SBPFinder algorithm would have taken prohibitive amounts of time to compute the boards for any larger size. For example, for the classic 4×5 grid, it would take somewhere around 128 days! A much worse problem is that it would have used approximately 64 GB of RAM, which, even at its cheapest, is an investment I cannot reasonably justify.

Fortunately, however, I soon realized how utterly stupid I had been when designing the SBPFinder algorithm. In case the reader doesn’t want to read the thousands of words in the previous posts, I’ll quickly describe it: Essentially, the algorithm used dynamic programming and a peculiar way of indexing into a 2D array to, cell by cell, generate all possible positions. The primary flaw with this technique is that it generates lots of duplicates, which both slows it down and requires the use of a hash set or other method of eliminating duplicate positions. (To go into the technical details, this is because certain oddly shaped pieces, which -not coincidentally- appear in the list of hardest simple^3 SBPs, cause the dynamic programming stage to consider too many branches of the tree. This, in turn, is because the computer cannot currently time travel and see what it does before it does it)

    The solution is to place entire pieces (or voids) in undecided spaces, proceeding left-to-right and top-to-bottom. Currently, this has been implemented as a recursive function, as follows:

Given a board B (which may be partially filled):

  1. Find the first cell which has not been decided yet- that is, does not contain a cell of a piece or a void, but rather exists in a state of indecision between the two. (This is implemented as a third cell type)
  2. If there are no undecided cells, the board is a valid placement of pieces and voids. (It may not be justsolved, though, so these are typically placed in a file to be processed further)
  3. Otherwise,
    1. Recurse to the case where that cell is filled with a void,
    2. Find all pieces which can be placed on the board and which cover only undecided cells and which covers the cell determined in step 1.
    3. For each of those pieces, recurse to the case where that piece is placed on the board.

Here’s the search tree for 2×2 SBPs using this method:

Click to enlarge; the search tree is really wide

Click to enlarge; the search tree is really wide. Also, the post continues after the break.

Continue reading

Hilbert(Hilbert)

hilbert-10-v2

In case you missed it, you can click on the image to view it at its full resolution (4096 by 4096 pixels). I highly recommend doing so- for one thing, that background’s not gray. Continue reading

Creating Fake Landscapes

Suppose, just for a moment, that you’re writing a program that allows you to explore a planet, similar to the Earth, but completely made up. The main problem in writing such a program would be generating the terrain of the planet- all the mountains, trenches, and everything in between. Sure, you could spend years modeling the entire landscape, meter by meter, kilometer by kilometer, but it’s much easier just to write a different program to automatically generate the terrain of the planet. (The former method, in fact, would take about 16 million years, even if you could create a square meter every second, without any breaks or sleep) It turns out that it’s possible to create very realistic landscapes, even by using methods which at first would seem to have no correspondence whatsoever with how terrain forms in real life. Continue reading

Joseph Luis Borges, Quantum Mechanics, and Lewis Carroll

While the fictional book in Jorge Luis Borges’ The Garden of Forking Paths resembles, and may have inspired, the many-worlds hypothesis in quantum mechanics, Borges was not the first to describe such an idea.

In Borges` short story, the fictional Sinologist Stephen Albert describes Ts`ui Pen’s “The Garden of Forking Paths” as essentially a “Choose Your Own Adventure” novel; the story branches based on choices the characters make. However, there are three things which set it apart from the modern version: Firstly, the reader can see everything happening in all the stories at once- if there were two stories being told, the book would list a part of the first story, then the same part, chronologically, of the second story, then the next part of the two stories, and so forth. (This style of writing is sometimes referred to as “hypertext fiction”) Another thing which is unconventional is that sometimes two stories merge. As Albert said to Dr. Tsun, in one path the protagonist came to his house as a friend; in another, as an enemy. In the book, an army marched through the mountains, and after acquiring a disdain for life, won the battle easily; alternatively, the same army passed through a palace in which a ball was being held, and because of this, won the battle the same way. Lastly, some things are inevitable: In life, this is death; in the story, this is the fact that Captain Richard Madden will capture the narrator.

To digress for now to the second topic: In the field of quantum mechanics, the Many-Worlds hypothesis (first printed by Hugh Everett in 1957, 16 years after Borges` story) is in its simplest state the idea that every time someone or something makes a choice, the universe branches off into many other universes, in each of which a different one of the possible choices was made. The usual example of this is the Schrödinger’s Cat thought experiment. Imagine a cat was placed in a box, and a device inside the box then flips a coin and measures whether it falls on heads or tails. If it falls on tails, it kills the cat; otherwise, it does nothing. After the first coin flip, the universe can be thought of as splitting into two different universes: one in which the cat is dead, and another in which the cat is alive. By observing the state of the cat, the experimenter can see which universe he’s in, but he can’t suddenly switch from the “plot” of one universe to the plot of another.

The Schrodinger’s Cat thought experiment, with a proton-spin measuring device instead of a coin flipper.
From user “Ramisses”, Wikimedia Commons.

Ts`ui Pen’s story shares many things with this theory: they both involve branching due to choices, the idea of separate timelines, and in fact Stephen Albert claimed “The Garden of Forking Paths” was, like Many-Worlds, “an incomplete, but not false, image of the universe”. The two ideas differ only in that Pen’s includes universes merging and inevitable events, while in the Many-Worlds hypothesis universes can’t merge, and there are somewhat extreme ways to keep otherwise inevitable events from happening. (See [2], pp. 26-27, 32-33, 54-57)

As it turns out, while the style of writing in Ts`ui Pen’s fictional book certainly was original, the most important ideas appeared more than half a century before Borges` story, in Lewis Carroll’s little-known novel Sylvie and Bruno, published in 1889. In the beginning of Chapter 23, the narrator witnesses a tragic event: a box is left in the street and a bicyclist crashes into the box and is flung over the handlebars, causing him to get very badly injured and go to the hospital. Using a magical watch, the narrator goes back to before the crash, removes the box, which causes the bicyclist not to crash. However, at precisely the time he wound the watch backwards, the scene instantaneously switches to the bicyclist in the hospital, with exactly the same injuries as when the narrator didn’t remove the box.

While this might initially seem strange, it can be interpreted as follows: At time, say, 1:00, the universe bifurcates into two different universes: A, in which the narrator does not remove the box; and B, in which he does. Initially, we see the narrator go down the timeline of universe A, but then at 1:30 (when the bicyclist is in the hospital of universe A) he goes back in time just before the bifurcation point. Here, he chooses to go down the path of universe B, and for a while he remains in that timeline, until 1:30, at which the narrator from universe A is returned to universe A. (It is unclear what the state of narrator B is during this timespan- are there two copies of the narrator, or is narrator A seeing the world through narrator B’s eyes?) In this way, Carroll not only gave the idea for the Many-Worlds hypothesis, but also presented how time travel might work in such a system. Carroll’s model shares the aspects of branching based on choices with Borges’ story and the Many-Worlds hypothesis, and shares merging and inevitability with Borges’ model.

Multiverse image

A flowchart of the interpretation above.

As with anything, there are a few objections that could be made- Carroll’s model switches back abruptly, as if a scene from a film had been replaced with another scene that just happened to match at the beginning, which seems unnatural; Ts`ui Pen’s novel shows every universe happening at once, which certainly the inhabitants of our universe don’t see; the description of universes ‘bifurcating’ is just a way to think of the evolution of the wave function, and so forth. However, one can definitely conclude from the evidence given that Borges’ Garden of Forking Paths, Carroll’s Magic Watch tale, and the Many-Worlds hypothesis resemble each other- and perhaps one even inspired another.

Sources

[0]          Joseph Luis Borges, “The Garden of Forking Paths” – from Collected Fictions, translated by Andrew Hurley. Published by the Penguin Group, 1998.

[1]          Lewis Carroll, “Sylvie and Bruno”. From The Collected Works of Lewis Carroll, 2005 Barnes and Noble edition. Illustrated by John Tenniel.

[2]          Jason Shiga, “Meanwhile”, Second Edition. Published by Amulet Books, 2010.

Reversing the Game of Life for Fun and Profit

This post is mostly a transcript with notes of a talk I did at G4GX, the 10th Gathering for Gardner. As such, it differs from the normal format a bit.

(Videography due to Peter Bickford- there was a cameraman recording all the talks there, but I haven’t heard from him recently.)

Transcript (sentences in brackets represent notes, i.e, things I wanted to say in the talk but didn’t have time for):

Continue reading

Follow

Get every new post delivered to your Inbox.

Join 37 other followers