Tuesday, September 15, 2015

Breakthrough in Machine Chess

Keeping in mind that my technical knowledge of computer chess is thin, this is impressive stuff (reported in MIT Tech Review):
While Deep Blue was searching some 200 million positions per second, Kasparov was probably searching no more than five a second. And yet he played at essentially the same level. Clearly, humans have a trick up their sleeve that computers have yet to master.

This trick is in evaluating chess positions and narrowing down the most profitable avenues of search. That dramatically simplifies the computational task because it prunes the tree of all possible moves to just a few branches.

Computers have never been good at this, but today that changes thanks to the work of Matthew Lai at Imperial College London. Lai has created an artificial intelligence machine called Giraffe that has taught itself to play chess by evaluating positions much more like humans and in an entirely different way to conventional chess engines.

Straight out of the box, the new machine plays at the same level as the best conventional chess engines, many of which have been fine-tuned over many years. On a human level, it is equivalent to FIDE International Master status, placing it within the top 2.2 percent of tournament chess players.

The technology behind Lai’s new machine is a neural network. This is a way of processing information inspired by the human brain. It consists of several layers of nodes that are connected in a way that change as the system is trained. This training process uses lots of examples to fine-tune the connections so that the network produces a specific output given a certain input, to recognize the presence of face in a picture, for example.

In the last few years, neural networks have become hugely powerful thanks to two advances. The first is a better understanding of how to fine-tune these networks as they learn, thanks in part to much faster computers. The second is the availability of massive annotated datasets to train the networks.

That has allowed computer scientists to train much bigger networks organized into many layers. These so-called deep neural networks have become hugely powerful and now routinely outperform humans in pattern recognition tasks such as face recognition and handwriting recognition.

So it’s no surprise that deep neural networks ought to be able to spot patterns in chess and that’s exactly the approach Lai has taken. His network consists of four layers that together examine each position on the board in three different ways.
If I didn't know better I might start proclaiming, "The singularity is near! The singularity is near! Repent and be saved! The singularity is near!" But I do know better. Chess is a finite game; abstractly considered, no more difficult than tic-tac-toe. In practice though the chess search space is vastly larger, and that makes it a challenging game. 

But there are many many human tasks where we don't know how to characterize the search space. Those tasks won't fall so easily.

Still, exciting stuff.

1 comment:

  1. Deep neural nets: good at being CEOs, venture capitalists, hedge fund managers. Not so much farmers, fruit pickers, firefighters, or community organizers.