October 11, 2006
I recently visited the Computer History Museum in nearby San Jose, which has a new exhibit on the history of computer chess. Despite my total lack of interest in chess as a game, computer chess has a special significance in the field of computer science. Chess remains the most visible and public benchmark of the relentless increase in computer speed over the last 50 years.
There are two general strategies available to computer chess programs:
- Brute force search or Type A. All possible positions are examined.
- Strategic AI or Type B. Only good positions are examined.
As it turns out, computers have a hard time with the concept of "good". That's why the history of computer chess is dominated by Type A programs. The most famous Type A chess computer is probably IBM's Deep Blue, which went through a number of incarnations before it defeated a reigning world chess champion in 1997.
I recently built myself a new PC based on the latest Intel Core 2 Duo chip. According to the Fritz Chess Benchmark, my current home PC is capable of evaluating approximately 4.45 million chess positions per second. The figure is actually expressed as 4452 kilonodes per second (kN/s), a common unit of measurement for chess engines.
4.45 million chess positions per second sounds impressive, until you compare that with the Deep Blue timeline:
The fastest desktop PCs are more than 15 years behind Deep Blue in computer chess. Of course, Deep Blue was built using large arrays of custom hardware designed for the sole purpose of playing chess, so it's a little unfair to directly compare it to a general-purpose, commodity CPU.
Chess is an inherently parallelizable problem. The dual and quad-core CPUs on the Fritz Chess benchmark results page almost exactly double the results of single-core CPUs of the same speed. You could certainly string together a bunch of these fast commodity desktops and build your way up to Deep Blue numbers. This fascinating ExtremeTech article on building desktop chess computers indicates it would take 24 dual, dual-core 2.2 GHz Opteron machines to match Deep Blue. Or at least it would have in January 2006 when that article was written. But something more significant than commodity hardware scaling is going on here --Type B chess programs are finally emerging:
Despite its vastly inferior brute force, the Deep Blitz machine could already be a match for Deep Blue because of improvements in chess software. Deep Fritz is able to evaluate lines of play to a similar depth because it successfully narrows its search only to the strongest lines of play.
The data suggest that Deep Blue spent a lot of time evaluating bad moves but overcame this weakness through brute force. In a match between Deep Blue and the Deep Blitz machine running Deep Fritz or Deep Shredder, it seems unclear which machine would win. Obviously, Kasparov did not evaluate 200 million chess positions per second when he defeated Deep Blue in game 1 of the 1997 match, thus the 200 million positions per second number is not a requirement to play chess at the word championship level. It seems likely that Deep Fritz, which is more efficient at filtering out weak moves, is a far more 'intelligent' chess program compared with Deep Blue's software.
The latest computer chess ratings are determined solely by computer vs. computer play. Bram Cohen thinks the derived ratings from computer play are enough to crown the computer chess programs champs over human grandmasters, too:
What's the best tournament chess game of all time? If by 'best' one means 'best played' then I'm afraid the answer is Zappa vs. Fruit. In this most recent world computer tournament, Zappa scored an astounding 10.5 out of 11, a better performance than any human has ever had in a human world championship, and against a stronger field than any human world champion has ever faced. Fruit came in a clear second, so this is the only tournament game we have between the two strongest chess players ever created. Of course, you'll soon be able to buy the commercial version of Zappa and have it play against itself, resulting in a string of games most of which are better than any game ever played between two humans. Welcome to chess in the 21st century.
Some humorous notes: Zappa and Fruit were both written by lone grad students in under two years. Dark horses obliterating the field is a common thing in AI. Zappa's lone draw was ironically against the program which lost every other game in the entire tournament.
Now that computers are clearly better than humans at chess, the question arises, can computers attempt to guess the strength of a game's play based on the moves in that game? And can we use that method to evaluate 'classic' games? Do we really want to?
I think this is a dubious claim, particularly since it's not based on any actual data from computer versus human games. Although Deep Blue did beat Kasparov in 1997, there's ample evidence that Kasparov was the better player and he psyched himself out during the match. All subsequent rematches between human world champions and computer chess programs have resulted in ties-- including two with Kasparov himself in 2003. Statistician Jeff Sonas believes computers will never consistently defeat the best human players:
Computers are becoming more and more dominant against everyone but the top 200 players in the world. That is leading to an overall performance rating for computers that is getting higher and higher. However, the players in the top-200 are holding their ground even against the latest and greatest computers. Perhaps that group will soon shrink down to only the top-100, or the top-50, but not inevitably, and not irreversibly. As you can see from my previous graphics, there is no sign that the top-200 players are losing ground at all against the top computers.
The top 20 humans (the 2700+ crowd) are managing a long string of drawn matches against computers, and the rest of the top-200 is averaging the same 35% to 40% score that they did a few years ago. So, amazing as it may seem, I don't see any evidence that the top computers are suddenly going to take over the chess world. Of course the top computers are improving, mostly through hardware and software upgrades, but somehow the top humans are improving just as fast, in other ways.
We are at a unique point in chess history, an unprecedented state of dynamic balance. The top computers have caught up with the top grandmasters, and right now I'm not convinced that the computers will zoom past the grandmasters. Everything depends on whether computers or grandmasters can improve faster, starting today. It may even be that the top humans can figure out how to improve their own anti-computer play, to the point that they will pull ahead again. Perhaps Garry Kasparov can lead the way once more.
I tend to agree. We may have reached an inflection point. The problem space of chess is so astonishingly large that incremental increases in hardware speed and algorithms are unlikely to result in meaningful gains from here on out.
Computer chess programs may have long ago crushed the rest of us in their inevitable Moore's Law march, but the best 200 chess players in the world are still holding their ground.
Posted by Jeff Atwood
There was a study years ago, based on Bobby Fischer IIRC, that good chess players (and better) use neither Type A or Type B paradigms. They simply have memorized more successful games than their competition. The study found, in particular, that the good players don't "think more moves ahead" than the opponent.
This might be thought of as Type B, but it really isn't. Whether a prolog program could be loaded with the last 100 years of successful games and smoke the grandmasters, I leave as an exercise to the reader.
Cool post! Since the problem is parallelizable, it would be interesting to see a chess applicaation built on top of Google's computer array.
but the best 200 chess players in the world are still holding their ground.
Not for long. I will soon unveil "Deep Haack!" and checkmate them all!
Joking aside, as buggyfunbunny points out, chess is a pattern recognition problem and we know that humans excel at recognizing patterns of other games they've watched, played, or read about.
However, considering that a computer could "remember" every significant game played in history, all it takes is a little bit better pattern matching, and I don't see how humans can keep up.
At some point, it becomes a question of whether or not chess is "solvable". It may well be that keeping up means simply not losing. Kind of like tic-tac-toe, a "solved" game. No matter how good you are at it, if you play someone else reasonably good, you'll never beat them.
"As it turns out, computers have a hard time with the concept of 'good'."
Yo. Quotes page.
While I no longer play chess I do find that benchmark one of the more usable ones around.
Do kind of wonder what my old C-64, from when I did play computer chess, would of rated.
Also with the newer home chess programs do they respond with thier moves quickly or have developers taken the extra CPU speed and used it to make far more time intesive calculations?
For parallel use of home PCs etc it's worth mentioning ChessBrain http://www.chessbrain.net/ , "a virtual chess supercomputer using the processing power of Internet connected machines.
On January 30th 2004 ChessBrain made history by becoming the first distributed network to play a game against a single human opponent."
I think your timeline of Deep Blue development is wrong for 1988. If I'm following the linked page correctly, the value should be 720k not 20k.
A very interesting article, though. Perhaps an idea for a future article is - I wouldn't have gone to check the Deep Blue Timeline link if your table didn't look so glaringly wrong. Sometimes it takes a big error to get us lazy guys to go check the facts!
Onset Computer Corp.
I have been intrigued by the advances of computer AI ever since I was a boy and witnessed the near destruction of planet earth by Dr. Falken's "Joshua" in WarGames. I have watched a few televised computer vs. man events over the years (you want to talk about some riveting television...NOT!)
However, I have always thought and continue to believe that artificial intelligence it going in the wrong direction. The trend seems to be along the lines of greater speed and greater capacity. That is not the solution. For some time now computers have been able to process data (albeit by 1s and 0s) much faster than humans. The storage capacity comparison is open to argument but humans can't match a computer's ability to accurately hold tons of data and retrieve said data line for line.
The problem is the human brain does not work like a computer. The real answer is to replicate the exact way the human brain works with some modifications, etc. Until we pioneer new hardware and a new approach to AI I don't see many advances in the field.
Maybe being in teams made the grandmasters less creative/daring - we've all seen how committees suck the cleverness out of projects.
Jeff, is the Blogger ban a new thing? You're moving up my self-hosting timetable.
I think the most efficient chess AI programming award goes to Atari for making Video Chess for the Atari 2600 with complete, working AI in 4 Kilobytes.
Did you see the movie about that Deep Blue match?
It was amazing! http://www.imdb.com/title/tt0379296/
I think something really went wrong there. Someone from IBM should have stepped to the podium and put this in perpective, instead of beating on Kasparov.
As the quote article says "Kasparov did not evaluate 200 milion positions per seconds", so that means that even if it looses one, he's still better. Deep Blue had no intelligence, only persistance and practically infinit time.
Ken - Hardware is trying to move in this direction. It's just very hard.
"but the best 200 chess players in the world are still holding their ground"
That is questionable. It is true that the world champion vs machine matches (some years back) resulted in draws (Kramnik and Kasparov), recently machines consistently mop the floor with top grandmasters. Remember Adams - Hydra last year? The result was 0.5 - 5.5 for Hydra... And Adams was around 7-8. best player in the world at that time. There was team matches also between a group of machines and top grandmasters. The result was the utter defeat. The best human was the recent world champion (Topalov) but he got still a score below 50%. And the opponents were not supercomputers, one of them was Fritz 9 running on a laptop...
The article by Jeff Sonas was written 3 years ago - an eon on computer chess terms. Have you noticed that very few GMs are prepared to play matches against computers nowadays?
The last significant match was played between GM Michael Adams (then rated number 7 in the world) and Hydra, in mid-2005. Hydra won 5.5 - 0.5.
Computers playing chess seems trivial when compared to Go.
I totally disagree that computers will never be able to consistently beat the best humans in the world. There are only a limited number of possibilities in chess. Its only a matter of time before chess is reduced to something as simple as tic-tac-toe for a computer.
Ah, lovely. Merge Zappa, Fruit, and Deep Blitz inside the Google memory space, have them decide on things by committee, and then watch them take over the government.
I, for one, welcome our chess-obsessed electronic overlords...
What everyone misses in this is that programs don't really play any better than the best humans now - they just don't make the mistakes that a human will always make because he or she is tired, distracted, or suffering a blind spot. Take back all obvious errors (caused by faulty calculation alone) and I can beat a very good program (and I'm not that good!) I lose against programs (and humans) because of blunders not because I can't strategize. In the recent World Championship Topalov missed a two move sequence that would have forced mate! I found the correct moves while I was following the game and program found the moves later in less than a 10th of a second. But in that same game the same program rated his position as very bad before he reached the winning position and while his opponent did blunder to get in the mating position he would have still been at a disadvantage if he had found the move that didn't lose immediately. In other words Topalov saw much more deeply into the position that the program could! But the program would have never missed the simple mate! Maybe brute force will eventually equal hundreds of years of experience - I think it will - but not yet!
The only way to win is not to play the game...
Here's a new match. Deep Fritz against the current world champion, Vladimir Kramnik.
The situation is quite different in the world of computer technology, where time never stands still. Today even an off-the-shelf Core Duo processor can match the speed of the four-processor system on which Fritz was running in 2002. In the current match Kramnik will face a Dual Intel Core 2 Duo 5160 system which allows Deep Fritz – also improved from version seven to version ten – to calculate around eight million positions per second.
Note that 8 million positions/sec is a far cry from the 200 milion that Deep Blue achieved. Of course, Fritz is remarkable for different reasons. It's a piece of commercial chess software on commodity hardware. The average american consumer could easily afford to buy both the software and the hardware. And it's playing the current world chess champion!
In the continuing quest to see if humans can outpace their electronic creations, the humans have lost another, perhaps decisive, round.
A six-game chess match between Vladimir Kramnik of Russia, the world champion, and Deep Fritz, a souped-up version of commercially available chess software made by Chessbase, ended today in victory for the computer, which won the final game and clinched the match, 4 games to 2.
Mr. Kramnik fell behind in the match when he lost Game 2 by walking into a checkmate in one move with hardly any pieces remaining on the board, a mistake that ranks as one of the biggest in championship-level chess history. Needing a win today to tie the match, Mr. Kramnik took some chances, eventually lost a pawn, and was then outmaneuvered by the computer.
i think the new processor is the grapic processor for the chessengine's with cuda or mainstream,
thats the new talk.
greetings Jan Commandeur
I still cannot accept that Deep Blue beat Gary Kasparov. This is why. The terms of the match were that two GMs would "escort" Deep Blue through the first 16 mjoves. Second, the Deep Blue programmers had access to Kasparov's chess history which they used to prepare Deep Blue to play Kasparov. My point is that Deep Blue had been prepared to play Kasparov more so than chess. I wonder what the outcome would have been had Kasparov got snowed in at some airport and some other top class GM had sat in for him. The match would probably have been called off, or so I believe. Kasparov said that when he asked to see sample games from Deep Blue he was flatly refused. These are terms that no one would accept in World Championship play.
As a novice in this field, I have a question about the amount of freedom of choice in the most complex chess-playing programs. If there is a given configuration of pieces on the board, will such a program invariably make the same move? Or might it make different moves, as a human player might, depending on matters such as tendencies toward falling into traps or other characteristics of the opponent that have been observed in prior moves?
Chess itself - with it's (almost) infinite cranial space is a tribute to the human mind. Adrian de Groot saw through the apparent limitations of the human against the awesome capacity of the most powerful a href="http://www.chessbaron.co.uk"chess computer/a.
"[Humans are] able to take actual chess positions and in an astonishing 5 seconds recognize a complex chess configuration and decide on a successful move. How? It seems that [humans] were able to recognize familiar configurations, and associate them with appropriate moves and plans."
I always get somewhat irked when people claim that computers can't do something the human mind can do, because the human mind is itself a computing device. Its based on a very different chemical system, but the brain is still composed of what can be broken down into logic circuits. All of the calculations the brain makes can be made by circuit boards, we just don't know how yet.
Here is a link to a very interesting online chess game in Java. You play against the computer. But, this isn't a typical, boring online game -- this one shows all of the moves that the computer is thinking about while it is doing its thinking. You'd have to see it to know why I think it is so interesting...
"At some point, it becomes a question of whether or not chess is 'solvable'. It may well be that keeping up means simply not losing. Kind of like tic-tac-toe, a "solved" game. No matter how good you are at it, if you play someone else reasonably good, you'll never beat them."
Nope. Combinatorial explosion.
Douglas Hofstadter's comments in _Scientific American_ following the Kasparov-Deep Blue matches (reprinted in his book _Metamagical Themas_) on the philosophical and cognitive-science significance of computer chess are still the last word on the subject.
The verdict that computers are the equal of human beings in chess could hardly be more official, which makes the caviling all the more pathetic. The excuses sometimes take this form: "Yes, but machines don't play chess the way human beings play chess!" Or sometimes this: "What the machines do isn't really playing chess at all." Well, then, what would be really playing chess?
Rybka 3 is the newest killer chess engine. It is vastly stronger than any human at any tournament time control (anything but postal). The strongest human was Kasparov at 2851 ELO. Rybka is at 3200 on a quad 2.4 Ghz machine. An Intel i7 overclocked to 4000 mhz is twice as fast and probably 50 elo stronger. A 400 Elo differential is utterly unsurmountable. The engine is so strong that some of the people who test engines have just been testing opening books rather than different engines because it is 100 elo stronger than any other chess engine. Coupled with the best book it gains yet another 80 Elo over the default book. It is doubtful Kasparov in his prime could win a single game in a 8 game match whole the machine would win 3/4 or so.
The Grandmasters do not even presume to play it in a fair public match. They have played several odds matches. It has won most of those.
to the post about Rybka 3... computer ratings are not in the same rating board as human FIDE ratings.... just to let you know rybka 3 has not won any odds matches with any of the top 100 players... alot of the info stated in your bulletin is false or made up... I do Think eventually computer wll be the better chess players only due to how eventually they will process insane amounnts of nodes and what not but humans have something special computer dont have at this point in time.... MEMORY! in the movie man vrs machine by kasperov he explains his beliefs about computers never being better then humans due to humans memorization of games... But nothing is impossible with the minds of all the great scientists including giving computers memory... well now i hear they have programs that play with the same streangth as SHREDDER, Rybka 3, fruit, ect... but memorizes games played so that the programmers and techs can then after the game make changes... well i think eventually computers will keep improving and probably alot faster then the greatest human minds in chess... in the past 10 years household computers came from 200 megahertz processors with 2 gigabyte hardrives and 64mgb ram to Some alian ware computers that have a 1000 GB hardrives or a TB, 4 sticks of 2gb of ram, and 4 processors of 4GB each...
In 1989 a lucked into beating a chess program. It did something pretty smart - it reversed the board and told me that it had won. I couldn't convince any of my friends that I'd beat the game; it sure didn't look like I had. If you can't win, cheat!
Rybka and Stockfish and others are IMHO winning the debate of whether a "Type A" program is best.
There is a discussion in the www.bookup.com forum called "MyDBSM" which outlines a hybrid approach of solving chess openings. Using brute force to pick the first layer of candidates, analysis by these killer selective program is then used to pick the next layer of candidates.
The topic that shows how Rybka is used to analyze chess opening is called MSbyDM. The "DM" in MSbyDM stands for data mining.
No, I didn't make this up. :)
I agree computers are stronger than most humans, especially in Game 30 like the Kasparov Vs Deep Blue match. In normal controls, such as 45/2, then 25/1, and even longer for championship matches, I think Kasparov's positional ability might have overcome. Moreover, I wonder if the computer would have won if the operators would have accepted obvious draws, instead of making G.K. Sweat it out for many more tedious moves. A human would have agreed to the draw and rested for the next game. Moreover, the programmers/operators operated Deep Blue from a sealed room, so we really don't know what went on in there. Humans can help a computer search out obviously positive lines to greater depth. But back to the draw thing, it's been known since the beginning that computers don't get scared, they don't get tired, and they don't get hangovers. Companies like Novag and Fidelity would enter them in the big, long chess tournaments and through that attrition, their rating was always inflated. My Super V.I.P. was rated 2000, but I doubt it would give a 1750 player much problem in 45/2 if he were fresh. Ultimately, I think type A will be the answer, brute force. In all honesty, strategy and positional play is merely a substitute for perfect tactics, something G.K. refused to see for the longest time, stating "Computers will never have a human's positional ability"...they don't have to.