Slashdot Mirror
Brain vs. Computer: Place Your Bets
dev_null_ziggy writes: "CNN reports that the current chess guru is going up against a supercomputer, amusingly titled 'Deep Fritz.' The match is scheduled for October, and the current champion, Vladimir Kramnik, stands to win $1 Million dollars if he wins. Of course, since he'll be snagging $800k for a draw, and $600k for a loss ... I'll give two to one odds on the machine."
A game is a draw is there have been no pawn moves and no captures for 50 moves each (except in special conditions). As pawns can only move forward there is a finite number of moves until all pawns must reach the eighth rank, at which point the game must end in fifty moves, or a piece must be taken. Then the maximum length of the game is (maximum number of pawn moves until last pawn reaches eighth rank * 50) + (50 * number of non-kings after last pawn is promoted).
The special condition mentioned above is where the game can go beyond 50 moves if there is known to be a forced win - King, Rook, and Bishop vs King and Two Knights can go on for 223 moves between captures.
Another way of looking at it is that there are only a finite number of legal chess positions. If any of these appear three times in one game then it is a draw (if you slightly generalise position to include potential moves from that position - pieces can be in the same position of the chess board but have different legal moves: en passant and castling are the two exmaples where this happens).
And in the end its worth remembering that for now, at least, machines are still just intermediaries. Chess is not a strong AI problem, although playing like a human (as opposed to as well as/better than a human) might be. Kasparov wasn't just going against a machine, he was going against decades of IBM technological advancement, half a dozen engineers and an International Grandmaster (Joel Benjamin, part of the IBM development team). All told I think he did pretty well. But I'd bet in this match the CPU gets its clock cleaned.
It Is the Nature of Information to Transgress Artificial Boundaries
Consider this, though: Supposing I know rules of chess, and am a decent player by the "livingroom" standard, but not really someone who could compete at much of any level. But I do understand the (finite) rules well, and I do have some concept of what it means to win or lose, and the relative value of the pieces. Since a computer is (inherently) a state machine, and a fast one at that, I could simply program it with the ability to consider many, many possible lines of play, to some arbitrary depth, and then compare the results of those hypothetical situations. What you'd end up with is a tree of possibilities, some branches of which would contain more "good" than "bad" situations. The program would be intstucted to select the branch with the most favourable overall evaluation, and in all likelyhood it could kick my butt every time (the "deeper" it considers, the more my butt gets kicked...). While this could certainly be computationally intensive, I don't think it's much that the average PC couldn't handle at a relatively shallow "lookahead" depth, and a big multiprocessor machine could certainly take the concept much furthur.
As it is, I think that what I have described is, roughly, how home PC chess programs work. Of course there has been some tweaking and refining, and probably a hell of a lot of precalculation of common scenarios on the home PC products - so that it's nice and fast and doesn't need a Cray. I'm not sure how Deep Fritz works, but I'm fairly certain it does something similar on some level (Hence the name?).
The advantage that computers tend to have over people in this kind of thing should be pretty obvious: most people can't accuratly remember that much stuff! Naturally, human creativity makes a big difference, as does talent and experience, but the computer being able to consider so many options so quickly and accurately makes up for a lot, and should allow it to surpass it's creators fairly easily (unless it's creators are Grand Masters!).
Behold the Power of Cheese!
Computer chess suffers many limitations that human beings do not. These limits are being extended, but they still exist and the human being in this match should not be counted out.
Many people think that since IBM's Deep Blue beat Kasparov that the debate has been settled that computers are better than people. However, there where some aspects of the way that match was played that gave the computer a decided advantage. Kasparov never got a chance to see any of Deep Blue's games. Kasparov never got a chance to play any warm up matches against Deep Blue. In otherwords, Kasparov went into the match "blind" as far as his opponent was concerned.
Deep Blue, on the other hand, had complete access to every professional game that Kasparov ever played, and a team of GM's working with the programmers to twink the machine to take advantages of weaknesses pin-pointed in Kasparov's games. In match play, preparation is the key to success. Against Deep Blue, Kasparov wasn't allowed to prepare.
This match is decidedly different. Kramnik has been given a copy of the program and the hardware to run it. He has been given time to analyze how the program plays and to see what weakness it has.
Moreover, Kramnik is a very positional player, whereas Kasparov was a very tactical player. Computers excel at complex tactics, even as good as Kasparov was, he can't out calculate a computer. However, that isn't the only way to play chess. Kramnik excels at finding positional improvements that will see their point well beyond the analysis horizon of the computer.
Kramnik has a very strong record against some of the best computers in the world. Including Fritz and Deep Junior - too offerings from the same company that makes Deep Fritz.
It is simply ignorance which would allow anyone to think that at this point in time the outcome of this match is a foregone conclussion. Certainly at some point in time the computers will be far better than people at Chess. But it is not the case that we are at that point today.
And for chess players and fans, this match promises to provide some very interesting games that will be well worth studying. And perhaps that aesthetic aspect is actually the point?!
This is nothing unusual. In many chess tournaments, even the loser still wins a sizeable amount of money. Consider it as a kind of gage to remunerate their willingness to participate (and to risk some of their prestige if losing).
This is a good poing, but you ruin it with:
Every game that is possible has been played before.
Chess is a finite game, but I think you're underestimating how big that finite area of 64 squares really is.
A sufficiently powerful computer will always beat a human opponent, but creativity is important for the human if he is to have a chance. As I understand it, great human chess players don't play like computers, they play like great human chess players.
Even if this guy should beat the computer, that should not lead anyone to having illusions about the future. Eventually, computer chess superiority will be a fact. Even though the program running on Deep Blue could beat Kasparov, that day is not today. The very fact that we are unsure whether Validimir Kramnik or the computer will win clearly proves this.
One reason that computers inevitably will beat us humans is that each year, computers get exponentially faster, which means the chess programs can search linearly deeper in the game search tree. It's simply a matter of waiting untill they are unbeatable.
However, that wait might be very long, but to top things over, algorithms are improving too. Some have thought in the past that our game-tree search algorithms were pretty close to optimal, but for example some of Aske Plaat's research clearly shows that this is far from the case, and that the old predictions about optimal performance was based on too simple and fundamentally unsound principles. Substantial improvements can be made. (not that I have anything to do with him. I don't know him and live in another country)
Even more important is the fact that we need not search the full search tree (indeed Deep Blue did not, using instead something called singular extensions). Rather, if we can make a heuristic that tells us which parts of the search tree are "interesting" we can skip the rest and only concentrate on those areas. In this way, computer chess is becoming a little more like human chess (though not much). The point is, as those "this part of the tree is interesting" heuristics get better, so will computer chess programs get better.
In short, the future of computer chess is bright, and we might have only seen the tip of the iceberg. Human superiority or even something resembling it simply will not last. Chess will neither be the first nor the last game where computers will always beat a human.
Bjarke Roune
The concept of computers becoming "smart" is a bit vague. While accepting that modern computers may appear smarter than their predecessors they aren't. Its just that as processor speeds increase more instructions can be done in a finite period of time and therefore the program can evaluate more information/possibility combinations making you think its smarter. The IBM machine which beat the Grand Master had been programmed with the assistance of 10 other grand masters to look for certain combinations which would lead to victory so it wasnt just evaluating every possibility but only those likely to result in a win.
As to taking away peoples jobs of course computers will. Most jobs are boring, dull and totally pointless. Would you want to spend your entire career screwing nuts onto wheels in some car manufacturing plant or actually designing the next generation of cars while a robot did the dull stuff?
Strange though it may seem, everytime computers take away jobs people become better trained and get to do things which they wouldn't have otherwise. Look at the increases in higher education in the past few decades, the improvements in the standard of living for the majority of people, would you give it up for dumber computers?
And in answer to your final question: The world is becoming more complex. Fun isn't it? 8)