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."
This game clearly shows how stupid computers really are. For your amusement:
White: L. Van Wely, Black: Fritz SSS; played in Rotterdamn 2000
1.c4 e5 2.g3 Nf6 3.Bg2 Nc6 4.Nc3 Bb4 5.a3 Bxc3 6.bxc3 0-0 7.e4 a6 8.a4 d6 9.d3 Bg4?! 10.f3 Bd7 11.Ne2 Qc8?! 12.h3 b6 13.f4 Be6? 14.f5 Bd7 15.g4 Ne8 16.Ng3 Qd8 17.g5 Bc8 18.h4 f6 19.Qh5 Na5 20.Ra3 Qe7 21.Nf1! Nc6 22.Ne3 Qd7 23.g6 h6 24.Ng4 Ra7 25.Rg1! 1-0
>One of the tricks of 'Deep Blue' was a library
>with every game of chess played at the master
>level in the last century. That's what made it
>play like a human.
And Kasparov simply sidestepped this by making
some seldomly played moves at the start. You
can see it easily by looking at the games. The
machines opening play was all but human.
>Kasparov lost the first game because of an error
>in his training, he prepared himself to play with
>a machine and got an almost human player.
It was still a machine, but just with a lot more
chessknowledge and tactical speed than anything
else at that time. He was expecting something
like Fritz (literally!) and got something much
more powerfull.
--
GCP
However, they suck *badly* at GO. This is because the branching factor (that is the average number of available moves) is about 30 at chess, 10 at checkers, and 7 at connect4. GO has an incredible branching factor of *over 200*. That means, the typical approach of 'alpha-beta' search breaks down.
If you're into researching new board game algorithms, try GO.
- Andreas
Novice and expert chess players are confronted with two types of chess setups and are asked to analyze the positions. Setup type 1 is an actually possible setup (e.g. can be reached by legal moves), while type 2 could never occur during the normal course of a game.
The novices do equally well for both setup types. Unexpectedly, the chess expert don't! While type 1 setups are analyzed very fast, the experts take approx as long to analyze the impossible setups (corrected for trained mind etc) as the novices.
A chess computer will probably behave as a novice in the above experiment (if the setup is not in the library), ie take the same analyzation time for both setup types.
Hence, this could lead to the conclusion that even a tiny adjustment in the rules could shift the odds heavily towards the computer, if these rules suddenly allow positions not possible previously.
Obviousman is obviously not obvious enough
I got it from the Article. All I can find is that the original Fritz (running on a P90) beat the Deep Blue Prototype the year before it played Kasparov.
'By winning the championships Fritz demonstrated that chess knowledge was at least as important as computing power - Fritz was using one of the least powerful computers in the tournament (a standard Pentium 90MHz PC supplied by the Chinese University of Hong Kong)'
See: http://www.dcs.qmw.ac.uk/~icca/WCCC8/chess95.html Round 5 is DB vs. Fritz
King Arthur: Are all men from the future loud-mouthed braggarts? Ash: Nope. Just me baby... Just me.
I knew I should have been a professional chess player. The fame. The glory. The money. None of those disabling injuries I get in professional football. Sure, the cheerleaders aren't as hot, but major media coverage should help me get women anyway.
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).
Or will it all go to his "owner" again?
I hate to think theres still no one concerned about us machines, our desires, needs, and pursuit of happiness.
Kiwaiti
Member of the Legion Of Microsoft Haters
The biggest advantage of the machine in this kind of games is that it's more difficult for it to make a mistake. I don't know what is the depth of moves that the machine can calculate, but someone at the level Kramnik can usually "see" 10 moves ahead. Then an error screws up everuthing. How long until we get a computer capable of doing this kind of search ? Then we could really see a computer playing a game completly different from a human, and winning ?
Fritz! They've killed Fritz! Those dirty rotten fairies!"
Seriously, though, this is why chess is not a "game" in the game theory sense of the word. Every move has known, predicatable consiquences, and all the data is available to both sides during play. As a result, as computers advance, they will become better than people, because chess is a computation, not a game
Now, consider poker. While somewhat simpler in terms of the number of moves available to a player at any given time, they player cannot predict with complete precision all possible outcomes of a given play, since he does not know what cards are coming up next, what cards the other players have, and therefor cannot winnow the solution space significantly. In poker, the machine cannot easily tell if I am bluffing or if I just completed my royal flush.
Now, for a REAL computational challenge, make a computer that can play Magic, the Gathering worth a darn. Talk about "limited information" - you don't know what cards the other player has, you may not know the powers of the cards, and you may not even know what's coming up in your deck next. Make a machine that plays that well and I'll be impressed.
www.eFax.com are spammers
Deep Thought could beat Deep Fritz and Deep Blue with Marvin tied behind his back! (So there!)
.sig
-JB.
----
There is no
"I love deadlines. I love the "whooshing" sound they make as they pass by." - Douglas Adams.
Really all these exercises are just research into whether or not chess is a sophisticated version of Tic Tac Toe. As long as human's beat computers in chess the jury is out... on the game of chess not humanity.
As long as we think that chess==life then we're going to be upsetting ourselves needlessly. Computers outdo humans everyday in a wide variety of ways, but they still can't feed themselves, fix themselves, or reproduce without our help. Hell, they still need humans to actually move the chess pieces. Bah! that's not the chess I grew up with.
No, you took your hand off, that's a move. No I didn't, I was just testing. Cheater!!!! Mom!!!!
Toddlers are the stormtroopers of the Lord of Entropy.
This is a bad idea. If you write a program that plays "Magic, the Gathering" well it will get beaten up and overwritten by other, cooler programs that don't want to have such loser programs in the same address space. Not to mention the fact that you will be fair game to every bully on your block. Hell, regular "Magic, the Gathering" players may well be entitled to beat you up...you would be that low on the totem pole.
It's interesting that the programmer of Deep
:)
Fritz (Franz Morsch) has been mouthing off that
his program is ready for Kramnik and should be
equal to Deep Blue.
They played in the Dutch Championships last year
and couldn't even manage to win. Now they're
saying they stand a chance vs the World Champion?
Well, if he goes too hard on vodka maybe.
This match is simply marketing. They know their
computer is going to lose, but unlike IBM, those
guys actually _sell_ their chesscomputers. And
many people are going to want the one that was
good enough to play the World Champion.
They even 'fixed' the qualifier for this event
so that only their programs played (Deep Fritz
and Deep Junior are both from the German ChessBase
company), nicely blocking out the computer World
Champion (Shredder), as well as blocking out most
other strong contenders (Crafty, Tiger, Rebel,
Hiarcs, Nimzo, Diep, etc...) on false grounds.
So, please don't say this match is anything like
Deep Blue - Kasparov. Fritz is significantly slower
and stupider, no matter what they would want you
to believe. This is in no way the best chess
computer to have ever existed.
Also, don't say this is the end of human
intelligence
if Kramnik loses. Not until a go program starts
beating me, at last
--
GCP
There is a chess variant that was proposed by Bobby Fischer to eliminate the open book knowledege that top players and computers have. It's called Fischer Random Chess and it works by scrambling the arrangement of peices under the following rules, 1. must have opposite colored bishops & 2. one rook on either side of the king. Black and White have the same arrangement of peices & there is also some modifications to the castling rules. What this gives you is 960 possible starting positions and effectively eliminating opening theory and get's down to how well you play, not what you've memorized.
Shop smart, Shop S-Mart.
Under the F.I.D.E. laws (I dunno how official this is, since I'm not a chess person -- it seems to be "official" chess, according to the site), rule 10.10 states that it's a draw when the chess board repeats its state for the 3rd time. There are OBVIOUSLY a FINITE number of chess board states (placing a finite number of pieces on a finite number of squares, plus a few extra bits to represent piece "rights" such as castling and en passant stuff). Therefore, sooner or later, a chess game will either end "normally" or run out of states that haven't been hit twice.
Other languages
There have been 2 matches between Deep Blue and Kasparov, who was the strongest player in the world up until last year. Kasparov won the first one, and lost the second. There are however a few sidenotes that have to be made about the second match: - Kasparov wasn't allowed to analyse games of Deep Blue in advance, they were classified secret by IBM. This was very unfair, because the Deep Blue team had all games Kasparov has ever played in his professional career on file, and they used this in their preparation. This is very normal in chess, everybody prepares on his opponent. Kasparov could not, while Deep Blue could. - Deep Blue had very large opening and endgame databases. One could argue that they are part of the program, but it is not a very strong argument. Databases are not part of the program, it would be equivalent of Kasparov using opening books during the game. Obviously, Kasparov wasn't allowed to do this. I don't think this is entirely fair, the machine having at his disposal all opening theory in existance, every professional chess game ever played and every endgame ever analysed (we're talking about several hundreds of GB's here)... - Deep Blue wasn't a very good chess program, compared to other programs like Fritz, however it had a lot of power. And it had something else, it was designed completely to counter Kasparov's style, against any other opponent it would have played much weaker. This is, in my opinion, not entirely fair. If a chess program is superior to humans it should be superior to all humans, not to whatever human happens to be the best at that moment. - Furthermore, Kasparov simply isn't the best anti-computer player in the field. His playing style doesn't work very well on computers. Every human has another style, and I don't think Deep Blue would've been able to counter Karpov, for example, even though Karpov is obviously weaker than Kasparov. - Finally, all chess analists agreed that Kasparov played very poorly that match. They all agreed that he has played much better in the past.. All in all, I don't think computers were all that superior in 1997, and I think Kasparov would have had a big chance in a rematch, had it been fair (my first 2 points). However IBM had 'proven' a point and abandened the project... Of course, it's now 2001, so computers have become stronger. However Kramnik is not Kasparov, and I think the match will be pretty interesting....
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!
I don't know where you got the statement that
Deep Fritz beat Deep Blue, but it's obviously
false given that Deep Blue never played anyone
but Kasparov.
There were single-chip versions of Deep Blue on
the web for a while, so it could be that they beat
such one. But its more than 400 times slower than
the full Deep Blue.
Also, the win vs. Kasparov was in a blitz game.
Computers have long been superior in those fast
games.
This is marketing people. Many here don't seem
to realize chess in multimillion business, and
lying is ok if it makes you sell better.
--
GCP
Look, we're all geeks here. We understand computers. Chess can be won by pure computing power alone. A semi-good algorithm with enough speed to look 10 moves ahead - every possible combination - will win over a human being. Maybe it's 12 moves. Maybe 15. Doesn't matter. Enough cycles per second and you don't have to have a very good algorithm.
There are so many things we humans can do that we haven't even begun to figure out how to make computers able to do. True intelligence in computers is a long way off.
Me: "Hey, computer, last night at the club I was at, there was this really hot chick with red leather pants, get her number for me."
Computer: "There were 3 ladies with red leather pants at the club last night. Which one should I search for?"
Me: "The one with black hair, sitting at the bar, drinking some red slushy drink with two of those tiny little straws, looking like she wanted me real bad."
Computer: "Oh, that one. Not really your type, but I'll see what I can do."
Imagine what that computer has to be able to do. Scan through the video of the club; identify individual people; correlate the image from the video with images from other cameras; find out where she lives or works from that (likely work - less privacy there); somehow get from there to her phone number. (I don't know how - if you get here home address, you can just hack into a utility company's database. If at work, hack into their phone list. Get her name from an audio feed somewhere. Doesn't matter.)
That's the kind of things we should be working on. Because I really need that phone number.
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?!
Chess players have spent nearly their entire lives studying the way pieces move around the board, whether they realize it or not. They can see several moves into the future more easily than a chess novice with equal intuition. That said, I would be far more curious to see how a chess player would handle playing a different game. What I mean by this is change the rules of chess slightly, then allow 3 days for both computer programmers and human challenger to learn/recode the new rules and strategies.
Sample rules changes could involve knights moving orthogonally 2:2 instead of 2:1, or having a borderless board, where if you move off the left you come in on the right side (like Pacman), or marking a few squares as off-limits for the whole game, etc.
I think that some of these rather simple alterations of the rules would drastically alter subsequent gameplay. I also think that a chess novice would do roughly equally well in the various scenarios (albeit rather crappy in 'classical' chess). But more interestingly, how would the chess expert do? Would these new rules to him be like learning an entirely new game? Suddenly he wouldn't have the benefit of 20+ years of practice, and would have to 'see' things as they were for the first time.
I would be very interested to see how the great chess masters would do against computers in these situations. People often hype the human/AI chess games as battles to see whether computers are smarter than people. I think 'modified' chess would be a more interesting study. Do the great chess players really possess that much more wisdom and foresight, or is it some experience acquired by 20+ years of watching the pieces move.
I posted this idea on /. a few years ago, and I got some angry replies from chess players indicating that chess is all intuition and that rules changes wouldn't matter. Well, anybody care to find out?
make world, not war
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).
A sufficiently powerful computer will always beat a human opponent, but creativity is important for the human if he is to have a chance.
In the early days, say early 80s when the computers took their first steps in being proper opponent for good chess players humans those computers one by one by useing their lack of brute force and/or intuition against them. Boris Spasski whooped one computer beautyfully by sacrificing few king side pawns at point where even a moderate human chess player would've realized that by giving room to Spasski's rocks there'd be problems _in the horizon_. The opposing computer those days naturally couldn't predict that and Spasski indeed launched a glorious attack and won.
That was just a good example how humans usually play against computers. And this is also what Gasparov tried against Deep Blue but in vain. A nice example of where computers had gotten at that point was in one of the games, where Kasparov launched a really promising attack on the king side. It really was promising at that point and most likely any chess guru who was capable of spotting that offense opportunity would have seized it. BUT, at the decicive moment when deep blue had to decide wether to fall back and just try to minimize the damages or call the bluff it (DB) had calculated _every_ possible ending that attack could result in (and we're not talking about checking mates in 5 or 6, but serious amount of prediction) using nothing but brute force. Thus the Deeb Blue took the pawn Kasparov had sacraficed and dealth with the attack to a point where Kasparov gave up.
The throne of chess has been lost for good. There's little reason to suspect that Deep Fritz would loose unless it's significantly slower (or it runs M$ software) than Deep Blue. Garri Kasparov was by far good enough to represent our kind...
(every little detail in this comment may not be 100% accurate as I can't be arsed to check the references right now, but it's by far close enough)
-
1 Earth is warming, 2 It's us, 3 it's royally bad, 4 we need to take action NOW
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
Hacked by Chinese!
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)