The Official MathGeek Blog

Go!

In 1957, Herbert A. Simon, a pioneer in artificial intelligence and later a Nobel Laureate in economics, predicted that in 10 years a computer would surpass humans in what was then regarded as the premier battleground of wits: the game of chess. Though the project took four times as long as he expected, in 1997 my colleagues and I at IBM fielded a computer called Deep Blue that defeated Garry Kasparov, the highest-rated chess player ever.

You might have thought that we had finally put the question to rest—but no. Many people argued that we had tailored our methods to solve just this one, narrowly defined problem, and that it could never handle the manifold tasks that serve as better touchstones for human intelligence. These critics pointed to weiqi, an ancient Chinese board game, better known in the West by the Japanese name of Go, whose combinatorial complexity was many orders of magnitude greater than that of chess. Noting that the best Go programs could not even handle the typical novice, they predicted that none would ever trouble the very best players.

Ten years later, the best Go programs still can't beat good human players. Nevertheless, I believe that a world-champion-level Go machine can be built within 10 years, based on the same method of intensive analysis—brute force, basically—that Deep Blue employed for chess. I've got more than a small personal stake in this quest. At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players. More...

King me! Science of winning checkers solved

With its uniform pieces and simple moves, checkers may seem like a simple kid's game. But it took hundreds of computers running continuously for nearly 20 years before researchers announced today that the game has officially been solved, a major benchmark in the development of artificial intelligence.

Thirteen years ago, a program named Chinook beat the reigning human world checkers champion, a feat that preceded Deep Blue's famous chess defeat of grandmaster Gerry Kasparov by three years.

Now, the programmers behind Chinook have fully solved the game, creating an unbeatable program that will choose the best move in every possible situation.

"In artificial intelligence, the chess and checkers groups have gone beyond the pale of what we thought we could do," said Michael Genesereth, an associate professor of computer science at Stanford University. "At one point, we thought we never could solve them in this way."

The team, led by University of Alberta computer science professor Jonathan Schaeffer, detailed the process Thursday on the Web site of the journal Science. The effort required up to hundreds of computers working since 1989 to analyze all possible board combinations of checkers, roughly 500 billion scenarios.

"Had I known it 18 years ago it was this big of a problem, I probably would've done something else," Schaeffer said. "But once I started, I had to finish." More...

Hyper-Dimensional Rubik's Cubes

MagicCube4D is a four-dimensional Rubik's cube. It is an exact analogy in four dimensions to the original plastic three dimensional puzzle. A five dimensional version is available here.  These are Rubik's cubes of the form 3^d, with the original popular puzzle being 3^3. We label the puzzles like this because they are a d-dimensional cube broken into 3^d smaller pieces or "cubies" of the same dimension. For example, the 3D cube has 3^3 or 27 total 3-dimensional cubies. Each of the d-dimensional cubies could be considered to have its faces covered by stickers of one smaller (d-1) dimension. But each cubie also only exposes a subset of its stickers to the "outside", meaning these are the stickers you could see if you lived and operated in d dimensions. We can use the number of exposed stickers as a classification of cubie types. For the 3D case, the 27 cubies are broken into 4 types, those that expose 0 stickers, 1 sticker ("centers"), 2 stickers ("edges"), or 3 stickers ("corners"). Each sticker on a given cubie has its own color, so we could also call these 1-colored, 2-colored, etc. pieces. More...