Go-Ghost in the Machine
The first problems tackled by artificial intelligence researchers tended to be those that humans find hard - proving mathematical theorems, for example. Early successes convince many that AI would not be a tough nut to crack. Claude Shannon wrote about computer chess in 1950, and many thought it would only be a short time before computers surpassed humans at it, but in fact it was almost another half-century (1996) before IBM's multi-million dollar Deep Thought beat Gary Kasparov. Computers and programs that can beat top grandmasters are now quite cheap.
One of the last refuges of human intellectual superiority in a purely formal setting is the game of go. John Henry still can beat the steam hammer in that game, but the first cracks in our dominance are appearing.
June's Scientific American reports on a new strategy that I think may have implications beyond purely formal tasks. It's based on so-called Monte Carlo techniques with some new refinements.
Monte Carlo methods have a long history in complex calculations. The idea is that you introduce an element of chance. Rather than try to explore all possible moves, you randomly select some and follow them a long ways out. Moves that tend to produce more good positions are rated more promising than others. Since the Monte Carlo technique can follow a move sequence all the way to game end, a definitive evaluation of that particular path is available.
Go can be played on boards of varying sizes, with 9x9 usually the smallest, 13x13 big enough to allow for a bit of strategy, and 19x19 for all serious games. Even the 9x9 board has hitherto proven to be to tough a nut for computers to crack, but the new algorithms can beat strong amateurs on it. The big boards, and the pros, remain to be conquered, but the developers predict that ten more years may be it.
One reason this type of algorithm may be important in general is that by inserting the element of chance, it truly opens a window for something like machine creativity. I hope to write more on that later.