Thursday, July 11, 2013

 Chess is Almost Solved


“There are some things we do much better than computers, but since most of chess is tactically based they do many things better than humans. And this imbalance remains. I no longer have any issues. It’s a bit like asking an astronomer, does he mind that a telescope does all the work?” -Vishy Anand

It used to be no contest. Even if a computer could perform million, billions, or trillions of calculations per second, a game like chess surely got too complicated too quickly for a computer to compete with humans. At least, that’s what we used to think, but some things just don’t stay the same, as Willy Mason would sing you with his song,

When The River Moves On.

Even after all the time that’s passed, it’s hard to believe that computers have caught up to human intuition. After all, the number of possibilities for both sides, given a game of chess, is astonishing.

 Image credit: Screenshot from Gameknot.com, correspondence chess site.

 

Image credit: Screenshot from Gameknot.com, correspondence chess site.

From a starting point on a chessboard, the white player has a choice of 20 different moves, to which black can respond with any of 20 moves of her own. For a computer to look even a few moves ahead, it must consider hundreds of millions of chess positions, a daunting task for any machine and its programmer.

 

Image credit: Profimedia.com, Corbis.

 

Image credit: Profimedia.com, Corbis.

The first big human vs. computer match that I remember came in 1989, when then-World Chess Champion Gary Kasparov took on the best computer ever built in a chess match. The computer — Deep Thought — came in as the reigning World Computer Chess champion, and had once found a forced mate 37 moves ahead, a truly amazing feat for a game of chess!

While human improvement in chess has been incremental, however, computers have continued to get far faster, and algorithms for evaluating chess positions continued to improve as well. The tipping point came eight years later.

 

Image credit: Adam Nadel/Associated Press.

 

Image credit: Adam Nadel/Associated Press.

In a six game match in 1996, Deep Blue — the successor to Deep Thought — became the first computer to ever win a game against the reigning World Chess Champion under tournament conditions and time controls. It was the only game won by the computer in the match, which Kasparov won, 4-2.

But in the rematch in 1997, Deep Blue not only defeated Kasparov in a game, but the entire match, by a score of 3½-2½. Since then, computers have gotten progressively stronger. No computer has lost a championship-caliber match against a human since then, and no human has won even a game against a sufficiently strong computer under tournament conditions since 2010!

 

Image credit: Colin Frayn and Carlos Justiniano, The ChessBrain Project.

Image credit: Colin Frayn and Carlos Justiniano, The ChessBrain Project.

I’m not so strong as a chess player; I enjoy playing, but anyone even approaching expert or master level will beat me pretty much 99% of the time. If you make a few small mistakes or give away a little bit of material, you can still win if you’re playing against me. But a top chess computer will crush you.

Disclaimer: The news story I link to below was apparently an April Fool’s joke that I fell for. It seems I’m not the only one. (You’ll notice the story was posted April 2nd, 2012 with no disclaimer.) I’m happy to leave this up as proof that even I get fooled sometimes, but you can safely ignore everything past this point.

Amazingly, this now extends as far back as move 3

 

Image credit: Me, using gameknot's interface.

Image credit: Me, using gameknot’s interface.

The three moves above are the King’s Gambit opening, one of the oldest and most storied openings in all of chess. Black typically takes white’s pawn, and then white either plays out his knight or bishop, trying to checkmate black.

Amazingly, chess computers are now strong enough to have determined that, with optimal play, black can force a win 100% of the time based on this opening

 

Image credit: Vasik Rajlich / Chessbase.com.

 

Image credit: Vasik Rajlich / Chessbase.com.

This setup of three computers — with software written by Vasik Rajlich – is used to control a cluster of about 300 cores, which can also tap in to IBM’s POWER 7 cluster, with 2,880 cores. (The same system that IBM’s Watson used when it played Jeopardy!

 

Image credit: Vasik Rajlich / Lukas Cimiotti, via Chessbase.

 

Image credit: Vasik Rajlich / Lukas Cimiotti, via Chessbase. About 50 of the 300 cores on the Cimiotti cluster are shown here.

And after a deep, detailed analysis, all of those massively parallel lines, all of the different combinations of moves — if black plays correctly at every stage — means that white will lose.

In other words, by choosing to play 2. f4 in just the second move of the game, white has made a mistake. In fact, only by playing the following weird bishop move — 3. Be2 — can white even have a chance at a draw in a mistake-free game by black; in all other lines, black can force victory.

 

Image credit: Me, screenshot from gameknot.com.

 

Image credit: Me, screenshot from gameknot.com.

That’s right: chess computers are powerful enough that — given just those first few opening moves — they can solve whether a position is a victory or not for one side. And surprisingly enough, even this early on, a tiny choice like playing the King’s Gambit in the traditional fashion — the way it’s been played for hundreds of years — means that white is lost. You know what’s the most interesting thing about this to me? The moves black must play to win, and “bust” white’s opening, were correctly theorized over 50 years ago by Bobby Fischer, all the way back in 1961!

Pretty amazing when you think about it, and this is a tremendously powerful demonstration that it’s just a matter of time before all of chess is completely solved. It will still be an interesting game for humans, but for computers, it will very likely become just an advanced version of tic-tac-toe (or nuclear war), where no one side can do better than a draw unless the other makes a mistake.

0 comments:

Post a Comment