Kasparov Wins Game 3 Against X3D Fritz

Vulcao writes "Garry Kasparov just brilliantly won game 3 in the Kasparov vs. X3D Fritz chess match, which pits man against machine. Kasparov created a positional advantage on the queen side with a very strong pawn structure to which Fritz didn't have an answer. The result is now 1.5 - 1.5, and the last game will be this Tuesday, Nov. 18."

Comments

The game of Go ?

[Thinkit3]

The ancient game of Go could be played in a virtual environment too. At 13h (nineteen) square, it would be a bit bigger. But there are only three states for each square--black, white, or empty. Go is mentioned in every slashdot article on chess, but that is only because it is in many ways more elegant than chess. And even with quantum computing, Go computers won't be beating humans anytime soon.

Re:The game of Go ?

[Space Coyote]

I always wonder how long it takes in any chess thread before someone who thinks they've discovered the lost city of gold pipes up about go. And the answers they get are always the same, it's a totally different problem. We haven't built a robot to play tennis either, tennis is simply a different problem with a much much larger data set, just like go. A chess game with a 19x19 board would send a computer into shock too.

Re:The game of Go ?

[Pakaran2]

Correct me if I'm wrong - but isn't Go proven to be EXPSPACE-Complete?

Meaning that no computer anywhere is going to be decent at beating a human on a relatively large board?

Re:The game of Go ?

[cornick]

I just got back from the 15th Mid-Atlantic GO championship about 30 minutes ago where we discussed this. (Images on my site). Apparently the largest GO board that's 'solved' is 5x5. One could imagine building a quantum computer that could solve a larger board using 3 state q-bits (q-trits?) -1 = black stone, 0 = empty, 1 = white stone. Then a simple 361 'q-trit' system could represent a 19x19 board. (And be in a superposition of all states at once). Just a thought, though the quantum computing guys I work with would probably have a fit about what I just said.

Re:The game of Go ?

[nodwick]

I think it's a knee-jerk reflex against an inferiority complex. I mean, sure, they can beat us at chess, but what about GO?

Kinda like how your average Slashdotter watching the crowd go wild over Barry Bonds breaking the home run record is secretly thinking, "Oh sure, but can he put together a Beowulf cluster of Linux boxes?"

Re:The game of Go ?

[tniemueller]

This gives a nice introduction to Go and AI and why it is so hard to play for a computer.

Re:The game of Go ?

[Lars T.]

And even with quantum computing, Go computers won't be beating humans anytime soon.

Especially with quantum computing, Go computers won't be beating humans anytime soon.

Re:The game of Go ?

[wfberg]

We haven't built a robot to play tennis either, tennis is simply a different problem with a much much larger data set, just like go.

A simple wall-shaped opponent pressed right against the net, with a large enough surface area, will beat any opponent. Well, maybe with a hole in there for serving.

A chess game with a 19x19 board would send a computer into shock too.

Less so than Go, since with Go the number of possible moves at each junction in time is larger than in chess - Go on a chess-sized board still features a larger search space than chess. Just like 110 in binary is less than 110 in decimal.

Re:The game of Go ?

[ReyTFox]

Sensei's Library is an excellent starting place - it's a wiki filled with information and examples. And if you can't follow up on what I posted through Google, this is a good place to look too.

Playing the game is most necessary - computer programs(GNUGo and Igowin are both worth checking out) can challenge any new player these days, but humans will usually be more helpful to learn from because they play less predictably and if they're polite will review the game with you afterwards to help point out mistakes.

If you can join a local club, do so. While you can get an online game almost any time of day, it's far better to play with a real board and stones and people you can see.

Once you have a few months of experience you should be able to understand what's going on in a lot of higher-level games. They are excellent to learn from.

Re:The game of Go ?

[Anonymous Coward]

A simple wall-shaped opponent pressed right against the net, with a large enough surface area, will beat any opponent.

Actually, no it won't, because it would still have to use a regulation-sized tennis raquet. If it couldn't move the racquet to hit the ball fast enough, it would actually lose all the points, since a tennis player loses the point if the ball strikes any part of their "body".

Re:The game of Go ?

[ottothecow]

I would think that if you were playing against a wall shaped oponent, it would be reletively easy to make them hit the ball out to the side or off the edge of the court. Only a moron would lose

Re:The game of Go ?

[sholden]

A simple wall-shaped opponent pressed right against the net, with a large enough surface area, will beat any opponent.

And building a chess program to beat any opponent is pretty simple, by making all the computers pieces queen king mixtures, so they move like queens but the computer only loses if *all* its remaining pieces are in checkmate at once.

But it's generally only interesting when you restrict the computer to actually following the rules of the game.

Re:The game of Go ?

[Anonymous Coward]

It's a sad world when one has an inferiority complex against a database.

Re:The game of Go ?

[terrab0t]

Okay, so to summarize the first page of that, if I don't want to be humiliated by a machine, I should challenge it to a game of go.

Honestly, a friend of mine heard about Deep Blue and wondered why there haven't been attempts to make the perfect machine player at other games and sports. Like wrestling. I bet you could make a machine that would destroy any wrestler stupid enough to tackle it.

My favorite was the ultimate bowling machine. We actually designed this while sitting in the car talking. You take a ramp, put the ball at the top and line it up so that it points just left of the center pin, and you've got a world champion! Go machines!

Re:The game of Go ?

[syle]

"The depressing thing about tennis is that no matter how much I play, I'll never be as good a a wall. I played a wall once. They're fucking relentless...." --Mitch Hedberg

Re:The game of Go ?

[JamesKPolk]

Ladders, one tactical aspect of go, have been proven to be PSPACE-complete. http://homepages.cwi.nl/~tromp/lad.ps

For those who wish to bet...

[r_glen]

Sorry Gary, my money's on the computer

I disagree...

[zeux]

...with people saying that if the computer wins over the human it means that "That's it, here we are, computers are more intelligent than man".

Computer chess games deal with statistics and historics of previous games to decide how they will move their next turn. Usually they analyze hundreds of thousand of differents moves, even dumb ones !

When a human player take a look at the chess board, he rejects the vast majority of the possible moves and concentrate only on very few of them.

I would call that efficiency and if computers where as efficient as human, they would win easily without requiring huge processing power.

Re:I disagree...

[yerricde]

When a human player take a look at the chess board, he rejects the vast majority of the possible moves and concentrate only on very few of them.

This is called pruning the search tree. Computer chess players do this too; see a description of alpha-beta pruning.

Re:I disagree...

[GauteL]

"...with people saying that if the computer wins over the human it means that "That's it, here we are, computers are more intelligent than man"."

Well, that is just a stupid thing to say anyway. If a computer consistently beats humans in chess, the only thing that has proved is that it is better than humans in chess.

Chess, is not as some people seem to believe, the absolute sign of intelligence.

Re:I disagree...

[Pakaran2]

Well, the thing is a chess computer can ONLY play chess - a human with the same degree of intelligence can do many other things. Kasparov could have become a doctor, a lawyer, a programmer, or a Go player. Or he could have developed a different aspect of his intelligence and been a poet.

I think computers need true intelligence before they're equal to humans, no matter how well they play one classic board game.

Re:I disagree...

[nodwick]

I agree that just because a computer can beat a human at chess, that's not a basis for saying that they're "more intelligent" than us. Intelligence incorporates things like creativity, self-improvement, etc. which are not demonstrated by a chess program.

Having said that, I have to disagree with some of the points in your post.

Computer chess games deal with statistics and historics of previous games to decide how they will move their next turn.

How is this different from human players? Most good chess players I know spend a large portion of their time studying historical games from the grandmasters, just like chess programs do. They even call the procedure of optimizing the program parameters "training".

Usually they [computers] analyze hundreds of thousand of differents moves, even dumb ones ! When a human player take a look at the chess board, he rejects the vast majority of the possible moves and concentrate only on very few of them.

I'll assume you mean that they analyze hundreds of thousands of move sequences, since you can only control at most 16 pieces and the number of moves you could make are much fewer than a hundred thousand. Computer chess programs actually proceed in a very similar fashion to human players - they consider the moves that could be made and discard the least promising ones. For moves whose "scores" are very close, it will look ahead more moves, always pruning the sequences which lead to poorly scored outcomes. They don't continue to analyze sequences which "score" poorly and hence are unlikely to yield a winning result.

The fact is that chess programs have become very good at homing in on promising move sequences and pruning out poor ones. That, combined with the relatively small set of moves on a chessboard, has led chess programs to make great gains over the past few decades. Your argument would be more applicable for Go (had to toss that in there somewhere!), where programmers still don't have a good understanding of how to "score" positions, and hence computers have performed poorly for precisely the reasons you mention: that they are unable to prune out the bad moves and focus on the good ones.

Re:I disagree...

[Comatose51]

Let me rephrase what McDermott said many years ago when people brought up the same argument. If a computer can beat us by calculating all the moves, so what?

Just because an airplane does not flap its wings to fly like a bird does, is it really not flying? On the contrary, airplanes are better fliers than birds.

AI isn't about emulating humans but about matching humans in mental capacity. How it will accomplish that is up to the researchers.

Re:I disagree...

[hawkestein]

Chess, is not as some people seem to believe, the absolute sign of intelligence.

Well, it used to be, back before people really thought about how to build a chess program. One of the problems with AI is that we don't really know what "intelligence" is. Every time we are able to write a computer program to solve a problem that we thought required intelligence, we conclude, "Oh, then that can't be what we meant by intelligence" rather than "The computer has now achieved intelligence."

Re:I disagree...

[venicebeach]

Yeah, it's funny that when the human wins it is seen a victory for humanity. It could just as easily be seen as a loss for humanity, since the humans weren't able to build a computer that could beat a person at chess!

Re:I disagree...

[Chess_the_cat]

I play a lot of chess and I can tell you I've never once in my life 'pruned a search tree.' Humans just don't play that way. When a human rejects the vast majority of possible moves he's not even considering them. Pruning a search tree--what a computer is doing--entails actually exploring each move on the tree as far as it can. Then it assigns it a numerical value and orders the moves. Humans, on the other hand, have the ability to instantly spot whether a move is worth exploring or not. Whereas I would be able to eliminate a move like moving my knight back to its original square within the first three moves, a computer would actually have to examine the tree that a move like that would generate (barring an opening book which in my opinion is not an example of chess playing at all.) At any rate, programmers love to think that since a computer does something one way, and computers are 'electronic brains' then the human mind must work the same way. Newsflash: brains are not digital computers.

Re:I disagree...

[cca93014]

After studying AI and Cognitive Science at University, the best definition of Intelligence that I heard was:

"Only intelligent beings can make stupid decisions"

It kind of encapsulates the problem with AI really nicely; whenever you try and define it, all you are really doing is pushing the definition requirement into another area.

People have been arguing this since Plato, and IMHO have not made much headway since. If anything computer models have only confused the issue. Until this problem is solved, you cant create AI? How can you create something that you cannot adequately define?

Having said that, neural networks and emergent behaviours are cool ;)

Re:I disagree...

[be-fan]

Its not so much a matter of computers doing things one way and humans doing things another way, but a matter of both being bound to the rules of computational theory. There is a large solution space, and both humans and computers have to decide what parts of the solution space to search and what parts to ignore. They have to do this, even if they do not do this in the same way. That's all that pruning the search space really means.

Now, just because you don't do it conciously doesn't mean you don't do it. Your brain does an incredible amount of processing behind your back. Think about visual processing or auditory processing. All of that goes on completely outside of your concious thought.

Re:I disagree...

[KD5YPT]

Actually I would disagree against the statement that human and computer are doing essentially the same thing. For one, computer will actually simulate every possible move to ensure there will be no mistaks. Human mind, on the other hand, once they have a general strategy in mind, they only focus on critical pieces. This is also the part where human make mistakes, since mentally, a human cannot possibly anticipate every possible move and prune it. Consciously or sub-consciously.

Re:I disagree...

[spazzm]

"Humans just don't play that way. When a human rejects the vast majority of possible moves he's not even considering them."

What you counsciously think your brain is doing and what your brain subconsciously is actually doing might be two different things, you know.

Re:I disagree...

[iabervon]

A computer will be intelligent when it is capable of learning things which are entirely new, by applying its knowledge, trying things, general reasoning, and developing new representations. Chess is fine, go is fine, but I'll be impressed when a chess program goes on the internet and learns to play go.

There have been a series of problems that people have posed with the idea that they couldn't be solved without giving the program the ability to figure out the problem. Each time, however, people figure out how to solve the problem without giving the computer general intelligence. But the problems weren't definitions of intelligence ("Intelligence is what is necessary to play chess"), but rather people thought (incorrectly) that the problems couldn't be solved without intelligence.

On the other hand, there is a cluster of problems which have not been solved, despite many attempts, which are not intended to be difficult (which can be overcome eventually with clever coding and fast hardware), but rather which explicitly require undirected learning and the ability to generalize to new applications.

Of course, many of the problems originally posed as measures of intelligence were, in fact, problems that people wanted solutions to, because they were difficult for people. So the effort put into solving these problems without trying to use general intelligence is actually worthwhile.

Re:I disagree...

[Bi()hazard]

When humans play they rely primarily on pattern matching rather than searching a tree (unless they suck). Computers tend to be very poor at pattern matching, and humans tend to be extremely good-that's why a small child can look at photographs and categorize them instantly, but the most advanced computers have great difficulty with that kind of task.

Most skilled human chess players apply pattern matching by looking at the board and identifying interesting things. They start with nothing and add new options to the list until they feel they have a sufficiently comprehensive understanding of the situation.

Search tree pruning, by contrast, starts by including the entire space of potential moves and identifying courses of action that can be eliminated. Alpha-beta pruning is a particularly poor example here since it has the useful property that all a-b pruned subtrees are guaranteed not to be optimal. However, humans often ignore superior courses of action and choose suboptimal ones that "feel right" or match prior experience.

There have been various experiments on the limits of raw pattern matching ability with chess pieces. An interesting one involved asking participants to memorize an arrangement of pieces and reconstruct it a minute after the arrangement is removed. Participants included people with little or no chess experience and masters.

Those without experience memorized it as raw data, and did as well as they would have if asked to memorize random numbers instead of chess arrangements. The masters were more interesting. They did about the same as the beginners on random arrangements that could never actually happen in a game, but they were infinitely better at reconstructing realistic arrangements that often show up in games. The experiments proved that masters can recognize groups of pieces and evaluate them collectively.

In a game situation this means the master looks at the board, and certain parts of it just stand out. The master will pay no attention to areas that don't grab his attention, and doesn't need to evaluate whether any of those individual pieces are worth moving. Interestingly, this means that playing with nonstandard rules (such as changing piece movements) will likely devastate a master's ability while only slightly reducing an amateur's skill level and leaving the computer's ability unchanged.

Even though I think the parent is a troll, here's an academic article detailing some other experiments on the topic.

Re:I disagree...

[gribbly]

How can you create something that you cannot adequately define?

Evolve it.

grib

Re:I disagree...

[mikera]

I have to say that I still think that humans and computers use essentially the same algorithm. Even the very best chess players search and prune a tree of moves.

Of course, grandmasters don't think of this as searching and pruning a tree, but that's what they are doing subconciously. If they didn't, they'd get obliterated in tactical exchanges.

The main difference between the human and computer tree searches is simply that the computers are far better (faster) at searching while the humans are far better at pruning and evaluation (thanks to the pattern matching you mention).

Humans simply ignore (prune) the vast majority of possible moves, so their "search tree" has a very low branching factor. I wouldn't be surprised if the average was less than 2 for top players, so they can look very deeply into a position without considering many alternative lines.

The other advantage that humans have is that they are much better at considering "strategic" aspects when evaluationg a position. It's very hard to get computers to recognise these. But in effect, this just means that the human has a much better evaluation function, so this is still consistent with the fundamental tree search approach. Like the parent post says, this ability doubtless involves considering groups of pieces using pattern matching etc.

The other interesting thing that humans do is remember aspects of the position which they subconciously make use of while doing move search and position evaluation, e.g. the existence of a pin or potential fork threat. My own style of play uses this quite a bit - I like to look for threats and weaknesses then try to find lines that will help me exploit them.

In this way, humans seem to be doing a kind of "directed search" which is theoretically possible in a computer's tree search but I've never seen actually implemented in computer chess. Anyone seen anything like this in a tree search algorithm? I think there could be potential for research in this area.

Checkmate

[lewko]

Subsequently, Kasparov created a positional advantage on the human side with
a very strong finger pointed at the reset button to which Fritz didn't have an answer.

Re:Checkmate

[zeux]

Subsequently, Kasparov created a positional advantage on the human side with
a very strong finger pointed at the reset button to which Fritz didn't have an answer.

Actually, that would be the ultimate proof of winning for Fritz.

Re:Checkmate

[Wylfing]

Subsequently, Kasparov created a positional advantage on the human side with a very strong finger pointed at the reset button to which Fritz didn't have an answer.

And that is why Fritz sent a Terminator back in time, to get rid of Kasparov before he was born.

Re:Checkmate

[NeoPotato]

And that is why Fritz sent a Terminator back in time, to get rid of Kasparov before he was born.

Except Deep Blue, Kasparov's original nemesis, is sent back to protect him!

There's the human advantage exposed right there

[Rosco P. Coltrane]

Kasparov created a positional advantage on the queen side with a very strong pawn structure to which Fritz didn't have an answer.

Well, what can poor Fritz, a cold emotionless computer, do when a handsome russian stallion of a man puts his pawn on the queen's side? Of course he didn't have an answer ...

Re:There's the human advantage exposed right there

[AbbyNormal]

Silly Chess players. When will they learn that it is not the Strength of your pawn structure, but how well you use it.

Other AI programs

[ekephart]

For those interested in AI game programming without the insane complexities of chess, Nine Men's Morris is fun. Also a frequently researched topic in AI.

Play here.

Re:Just goes to show

[spektr]

People learn faster than machines.

No, they just saw this stuff on TV. Once Fritz gains access to the Star Trek archives he won't again be so easily distracted and outplayed by Kasparov using his secret weapon: "how do you feel?".

Kasparov's Comment

[BinBoy]

Kasparov: pwned!

Programmer: No way! Look at my ping. It was lag!

Whew!

[ChicoLance]

There is a lot of relief here to me, as a spectator. The first game had Garry as white with a strong opening and everything looked good, then due to some dubious moves, it was a drawn game.

The second game on Thursday had Garry as black beat pretty much from the beginning. Garry fought back very well and might have drawn the game, but then foolishly blundered which cost him the game almost immediately. You could see the frustration level just go through the roof, as he's still trying to prove that he's better than the computer, but only to be beaten by the slow, steady computer approach.

But today, he's redeemed himeself. Although the match is now tied, he has shown that he can win against the computer. I feel better. :)

The last game will be difficult for Garry as black. But the fact that he won an game, and didn't draw them all has got to have him elated.

Battle chess

[zokum]

So, does anyone know when all this fancy AI will be backported into Battle Chess?

Re:Battle chess

[whiteranger99x]

To hell with Battle Chess, I say put it in Archon!!! >:)

Eight Pawn Chess

[__aanonl8035]

I play a little chess. When I was younger I had a 1600 rating. I wanted to play because I was humilated at getting beat by the chessmaster on Nintendo. So I practiced and finally became good enough to beat the computer (albiet only a Nintendo) What I learned then (and seems to be common knowledge among chess players) is that when playing a computer, you stand a much better chance if you keep all your pawns on the board and manouver your pieces behind them. Computers think about the game in a very different manner, and I think eight pawn chess highlights where their weakness lies. They do not have a plan. They do not start the game with a long term plan to the ending. I believe that in the past, Garry was a true sportsman and did not play eight pawn chess against the strongest computers. He played real chess. He played what he would play against another Grandmaster. I really think he could probably beat the computer almost all of the time by playing eight pawn chess.

Re:Eight Pawn Chess

[Rosco P. Coltrane]

I wanted to play because I was humilated at getting beat by the chessmaster on Nintendo.

Good thing you latched on the chess game cartridge, otherwise you'd have grown a moustache, started wearing red overalls and sporting a strong Italien accent, and become a plumber ...

Re:Eight Pawn Chess

[Craig3010]

Yeah and 3 Card Monte REALLY confuses the fuck out of them

Re:Eight Pawn Chess

[An Onerous Coward]

Not a terribly convincing syllogism there. It is highly likely that Fritz is more competent against your eight pawn strategy than your Nintendo.

Re:Eight Pawn Chess

[QBobWatson]

I don't think this applies to Fritz. From the interview with #2 player Vladimir Kramnik after his 2002 match with Fritz, when asked if he's trying to play "anti-computer chess", he replies:

In my preparation I tried to play this kind of anti-computer strategy, in some rapid training games. I could see clearly that it's not working anymore. The positional technique of this program is so much higher than years ago. It pushes pawns, builds the center, and begins activity on the flank. You cannot play like this anymore against computers. So many things I looked at in my preparations simply didn't work. I was shocked to see the level of positional improvement they had made.

I should note that IANAGM though.

Re:Only a matter of time..

[Rosco P. Coltrane]

given a finite amount of time the human brain can figure out how to solve any problem.

Okay, I give you 10 seconds to demonstrate the Fermat theorem : 1..2..3 ...

Imho computers are 100 years too early to even compete with the human brain

[/me checks the date]
No, I knew I was right, it is 2003.

Televised Chess

[porp]

For those who receive ESPN/ESPN2, the sports network has televised all three matches and will televise the fourth on Tuesday at 1:00pm. I've watched all three games on there, and it's actually very entertaining, if only for the humor of seeing history's greatest chess player in action and wearing those stupid X3D goggles. I just hope Garry can pull off Game 4 with a win.

porp

Two classic computer chess articles

[purplejacket]

I wrote an email to chessbase two months ago and actually got a response from Fred Friedel (the Chessbase president). I then replied to him about two classic articles I'd seen on chess as I was interested in seeing more of such in regard to the current match. They did some interesting statistical analysis (here's part five of a series, it links to the other parts) but, of course, I'm still hoping for more more more. Here's some of what I wrote in my email:

In replying to my original email you asked if I had any specific thing I miss. I can reply that over time I've seen two really good articles on computer chess. The first was the cover story from Scientific American in 1990:
http://www.sciam.com/article.cfm?articleID=0005CCF 5-D9D7-1CF6-93F6809EC5880000
It was about Kasparov vs. Deep Thought. The second was in 1997 from Byte Magazine:
http://www.byte.com/art/9707/sec6/art6.htm
The thing that stuck in my memory from the second article was this information:
"Hsu told BYTE that his team chose the RS/6000SP because it was the best available IBM system for the job, even though its P2SC processors don't have the best integer performance. Although the P2SC lags in raw integer horsepower, the RS/6000SP largely makes up for it by uniting 32 of the processors in a parallel system architecture with high-speed, low-latency connections."

I would be very interested to see the above sort of coverage of the current chess match. To put it in colloquial terms I'd like to see a big fat writeup of the workings of fritz, how it's design is broken down, how it makes tradeoffs between one kind of technique vs another, how it works with the intel architecture, how it uses null-move ordering, RAM caching, and how it fits into the history of human-chess matches.

I love these stories...

[Valar]

because they bring out so many people who bitterly complain and make excuses and want to challenge Fritz to a game of poker or something because it would give the human the advantage.

This is far from the end of our species, chill out. Even if we are worse at chess than the computers, it doesn't make the experience of being human meaningless. It doesn't mean we will be welcoming our new robot overlords any time soon.

Anyway, would it really be so bad, if AIs started getting better than humans at a lot of things? I think that in the end, we could take our greatest joy as a species in knowing that we created something better than ourselves.

Of course, that is an issue so seperated from computer chess, that many of you are probably complaining to yourselves.

That's how I feel when I read the excuse making and naysaying.

Is Fritz learning?

[LostCluster]

Does Fritz learn from today's defeat... or could Kasparov repeat today's win simply by repeating today's move sequence on Tuesday?

Re:Is Fritz learning?

[geekoid]

well, the next match they will switch sides. It would be interesting if the computer tried his own stratagy against him.

I am curious to find the answer to your question.

Re:Is Fritz learning?

[Nate Eldredge]

Don't most chess programs include some measure of non-determinism in their move choice, precisely so this isn't possible? For instance, if two different moves are found to have scores which are "close", the computer could select one at random.

In the simplest case, there must be some random mechanism to choose which opening to play. It would be boring and weak to always use the same one.

Probably Fritz will learn from this game, but I don't think that it's necessary in order to avoid meeting exactly the same defeat.

Re:Is Fritz learning?

[fishbonez]

I think the issue isn't that the computer will learn in between matches. I think the issue is that the computer will be reprogrammed in between matches.

One of the main shortcomings of these matches is calling them "man versus machine". Because that's really a misnomer and obscures the actual situation. Which is, that the Kasparov is playing a computer program that is not thinking entirely for itself. A lot of the decisions that the program makes have been pre-programmed by the team of chess experts prior to each match. It's the group of experts that evaluates the opponent and decides the general strategy of each game.

The program isn't altered in the middle of a game. But it also isn't Kasparov versus a completed chess program thinking for itself. I would go so far as to say the reprogramming during a multiple game match and the evaluation of the opponent by the chess experts is cheating. And really relegates these matches to novelties to be gawked at but not to be considered real.

Re:Is Fritz learning?

[kavau]

No, Fritz does not have a learning algorithm. The developers will surely analyze today's game and tweak Fritz accordingly, though.

However, Kasparov won't be able to reproduce this exact game in the next game for two reasons:

1) He has the black pieces in the next game, and

2) Even if he would be playing white again, Fritz chooses opening moves and variants from his database with a random element. So it's very unlikely that two of the games will turn out exactly the same. In one of the previous matches, the Fritz developers were even allowed to change Fritz's opening preferences between the matches. So you can be sure they'll eliminate this line from Fritz's choices.

1600 is nothing

[jbellis]

Fritz has grandmasters working for them. They're not stupid and neither are the programmers...

Kasparov tried playing "anti-computer" chess against Deep Blue and got his butt handed to him. After losing to Deep Blue Kasparov really, Really, REALLY wants to beat Fritz (after helping hype him as "even better than Deep Blue"). If it were as simple as you describe, he wouldn't be wasting any time doing it now.

Human

[cfuse]

Does Kasparov play human beings anymore? or is he too good for us?

Re:Human

[Craig3010]

After he discovered Tara Patrick's Virtual Sex With Me, he doesn't give a damn about human interaction.

'brilliantly won game 3' my shiny metal ass

[Sprunkys]

To quote (from memory) the online commentator Mig Greengard:
"If X3D Fritz lacks a clear target it plays like a braindamaged lemur"

As Fritz moved its pieces back and forth throughout the game, Kasparov could make several free moves. That isn't brilliant, that's just making use of the other guys mistakes. Kasparov dominated the whole game, while Fritz had no clue at all what to do. According to one of its makers, X3D Fritz reached a new record of reading deeply (19 ply if I'm not mistaken) since the number of possible moves was so small in the cramped space they were building up their positions. This, however, didn't help a bit and I had a few giggles over bishops and knights moving away and then back again to the very same place they were coming from.

Only at the very end did Fritz realize it was losing, throughout the whole game it couldn't see what was glaringly obvious to the audience.

I've been told that this was proper anti-computer chess. The cramped position makes it tremendously difficult for a computer program to play properly while a human can easily see what's to be done.

All in all, it wasn't brilliant, Fritz just didn't have a clue

What am I discussing all this chess for? Let me get back to KGS...

Re:'brilliantly won game 3' my shiny metal ass

[Mulletproof]

Now I'm not one that thinks chess is the end-all-be-all of society, but some might consider it brilliant that he was able to absolutely dumbfound the pinnical of chess technology. Yeah he made use of the other guy's mistakes... That's called "winning". Since the computer is brute forcing it's way through the chess match by trying to calculate ever possible senario per move, I consider it brilliant that he found a way to neutralize that huge advantage, even if the games was rather one-sided. Now to continue to win using the same motis operandi is cheesy simply exploitng a blindspot, but to find that blindspot [i]is[/i] brilliance in and of itself.

It's not like I rode the Short Bus to school

[teamhasnoi]

but I have a long history of getting my ass kicked at chess. The only time I *ever* beat a computer at chess was when I played the easiest level on Chessmaster 2100 on my Apple IIgs. I celebrated for days.

I played chess all the time with pals about 10 years ago. We were all at about the same level of bad. I thought I would prove my chess-skilz one day and played some guy at the local coffeeshop. After 3 moves, I was checkmated. My middle eastern opponent turned to my friend and said, "Your friend is stupid. I will not play him again.", swept all the pieces off the board, got up, shook his head and left.

That stung. So You Go Gary! I must live vicariously through you! Kick some ass! Then I must go back to OS X gnuChess which mocks me every time I play, "You are stupid. I will not play you again."

/me weeps into hands.

Re:It's not like I rode the Short Bus to school

[geekoid]

haha, thats is a damn funny story.

I remember one time, I was tossing darts, and won a game of cricket in the fewest possible throws.
By the time I was on my last toss, everybody in the bar was gathered around. My last toss landed perectly, the crowd goes wild. I had a great reputation, free drinks when I retold that story, and I never, ever, threw darts anywhere near that bar again. heh.

A matter of fact, about 10 years latter, I meet a guy at agaming clubg. He kept looking at me funny. Then one day he looks at me and runs off. about 30 minutes latter he returns. Turned out his father was the guy a beat, and gave him a picture of me tossing that last dart. the caption:
"With practice comes perfection."

I was laughing so hard, I had tears rolling down my cheeks.

Re:darn flash...

[__aanonl8035]

http://www.chesscenter.com/twic/twic.html#news130 This Week in Chess

a different strategy

[wilsynet]

In game two, Kasparov played the Berlin defence, which is a more closed game than the traditionally sharp Sicilian that Kasparov usually employs. It is well known that the sheer number crunching ability of the computer puts it significantly above the very best human tacticians. So yes, I think Kasparov has changed his strategy somewhat.

Re:a different strategy

[RevMike]

In game two, Kasparov played the Berlin defence, which is a more closed game than the traditionally sharp Sicilian that Kasparov usually employs.

Inconceivable. After all, one should never enter a battle of wits with a Sicilian, especially when death is on the line. It is the second greatest strategic blunder, the first being "Never get into a land war in Asia."

Re:darn flash...

[Davak]

[Event "Man-Machine World Championship"]
[Site "New York"]
[Date "2003.11.16"]
[Round "3"]
[White "Garry Kasparov"]
[Black "X3D Fritz"]
[Result "*"]
[ECO "D45"]
[WhiteElo "2830"]
[Annotator "Greengard,M"]
[PlyCount "89"]

{61MB, DELL8200} 1. Nf3 Nf6 2. c4 e6 3. Nc3 d5 4. d4 c6 5. e3 a6 {
Diverging from game one.} 6. c5 Nbd7 7. b4 a5 8. b5 e5 9. Qa4 Qc7 10. Ba3 e4
11. Nd2 Be7 12. b6 Qd8 13. h3 O-O 14. Nb3 Bd6 15. Rb1 Be7 16. Nxa5 Nb8 17. Bb4
Qd7 18. Rb2 Qe6 19. Qd1 Nfd7 20. a3 Qh6 21. Nb3 Bh4 22. Qd2 Nf6 23. Kd1 Be6 24.
Kc1 Rd8 25. Rc2 Nbd7 26. Kb2 Nf8 27. a4 Ng6 28. a5 Ne7 29. a6 bxa6 30. Na5 Rdb8
31. g3 Bg5 32. Bg2 Qg6 33. Ka1 Kh8 34. Na2 Bd7 35. Bc3 Ne8 36. Nb4 Kg8 37. Rb1
Bc8 38. Ra2 Bh6 39. Bf1 Qe6 40. Qd1 Nf6 41. Qa4 Bb7 42. Nxb7 Rxb7 43. Nxa6 Qd7
44. Qc2 Kh8 45. Rb3 *

The revolution will not be televised.

[LostCluster]

The telecasts have begun on ESPN2 at the start of play, but so far all of them have been kicked over to sister network ESPNews because they ran longer than their allotted airtime. Today's game, however, got bumped off of ESPNews to make room for NFL highlights today, so the chess coverage was regulated to two-minute live updates during the football coverage. Why did ESPN allow a match to be scheduled for today knowing that they would have run out of networks on which to put the full telecast unless an early blunder would be made?

It's fully expected that Tuesday's match will also spill into ESPNews territory as well, but at least they should be able to air the conclusion live since it will be weekday with no major sports events scheduled for the daytime.

Re:The revolution will not be televised.

[porp]

During the first match they went over 30 minutes and then moved over to ESPNEWS. Though they still cut into the match to show regular ESPNEWS highlight crap, they showed the majority of the match. I expect Tuesday's coverage to be similar. The match today just happened to coincide with NFL Sunday, and there are millions of people that watch ESPNEWS for news conferences and such. I just wish they would have not opted to show Women's College Hoops instead on ESPN2. I guess they were surprised by the large number of viewers the match garnered.

porp

Does he still play humans?

[smkndrkn]

...or does that not get any press?

I play chess...since 3rd grade but I don't follow tournament play. Does he get more money to play the computers?

Re:Does he still play humans?

[PDAllen]

I think it was more like three years ago he played Kramnik with the world championship at stake.
Most people also think that the reason he lost that was that he accepted Kramnik's challenge to play shorter games than standard: Kramnik thinks faster than Kasparov, but not as deeply, and hasn't beaten him in any matches with normal time rules.
He doesn't get many one-on-one matches any more, because no-one wants to be beaten repeatedly. He does enter tournaments, and tends to win those.

Does this still mean anything?

[owlstead]

Obviously these kind of matches are very interesting for chess players. But I wonder if there is any other significance, in theoretic science or in the computer science depts.

In other words, why should we care who wins? I don't want to troll, but the machine vs human chess player story is getting a bit stale. If the computer wins, that will mean, what? It's such a specialized field that you can hardly call it a milestone in computer science.

maybe Kasparov should be an Action Ranger

[dandelion_wine]

Al Gore: You already know Stephen Hawking. Also with us is Nichelle Nichols a.k.a. Commander Uhura.

Nichols: Incoming transmission from MCI one rate department. It sounds like a limited time offer.

Gore: Tell them I'm in the tub! To my left you'll recognise Gary Gygax, inventor of dungeons and dragons.

Gygax: Greetings! It's a...[rolls dice.]...pleasure to meet you!

Gore: And our summer intern, Deep Blue. The world's foremost chess playing computer.

Deep Blue: Bishop to knight 4.

Gore: Not all missions can be solved with chess, Deep Blue. Someday you'll understand that.

Kasparov: World's Best Computer Programmer?

[Latent Heat]

The only thing this will prove is whether or not Kasparov is in the top ranks of computer programmers.

A lot of people are trying to make of this a kind of John Henry against the steam drill contest. Here is my take on it.

Some while ago someone told me that computer programmers "break things", and I never quite understood what they meant. Some while later, a "competitor" was demoing a Windows version of a type of program for which I had put a great deal of effort into a DOS version. The program had a lot of graphical and interactive displays of scientific plots and other data, and I knew enough about Windows and all the stuff you had to do (WM_SIZE, WM_PAINT) to make it look right, and I suspected my acquaintence was "first to market" by taking a lot of short cuts on his UI. He let all the scientists in the room play with his program, but he was very reluctant to let me near the thing -- because the first thing I was going to do was try and break it to find out how much work he had yet to do.

The only way Kasparov is going to beat that chess program is if he uncovers some limitation or shortcoming -- in other words to break it, and once broken I bet he could beat the thing at will. Last time around the cheat was a team of programmers hanging around trying to patch the program as soon as Kasparov latched on to such a weakness.

The chess program will have reached true AI (in a limited problem set) once Kasparov is able to find a weakness, beat if for several games straight and for the program to somehow learn from what is going on and "close the hole", and if the program can withstand other such attacks from other chess grand masters and likewise "close the hole" without going unstable (one of the problems with learning algorithms is that can overadapt and go into limit cycles). That would have far reaching implications in terms of computer security, spam prevention, 24-7 uptime, and automated bug correction -- a program capable of fixing itself would be an advance indeed.

Re:Kasparov: World's Best Computer Programmer?

[An Onerous Coward]

I think you're onto something here, but there's still some confusion to be worked out. It's more conceivable to say that the computer is "playing chess" than to say Kasparov is "programming." Admittedly the programmers have to understand chess thoroughly, but Kasparov could wipe the floor with the lot of them. Meanwhile, any of them could "Hello, World" Kasparov into a quivering mass of jelly, if the battle were waged on their own field of expertise.

So what is actually going on? The programmers have been given a problem (chess) to solve, and have created a system that is very good at solving it. Kasparov is also good at "solving" chess, and he's putting his expertise in that field up against the best automated chess-solving system that can be devised. Meanwhile the programmers are improving the rules governing the automated system as the game progresses.

AI requires some level of situational awareness, but what you describe is a form of self-awareness. Admittedly, a program able to analyze its own rulesets and tactics for weaknesses is higher on the AI scale than a program which slavishly follows them.

But I don't think it's worthwhile to draw a sharp line separating "true AI" from imitators. Chances are, the program currently has some limited "self-adaptation" built in; it's just not robust enough to allow the programmers to exit the loop entirely. If a sharp line could be drawn, then one would have to point out which of the thousands of potential improvements would push the system over the line.

I'm of the opinion that chess programs have been demonstrating rudimentary intelligence at least since my 486 first beat me.

Re:Kasparov: World's Best Computer Programmer?

[DG]

The comment about "breaking things" is very insightful.

I'm no master chess player, but I used to play a lot of chess against Sargon III on my C=64 back in the day.

I discovered, quite by accident, that the chess engine in Sargon III could not see "indirect" attacks (there's probably some real chess term for this - if you want to threaten a piece with some other piece, put some third piece in the line of intended attack, move the attacking piece into position, and then "reveal" the attack by moving the "blocking" piece someplace else)

After a while, the program had trained me to set up these elabourate attacks... that a real human, even another amatuer like myself, would instantly recognise.

Say... I wonder if the computer was programming me?

DG

Re:O_o

[hookedup]

Uh.. mods might want to check this link again before modding it up 'interesting', seeing as the article isnt even real. Other headlines on that site include "POWER OUTAGE HID MARTIAN INVASION" and "SCI-FI FANBOYS WANT HUMAN RIGHTS FOR ROBOTS".

Give me a break.

Kasparov's nationality

[oob]

GK was born in Baku, the capital of Azerbaijan. While Azerbaijan was once a member state of the Soviet Union, this does not make him Russian.

Re:Kasparov's nationality

[the_consumer]

Doesn't make him not one, either. If your parents are Japanese, it doesn't matter where you're born. You're Japanese too.

Its not Human V Computer

[bacon-kidney-pie]

Its ridiculous to say oooh the computer has beaten the human. Whats actually happening is that a human unassisted is being beaten by a team of humans using a tool (the computer). Computers are just tools. What this means is that us dumb humans have figured out a way to model what this really smart (well good at chess at least) human is doing. To me its about as big a deal as saying ooh the worlds strongest man just got beaten by a guy with a forklift truck.

Mod up!

[EvanED]

The parent hit the nail on the head. Computers require a different strategy than human players. For instance, there was one particular move in this game that illustrates this, 18. Rb2, that is a loss of tempo against a human opponent. However, against Fritz it was a very smart move. The computer should have moved the piece on f6 then pushed its f pawn to f5 then f4, attacking Kasparov's f pawn. Moving Rb2 however had the effect of making black work a little harder to attack, apparently pushing the number of moves it needed to consider to find the advantage beyond where it was searching. Against a human player it would have had little or no effect (all the commentators were saying how Fritz was ignoring the opportunity with the f pawn), but against Fritz it made Kasparov's game much much easier.

An interesting game...

[TygerFish]

The game was interesting. It resembled a classic game from the thirties with either Saemisch or Maroczy as white. It underlines the strengths of the human mind versus computers.

The annotators of the first game pointed out over and over again, that some of each player's decisions were based on the computer's looking over a few million positions, and 'knowing' that it was safe to play the kind of moves that a human's fears and instincts would have made it very uncomfortable for a human to have played (e.g., the capture of the bishop by the king in the drawn game). Games like the first two show the greatest strengths of computers: superhuman ability in positions involving the calculation of tactical complications.

The current game by contrast grave rise to a position that is possibly the greatest illustration of a human's real strengths: the ability to create closed positions where tactical calculations of severely reduced utility; creating a position where experience and 'instinct' far outweigh calculation.

In the latest game, the computer's playing, 5...a6 created a 'hole,' a 'positional weakness,' and the rest of the game was a matter of exploiting its consequences while simultaneously giving the computer no chance to balance the game neither by winning back material, nor by a compensatory attack against white's position.

To put it another way, the nature of the position allowed white to create and exploit a position where the computer's ability to look at millions of positions per second was essentially useless.

It was clever and precise play on Kasparov's part.

Nine Men's Morris (and more) is solved

[yjlim]

Nine Men's Morris has been solved by Ralph Gasser in 1996 (Draw).

So has Qubic (4x4x4 Tic-Tac-Toe) by Patashnik O in 1980. (First Player Win)

Connect Four by James Allen in September 1998. (First Player Win)

Let's see John W. Romein and Henri E. Bal from that wonderful games research group in U of Alberta solved Awari in 2002. (Draw)

Read Victor Allis' PhD thesis for a good overview on finding game theoretic results of games. He invented the proof-number search technique that he used to (re)solve Qubic and Connect-Four. http://www.cs.vu.nl/~victor/thesis.html


Nine Men's Morris is not researched actively anymore, but Ralph Gasser's paper is often cited in any paper that deals with artificial intelligence in games.

Of course, even though the game might already be solved, that does not mean that it is not fun to play...

Re:O_o

[Doug Merritt]

Something as intense as calculations for chess really much push the brain to its "limits."

Sure, but:

The X3D technology fools the brain into seeing 3D. I wonder how much this 50% lack of visual stimuli changes the way the chessmaster's brain works here.

No effect whatsoever, because there is no "50% lack of visual stimuli". Anything that flickers fast enough is perceived by the retina itself as a solid unchanging image.

The "critical flicker fusion rate" that determines "what is fast enough" varies from about 40 frames per second to about 80 frames per second, depending on image brightness, ambient illumination, the particular individual viewing it, etc.

TV in the US, for instance, flickers at about 60 hertz, but in non-flourescent ambient illumination, most people don't notice. In Europe the rate is 50 hertz, and people frequently do notice. And some people get headaches from computer monitors that flicker even at 72 hertz, especially under flourescent lights.

I used to regularly get annoyed at PC monitors in conference rooms flickering at 60 hertz, when others didn't notice -- so I'd bring up display preferences and set it at the highest refresh rate. Until it occured to me that I was sabotaging people who needed to interface it to the overhead projector at 60 hertz. Oops! :-) But I digress.

Movies are displayed at 48 hertz (although only 24 unique frames per second; they are "double-shuttered" to double the frame rate). Cartoons sometimes have as few as 6 unique frames per second (although they are displayed at movie or tv flicker rates) because that's about the threshold for perceiving continuous motion. Lots of issues, lots of thresholds.

But even if the 3D viewing shows perceptible flicker, there isn't any issue of "50% lack of visual stimuli". Both eyes are constantly receiving information.

I could imagine that any number of things about this 3D gadget could distract a chess player -- but so does cigar smoke (a trick used to advantage in chess matches early in the 20th century).

Years ago I used to use similar 3D goggles to play first person shooters like Quake, and it was great. It helped my game. Quake isn't chess, but 3D goggles aren't rocket science.

You can assume that, if he agreed to use this 3D setup, he was confident it wouldn't throw off his game. He does care, after all.

Re:O_o

[Quixotic137]

I wonder how much this 50% lack of visual stimuli changes the way the chessmaster's brain works here.

Besides which, why don't they just have a real chess board with a guy sitting there moving the pieces as the computer directs? Maybe I'm missing something, but it seems like that would be more like playing a person face-to-face.

Axiom of Choice and game of Go ???

[Doug Merritt]

Actually, the computer could win if the axiom of choice happens to be true. Even if that isn't true, a computer could still beat every human on earth.
--
Be incomprehensible. If they can't understand you, they can't disagree with you

Are you trying out an application of your .sig here?

Because (1) the axiom of choice only applies to infinite sets, whereas the number of possible games of GO is huge, but not infinite, and (2) The axiom of choice is not an open question that may "happen" to be true or not; it has been proven to be independent of the other typically used axioms. You can declare it to be either true or false, and either way, develop an interesting branch of math that depends on your choice -- as many mathematicians have done.

In other words, your .sig philosophy of "if you can't dazzle 'em with brilliance, baffle 'em with BS" isn't cutting it this time around. :-)

Be afraid, be very afraid...

[linuxjack55]

The position after 29. a6 was indicative of how paranoid Kasparov was about the computer's tactical capabilities. In addition to the pawn blockade stretching diagonally from f2 to b6, he had marched his king all the way from e1 to b2 and protected it behind a wall of pieces. The king's bunker looked like this:

B
N N
K R Q

As chess positions go, that one cracked me up.

Re:Be afraid, be very afraid...

[Entropy248]

He did that to maximize the number of moves that computer would have to compute to capture his king. Think about it, the possibilities are endless. Moving any piece opens up an escape hole for the King while maximizing the number of possible moves for the situation. The queen's capabilities in that position are enormous; she has a clear line of fire towards most of the squares that any piece can move to. The same is true for every piece on that formation. Again, further maximization of possibility. It's brilliant.

Style.

[nicodemus05]

I'm not sure who I should be cheering for.

On one hand, a victory for the computer means a victory for everything we've been working at for a long time. It means that computers are getting smarter, and smarter, and smarter.

Call me a hypocrite, call me sentimental, but I desperately want Kasparov to win. I want us to still be better than computers at this game. It's highly mathematical, but there's always been a level of flare, panache, and style to the game. Even though 'Knight to King 4' may not sound particularly interesting, it could have been something intrinsically bold and audacious when done by a human player. When the same move is made by a computer it becomes purely calculated.

I want Kasparov to win because I feel like it'd be a blow to the game to let an algorithm (albeit a brilliant one with an unbelievable amount of brute force behind it) beat something feeling.

Re:How does the computer play?

[linuxjack55]

The game of chess has been around so long that opening moves and their variations have been cataloged, categorized, and analyzed in great detail. It's been a while since I was a serious student of the game, but I think Modern Chess Openings is still the standard reference for opening play.

In any event, X3D Fritz has a database of analyzed opening moves, including, for this match, a database of Kasparov's opening moves. It's called the opening book. Opening books save the computer time at the start of the game, since it doesn't have to reinvent the wheel every time it plays.

As for deciding the first move to play, the computer has a randomizer to select a move from its opening book. For this match, though, I wouldn't be surprised if X3D's programmers didn't pick its first move for it.

We've already won

[Szplug]

A human can pick up another game and learn it, and get better at it. He/she can notice shortcuts / regularities in the way the game works that reduces the amount of thinking s/he has to do, build a higher level, meaningful way of looking at the game. You can drop a human into any novel situation and they'll similarly figure out the rules, and shortcuts.

We handle it completely differently - we rely on this ability, and chess programs look ahead some 15 or more moves, where humans supposedly top out at about 6.

Now, if you think of Kasparov making a close game with a specially written, highly-refined program with his general purpose brain, look at it as the measure of what it takes to beat our brains! 15-20 move lookahead! It validates the brains' elegant and powerful design.

Law of Large Numbers

[PingPongBoy]

Four games is not enough to statistically show who is better, especially if they are tied after three games.

I think Kasparov still knows a lot of tricks but will not reveal many of them even if it means losing a match of just 4 games. He would know after just a game or two who is really stronger, and if the machine is limited, he woould't care to play 100% in case the next upgrade learns too much.

Does this mean

[boatboy]

Does this mean Gary could be The One? (spoiler) I expect him to lay down and feed himself to X3D to save us all.

Re:How does the computer play?

[Bohnanza]

I wouldn't be surprised if X3D's programmers didn't pick its first move for it.

That would be cheating, wouldn't it? It's supposed to be "Man Vs. Machine", not "Man Vs. Machine and Another Man"

Ducking Kasparov

[amightywind]

Does Kasparov play human beings anymore? or is he too good for us?

Ponomariov held out for more money (non-existant) in a sheduled match with Kasparov that would have led to a championship match between either Kramnik or Leko. Neither match ever happened so Kasparov headed back to New York for another payday with Fritz. The problem is not Kasparov playing other humans but other humans having the guts to play Kasparov. Kramnik has not defended his title in 3 years. The FIDE stripped Fischer's title after that long.