Bram Cohen ([info]bramcohen) wrote,
@ 2006-01-29 15:12:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Quality of Chess Games
What's the best tournament chess game of all time? If by 'best' one means 'best played' then I'm afraid the answer is Zappa vs. Fruit. In this most recent world computer tournament, Zappa scored an astounding 10.5 out of 11, a better performance than any human has ever had in a human world championship, and against a stronger field than any human world champion has ever faced. Fruit came in a clear second, so this is the only tournament game we have between the two strongest chess players ever created. Of course, you'll soon be able to buy the commercial version of Zappa and have it play against itself, resulting in a string of games most of which are better than any game ever played between two humans. Welcome to chess in the 21st century.

Some humorous notes: Zappa and Fruit were both written by lone grad students in under two years. Dark horses obliterating the field is a common thing in AI. Zappa's lone draw was ironically against the program which lost every other game in the entire tournament.

Zappa's high win rate as black against extraordinarily strong opposition indicates that the frequent grandmaster claim that they can automatically draw as white is a bunch of bullshit. In a match between Zappa and any human on the planet with Zappa taking black every game and an even score giving the match to the human, I'd put my money on Zappa in a heartbeat.

Now that computers are clearly better than humans at chess, the question arises, can computers attempt to guess the strength of a game's play based on the moves in that game? And can we use that method to evaluate 'classic' games? Do we really want to?

As for rating play based on moves, a simple algorithm which compares the strength of the move actually played to the strength of the best move will probably do nicely. It's necessary to have some formula for determining how much a blunder counts against you versus a series of small mistakes, but that should be straightforward to determine with some experimentation. There's a bit of a problem with endings which the computer totally works out, since then the difference between the best move and the second best is likely to become very large based on what the computer happens to have worked out completely, but it shouldn't be terribly difficult to deal with that issue either.

On the question of whether classic human games are any good, I'm afraid the answer is most likely no. There is nothing special about grandmaster human strength in the continuum from random move play to perfect play, and the computers are now better, rendering human grandmaster games just as childish to computers as human international master games are to human grandmasters.

That, by the way, is why computers these days typically throw out the opening book after the first few moves, if not ignore it altogether. The opening book was generated by humans whose skill level was far worse than the computer, and the only advantage they have is the sheer number of hours put into study of the opening position. You don't have to get many moves deep before that advantage goes away.

However, there computer evaluation of human play may give an opportunity to find the occasional game in which the humans understood something which the computer still doesn't grok. In each game, the computer will evaluate one side as having played superiorly to the other. We could have the computer evaluate all available grandmaster games, and find ones in which the computer rates the play of the side which lost as superior to the side which won. The largest gaps in that direction will undoubtedly be games in which someone resigned a won position, but there are probably many games not too far down the list which indicate something useful.



(Post a new comment)


[info]barbobot
2006-01-30 12:36 am UTC (link)
Personally, i've always been a fan of Go

(Reply to this) (Thread)


[info]strangegod
2006-01-30 01:24 am UTC (link)
The last bastion.

(Reply to this) (Parent)(Thread)


[info]bramcohen
2006-01-30 02:51 am UTC (link)
Globally go is far more popular than chess, so switching the emphasis to it can hardly be called an act of desperation.

(Reply to this) (Parent)(Thread)


[info]strangegod
2006-01-30 06:14 am UTC (link)
I was referring to its current immunity to superhuman AI, and that I don't believe there is another (popular) game like it as far as that goes.

(Reply to this) (Parent)


[info]misterajc
2006-01-30 03:01 am UTC (link)
The decision tree has far more branches in Go, so it is harder for a computer to analyse.

(Reply to this) (Parent)(Thread)


[info]chaoticset
2006-10-16 04:12 pm UTC (link)
Just means the wrong approach is being used...

(Reply to this) (Parent)


[info]utilitarianist
2006-01-30 01:41 am UTC (link)
It is now widely agreed that the Kasparov - Deep Blue match of 1996 was a less dramatic version of John Henry and the Steam Hammer. So yes, games between humans are now bound to be boring and tactically juvenile compared to those played by computers. However, I don't think this is the end of humans in high level chess. Instead, with cooperation between human and computer, it's an opportunity to play games of chess 'better' than any of those ever played before.

You might be interested in this:
http://en.wikipedia.org/wiki/Advanced_Chess

or, if you inherently distrust wikipedia:
http://advancedchess.netfirms.com/description.htm

A human and a computer together have thus far been able to beat all lone humans and lone computers.

(Reply to this) (Thread)


[info]bramcohen
2006-01-30 02:50 am UTC (link)
I'm unconvinced that with recent computers a human would really add all that much. It's probably useful to take the top three programs and add up their evaluations though, since they're likely to have slightly different strengths and weaknesses.

(Reply to this) (Parent)(Thread)


[info]agthorr
2006-01-30 05:07 am UTC (link)
The problem with computer chess programs is that they think very one-dimensionally. They can search several moves ahead, and they can have a database of endgames, but their strengths end there. Players like Kasparov (3-to-3 against Deep Junior and 2-to-2 against X3D Fritz in 2003) and Kramnik (4-to-4 against Deep Fritz in 2002) have been able to hold their own against computer chess programs because they plan very carefully and use strategies that give him a long-term advantage that is too far away for the computer to see in its search.

A large part of the computer players relative strength against such a player is how smart their evaluation function is. At the of the depth of their search, they need to decide "How well am I doing given this board configuration?". Chess program authors spend a lot of time trying to figure out the best way to do this, but, ultimately, this part is still based on all those old books and what people can reason about chess.

(One of the reasons Computer Go is so much more difficult, aside from the larger search space, is that it's so much harder to define a good evaluation function)

In Chess, being able to search move moves ahead requires exponentially more computations, so even though processing power has been growing exponentially, the strength of computer chess players has been growing only linearly.

(Reply to this) (Parent)


[info]audi100quattro
2006-01-30 02:23 am UTC (link)
Computers may help us understand the nuances and subtleties of a move better, but chess is bound to be a human game more often than not. With that said, are the new computers strategic players or do they remain tactical players, even if on a deeper level? There have and probably will always be certain Original strategies humans will have mastered to beat computers, but that was primarily because computers remained massively tactical players.

I'd have to disagree with most of your post, but I haven't been following the chess world for the last 5 years, and I can see it's changed a lot when it comes to computers.

As for different types of chess, Bughouse is where it's at!

(Reply to this) (Thread)


[info]bramcohen
2006-01-30 02:49 am UTC (link)
There have and probably will always be certain Original strategies humans will have mastered to beat computers

You can keep wishing that.

(Reply to this) (Parent)


[info]frdelrosario
2006-07-05 11:00 pm UTC (link)
Bughouse is an incredible waste of time. Chessplayers spend their whole lives learning how to bring new force into the game, but in bug, who cares? New force magically drops from the sky.

(Reply to this) (Parent)(Thread)


[info]audi100quattro
2006-07-05 11:30 pm UTC (link)
It's the same for my opponents as well...

Some of the ways to win are offcourse counter-intuitive to chess, but that doesn't make it any less of a strategic (good) game.

(Reply to this) (Parent)

bug
[info]whyso
2006-08-08 12:42 am UTC (link)
fics handle :?)

(Reply to this) (Parent)(Thread)

Re: bug
[info]audi100quattro
2006-08-08 07:04 am UTC (link)
It's lordoftheworld... i haven't played in a while, and bug i think is much better in person, anyway, see you on fics :)

(Reply to this) (Parent)


[info]nvioli
2006-01-30 03:46 am UTC (link)
i was really hoping that link was going to be some performance art piece of frank zappa playing chess against a bowl of fruit or something.

alas...

(Reply to this)


[info]barbobot
2006-01-30 04:33 am UTC (link)
Also this post reminded me of an Asimov Quote:

"I do not fear computers. I fear the lack of them."

(Reply to this)

people will still play chess.
[info]maelorin
2006-01-30 04:53 am UTC (link)
imnsho, computer programs may well have it over humans on raw processing power, etc. but humans will still play, and still watch humans play, for some time yet.

at some point one might recall that games are about playing, however much scorekeeping get computerised. chess, go, and similar games of strategy are as much about two people as they are about the boardgame.

at least, so i always believed.

(Reply to this)


[info]lupoleboucher
2006-01-30 05:20 am UTC (link)
Personally, I think it is a great tribute to the incompetence of computer scientists that it has taken 50 years to resoundingly beat humanity in the chess game.



(Reply to this) (Thread)


[info]dojothemouse
2006-01-30 07:44 am UTC (link)
Pshaw. I've been losing to comptuers at chess since I was 8.

(Reply to this) (Parent)


[info]granting
2006-01-30 01:36 pm UTC (link)
Chess programs are generally only as good as the people who make them. Raw processing power helps, but it alone isn't the solution. Regardless, you are making the assumption that the best computer programs participated in the tournament - which is not necessarily the case. Where was Fritz?

I just watched the entire game you mentioned, and I have to disagree on it being the best played ever anyway - perhaps mostly Fruit's fault. I didn't spend all that much time but I saw a few very "computer like" moves that Fruit made that were worthless. Fruit late compensated for them, but that's not the point.

By my definition, at least, that would kill it from being the "best played" game.

(Reply to this)

So...
[info]bitjuggler
2006-01-30 04:29 pm UTC (link)
...is the difference between tic-tac-toe and chess more than just a matter of degree? I don't think so, but chess zealots always argue with me about this. My take is that a sufficiently powerful computer can solve chess strategy with just a bit more effort than it would take to solve tic-tac-toe strategy.

(Reply to this) (Thread)

Re: So...
[info]granting
2006-01-31 01:19 pm UTC (link)
It isn't how big your CPU is... it is about how you use it.

(Reply to this) (Parent)


[info]akshoslaa
2006-01-31 02:41 am UTC (link)
A victory by Deep Blue would be a very important and frightening milestone in the history of mankind. - Gary Kasparov

One of my all time favorite quotes (albeit a tad outdated now :P)

People, particularly those in endangered fields, always say that 'machines' could never replace them. these same people tend to overlook the vast amount of evidence to the contrary. Throughout history we've always developed machines to make our lives easier, replacing ourselves in the process. The problem, (as I see it) is that the machines have reached a point beyond making our work easier, and are now getting to be capable in fields that were once considered purely intellectual.

Personally, I have no problem with this... but I can understand when others do.

(Reply to this)


[info]gjm11
2006-02-04 06:26 pm UTC (link)
Either Bram's missing some things here, or I am.

1. Chess skill is not something that can be measured adequately along a one-dimensional scale; A can be better at some things than B and worse at others. Therefore, supposing it to be true that the best computers now far outplay the best humans, all that follows is that they are much better at some things. (Imagine a tennis match between a human player and a machine that serves balls at 300mph but only manages to return one shot in ten. The machine will probably win every game.) This has some interesting consequences. One of them:

1a. It's somewhat plausible that all (or most) computer chess programs have similar areas of strength and weakness. In that case, the programs that do best against other programs might be very weak in areas that programs don't understand how to exploit. For all we know, there might be human players who could latch onto a weakness in Zappa's play and take it to pieces. (That's less likely for programs that play more against humans, because the humans have had more of a chance and not succeeded.)

2. The statistical noise in a computer chess tournament is large. The program that wins (even if it wins by a long way) need not be the best player. Even less need the program that places second be the second-best player.

3. That tournament didn't include all the candidates for "best player ever". For instance, it didn't include Deep Blue; it didn't include Fritz; it didn't include Rebel or Pro Deo; it didn't include Hiarcs.

4. The quality of a game is not determined by the overall skill of the players involved. Even a computer can play an uncharacteristically bad game.

As evidence for some of the above: remember that half-point that Zappa lost in WCCC 2005? It lost it to a program called Fute, which took last place in the tournament with a total of ... 1/2 a point. Therefore, the following three things can't all be true: (a) "A program that beats all but one other contestant in WCCC 2005 must be stronger than the others", (b) "A program that loses to all but one other contestant in WCCC 2005 must be weaker than the others", and (c) "The quality of a program's play is entirely determined by how strong the program is". Because if they were all true, Zappa would have beaten Fute.

Going back to consequences of #1:

1b. There's nothing special about the current level of computer strength on the "continuum" from random play to perfect play, either. Computers will certainly see tactical errors in human grandmasters' games, but (because they and the grandmasters may be good at different things) they may also miss important things that the GMs don't. It's plausible that human GMs are *simply better* than human IMs: they're players of basically the same sort, at a higher level. But the differences between humans and computers go deep enough that I don't see any grounds for thinking that computers are *simply better* than GMs; more likely they're *complicatedly better* by virtue of being good enough at enough aspects of the game.

If you want to define the quality of a game in terms of minimizing the number of tactical errors, the best ever may very well be a computer-computer game (though I see no reason to think it's Zappa versus Fruit). Seems an unsatisfactory definition of quality to me, though.

(Reply to this)


[info]kosai
2006-02-06 11:54 pm UTC (link)
frequent grandmaster claim that they can automatically draw as white is a bunch of bullshit.

I'm preparing to be very wrong here, but.. *is* that a frequent claim? I've always heard being able to force a draw as something black (frequently) attempts, not white.

I could make an argument for why it might be harder for white to force a draw than black -- white's first-move choice is pretty much limited to e4/d4, neither of which specifies the closed game white is aiming to head for a drawn position with. On the other hand, *black*'s first move contains far more entropy. Can white close the position after black gets to choose a second-move response he knows deeply and wants to create an open game from?

(I don't know the answer; I'm interested in how much more the second-fourth-sixth moves dictate the position than the third-fifth-seventh, if any.)

- C.

(Reply to this) (Thread)


[info]bramcohen
2006-02-07 09:18 pm UTC (link)
Generally grandmasters try to win as white, not just draw. It's based on having the initiative with the first move, not on being able to force a closed game, so it isn't clear that having an open vs. closed game matters, but even if it does, white can still play Nc3, Nf3, c3, d3, or e3 as their first move, all of which are considered legitimate first moves.

(Reply to this) (Parent)(Thread)


[info]frdelrosario
2006-07-05 11:07 pm UTC (link)
That's pretty much the basis for the notion that a grandmaster should always be able to draw with White: by sustaining the first-move initiative sufficiently so that Black never generates enough threats to unbalance things.

(Reply to this) (Parent)


[info]frdelrosario
2006-07-05 11:05 pm UTC (link)
It is a frequent claim by grandmasters, and one in which I put a lot of faith. A grandmaster with white ought to draw at will, and he does not need to steer for a closed game in order to do so. An open position without imbalance is just as drawish, and in many cases, even easier to bring to that draw for the relative ease in reducing force on the board.

(Reply to this) (Parent)

the final stand....
[info]spoo_k_pryme
2006-04-04 02:35 pm UTC (link)
eventually it will be impossible to improve upon the AI in a chess program without instilling into it, a sense that it needs to win.

then we would become useless.

(Reply to this)

rybka!
[info]clumma
2006-12-03 04:33 am UTC (link)
http://www.rybkachess.com

Rybka is now, and has been for most of 2006, the strongest engine
by a wide margin, at all playing speeds. It is also widely thought
to have the best positional and thematic understanding. Some
tournament results

http://rybkachess.com/index.php?auswahl=Tournaments

Of course, tournaments are not as conclusive as computer rating
lists, in which hundreds or thousands of games are played. Rybka
leads all the rating lists at the moment.

Some evidence suggests the first versions were based on Fruit,
but considerable changes have been made since. Rybka is thought
(and the developer claims) to use a novel evaluation function.
One author speculates piece values are calculated dynamically...

All of this applies to publicly-available engines only. It
remains to be seen if Hydra

http://hydrachess.com

is stronger than Rybka.

Meanwhile, the best human is holding his own against the best
computer that sponsors will pay to challenge him.

http://www.kramnik.com

Despite being down a point in this match, Kramnik has outplayed
the machine in most games. The point loss is due to a blunder.
As was the decisive game in Kasparov's '97 loss to Deep Blue,
though this is almost never mentioned in the press.

I don't know what you're basing your comment on opening books
on. All top engines that I'm aware of use (human created) books
extensively. I am anxiously awaiting a human-computer Chess960
tournament

http://en.wikipedia.org/wiki/Chess960

Unfortunately, Rybka does not yet support Chess960.

As for positions from human games that fool computers, several are
known, but Rybka is getting more and more of them. There is also
a new engine from the creator of Rybka called WinFinder which is
made specially for solving such positions...

-Carl
http://lumma.org/microwave

(Reply to this)


Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…