After nearly five years (and nearly 10 years since I started blogging), I’m starting a new blog, Page Fault, at https://www.neilbickford.com/blog/. The first new article is a tutorial that shows you how to build a real-time denoiser in JSFX, REAPER’s audio programming language. It has some nice behavior, and it’s been used in production for several videos at the UCLA Game Music Ensemble.

You’ll also notice that the last two posts have been copied over to Page Fault. Since there are many websites that link to https://nbickford.wordpress.com, this blog will also remain online to avoid breaking those hyperlinks. Please note that some articles on this website are down for maintenance at the moment.

Congratulations! You’ve just been hired to record the crowd at the Super Bowl!

The producer wants you to figure out how loud each section, and ideally how loud each fan, is cheering so that they can better choose where to station the T-shirt cannons. They don’t want to know the actual dialogue – they’re not the NSA – only each fan’s loudness, or amplitude*. You don’t even have to record the fans’ cheering over time, but just how loud each one is, on average, over the full game.

*technically, loudness is a psychoacoustic property of the amplitude, the average intensity, and the frequency spectrum of the signal, but in this article we’re assuming (for the purposes of keeping it relatively short) that they’re essentially the same.

The only problem?

You’re on the other side of the field, 160 feet away from the nearest spectator. And you have one microphone with which to record all twenty thousand fans.

Source: Getty Images

Hi! This is an introduction to astronomical interferometry and radio telescopy! This article might assume that you have some familiarity with Fourier transforms, but that’s about it. This article is currently in beta; if you find any issues, errors, or omissions, please let me know through the comments below. Thanks!

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.

Although Threes is popular, a clone of a clone of Threes, Gabriel Cirulli’s 2048, seems to have managed to reach a much wider audience. Its rules are almost identical to those of 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 Threesfound 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 →

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.

A 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)

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):

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)

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)

Otherwise,

Recurse to the case where that cell is filled with a void,

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.

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. Also, the post continues after the break.

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 →