USA's Top Daily Chess News Blog, Informative, Fun, and Positive

hosted by Chess Queen™ & 12th Women's World Chess Champion Alexandra Kosteniuk


Monday, June 3, 2013

Hackers Spawn Web Supercomputer on Way to Chess World Record

Chess blog for latest chess news and chess trivia (c) Alexandra Kosteniuk, 2013

Hi everyone,

This one looks a bit geeky: Hackers Spawn Web Supercomputer on Way to Chess World Record!

Three months ago, Ruan Pethiyagoda didn’t even call himself a computer programmer. But now he’s knee-deep in the Hack Reactor. Based in San Francisco, the Hack Reactor is one of many crash software development courses that seek to teach computer programming through several weeks of complete immersion in code, writes Klint Finley in the

Pethiyagoda enrolled in the school this past March, and over the past several weeks, he and three other hackers-in-training have teamed with one of the giants of the tech industry — the Pivotal Initiative, the big data spin-off company from EMC and VMware — to approach a new world record for what’s called the N-Queens Problem, a classic math puzzle that plays out on a chess board.

But more importantly, in working to solve this problem, this four-person team — Cameron Boehmer, John S. Dvorak, and Tim Sze, as well as Pethiyagoda — has developed a new breed of software that lets you pool the processing power of potentially thousands of machines just by pointing them to a single website. They call this creation Smidge. It’s a kind of ad hoc supercomputer built with JavaScript, the standard programming language of the web.
Hack Reactor is a place where you learn by practice. When you show up, you’re tossed into a group of other students and you’re all given a common project meant to further your understanding of computer science and engineering. You work 11 hours a day, six days a week.

Though little more than an experiment at this point, the project is yet another way the net is stretching the boundaries of “distributed computing,” where thousands — or even tens of thousands — of machines are pooled together to solve a common task. Popular web outfits like Google and Amazon operate in this way, and these web giants have spawned a whole new breed of distributed software that lets others benefit from the same tricks of the trade.

Hack Reactor is a place where you learn by practice. When you show up, you’re tossed into a group of other students and you’re all given a common project meant to further your understanding of computer science and engineering. You work 11 hours a day, six days a week.

It accepts seasoned programmers as well as students who have practically no programming experience, and the Smidge team is a nice reflection of this mix. Pethiyagoda had precious little programming experience when he joined, majoring in communications at Seattle University. He was working working at a product incubator, telling engineers what to build. But at some point, he realized his life would be easier if he could just build products himself. Sze had worked as actuarial consultant, after completing a degree mathematics and quantitative economics. But Dvorak came to school a programmer. At the age nine, he turned up in a documentary as the world’s youngest 3D graphic artist.

When the group arrived at the school, which sits on the edge of downtown San Francisco, their task was to create an algorithm that could solve the N-Queens Problem. The original version of the N-Queens Problem was posed as the “Eight Queens Puzzle” by chess player Max Bezzel in the German newspaper Schachzeitung in 1848, according to Across the Board by John J. Watkins. Bezzel asked how many different ways eight queens could be arranged in such a way that no two queens could attack each other, given a traditional 8-by-8 chessboard grid. This would be N=8.

Since then, computer scientists and mathematicians have worked to solve progressively harder versions of the problem, and at Hack Reactor, Boehmer, Dvorak, Pethiyagoda, and Sze joined the fight.

They began with an N-Queens Problem algorithm created by Martin Richards of the University of Cambridge Computer Laboratory and then translated it into JavaScript. “It fit in a Tweet,” Pethiyagoda says. “It was just over 100 characters.” On a single machine, this JavaScript program could calculate N=15 — 15 queens on a 15-by-15 grid — without crashing. Then they found a way to run it in parallel on two machines, and soon, they had solved N=17.

That was impressive enough, but with Smidge, the aim is to take this idea even further. Based on Node.js — a platform that runs JavaScript on servers — Smidge is similar to BOINC, the system originally created for the SETI@Home project. With SETI@Home, volunteers can donate their excess computer power to help comb telescope data for evidence of extraterrestrial life. Individual computers can’t do much processing on their own, but when networked with thousands or millions of other users, SETI@Home can process massive amounts of information in relatively short order.

BOINC has been adapted to other purposes — such as protein-folding and the search for black holes — and it has even been ported to Android phones. The rub is that, in order to participate, you have to install specialized software on your machine. Smidge is different in that it can run the same sort of distributed number-crunching applications inside web browsers — so the user doesn’t have to install software.

“We were able to scale it across every device in the building, including everyone’s laptop, iPhone, Android phone. Even my BlackBerry ran it, which surprised me,” Pethiyagoda says.

By inserting a bit of JavaScript into a webpage, Pethiyagoda says, a site owner could distribute a problem amongst all the site’s visitors. Visitors’ computers or phones would be running calculations in the background while they read a page. With enough visitors, he says, a site could farm out enough small calculations to solve some difficult problems.

As it turns out, the team has taken a different route in trying to break the record for the N-Queens problem. At one point, Pethiyagoda had dinner with a friend who works at Pivotal, who mentioned that the company runs a 1,000 node Hadoop cluster that it lets organizations like NASA crunch massive amounts of data. Hadoop is the open source clone of massive distributed data crunching system that underpins Google, and Pivotal maintains the cluster in order to test the software.

This Pivotal cluster, called the Analytics Workbench, often sits around doing nothing, so Pethiyagoda asked the company if he and his teammates could use the thing to take the N-Queen problem to new extremes. It so happens that Pivotal chief scientist Millind Bhandarkar — who worked on Hadoop at Yahoo prior to Pivotal — has longstanding fascination with the N-Queen problem, and he was happy to give them a crack at it.

With help from Bhandarkar and other Pivotal staff, the team translated the algorithm from JavaScript to Java, so it could run on Hadoop, and as of Sunday night, the cluster was on the verge of calculating the total number of potential solutions for N=27 — which would break the world record. The current record is held by the Dresden University of Technology, which calculated the number of solutions for N=26 in 2009.

‘We were able to scale it across every device in the building, including everyone’s laptop, iPhone, Android phone. Even my BlackBerry ran it, which surprised me’
— Ruan Pethiyagoda

With the record out the way, the team will turn its attention back to Smidge. Pethiyagoda and his cohorts believe they can actually build a business that will help organizations solve large number-crunching problems. The idea is to connect these organizations with websites that have large amounts of traffic, using that traffic to funnel processing power through Smidge.

If Smidge can charge less than cloud services like Amazon, Pethiyagoda thinks they could actually attract a large enough base of customers to provide a serious revenue stream to web publishers. The script would be designed in such a way that end-users would have to authorize web publishers to run the script on their computers, he says.

But the Smidge team aren’t the first to come up with this plan. “This idea has been discovered many times over the past 10 years. As far as I know none of these efforts has led to significant usage,” says BOINC architect David Anderson. BOINC hasn’t explored a JavaScript based approach in the past because of limitations such as the inability to use the graphical card of a computer.

Pethiyagoda says that JavaScript has come a long way in the last 10 years, thanks in large part to Google’s JavaScript rendering engine V8 and the Node.js platform. And Dvorak says they will be using the WebGL stand to access GPUs for faster computations.

With this year’s run on the value of Bitcoins — the popular digital currency — security expert Mikko Hyppönen thinks that criminals might soon start experimenting with this type of distributed computing too. He believes that crooks could infect websites with JavaScript code that would turn visitors into unsuspecting Bitcoin miners. As long as you’re visiting the website, you’re mining coins for someone else, says Hyppönen, the chief research officer with F-Secure.

The trick for Smidge will be finding problems that are a good fit for its approach. The bottleneck will be how much data can be sent between machines over the internet, so Smidge will work best for problems that don’t have large data sets but are computationally difficult, such as scientific simulations and graphical rendering. And yes, Pethiyagoda says Smidge could be used to mine Bitcoins. “When this comes online,” he says, “Bitcoin is going to have to adapt.” (Additional reporting by Robert McMillan)

From Alexandra Kosteniuk's
Also see her personal blog at
Don't miss Chess Queen™
YouTube Channel

Labels: , , , , , , , , , , ,


Post a Comment

Note: Only a member of this blog may post a comment.

Subscribe to Post Comments [Atom]

<< Home