Slashdot Mirror
Man Vs Machine In Chess - Who Is Winning?
FFriedel writes "In a few weeks, the world's strongest player Garry Kasparov will take
on X3D Fritz in a high-profile man-machine
chess match. Who is the statistical favourite? Since computers have been steadily
improving and are now holding their own against the very strongest human players,
one would think it may be Fritz. Not necessarily, says statistician Jeff Sonas,
who doesn't believe computers will inevitably surpass the top humans, and presents empirical evidence to support his claim as part of a series of articles for ChessBase."
If you think you know something about computer chess but haven't read Behind Deep Blue by the man largely responsible for creating it, you need to correct your error asap. Did you know, for instance, that in 1997 Deep Blue had 480 chips running its chess program _in silicon_ with 30 rs/6000 nodes controlling them? Moore's law isn't going to let a 2 (4?) cpu PC catch up THAT fast, let alone when it's pure software.
BTW, the Fritz people make a big deal about beating deep blue in 1995. That would have been a big deal, but the program they beat was Deep Thought II ("Deep Blue Prototype"), not deep blue, a weaker program running on weaker hardware. The match was in Hong Kong where DT2 had persistent problems with their data line to the USA where DT2 was physically located.
Moxy Fruvous did an amusing take on the topic a few years ago at MIT on their U.S. tour. The discussion made it on their "Live Noise" album as "Kasparov vs. Deep Blue", and a transcript is available at http://www.fruvous.com/ln-lyr.html about 2/3 of the way down the page. (Warning, there are a few instances of adult language in the discussion)
chess is a finite problem, and although it's a very large finite problem, it's one that some day can be solved. I don't know why people care all that much about computers being able to beat humans, maybe they will just have to start playing each other. I'm only going to be worried when computers start writing more interesting stories than the top writers
Part of the problem is that Kasparov is this generation's GM. Kasparov plays very emotional games. He's not just looking to beat you in his first match; he's looking to utterly destroy, smash and humiliate you with a dramatic and embarrassing win.
This is a great strategy against people, but it's not so effective against computers. Kasparov is probably the worst chess master to pit against a machine since Ruy Lopez (I think he's won with the Ruy Lopez opening a few times, case in point: it's a brutal and humiliating play for the losing opponent).
Kasparov knows that the computer can "think through" future moves better than he can. Computers, in fact, do the opposite of human chess players: we set goals and try to find ways to get there while computers search through various ways to find a satisfactory goal they can achieve. So, Kasparov plays it very conservative and keeps himself out of any situations that give the computer too much range of foresight, which is why the Kasparov/computer matches tend to look like Verdun (though he's been surprised a few times).
Personally I'd like to see some of the younger generation take on the big programs. They tend to play more technically and less passionately than Kasparov and his generation.
All's true that is mistrusted
Not to get too off-topic, but there are also now several (increasing) prizes for beating top ranked players (well, rather, any professional player and occasionally there's a prize for beating a dan ranked amateur) in Go.
For those of you who are unfamiliar, there is an excellent, if somewhat dated, article that discusses some of the difficulties for getting a computer to play Go well. It also talks about Janice Kim, a 1 dan (professional) at the time (now a 3 dan), beating the then-best program when the computer had a 25 stone handicap. To give an idea, a 9 stone handicap in an experimental games between evenly matched professionals generates about 140 point advantage.
As I said, it is a bit dated (5 years old) and computers have improved, but we are still nowhere close to beating a professional.
Integrate Keynote and LaTeX
I was wondering a while ago if chess could be set out into a possibility tree with work such as seti@home where one players actions will always be counterable. Theoretically it's possible, but i haven't done the preliminary calcs to determine processing power necessary/time/etc. Your thoughts?
Since when has this country used intellectual elite as a pejorative term?
Computers are only good at chess for two reasons:
1) They can brute force the game. On the 8x8 board there is a very limited number of permissible moves at any given moment, and an even lower number of desirable ones.
2) They can easily tell if a move benefits them. Chess is a game where its very easy to look at the board and say who's winning. Board position, captured pieces, influence are all key points that anyone can spot at a glance.
In my eyes, this just isn't a challenge, but straightforward application of raw computing. If the programmers want to impress me, they'll create a program that can play Go. As of this post, there still isn't a program in existance that can consistantly defeat a shodan (beginning level pro). Why? The 19x19 board and the ability to play just about ANYWHERE on it makes the game much more difficult to brute force. Also, strategy is much more complicated and board positions take a very experienced player to accurately analyze (at least in games involving professional-level players).
No, Chess may become the dominion of the machines, but I won't consider it a statement of supremacy until they can beat us here. That should be the programmers' next challenge.
One thing that will keep people on top for a while is our inconsistancies. A computer works on logic, and can usually be predicted to do something. People, on the other hand, are spontanious, and use a different kind of logic. We also take risks that do not make sense. But if something is crazy enough, it could trick a computers. Because computers do not lie. They cannot lay traps and they cannot bluff.
Marvin knew: "Think of a number, any number..."
This guy has a very interesting write up about chess and probability. Worth a read.
While the total number of states in Tic Tac Toe is a boringly small finite number, the total number of states in chess is rather amusingly large. And by "amusingly large", I should point out that I'm a large number theorist.
How large is "amusingly large"? Around 10^150, if I remember my AI class correctly. Discarding entirely the problem of how you'd create a game tree of that size (given the cosmos has about 10^77 particles), let's just address the energy required to compute the table.
It requires an absolute minimum of kT*ln2, or about 3*10^-26 Joules, of energy to set a bit. Each cell on a chess board requires a minimum of four bits to store its state (it has to store a three-bit enum { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING } and a one-bit enum { BLACK, WHITE }). So for a 64-block chess grid, you're looking at 256 bits just to store state.
256 * 3*10^-26 = 7.7*10^-24
7.7 * 10^-24 * 10^150 = 7.7 * 10^126
Do you have any freaking clue how much energy 10^126 Joules is? It's frickin' huge. Like enough to cause a symmetry-breaking event which would propagate through the universe at the speed of light and utterly annihilate everything in its path, including the computer churning out the complete decision tree for chess.
I can see it now. When Judgment Day comes, it's all going to be because of a Slashdotter who thinks he knows a lot more about what computers can and can't do than he really does, and goes off to solve unsolvable problems without considering the thermodynamic consequences of his actions.
Typical for Slashdot.
Something the article doesn't touch on is that although chess grandmasters were caught off guard by the strength of chess computer's in the mid-90's, since then we have learned a tremendous amount about the computer's weak spots. The computer for example is very poor at playing in tight positions like some lines in the Caro-Kann and French defenses. Also many of the so-called hypermodern openings.
I imagine the new breed of young GM's like Ponmariov, Grischuk and Malakhov probably find the prospect of beating stock Fritz/Junior/Hiarcs rather boring. A few extra CPU's isn't going to make a big difference in terms of playing power. Much more effective is to spend time tuning the engine's opening book and that takes traditional GM's with novelties.
Kasparov should win this easily, though he did miss a trivial 2 move combination in a tournament recently so you never know...
There has been a chess message board discussion where the author of the article mooted his ideas last week. I write for ChessBase and worked on both of the last big man-machine matches (Kramnik-Fritz 2002 and Kasparov-Junior 2003).
For those here who claiming obvious Deep Blue superiority over current micros because of how many chips it had and how many positions per second it looked at, some chess knowledge would help. Deep Blue only played six games and all have been analyzed to death. We know two things. One is that Deep Blue beat Kasparov and that's the only thing most people care about, the result. The other is that Deep Blue's play was far from perfect.
Years of human and computer analysis can about as close as you can to the truth in chess. With that knowledge we can compare Deep Blue's moves to those of the current top programs such as Fritz and Junior. And we have, extensively. The bottom line is that they play better in many places, the same in others, and worse only in very few. The overall level of play by the micros in the same positions from the Deep Blue games is better. With Deep Blue in pieces that is the only way to compare the quality of their chess. Positions per second is interesting and not irrelevant, but time marches on and knowledge is important too.
While the humans in these matches obviously have some interest in saying that the program they are playing is the strongest, hundreds of other analysts don't. And Kasparov and Kramnik aren't going to make fools of themselves by recommending moves that could be easily shown to be inferior.
Kasparov played some of the most inconsistent and nervous chess of his life in the pressure-cooker match against Deep Blue in 1997. He resigned in a drawn position for the only time in his career and Deep Blue's other win, in the final game, came in a total mental collapse by Kasparov and was the shortest loss of his career in a serious game. All credit to the Deep Blue team, mission accomplished and all that, but it wasn't the greatest chess.
Meanwhile, humans studied and learned. Kasparov's attempts to baffle Deep Blue by playing intentionally inferior moves was ill-advised. That era was over, he just didn't know it. But computers still have their weaknesses, as Kramnik showed in the first half of the Bahrain match.
The top programs today running on the fastest micro hardware available play better chess than Deep Blue '97. But the top humans play better, and smarter, against them than Kasparov did in 97.
The bigger problem is that the computers aregetting their rankings solely by playing other computers (if I'm reading the article right). The ratings are dependant on who's in the pool of players.
Say the best computer in the set of computers always beats or draws the other computers. lets say it wins more than it draws. In that pool of players, it's rating will tend to creep up.
So the ratings aren't necessarily comparable. Take a 1700 player, throw him in a pool of only 1000 players - when his rating breaks 2200(after quite a few games), that doesn't mean he'll be able to consistently beat a 2000 player, because there's no one above him in the pool he gained the 2200 rating, to lose games against and keep his rating down where it belongs.
I've no doubt computer ratings are increasing, but if there's no humans in the pool they play with there is quite concievably an effect such as this, although it's probably not as extreme.
Code or be coded.
However, noting that the state-space size is large isn't really a very useful observation, since chess programs these days don't try to map out the entire tree of possible outcomes. Instead, they operate on neurodynamic programming techniques, which basically try to extract which "features" of the game are important and weigh those features to decide which moves to make. This significantly reduces the complexity of the system, but requires that the person writing the program have some intuition about which "features" are important. In chess, for example, these include such things as material balance, piece mobility, king safety, and other positional factors. A period of training is usually required as well, where basically the computer goes over a lot of games that grandmasters have played and tries to "learn" how to weigh the different features in order to choose the optimal move.
For those who are interested in reading further about this (yeah, yeah, this is Slashdot, if people can't RTFA what are the odds they'll want to pick up a book? :) ) a good place to start would be Chapter 6 of Bertsekas' "Dynamic Programming and Optimal Control".
The bold print giveth, and the fine print taketh away
Your first quote references Kasparov vs Computer
Your second quote references "strongest humans"
Basically, what you post states that computers are getting better via one person, but a few/many/some people that are getting better vs the computers. Therefore, no necessary contradiction.
Nowhere referenced is Kasparov vs the other guys.
We could take it as a given that Kasparov is better than all the other guys, but I reject that arguement. On the flip side, I also reject an arguement that says the other guys are better than than Kasparov because they are doing progressively doing better against the computers.
There are a couple of posts above re: pitting a computer against a more "technical player" than Kasparov. I think this could be interesting.
In short, no. The statements are not contradictory. Kasparov is not plural.
(BTW... in deference to the people that bitched about people being sexist, I mean "guys" to reference men AND dames. We cool on that?)
A human player may, in the same amount of time, only actually evaluate a few dozen board possibilities before making a single move, The human player can somehow eliminate even *considering* 99.9% of the possibilities, and even then the human often doesn't fair too badly, especially considering the odds against him.
Until computers can pull off this sort of "magic"*, no computer can ever be considered a match for a human player. It's no more astounding that a computer can occasionally (or even usually) beat a human at chess by considering more moves than a human player does than it is astounding that a pocket calculate can show you the value of pi to 8 decimal places with a single keystroke. That's not intelligence, just raw computation. Put another way, it's no more suprising than the fact that a heavyweight wrestler of lesser skill would have a good chance at being able to take down a more skilled featherweight.
* Clarke's law says any sufficiently advanced technology is indistinguishable from magic (and the corallory which says that magic is always indistinguishable from some sufficiently advanced technology).
File under 'M' for 'Manic ranting'