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