Computer Program Teaches Itself to Solve Rubik’s Cubes!

I tried to warn you, fellow puzzlers.

I wrote posts about computer programs that play chess, Scrabble, Go, Atari games, and Jeopardy! I wrote posts about programs that solve crosswords. I even wrote posts about robots that solve Rubik’s Cubes in a fraction of a second.

And they’re getting smarter.

Say hello to DeepCube, an AI program that is now the equal of any master Rubik’s Cube solver in the world at solving 3x3x3 cubes.

And unlike other AI programs that have learned to play games like chess and Go through reinforcement learning — determining if particular moves are bad or good — DeepCube taught itself to play by analyzing each move, comparing it to a completed cube, and reverse-engineering how to get to that move.

It’s labor-intensive, yes, but it also requires no human intervention and no previous information. Chess-playing programs like Deep Blue work by analyzing thousands of previously played games. But DeepCube had no previous history to build on.

It started from scratch. By itself.

And became a Rubik’s Cube master.

In only 44 hours.

Compare that to the 10,000 hours it supposedly takes for a human to become an expert in anything, and that’s a mind-blowing accomplishment.

[Image courtesy of YouTube.]

From the Gizmodo article on DeepCube:

The system discovered “a notable amount of Rubik’s Cube knowledge during its training process,” write the researchers, including a strategy used by advanced speedcubers, namely a technique in which the corner and edge cubelets are matched together before they’re placed into their correct location.

Yes, the program even independently recreated techniques designed by human speed-solvers to crack the cubes faster.

The next goal for the DeepCube program is to pit it against 4x4x4 cubes, which are obviously more complex. But supposedly, deposing human puzzle solvers as the top dogs on the planet isn’t the finish line.

No, this sort of three-dimensional puzzle-solving is only an intermediate goal, with the ultimate endgame of predicting protein shapes, analyzing DNA, building better robots, and other advanced projects.

But first, they’re coming for our puzzles.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

The Robots Are Here and They Can Spell

[Image courtesy of World of Weird Things.]

I warned you, fellow puzzlers. You can’t say I didn’t warn you.

The robots are coming, and they want our puzzles and games.

Let’s look at the hit list:

  • Deep Blue defeated Russian chess grandmaster Garry Kasparov under standard chess tournament time constraints
  • IBM’s supercomputer Watson bested previous Jeopardy! champions Brad Rutter and Ken Jennings to nab a million-dollar prize
  • An AI program called DeepMind taught itself to play several Atari games with superhuman proficiency
  • There are several robots constructed out of LEGOs that solve Rubik’s Cubes in seconds flat
  • Dr. Fill, the crossword-solving computer program, competes at the American Crossword Puzzle Tournament, and in a matter of five years, it has jumped from 141st place in the 2012 tournament to 11th place in the 2017 tournament
  • Just last year, an AI developed by Google, AlphaGo (a product of DeepMind), twice defeated Ke Jie, the 19-year-old Go tournament champion ranked number one in the world

And Scrabble fans, you’re the next ones in the crosshairs of the machines.

During last week’s Consumer Electronics Show (CES), the Industrial Technology Research Institute out of Taiwan debuted the IVS Robot — aka The Intelligent Vision System for Companion Robots — a machine capable of defeating human competitors at Scrabble.

[Image courtesy of ABC News.]

Instead of tiles and a standard Scrabble board, the IVS reads letter cubes (similar to a child’s alphabet blocks) played on a slightly larger gameboard. But time limits for play and standard rules still apply.

From an article on Engadget:

It’s hard not to be impressed by all the moving parts here. For one, the robot has to learn and understand the rules of the game and the best strategies for winning. It also needs to be able to see and recognize the game pieces and the spots on the board. That means it can read the letters on the cubes and identify the double-letter and triple-word score spots.

And, last but not least, it needs the dexterity to place the pieces on the board and not disturb the existing letters — which is especially difficult when you’re laying down two words next to each other to rack up those two-letter combos.

A quick Google search confirms that the robot bested practically every reporter, tech-savvy or otherwise, that crossed its path.

In the video below, North American Scrabble champion Will Anderson teams up with reporter Lexy Savvides to battle the robot, but a technical error prevents the game from getting very far:

Still, you can see the potential here. I’m sure it won’t be long before the IVS Robot is making appearances at Scrabble tournaments, attempting to establish machine dominance over another puzzly activity.

Stay strong, fellow puzzlers.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

Puzzle History: Codebreaking and the NSA, part 3

[Image courtesy of NSA’s official Twitter account.]

At the end of part 2 in our series, we left off during the early days of the NSA, as American cryptographers continued to labor under the shadow of the Black Friday change in Russian codes.

You may have noticed that part 2 got a little farther from puzzly topics than part 1, and there’s a reason for that. As the NSA evolved and grew, codebreaking was downplayed in favor of data acquisition. The reasons for this were twofold:

1. Context. You need to understand why given encrypted information is important in order to put it toward the best possible use. As Budiansky stated in part 1, “The top translators at Bletchley were intelligence officers first, who sifted myriad pieces to
assemble an insightful whole.”

2. Russian surveillance and bugging continued to grow more clever and sophisticated, pushing attention away from codebreaking. After all, what good is breaking codes or developing new ones if they can just steal unencrypted intel firsthand by monitoring
agents in the field?

Moving forward, the NSA would continue to pursue all manner of data mining, eventually leaving behind much of the codebreaking and analysis that originally formed the backbone of the organization. But that was in years to come. Cryptography was still a major player in NSA operations from the ’50s and onward.

[The progression of “secret” and “top secret” code words.
Image courtesy of NSA’s official Twitter account.]

In May 1956, NSA cryptanalytic veterans pushed a proposal titled “Recommendations for a Full-Scale Attack on the Russian High-Level Systems,” believing that specially designed computers from IBM could provide the key for cracking the impenetrable Russian cryptography wall. Some cryptographers believed that ever-increasing processor speeds would eventually outpace even sophisticated codes.

By 1960, the NSA had spent $100 million on computers and analytical tools.

The problem? The NSA was collecting so much information that their increasingly small team of cryptoanalysts couldn’t dream of processing even a tiny portion of it.

But the quest for data access would only grow more ambitious.

In the wake of Sputnik’s launch in October of 1957, US signals intelligence would go where no man had gone before. The satellite GRAB, launched alongside Transit II-A in June of 1960, was supposedly meant to study cosmic radiation. (GRAB stood for Galactic Radiation and Background.)

[Image courtesy of NSA’s official Twitter account.]

But it was actually intended to collect radar signals from two Soviet air-defense systems. This was the next step of ELINT, electronic intelligence work. (The younger brother of SIGINT.)

The NSA would later find a huge supporter in President Lyndon Johnson, as the president was heavily invested in SIGINT, ELINT, and any other INTs he could access. This did little to quell the intelligence-gathering rivalry growing between the CIA and NSA.

Of course, that’s not to say that the NSA ceased to do any worthwhile work in codebreaking. Far from it, actually.

During the Vietnam War, NSA analysts pored over North Vietnamese signals, trying to uncover how enemy pilots managed to scramble and respond so quickly to many of the US’s airstrikes conducted during Operation Rolling Thunder.

Careful analysis revealed an aberrant character (in Morse code) in messages that appeared in North Vietnamese transmissions before 90 percent of the Rolling Thunder airstrikes. By identifying when the enemy used that aberrant character, the analysts
were able to warn US pilots whether they were heading toward a prepared enemy or an unsuspecting one during a given sortie.

Other NSA teams worked to protect US communications by playing the role of an enemy analyst. They would try to break US message encryptions and see how much they could learn from intercepted US signals. Identifying flaws in their own procedures — as well as members of the military who were cutting corners when it came to secured communications — helped to make US communications more secure.

[Image courtesy of NSA.gov.]

In 1979, Jack Gurin, the NSA’s Chief of Language Research, wrote an article in the NSA’s in-house publication Cryptolog, entitled “Let’s Not Forget Our Cryptologic Mission.” He believed much of the work done at the agency, and many of the people
hired, had strayed from the organization’s core mission.

The continued push for data acquisition over codebreaking analysis in the NSA led to other organizations picking up the slack. The FBI used (and continues to use) codebreakers and forensic accountants when dealing with encrypted logs from criminal organizations covering up money laundering, embezzlement, and other illegal activities.

And groups outside the government also made impressive gains in the field of encryption, among them IBM’s Thomas J. Watson Research Center, the Center for International Security and Arms Control, and even graduate student programs at universities like MIT and Stanford.

For instance, cryptographer Whitfield Diffie developed the concept of the asymmetric cipher. Joichi Ito explains it well in Whiplash:

Unlike any previously known code, asymmetric ciphers do not require the sender and receiver to have the same key. Instead, the sender (Alice) gives her public key to Bob, and Bob uses it to encrypt a message to Alice. She decrypts it using her private key. It no longer matters if Eve (who’s eavesdropping on their conversation) also has Alice’s public key, because the only thing she’ll be able to do with it is encrypt a message that only Alice can read.

This would lead to a team at MIT developing RSA, a technique that implemented Diffie’s asymmetric cipher concept. (It’s worth noting that RSA encryption is still used to this day.)

[Image courtesy of Campus Safety Magazine.com.]

The last big sea change in encryption came when the government and military realized they no longer had a monopoly on codebreaking technology. Increased reliance and awareness of the importance of computer programming, greater access to computers with impressive processing power, and a groundswell of support for privacy from prying government eyes, led to dual arms races: encryption and acquisition.

And this brings us to the modern day. The revelations wrought by Edward Snowden’s leak of NSA information revealed the incredible depth of government data mining and acquistion, leading some pundits to claim that the NSA is “the only part of government that actually listens.”

Whatever your feelings on Snowden’s actions or government surveillance, there is no doubt that the National Security Agency has grown and changed a great deal since the days of cracking the ENIGMA code or working with the crew at Bletchley Park.

Where will American codebreaking go next? Who knows? Perhaps quantum computing will bring codes so complicated they’ll be impenetrable.

All I know is… it’s part of puzzle history.


I hope you enjoyed this multi-part series on the history of 20th-century codebreaking in America. If you’d like to learn more, you can check out some of the valuable sources I consulted while working on these posts:

Code Warriors: NSA’s Codebreakers and the Secret Intelligence War Against the Soviet Union by Stephen Budiansky

Whiplash: How to Survive Our Faster Future by Joichi Ito

The Secret Lives of Codebreakers by Sinclair McKay


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

Rise of the Machines!

hqdefault5

I don’t mean to alarm you, fellow puzzlers and PuzzleNationers, but the machines may be taking over.

First, there was Deep Blue, defeating Russian chess grandmaster Garry Kasparov under standard chess tournament time constraints.

Then, there was IBM’s supercomputer Watson, sitting at the buzzer on Jeopardy!, besting previous champions Brad Rutter and Ken Jennings to nab a million-dollar prize.

An AI program called Deep Mind can play several Atari games with superhuman proficiency.

These days, you can design robots with LEGOs that are capable of solving Rubik’s Cubes in seconds flat.

And, of course, crossword fans probably know of Dr. Fill, the crossword-solving computer program that competes at the American Crossword Puzzle Tournament each year. In a matter of five years, it has jumped from 141st place in the 2012 tournament to 11th place in the 2017 tournament.

drfill_400x400

Now, the machines are coming for Go players next. Google has developed an artificial intelligence known as AlphaGo which twice conquered Ke Jie, the 19-year-old Go tournament champion ranked number one in the world.

This strategy board game is played with white and black gamepieces called stones, and the objective is to surround a greater total amount of territory on the game board than your opponent. Along the way, you can surround your opponent’s pieces in order to capture them and remove them from play.

Wikipedia aptly describes the depth and difficulty of the game:

Despite its relatively simple rules, Go is very complex, even more so than chess, and possesses more possibilities than the total number of atoms in the visible universe. Compared to chess, Go has both a larger board with more scope for play and longer games, and, on average, many more alternatives to consider per move.

go-game

People have been playing Go for over 2,500 years, and yet, machines have already surpassed our greatest player.

Science fiction movies have been warning us about this for years. I just never expected them to come after our games and hobbies first.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!