Fog Creek Software
Discussion Board




machine vs. human chess

Why do people make such a big deal of machine vs. human games of chess?

Athlete's don't run against cars! The results of such a contest would not be considered relevant. I would prove nothing.

So, why is it relevant if a chess computer beats a human chess grandmaster?


Also, I don't understand why the dispute is so emotionally-loaded.

I am sure that the computers will beat the cr#p out of humans at chess.

So what? Why do so many people make so much fuss about this?

Eniac
Thursday, October 09, 2003

I play chess so I do know the limitations of human players when compared to the cold calculating CPU.

However, having said that, I can tell you that chess Grandmasters play according to feel when trying to determine the best stragtegy to employ.

To achieve that strategy, tactics (and hence seeing moves in advance) becomes important. However, in essence, the ability to determine which startegy to employ usually determines the outcome of the game.

The argument is this:
Can a human who has a superbly intuitive feel for chess positions beat a computer which tends to calculate many many more moves ahead?

The best human players have proven that an intuitive feel of the game sometimes (usually?) beats computers.

so I think the analogy comparing chess games to races is a little inaccurate because boundaries of the arguments differ slightly.

That's my humble opinion anyway..

Allan Kenneth Ang
Thursday, October 09, 2003

>I am sure that the computers will beat the cr#p out of
>humans at chess.

I have $100 here that says most grandmasters will beat chess playing computers. I have heard of some IBM machine (deep blue, or something or other blue) that did beat a grandmaster.

I wouldnt say there is much fuss, I havent heard anything recently about these things. I dont know about the current state of the AI research - however a few years back a good chess player would beat a computer.

Emotionally loaded? Are you kidding? The brain is rightfully considered superior to any AI, and being a beaten grandmaster would be a hard blow to your ego, or at least it would be to mine :-)

Patrik
Thursday, October 09, 2003

It was Karpov that was beaten.

Simon Lucy
Thursday, October 09, 2003

> Can a human who has a superbly intuitive feel
> for chess positions beat a computer which
> tends to calculate many many more moves
> ahead?

It may be, for now.

But maybe now the computer calculates and evaluates the merits of a certain amount of moves ahead.

10 years from now, the computer will be able to calculate a lot more moves ahead. Maybe, 10 times, or 100 times more moves ahead than it does now.

This is inevitable.

So, the computer will inevitably get to a point where it will easily crush any human chess grandmaster.

It will get to a point where it will win each and every game against any human grandmaster.


> Emotionally loaded? Are you kidding? The brain
> is rightfully considered superior to any AI, and
> being a beaten grandmaster would be a hard
> blow to your ego, or at least it would be to
> mine :-)

Yes, if you consider chess to be the ultimate benchmark for intelligence.

Very good chess players may be very intelligent people, but intelligence is much more, a lot more, than being good at chess.

Let's say intelligence consists of abilities A, B, C, D, E, F, G.

So, the computer got to be very good at C - playing chess.

But there are still abilities A, B, D, E, F, G - at which the computer has performance inferior to that of a dog, and shows no sign of improving.

So what if the computer is good at C - it only conquered a tiny fraction of what is known as human intelligence.


Do you know what else the computer is good at? Geometry! There have been geometry theorems which humans were unable to prove, but were proven with the help of a very powerful computer.


> I have heard of some IBM machine (deep
> blue, or something or other blue) that did
> beat a grandmaster.

They dismantled Deep Blue. If I was the CEO of IBM, I would have ordered myself the dismanting of Deep Blue.

Why?

Because it was bad publicity for IBM.

Many people think that:

Chess == the ultimate proof and benchmark of intelligence (I consider this statement false). IBM made a computer which beats humans at chess. Evil, evil IBM!!!!

So, it was bad publicity for IBM to keep Deep Blue in working (competing) condition.

I don't want to sound like a conspiracy theorist. I don't think there wasn't any conspiracy.

Just wait 5 to 10 years, and you shall see that chess programs, running not on super-hardware, but on normal hardware (for that time), will beat human grandmasters to the punch at chess.

Eniac
Thursday, October 09, 2003

Kasparov was beaten by the second version of Deep Blue, though many people interpreted this as Kasparov being unable to intimidate his mechanized opponent, and being disturbed by the lack of human element to the game.

Also, the computers use brute force methods and inputted teaching which they never forget, so computers will only get stronger as they get faster and are around for longer.

Domnic Fitzpatrick
Thursday, October 09, 2003


Actually, if you followed the match, Kasparov was denied access to analyze games of Deep Blue while the programmers who run Deep Blue were allowed access to all his games. A little unfair but fair enough, he was rattled.

Anyways, I do play chess with my computer everyday (I try to anyway) and the shortfall of computers is that their assessment of a position is entirely dependent on the programmers skill. I trick my computer sometimes by sacrificing a pawn for an attack. The computer merely assess the pawn as +1 and views the attack as maybe a -0.5. So it sees a +0.5 gain, takes the pawn and gets crushed.

Unless Eniac suggests that one day, computers will become so powerful, that when it's human opponent starts the game with say 1. e4, the computer promptly responds by resigning coz it calculates that it will be checkmated at g8 on move 35 !!

and humans win again :)


my humble opinion, anyways,

Allan Kenneth Ang
Thursday, October 09, 2003

I wonder why my brain wired Kasparov to Karpov?

Simon Lucy
Thursday, October 09, 2003

I think the human-computer chess contest is very interesting.  Apart from my interest in chess and go and corewars and things.

It is really a battle between two different approaches: the whole way that a chess computer goes about playing a game is fundementally different from the way the human player does.  The more we can learn about different approaches, the broader and more useful computer power will become.  And that is a good thing.

I am glad the researchers are making progress using games, and not nuclear reactor programs or something!

i like i
Thursday, October 09, 2003

IBM stock rose after the Deep Blue victory.  However, I'm not sure that was a good example of machine chess.

Kramnik (Kasparov's successor) pointed out that the world champion and the top program were approximately equal.  But with the breakdown of the Soviet Union, human play should be going through some turbulence.  I'd think there is less incentive for former Soviets to play chess all day.

With all the opening knowledge, chess was going through problems anyway.  It's unlikely there would be another Capablanca, who was known for good technique and extreme laziness with memorization.  Opening traps abound to catch novices and many entertaining ideas were already explored by the hypermodernists.  Maybe Fischer Chess, which randomizes the back row, is a good alternative.

In the past, people thought calculation and memorization were signs of intelligence... now we have to adjust to realizing humans are not the last word in evolution.  We can stand to be taken down a couple notches.  A lot of people who don't need to define their worth by dominating their environment, don't care the slightest bit that computers are taking up residence on our intellectual territory.

Tayssir John Gabbour
Thursday, October 09, 2003

Was Kasparov only beaten at speed chess, with a twenty minute limit, anyway?

Mr Jack
Thursday, October 09, 2003

By the way, notice that computer players are still human.  In these cases, humans fashioned solutions to chess, on a more meta and lazy level.

Tayssir John Gabbour
Thursday, October 09, 2003

I think its because chess has always been a symbol of human intelligence.

Some people see themsevles as superior to others because they are so good at chess, so it is a little annoying that computers find chess so easy while they still cannot understand somebody talking.  Even a 5 year old can do that.

Ged Byrne
Thursday, October 09, 2003

Hi folks,

Some misunderstandings in this thread. As a ex-pro (chess hustler), an ex national-level chess master and an amateur
chess programmer (co-author of a program that came 3rd in the World Microcomputer Championships in the mid-1980s), I thought I should give a quick FAQ on this subject before addressing the original questions.

FAQ: How is chess strength measured?

Chess strength is measured using a numerical system invented by Professor Arpad Elo. When you play a game against another player, your rating is adjusted depending on the result of the game and a comparison of your current Elo grade and your opponent's ELO grade. Confusingly, there are 2 Elo systems in widespread use: the International system and the American USCF system. For this FAQ, I will use the International system - you should add about 150 to convert to the USCF system.

FAQ: How strong are the best humans ?

Average club player: 1000-1700
Strong club player: 1700-2000
State-level player: 2000-2200
National master: 2200-2400
International master: 2400-2500
Grandmaster: 2500-2700
World contender: 2700+
Number 10 in the world: 2723 (Peter Leko)
Number 3 in the world: 2766 (Vishy Anand)
Number 2 the world: 2777 (Vladimir Kramnik)
Number 1 in the world: 2830 (Gary Kasparov)

FAQ: How strong are the best commercial chess programs?

Shredder 7.04 256Mb Athlon 1200Mhz: 2810
Shredder 7.00 256Mb Athlon 1200Mhz: 2770
Fritz 8.0 256Mb Athlon 1200Mhz: 2762
Deep Fritz 7.0 256Mb Athlon 1200Mhz: 2761
Fritz 7.0 256Mb Athlon 1200Mhz: 2742

FAQ: Are the ELO scores for computers and humans comparable?

Not directly. The human ELO scores come from human-human games, the computer ELO scores come from computer-computer games (to be precise, 92,970 games played by the SSDF). There are no statistically-relevant ELO scores arising from human-computer games, mainly because there have been so few of them.

FAQ: Is there any other way of comparing humans with computers?

Yes, there are some human-computer matches, but they don't really provide sufficient data. As others here have noted, Kasparov was beaten by Deep Blue, but that was in a very short match using a hardware-based research chess program not available commercially. Quite recently, both Kasparov and Kramnik had drawn matches with the top commercial programs.

FAQ: So what's the "expert" concensus?

The best commercial programs currently rival the top 10 GMs in the world. The window when a human can still beat the best programs is closing rapidly, as Moore's law and advances in tree-searching algorithms are inexorably relegating even the world's best GMs to also-rans. Although there appears to be some flattening in the improvement curve produced by faster hardware, it's now only a matter of single-digit years before the chess computers rule supreme.

And now back to Eniac's original questions:

>> So, why is it relevant if a chess computer beats a human chess grandmaster? Also, I don't understand why the dispute is so emotionally-loaded <<

Chess has traditionally been regarded as a game of intellect. People aren't worried by cars going faster than humans, but they do seem to be worried by computers beating humans in a highly intellectual activity, especially one that carries connotations of mental superiority. Defeat in chess tracks your ego down to its mental lair!

In reality, computers don't play chess in the same way as humans. Humans use experience, deep strategic planning and an immense amount of chess knowledge to examine a few dozen possibilities before playing their next move. Computers, on the other hand, use very clever tree-searching algorithms combined with brute speed and a moderate amount of chess knowledge to examine hundreds of millions of possibilities before playing their next move. 

Think of a computer chess program being like a big dumb shark swimming in a huge ocean. As long as you can find areas of the ocean that avoid the shark, you're okay. But as soon as the shark locks onto you, you're in deep trouble...

So logically, there should be no concerns. Human intellect is still far superior to any machine intellect, even if the two intellects produce roughly the same performance on a single dedicated task. But then, humans have never been that logical...:)

HTH,

Mark
----
Author of "Comprehensive VB .NET Debugging"
http://www.apress.com/book/bookDisplay.html?bID=128

Mark Pearce
Thursday, October 09, 2003

Allan,

>> I trick my computer sometimes by sacrificing a pawn for an attack. The computer merely assess the pawn as +1 and views the attack as maybe a -0.5. So it sees a +0.5 gain, takes the pawn and gets crushed. <<

Don't try this against any of the top commercial programs! They're not nearly so materialistic nowadays. In fact, they often produce spectacular and beautiful material sacrifices of their own, purely for positional benefits.

What program do you use?

Mark

Mark Pearce
Thursday, October 09, 2003

I used to play a lot of chess when I was a kid, but not so much in the last twenty years.

I read somewhere that Kasparov's results vs. computers improved when he realised that you had to play differently against them. Unlike human players, they don't form strategic plans, though they react very accurately when you start making threats of any kind. So it may be best to try to let them drift into small losses of position, which can eventually be converted into say, a pawn advantage. Then repeat as necessary. This must have been very difficult for someone as aggressive in their playing style as Kasparov!

Actually, this strategy works quite well against human players too. The only time I won a (junior) tournament as a teenager was when I decided to play less aggressively and instead wait for my opponents to blunder. Sure enough, they did! But too boring for my taste...

I think the programmers should leave chess alone for a while and go to work on Go instead. The best chess computers are really good players now, as Mark says. Whereas no computer can play Go worth a damn, AFAIK.

Dave Hallett
Thursday, October 09, 2003

It's a good thing Mark has come along to breathe some knowledge into the discussion. It always amazes me how seemingly technical types are quite prepared to sound off about something they know little about.

Machines are now capable of beating all but the very best in the world; this is more the effect of developments in hardware than of developments in computing.

To understand the importance attached to the matter you need to know a little of trhe history of machines playing chess and AI. It was soon realized in the early 60's, that chess was an intellectual field where a computer could measure up to humans, and more importantly, it would need to "think" in a human sort of way in order to be able to do so.

It is worht remembering that the number of possible chess games has been calculated as being around 10 to the power of 120, whereas the probable number of atoms in the universe was calculated in the 1960's as 10 to the power of 106. So working out all possible games, as had been done with noughts and crosses and was to be done with draughts was not an option.

Teaching the computer to play chess was one of the main aims of artificial intelligence for a considerable period, and both Russians and Americans put a great deal of work into it (there was a famous match at the end of the 1960's between a Russian and an American machine in which the losing machine missed a mate in three because after two and a half moves - which was the most it had time to calculate for - it was material down). Indeed, Bottwinik, who was a trained engineer as well as the World Champion form 1948 to 1963, spent much of the 1960's co-operating in the Russian research.

Problems of course soon became apparent; the better the chess player the less possible alternatives he considers, but the mechanism by which the expert dismisses 95% of the alternatives at each juncture defied attempts to break it down into binary or any other terms. So when the Scottish Champion, David Levy, a researcher into artificial intellgence and a mediocre International Master, was discussing the matter with a layman, Jim Slater I believe, he was quite prepared to wager a thousnad pounds - no mean sum in 1971 - that there would be no computer program capable of beating him in ten years time. In 1981 Slater paid up without bothering to call for the match.

In the 90's however things changed, and the main reason for that was the increased speed of hardware that let machines go back to the 60's plan of analyzing every possible variation for a limited number of moves, and become successful. As I said in an earlier post in 1992 I could annihlate a commerical program running on a x386 simply by throwing a few pawns at it. By 1996 I was struggling against the cheapo ChessMaster series on a Pentium 133 and only succeeding because it had not been programmed to pay enough attention to flank attacks. Since then, I've not even bothered - I don't run after buses any more either!

There has been considerable improvement in the programming of computers; their positional knowledge is vaslty superior to what it was a few years back, but basically brute force is how they have won, even if it is aided by some human ingenuity.

The general feeling is a little bit of a letdown, since it was hoped that a chess playing computer would give us some insight into human thought processes, and it hasn't. Think of a competition between a mountain goat and a moto-corss bike. The mountian goat will always get up the mountain first even though it is seriously underpowered, but eventually somebody manufactures a moto-cross bike that simply uses a laser to zap all obstacles in its way and power up the slope. The race is over but nobody is really satisfied.

Stephen Jones
Thursday, October 09, 2003

Heh.

"Yeah, computers can win at chess. But only by counting cards."

Philo

Philo
Thursday, October 09, 2003

I think the IBM Deep Blue was a brilliant return on investment for the marketing department at IBM. IBM can win at chess, IBM can build computers that are better at a skill than the best this planet has to offer. Look at all the press, the PBS specials, the magazine articles. Cheap advertising compared to the cost of this project for IBM.

m
Thursday, October 09, 2003

Stephen,

>> The mountian goat will always get up the mountain first even though it is seriously underpowered, but eventually somebody manufactures a moto-cross bike that simply uses a laser to zap all obstacles in its way and power up the slope. The race is over but nobody is really satisfied. <<

Yes - excellent analogy.

Mark

Mark Pearce
Thursday, October 09, 2003

I think the game of chess may eventually be 'solved' (ruined) if research in quantum computers comes to fruition. That kind of indignity would never impinge on soccer.

Knowledge Maker
Thursday, October 09, 2003

I'm coming in late to the discussion, but I read Eniac's comment:
"Many people think that:

Chess == the ultimate proof and benchmark of intelligence (I consider this statement false). IBM made a computer which beats humans at chess. Evil, evil IBM!!!!

So, it was bad publicity for IBM to keep Deep Blue in working (competing) condition."

...and I can add a footnote to that ( though I don't think it was true for Deep Blue's situation in modern times! )

In the late '60s and early '70s I ran chess tournaments in the Washington area and a programmer for IBM, Hans Berliner, the World Correspondence Champion, had written a chess-playing program and wanted to use it as a demo in one of my tournaments.  He arranged for a drop to a teletype, got media coverage, etc.  At the last minute the connection was unavailable and the human-computer play never took place.  Why?  We found out much later that the idea had been nixed by IBM execs at a high level because they were afraid that the computer might WIN!  This would reinforce the negative stereotype of computers taking over the world, instead of being the gentle office assisstants that IBM's ads were portraying!

Barry Sperling
Thursday, October 09, 2003

"I think the game of chess may eventually be 'solved' (ruined) if research in quantum computers comes to fruition. That kind of indignity would never impinge on soccer. "

Oh Yeah...

Check out RoboCup - Sony Aibo robot dogs playing soccer.

http://www.rurnt.com/brian/archives/technology/000060.html

DJ
Thursday, October 09, 2003


Well, at least it's still humans making the chess computers.

I'll be really worried when the best human made chess computers are routinely beaten by the best computer made chess computers...

Bill Tomlinson
Thursday, October 09, 2003

Barry - LOL!
Like a headline of "computer beats chess champion" would do any more damage than Demon Seed or Forbin...

Philo

Philo
Thursday, October 09, 2003

Stephen, your unkind comments aside, what makes you think we have learned nothing from chess AIs?  You mention that humans learn to prune away obviously bad moves.  In what way is this different from alpha-beta pruning?  And do you think our pruning heuristics always serve us well, as in the computer game Kasparov resigned when there was an clear draw on the board?

You also assume that chess is an appropriate environment to analyze human intelligence.  However, Kasparov is well-known for using intimidation.  In his championship game with Short, Short's coach Boris Gulko often complained that Short made obvious mistakes because of Kasparov's presence; one tactic he uses is to push a piece down with a screwing motion on strong moves, and occasionally he does this in flawed positions to trick opponents.  Against a computer unrattled by his presence, Kasparov's Elo should be docked a couple hundred points.

If you want to learn how humans think about chess, go search for Mark Dvoretsky.  Or study biology.  Computers are models, and you can choose never to be pleased by a model.

You mention that computers win by brute force.  That could be taken to mean that computers have only started to be decent.  Come on, only recently have they been able to run some of our /programming languages/ decently, much less programs.  To top it off, the Soviets were a decade behind the US with computer hardware.  In the '60s, that means they were running around with machines weaker than pocket calculators.  Their algorithms and chess R&D were impressive, but these only go so far.

We've been playing chess for centuries because we don't actually do it well.  If we did it well, chess would be about as interesting as walking to the post office.  So it's not a surprise that computer can hand our asses to us.  Hell, I'm still impressed when someone memorizes 500 digits of pi.

Tayssir John Gabbour
Thursday, October 09, 2003

So Kasparov can be intimidating to play. Petrosian used to annoy his opponents by stirring his drinks loudly while they were thinking, then turning off his hearing aid if they tried to retaliate. And the things Fischer got up to would fill an entire book (and probably have).

Isn't the fact that you're playing a computer that you *know* is analysing all the possible moves to n-ply deep, and therefore is not going to just overlook something, also rather intimidating? Maybe Kasparov was spooked just as Short was. Let's knock 200 ELO point off all the great players, just for having the reputation of being good...

Dave Hallett
Friday, October 10, 2003

I have no idea what you mean by alpha-beta pruning., but I am not at all sure that good chess players do any active discounting - it's much more that the two or three lines thay will look at "stand out". Whatever the procedure is, no chess playing program has got anywhere near understaniding it, and the way a chess program analyzes moves is completely different from the way a competent human does.

I fail completely to understand your point about intimidation, or "sledging" as it is known in cricket. You're not seriously suggesting that Kasporov wins because he bangs the pieces down are you? Seems like you've been reading too many tabloid articles.

Stephen Jones
Friday, October 10, 2003

Tayssir,

>> You mention that humans learn to prune away obviously bad moves.  In what way is this different from alpha-beta pruning? <<

Humans learn to prune certain moves without any analysis of those moves. It's a pattern recognition process that runs subconsciously and without explicit calculations.

Alpha-beta pruning, on the other hand, is a deterministic process that involves analysis of  the search tree followed by pruning of parts of the search tree where you can calculate mathematically that it's not worth searching. 

So the former process is pure intuition while the latter process is pure calculation. They're completely different.

Note however that certain search techniques such as razoring and its variants do perform some speculative tree pruning.  These techniques bear some very slight resemblance to the way that humans prune moves.

>> And do you think our pruning heuristics always serve us well, as in the computer game Kasparov resigned when there was an clear draw on the board? <<

Well, alpha-beta also exhibits pathological behaviour in some relatively rare situations. With machines and with humans, our search algorithms don't work in every situation.

Mark

Mark Pearce
Friday, October 10, 2003

Dave, I have no disagreement since your point is that chessplayers use psychological tactics to weaken opponents' play.  BTW, I only mentioned the Kasparov-Short game because the controversy was very publicized so no one could say my evidence was bad.  (Well, someone still did.)  In fact, I mentioned I didn't think the original Deep Blue game Kasparov lost was worth much.

Stephen, what are these chess tabloids you claim I read?  I'm pretty impressed anyone could make money selling tabloids about chess; I guess you can make money off anything.

Another point you oversimplify (but I didn't mention) is that AI people care about providing insights into human behavior.  Check out the intro to Russell/Norvig's _Artificial Intelligence: A Modern Approach_.  They present a matrix of a few approaches taken by AI people; some want to make machines that think like humans, like cognitive scientists.  Others might take the position that humans are just optimized for a environment and are far from perfect, and they care more for the general notion of rationality.  (Were Neanderthals and some aquatic species smarter than us?) 

So you probably don't want to label people as having an agenda.  Some players don't give a damn about how some guy plays chess, but instead they love the beauty of the game itself, no matter who plays.

And it's not like players think alike either.  What most players have in common though is a desire to win games, and perhaps win beautifully.  Computers can teach us lessons, if we're not so wrapped in our human ego.

If a computer could make beautiful music, would you care if it didn't teach us anything about how someone dreamt up Britney Spears' lyrics?

Tayssir John Gabbour
Friday, October 10, 2003

Mark, is alpha-beta so different from human pruning?  It sounds like a very fundamental thing humans do; if we already calculated a decent line and are checking out some new ones, and the opponent has a really good countermove in a new line, we prune it.  I'm tempted to defer to you since you actually implemented this, but our disagreement (as I understand it) has more to do with human cognition -- I don't think everything is completely intuitive with humans.  Humans also calculate.

Basically, game theory was influenced by human behavior, so computers will actually be a little like humans.  After all, von Neumann did study neuroscience a bit carefully (see his _The Computer and the Brain_) and there may be a point where human brains are simulating similar algorithms that computers also imitate.  He wrote, "When we talk mathematics, we may be discussing a secondary language, built on the primary language truly used by the central nervous system."  Maybe cognitive scientists have answered this question, but if they haven't, what is wrong with a computer simulating the language that humans simulate?  Won't we occasionally have some strategies in common; other times differ?  Don't good human players also differ on how they approach chess, like night and day?  Reti didn't play like Capablanca in most situations, for example.

BTW, I looked at my Kasparov-Short example; I realize now it sounds flimsy.  There are much better examples, even with Kasparov, but I just sorta spit something out because I was annoyed by Stephen's condescension.  Whatever, I'm human too. ;)  And like chessplayers, I wish I had more time to give to these ideas.

Tayssir John Gabbour
Friday, October 10, 2003

1. Chess is considered a measure of intelligence, as people have mentioned. Cars don't have wills of their own, but the fear is, computers will become decision makers, and I'm sure in my instances, they are. Even in cars now, a computer determines which wheels move while which don't (ever see those commercials "transferring powers from the wheels that slip to the wheels that grip"). Our fear is that one day a cold, hard, machine will make decisions for us, who will keep their job and who will not, who will live and who will die.

2. Deep Blue has a database of every chess game ever played. From what I've read, in Chess there is a point where if you're in a certain position, by playing certain moves you can gaurantee victory. Once you get to a certain point, Deep Blue will pull from one of its thousands (millions?) of games and flawlessly execute a known path to Checkmate.

Until this point, the basic strategy is to try every possible move on yours and your opponents parts and see which moves will be best, 1, 2, 3, n moves later. The farther you can see, the better. Computers do this by brute force. I'm sure Deep Blue, which in it's original incarnation had circuits specially designed for it, but I believe recently ran on a run-of-the-mill super computer that anyone could build with enough parts, has a more specific  way of working. Most likely by somehow weighting different kinds of moves, and thus reducing the search tree. I.e. Kasparov wouldn't likely execute these moves, so I don't have to search down those trees of possibilities, and can thus search that many more moves deeper.

3. Yep, Kasparov wasn't allowed to study Deep Blue's games, while Deep Blue could study every single one of Kasparov's games. I'd followed this for a little while around when each game happened, but if there was no news about it, I didn't go seeking it out. Perhaps IBM's dismantling of Deep Blue has more to do with the fact that it actualy won, than with bad publicity. In fact, their dismantling it IS news, and therefore IS publicity.

http://www.research.ibm.com/deepblue/

"In May 1997, IBM's Deep Blue Supercomputer played a fascinating match with the reigning World Chess Champion, Garry Kasparov. The event was captured live only on this Web site, where millions of chess and computing fans tuned in to witness the event in real-time. This Web site is an archive of that event, and information on this site has not been updated since the end of the match. Some content may no longer be relevant or up to date, and some links may not function. In particular, the audio and video clips are no longer available. Current information about IBM deep computing can be found at the IBM Research home page."

www.MarkTAW.com
Saturday, October 11, 2003

----"2. Deep Blue has a database of every chess game ever played."----

Err, no! It has a database of every game it's programmers have been able to get hold of, which is a different matter.

----"From what I've read, in Chess there is a point where if you're in a certain position, by playing certain moves you can gaurantee victory.----"

Plenty of them actually. Humans normally resign when they're on the losing side of one of them (and occasionally get if wrong as Kasparov proved in the match against Deep Blue).

---"Yep, Kasparov wasn't allowed to study Deep Blue's games, while Deep Blue could study every single one of Kasparov's games."----

I suspect Kasparov would have won easliy if he had been allowed to study the games. When you find out what mistakes a computer is prone to make, then you can lead it into those kind of positions again and again. It will continue making the same kinds of mistakes until its programmers have worked out how to change the algorithms. As I mentioned before I could always beat the Chessmaster program by attacking on the flank - it wasn't programmed to give enough weight to the danger there.

---"Most likely by somehow weighting different kinds of moves, and thus reducing the search tree. I.e. Kasparov wouldn't likely execute these moves, so I don't have to search down those trees of possibilities, and can thus search that many more moves deeper."----

Ay, there's the rub; computers are simply not good enough at doing this; they can reduce the search tree somewhat - originally they simply searched for n moves but for a long time now they have learnt to stop when a position is obviously either lost or won --- but they are way off being able to make that initial triage.

Stephen Jones
Saturday, October 11, 2003

> Err, no! It has a database of every game it's programmers have been able to get hold of, which is a different matter. <

Obviously, they don't have their hands on the game I recently played via Yahoo messenger, or the ones I played as a kid. Besides, there's probably nothing of value in those games anyway.

> I suspect Kasparov would have won easliy if he had been allowed to study the games. <

Perhaps. It seems we'll never know.

> Ay, there's the rub; computers are simply not good enough at doing this; they can reduce the search tree somewhat - originally they simply searched for n moves but for a long time now they have learnt to stop when a position is obviously either lost or won --- but they are way off being able to make that initial triage. <

So what advantage was gained by the computer "studying" Kasparov's games?

www.MarkTAW.com
Sunday, October 12, 2003

Tayssir,

First, I agree with your general point that we've learned a great deal about human thought processes, and to a lesser degree about AI, by creating such strong chess programs. But perhaps a comparison of techniques will explain some of the differences.

1) The vast majority of chess programs use alpha-beta pruning as one of their tree search algorithms. Alpha-beta pruning is guaranteed to produce the best answer in a time of X. Humans also use a similar technique: when they have analysed part of the search tree, they calculate that certain other parts of the tree don't need to be searched because those parts can't produce a position as good as the best position evaluated so far.

2) Many programs use some form of speculative tree pruning - these techniques generally produce a good answer (not always the best answer) in a time of less than X. Humans also use a similar technique - in fact, this is very common among humans.

3) Humans use pattern recognition to filter a large amount of possibilities without even considering them. Typically, they will examine only 2 or 3 out of 30 possible moves in a position. Chess programs have no similar algorithm. We don't really understand how humans do this, and we have even less understanding of how to translate this into a form that a machine can handle.

Mark

Mark Pearce
Sunday, October 12, 2003

Stephen,

>> Ay, there's the rub; computers are simply not good enough at doing this; they can reduce the search tree somewhat - originally they simply searched for n moves but for a long time now they have learnt to stop when a position is obviously either lost or won --- but they are way off being able to make that initial triage. <<

This is no longer true, in fact hasn't been true since at least the advent of Deep Blue which introduced the technique of singular extensions.

Nowadays most of the best programs use very strong forward (speculative) tree pruning techniques such as singular extensions and null-move searching.

It's hard to separate the contribution of improved hardware speed and improved search algorithms to the arrival of computer-based chess GMs. But the improved search algorithms have made a significant contribution.

Mark

Mark Pearce
Sunday, October 12, 2003

For a good introduction to chess programming: http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html

For those interested in the theory behind chess search tree algorithms:
http://www.chessbrain.net/beowulf/theory.html

For some more advanced stuff about chess programming: http://www.gamedev.net/reference/programming/features/chess5/page4.asp

HTH,

Mark

Mark Pearce
Sunday, October 12, 2003

I think you have misunderstood me, or possibly I explained myself badly talking about the "initial triage", but your comments

---"Humans use pattern recognition to filter a large amount of possibilities without even considering them. Typically, they will examine only 2 or 3 out of 30 possible moves in a position. Chess programs have no similar algorithm. We don't really understand how humans do this, and we have even less understanding of how to translate this into a form that a machine can handle."----

describe exactly what I was referring to.

Stephen Jones
Sunday, October 12, 2003

I do agree we use pattern recognition, especially with Go.  Similar problems come up elsewhere -- soap bubbles can easily solve problems that computers take a long time on.

There exist machines that perform better algorithmically than von Neumann machines.  Hillis' _The Connection Machine_ talked about one.  We're using the wrong machines.

That's especially why the brute force critique is shaky.  In 10 years, people will get hernias laughing that we believed our computers used "brute force."  Computers haven't had millenia to evolve.

Depending on your definition of computer.

Tayssir John Gabbour
Sunday, October 12, 2003

I find it more impressive that the best human players can still hold off and even defeat a supercomputer in chess, than the chess computers being able to occasionally beat the best humans.

Even with alpha-beta pruning, the chess computers still actually evaluate hundreds of millions of possible positions before making a move, while the human players only consciously consider a handful of positions.  That the human brain can somehow accomplish the equivalent result of evaluating hundreds of millions of positions without having to think about them is quite interesting.

T. Norman
Sunday, October 12, 2003

The big advantage for the computer program is that it can process thousands of possible moves in just seconds. Chess is a time controlled game. Whereas you, if you are
good, will only have time to evaluate a few workable moves.
Friendship and communication are no longer important. The movers and shakers don't waste valuable time with social
intercourse.
So, it has to some extent, become an obstacle. Chess is a sport. Why?  The object is to win. Win the game over a human or an electronic program is all that matters.
Therefore, playing a tournament size board with large weighted Nathan Cook (Staunton) pieces is all you are interested in. It doesn't matter if man is no longer able to
beat computers. Nobody is going to change progress.

Don Steiner
Friday, April 23, 2004

*  Recent Topics

*  Fog Creek Home