You are viewing bramcohen

Sun, Jan. 29th, 2006, 03:12 pm
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.

Mon, Jan. 30th, 2006 12:36 am (UTC)
barbobot

Personally, i've always been a fan of Go

Mon, Jan. 30th, 2006 01:24 am (UTC)
strangegod

The last bastion.

Mon, Jan. 30th, 2006 02:51 am (UTC)
bramcohen

Globally go is far more popular than chess, so switching the emphasis to it can hardly be called an act of desperation.

Mon, Jan. 30th, 2006 06:14 am (UTC)
strangegod

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.

Mon, Jan. 30th, 2006 03:01 am (UTC)
misterajc

The decision tree has far more branches in Go, so it is harder for a computer to analyse.

Mon, Oct. 16th, 2006 04:12 pm (UTC)
chaoticset

Just means the wrong approach is being used...

Mon, Jan. 30th, 2006 01:41 am (UTC)
utilitarianist

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.

Mon, Jan. 30th, 2006 02:50 am (UTC)
bramcohen

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.

Mon, Jan. 30th, 2006 05:07 am (UTC)
agthorr

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.

Mon, Jan. 30th, 2006 02:23 am (UTC)
audi100quattro

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!

Mon, Jan. 30th, 2006 02:49 am (UTC)
bramcohen

There have and probably will always be certain Original strategies humans will have mastered to beat computers

You can keep wishing that.

Wed, Jul. 5th, 2006 11:00 pm (UTC)
frdelrosario

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.

Wed, Jul. 5th, 2006 11:30 pm (UTC)
audi100quattro

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.

Tue, Aug. 8th, 2006 12:42 am (UTC)
whyso : bug

fics handle :?)

Tue, Aug. 8th, 2006 07:04 am (UTC)
audi100quattro : Re: bug

It's lordoftheworld... i haven't played in a while, and bug i think is much better in person, anyway, see you on fics :)

Mon, Jan. 30th, 2006 03:46 am (UTC)
nvioli

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...

Mon, Jan. 30th, 2006 04:33 am (UTC)
barbobot

Also this post reminded me of an Asimov Quote:

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

Mon, Jan. 30th, 2006 04:53 am (UTC)
maelorin : people will still play chess.

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.
(Deleted comment)

Mon, Jan. 30th, 2006 07:44 am (UTC)
dojothemouse

Pshaw. I've been losing to comptuers at chess since I was 8.

Mon, Jan. 30th, 2006 01:36 pm (UTC)
granting

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.

Mon, Jan. 30th, 2006 04:29 pm (UTC)
bitjuggler : So...

...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.

Tue, Jan. 31st, 2006 01:19 pm (UTC)
granting : Re: So...

It isn't how big your CPU is... it is about how you use it.

Tue, Jan. 31st, 2006 02:41 am (UTC)
akshoslaa

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.

Sat, Feb. 4th, 2006 06:26 pm (UTC)
gjm11

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.

Mon, Feb. 6th, 2006 11:54 pm (UTC)
kosai

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.

Tue, Feb. 7th, 2006 09:18 pm (UTC)
bramcohen

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.

Wed, Jul. 5th, 2006 11:07 pm (UTC)
frdelrosario

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.

Wed, Jul. 5th, 2006 11:05 pm (UTC)
frdelrosario

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.

Tue, Apr. 4th, 2006 02:35 pm (UTC)
spoo_k_pryme : the final stand....

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.

Sun, Dec. 3rd, 2006 04:33 am (UTC)
clumma : rybka!

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