Slashdot Mirror

← Back to Stories (view on slashdot.org)

Chess: Man vs. Machine Debate Continues

Posted by Hemos on from the the-battle-rages-on dept.

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.

11 of 295 comments (clear)

  1. New Turing Tests by KFury · · Score: 5, Interesting

    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.

    --

    Kevin Fox
  2. Programming is not creative? by hij · · Score: 5, Interesting
    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!

    --
    Believe nothing -- Buddha
  3. Limits of computers? by adam613 · · Score: 5, Interesting

    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?

    1. Re:Limits of computers? by sh4de · · Score: 5, Interesting

      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.

    2. Re:Limits of computers? by sphealey · · Score: 5, Informative
      There's only a limited number of positions. You can enumerate them and then 'solve' the game in the same way we generate endgame tablebases. But we lack storage and processing power for many many many years to come.
      The number of possible chess games isn't known excatly, but since even the lower estimates approach the number of atoms in the known universe we will be waiting a long time for enough processing power and memory to enumerate every possible game!

      sPh

    3. Re:Limits of computers? by Grond · · Score: 5, Interesting

      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) :)

  4. Re:hm by Skuto · · Score: 5, Informative

    >From someone who has played them, how does Chess
    >compare to Go or Shogi in terms of depth and
    >style of play?

    I've played all three and written strong programs to play two of them, but this still is a hard question.

    Go is by far the deepest. The current top programs play at the level of a (rather weak) club player. It's got a huge branching factor (number of possible moves) which makes any brute or semi-brute force appraoch (what is used for chess) impossible. Most programs around right now are based on pattern recognition.

    Funny thing is, the game is by far the simplest. John Tromp (the guy that wrote the 'shorter turing machine' that was posted to /. a few weeks ago) designed a complete ruleset that's only a few lines long. In practise, there are many rulesets, most of them because of tradition. This is somewhat problematic when making a program, because some rulesets are simply not complete.

    Playing go is a very nice mixture of tactics and strategy. One other thing that's very nice about it is that there is a very good handicap system. The games can always be close, even against much stronger players.

    Chess, well, it's mostly about tactics. Of course positional understanding matters a lot, but it's actually rather insignificant compared to the tactical part. Mostly due to continious small advances in technique and hardware, we've now got programs that are able to search about 16 half-moves (move by one side) deep. That'll nearly always take care of the tactical part. Programming strategical understanding is much harder, but a lot of progress is being made in the latter. Especially the latest generation of programs took a big step forward. We've got computers that can successfully compete with the very best humans.

    Shogi I've only played once, but I've been working a lot on a chess variant that behaves like Shogi in the past. (captured pieces can be dropped) It's got almost double the branching factor of chess, and hence is somewhere halfway between go and chess. The big issue with it is that it is also very tactical, unlike go. Even though the brute force depth of current programs isn't great, they can extend mating lines very well. And mates are important in shogi/dropchess :) I would have to check for the current state of the art, but I believe the top programs are quite competitive here.

    --
    GCP

  5. He's going to play against a boxed product by Animats · · Score: 5, Interesting
    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.

  6. Grandmasters can tell computers and humans apart by iskander · · Score: 5, Insightful

    Grandmasters can in fact tell whether their oponent is a computer, sometimes even after playing just a single game, and certainly by the end of a match. In fact, I believe Kasparov lost to Deep Blue precisely because he counted on the computeresque behavior of his opponent when designing his strategy. If you read the article, you will learn that Kramnik can tell computer programs apart by their style, and that he thinks Fritz is becoming more human-like in its behavior, from which I infer that he can still identify its style as computeresque on some level.

    So, the test you propose has already been carried out, and the machines "failed". This may have more to do with the fact that the people who write chess playing programs are more concerned with the programs' ability to win than they are with the programs' ability to emulate the playing style of humans. If humans could calculate better [Note: "calculate" has a precise technical meaning in chess] or chess playing computer programs were slower and considerably more stateful, their respective styles might be much more similar and your test, therefore, be met.

    My own belief is that the ability to play chess well, let alone the ability to play chess in the style of a particular grandmaster, is not an accurate or even adequate measure of intelligence, so I will not be particularly hurt when the day comes on which computers at last surpass our chess playing skills, just as they have surpassed our (numerical) computational skills.

  7. Re:Strategy versus Tactics by Spy+Hunter · · Score: 5, Insightful
    It's been well known since, well, before I was born, that a computer could easily trounce a human in any game involving only tactics.

    Well known, perhaps, by people who have never heard of Go.

    --
    main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
  8. Internet Chess Orgy by Tom7 · · Score: 5, Interesting

    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!