Chess: Man vs. Machine Debate Continues

Frederic Friedel sent in an interesting submission. It's an interview with the current world's chess champion, Vladimir Kramnik, in which they talk about the upcoming year in chess competitions, but also get into [Deep Blue] and where computer chess playing is versus several years ago, with a comparison between Deep Blue and Fritz. If you want more info, check out Chessbase for additional news.

Comments

New Turing Tests

[KFury]

Forget conversational ability. I'd like to see a Chess Turing Test, where grandmasters go up against an unknown opponent, and have to ascertain whether they're playing a computer or a machine.

Re:New Turing Tests

[marcelk]

> Forget conversational ability. I'd like to see a Chess Turing Test, where grandmasters go up against an unknown opponent, and have to ascertain whether they're playing a computer or a machine.

Actually, the computers have already demonstrated greater skill in judging chess Turing tests: they are better than grandmaster at deciding if an unknown player is human or not.

computers and Grand Masters

[56ker]

If you remember - for a long time no professional chess player would play a computer. I'm curious as to what the reasoning was behind this. Maybe they thought it's best to concentrate on learning how people play the game and not how a computer plays.

Programming is not creative?

[hij]

There is an impicit assumption that the person playing the computer is only playing against the computer. This is the creativity of humans vs the brute force of computers argument. I would argue that the person is up against the programmers skills as well as the hardware.

There is an enormous amount of creativity and human effort in creating Deep Blue or Fritz. Deep blue's win was not a machine beating a man. It was a team of programmers who were able to figure out how to get a piece of hardware to beat man at his own game!

Limits of computers?

[adam613]

It's interesting that computers haven't been trained to always win or tie at chess.

Chess is a game of perfect information. Each player knows every detail of the game state at any moment. Therefore, there has to be formula of some sort that can be applied to guarantee one player victory. Reasoning as follows:

Say I construct a lookup table for every possible combination of moves. Then I eliminate every move which doesn't lead to my victory. I am left with a lookup table which contains the proper response to every move my opponent makes.

There are two possibilities: I win the game, or my opponent wins the game. However, in order for my opponent to win, he/she would have to come up with a sequence of moves which is not in my lookup table. Since my lookup table is exhaustive, this is impossible.

Given an infinite amount of processing power and memory, could someone "solve" the game of chess?

If so, could someone use techniques such as genetic programming or neural networks to learn the lookup table in a finite amount of time/space?

Re:Limits of computers?

[sh4de]

In chess, we're not ultimately hampered by storage or processing power, but the size of the universe itself. I remember reading that in chess, there are more valid positions than there are atoms in the known universe! This calculation even took account the fact that some positions aren't necessarily reached by any sequence of legal moves.

In either case, the storage requirements are so astoundingly huge that chess cannot be "solved" in that sense. Instead, the position at hand has to be evaluated from scratch each time, applying an "n-ply" tree lookup to determine the best move, leading to the best outcome.

Now, the best outcome is a moving target itself. Chess programs tend to emphasize advantage in raw materials, which is often directly transferable to a victory, if both players know what they're doing.

A human player, on a grandmaster level, may sport an ability to play in a "creative" way, wherein the computer is confused by a series of "non-op" moves that will pay off in 20 moves or so. A well known positional genius, Bobby Fischer, has played games that are intriguing to watch and analyze. A computer wouldn't rank some of his moves very high, but they all carry a meaning in the long run.

Re:Limits of computers?

[Grond]

This question comes up quite a bit. The answer hasn't changed in years because of the way the question is usually posed. You asked, essentially, if it is possible to solve chess by searching the entire move tree. Then you asked if it could be done with an infinite amount of processing power and memory. Well, of course it can be done with an infinite amount of each. The trick, as you then go on to ask about, is to do it in a finite amount of both.

Well, first of, the search space for chess is on the order of 10^43. Now, that's a lot. So, in order to see if it's possible to search that, we'll need an extremely fast computer. Turning to Seth Lloyd's article in Nature about the 'ultimate laptop' (the fastest possible computer using 1kg of mass), we see that such a device would be capable of executing 10^51 operations per second. Unfortunately, those are bit level operations, so first let us scale that by the number of bits necessary to encode a chess board state: 164 with Huffman coding. That yields 10^49 operations per second for the size of the data that our brute force algorithm will likely be working with. Now, normally at this point we would go into a discussion of evaluation functions and tree pruning, but what you want is a brute force algorithm, so no short cuts, just the right answer, for sure.

So what can we do with our 10^49 operations per second? Well, we have to search the tree and compare all the possibilities to determine which one is the optimal move. Well, that means that we have to compare all of the possible leaf nodes after ranking the path that got us there. Well, the branching factor for chess is approximately 7. So, there are about 10^42 paths to work with. Now, evaluating them means doing some hundreds of executions of our evaluation function (which will take thousands of instructions to execute). So, that means, for each of the 10^42 paths, we have to do 10^5 instructions, for a total of 10^47 instructions per move!

So, we can consider a move in a hundredth of a second. Assuming our game goes quickly (and discounting the time it takes our feeble opponent to make a decision), it'll all be over in about half a second. Unfortunately, in that time it will have consumed 2x10^26 watts. Now, you get 10^17 joules out of 1kg of mass, so we'll need 5x10^8kg of mass converted to pure energy just to power our laptop. (To give you an idea of how much matter that is, consider using lead as our source of energy: we'd need 44,000 cubic meters of lead to power our device.

So we feed our computer 500,000,000kg of lead and play the perfect game of chess in half a second. What happens to the 2x10^26 watts of energy fed into it? Well, since we just fed it into 1kg of matter occupying 1L of space, we will soon be facing an explosion equivalent to 100 solar flares compressed into a soda bottle.

So, yeah, sure, you can play a perfect game of chess...if you're prepared to annihilate a solar system. (not to mention be playing against another, equal computer, since you've only got half a second to play in) :)

Don't be fooled by propaganda.

[Skuto]

Kasparov sent out a reaction shortly afterwards claiming that Kramnik's statement that Fritz is better than Deep Blue is nonsense.

There's some PR involved here. If Kramnik wins, he wants to look good, so saying Fritz is better than Deep Blue makes him look better. For Kasparov, it's just the opposite.

Whether or not Fritz is actually better than Deep Blue is a matter of endless discussion even among computerchess experts. And we'll never know the answer, because Deep Blue no longer exists.

--
GCP

He's going to play against a boxed product

[Animats]

The world chess champion is going to play against Fritz 7, a commercial boxed product chess program. A cheap one: €102.50 in the multiprocessor version. The program will be run on an 8-processor IA-86 machine, more than a typical PC, but not that much more. (OK, the multiprocessor version shipping is Fritz 6, while the uniprocessor version shipping is Fritz 7, so the latest high-end version isn't quite shipping yet.)

Kramnik says that the Fritz 7 program on a laptop is producing some better moves than Deep Blue did against Kasparov. That's how much progress there's been.

Chess programs are now so powerful that unless your're a rated master, you can be trounced by a palmtop. Even the palmtop programs are now achieving draws against grandmasters.

Re:Strategy versus Tactics

[lkaos]

that a computer could easily trounce a human in any game involving only tactics.

Be careful with the word easily. Remember, programmers are only human too. A human must first master the game before he can write a program to beat anyone. There has to be a "perfect solution" as there is in tic-tac-toe found. A computer can assist in finding the perfect solution, but a programmer has to at least give it direction.

is the strategy that a human chess player would use also based on these millions of tiny tactical evaluations, only so subtle that he's not aware they're going on in the vast electrochemistry of his brain?

More or less. At least, this is the current thinking. The brain is just a big-ole circuit that produces an output when given inputs. The neat thing about the brain is that its output can be used again as inputs to allow the path to be optimized. Computers currently can't really do that.

making computers that can function like minds, or simply working really well with computers, I leave to you.

This is the basis of artificial intellegence research. I do believe though that we will need to advance more in biomechanics before we can do anything worthwhile in AI since it isn't particularily easy to replicate the ability for organic compounds to evolve and recreate themselves.

Then again, what we really should be asking is not how do we replicate biology, but what is it that is more effecient than biology for performing calculations?

A glimpse into the future.

[HanzoSan]

Slashdot News: "Krammik destroyed by Fritz, breaks computer and throws it out the window"

If you honestly believe Krammik stands a chance, you must not have seen the games with deep blue.

Anyone who is interested in playing chess can check out this chess site Chessline

Re:Chess programs demonstrate we don't know anythi

[Xyonz]

I think the answer here is that humans are writing these chess programs, and therefore they are limited bu the restraints of human thought. A freight locomotive on the other hand is only constricted by the laws of physics.

Internet Chess Orgy

[Tom7]

Forget playing against a computer and losing all the time. At SICO we're on the opposite end of the spectrum -- you can play against thousands of idiots all around the world. Tired of the same old boring pieces? Well, we've got new pieces too. In fact, since you lead such a busy life, you don't even have to play a whole game! Just play a single move, and back to work!