Editorial: “Seek them here, seek them there: Anonymous is everywhere“
SOLVING jigsaw puzzles might seem worlds away from ensuring national security, but $50,000 says otherwise. That is the prize on offer in the , which tasks computer scientists and puzzle-solvers with reconstructing shredded documents to reveal the information they contain.
Set up by the US Defense Advanced Research Projects Agency (DARPA), the challenge consists of five increasingly difficult puzzles, ramping up from 224 pieces to over 6000. There is more than just money at stake. Methods used to solve the challenge could one day help read a despot’s destroyed documents or tackle biological puzzles.
Advertisement
The pieces to the puzzle are all on DARPA’s website as scanned images. “The DARPA puzzles are somewhat like jigsaw puzzles, but there are major and important differences,” says Craig Landrum, a former codebreaker for the US National Security Agency who is tackling it as a solo effort.
While the varying colour and shape of jigsaw pieces offer clues to their solution, the DARPA puzzle pieces, or chads, are all roughly the same shape and have just a few colours, normally black ink on lined paper.
Landrum has been assembling the pieces using a commercial image editor, manually sorting them into categories based on ink colour or the number of lines. “I could fairly easily predict the pattern that would need to appear on an adjoining chad and because of the way I organised them, I could quickly search and find good candidates,” he says.
To win the prize, puzzle-solvers have to answer questions based on the contents of the reconstructed documents. Points are awarded for full or partial solutions, and contestants ranked on a leader board according to the time taken to get those points. Landrum is currently fifth with 19 points out of a possible 50, with each being worth $1000. It took him 8 hours to complete the first puzzle, 20 for the second and over 40 for the third. The fourth has proved more difficult because it uses unlined paper, and he has only obtained a partial solution.
The time-consuming nature of the problem suggests a collaborative strategy might be more successful. This is the approach being (UCSD). Their effort is lead by , who was a member of the team that won a previous DARPA challenge to find weather balloons scattered around the US (see “Pin the coordinates on the balloons”). That effort used crowdsourcing and he hopes to apply the same technique this time. But building an army of puzzle-solvers alone won’t be enough to win.
“It is a necessary component but I don’t think it is going to be sufficient,” says Johnny Lee, an engineer at Google. Lee and colleagues have also built a crowdsourcing tool to tackle the puzzles but have not entered the competition, instead for anyone to use.
“Even puzzle one is harder than the balloon challenge,” says Cebrian. “The combinatorial nature of the problem makes it much more difficult.” So the UCSD team is taking a hybrid approach, using both computational number-crunching and human pattern recognition.
Computers are pretty poor when it comes to jigsaw puzzles – even the best automated solvers can only handle 400 pieces. But they can help speed up the manual sorting that Landrum is using. “All the computer has to do is turn a 6000-piece problem into a bunch of 200-piece problems,” says Lee.
The UCSD team hopes that once their cluster analysis algorithms have grouped similar pieces together, a crowdsourced group of over 3000 people will assemble them (see photo). Cebrian plans to use an edge comparison algorithm to provide puzzlers with the top 100 closest matches when they click on a piece.
Crowdsourcing does have its downsides, however. “One of the weaknesses of our approach is that you can see what we are doing and disrupt it,” says Cebrian. Soon after entering the top five on the leaderboard, the UCSD team came under attack from at least five people who interfered by moving pieces around or locking incorrect ones in place. The team has had to roll back to before the attack and implement a levelling system, which determines how often someone can move a puzzle piece based on their previous success.
“A downside of using crowdsourcing to solve the puzzle is people can disrupt the process”
The UCSD team is now in fourth place, but racing ahead is a competitor dubbed “All Your Shreds Are Belong To U.S”, the only ones to partially solve the fifth puzzle. The team could be a small group of hardcore puzzle-lovers, “manual solvers that worked all five puzzles in parallel”, says Landrum, but an email to Cebrian from “ucsdsaboteur” hints otherwise. The saboteur admits to recruiting others on 4chan, the favoured forum of Anonymous, to help disrupt the UCSD team, because “crowd sourcing is basically cheating”. The email signs off with the line “may all your shreds belong to us”.
The saboteur has a point, as DARPA would likely prefer a fully automated solution. “If we lose to manual brute force, that’s really sad for science,” says Cebrian. He believes that a semi-automated solution could have applications to other combinatorial problems, such as protein folding, genome assembly or building 3D models of the brain. “The brain could be the largest puzzle ever solved, and humans could help put it together,” he says.
Another application that might interest DARPA is sifting through a WikiLeaks-style data release. “Say there was a series of events that lead to some diplomatic situation. It is not easy to trace the origin and the causal path of this situation unless we have a way to put the pieces in the right place,” says Cebrian. In this case, individual documents become the puzzle pieces and the challenge is stitching them together into a readable narrative.
These problems will have to wait until the challenge finishes on 4 December, and the contestants are under no illusion of what’s ahead. “This is probably the hardest computational problem I’ve ever met in my life,” says Cebrian.
Pin the coordinates on the balloons
A 2009 DARPA competition had teams trying to find 10 red weather balloons floating somewhere in the US – a feat that Manuel Cebrian’s team at the University of California, San Diego, managed in less than 9 hours thanks to crowdsourcing.
His approach worked because anyone who submitted a correct set of coordinates was awarded $2000 of the $40,000 prize. The person who invited the balloon-spotter to join received $1000, with the awards continuing down the network. Cebrian is applying these incentives to the puzzle challenge (Science, ).
The Playstation 3 hacker George Hotz, who has 35,000 Twitter followers, was able to achieve a spike of interest and find eight balloons, but Cebrian’s team beat him by sustaining a lower level of interest over a longer period.
