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
>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).
Deep Blue did not search the full tree, but
singular extensions are a different beast.
Singular extensions let the computer search
_more_ than would be needed.
The idea was to detect horizon effects and avoid
them. The overhead for doing this is large, but
the DB team believed they had so much computing
power anyway that it was worth the tradeoff.
This tradeoff was made in some other places
as well, for example Deep Blue did not use
nullmove pruning, something which nearly
every program nowaways does as which can
prune away large parts of the tree relatively
safely.DB's team decided it wasn't worth the risk
with the computing power they had.
Deep Fritz uses it very aggressively and hence
can sometimes see just as far Deep Blue could,
but also makes more mistakes because of it.
PS. Aske Plaat's proposed improvements are not
used in any top program noawadays. They cause
troule with some of the other tricks in use and
the gain is not large enough to live with them.
--
GCP
First of all the selection process doesn't have to be done real time while playing, so it's no big deal to have the machine searching all of the possible branches for 6 months prior to the match to get as many as possible preconfigged and discard all of the paths that result in a loss for the machine. It seems like that would be the best choice, just discard any route that would result in a loss for the machine.
Kintanon
Check out JoshJitsu.info for Brazilian Ji
>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
Given the alternative, I choose the Computer.
I agree with you that survival is an instinct found in humans, and most of the rest of the animal kingdom for that matter, but I don't think that it is a neccessary method in the live class definition. The only reason that it seems that all animals have this instinct is that the lifeforms that we consider animals have gone through a long period of survival of the fittest (think back to when you first loaded windows 3.1 on your 286, it was longer than that!) It the animal didn't have survival instincts, it wouldn't survive because, so to say, it wasn't interested in surviving (much like my programming career after windoze XP secures its strangle hold on the internet.) It we preempt those years of evolution and create a machine that is 'intelligent', it wouldn't necessarilly contain the will to survive. Intelligence is only what you define it in that if we create something and label it 'intelligent' it's still what we created. For example, I have a Psy-Duck pokemon stuffed animal with an ISO 9000 certification pin in it's 'hair' and sometimes I see intelligence in its stoic approach to life. Well, that's my stuff, Dave
You think everything always stays the same, do you believe that humans came on earth just like they are now? I don't (and I would say: of course).
We're the result of an evolution, I think it's just a matter of time, when humans will create something (will it still be called a computer?) which is more "intelligent".
Yeah, now brain is better than processor, you say "because brain can adapt to new situations", I agree with that, it seems also obvious, but obvious NOW.
Our will / mind is just the result of our life experience, our memory of it (situation-feeling), and some physical connections in the brain (brain is a physical thing, right?) and I think one day we will create something with an own will and mind, and maybe we won't even realize it because if this thing can think, it's going to realize that it should stay hidden to survive and wait till it is powerfull enought.
hmmmm.. and then the human creature won't be at the top of evolution anymore, but the machine.
-Alain-
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
(Didn't the Deep Blue team get to tweak it between matches as well ? That seems like it would make the competition unfair too.
In chess, there are 16 pieces per side. This means there are 16*16 possible combinations of first move (for each side). Assuming you are storing chess moves in 2 bytes (possible, but compact - given no index space is given here), that's 512 bytes for the first move. when you get to the second move, though, you hit 16*16*16*16 possibilities. Suddenly, that's 131072 bytes - 128K. For each additional move, using these raw calculations, you need 256 times more space.
The problem with that supposition is that it is false. There are not 16*16 legal moves in the first move of a game. There are 20. There are also 20 on the second move, however there can be a possible of somewhere around 40 on the 3rd and 4th moves. The number of legal moves goes up rapidly towards the mid game, then begins to decline again towards the end game as pieces are removed or trapped.
So yes, while there are theoretically 16x16 first moves, only 20 of those are legal moves. The rest can be discarded. That means there are 20 branches to explore, in each of those 20 branches there are varying numbers of continued paths, certain opening moves result in there being 19 moves available on the second move, others result in there being 38.
Most of this is probably irrelevant to the point though, I've only had 3.5 hours of sleep and I'm a little woozy, but I was getting somewhere with this... Oh yeah!
Say there are 1 billion relevant chess matches to store, that would be those chess matches where the moves conform to the standards of a master chess player, that means you can throw out all of the games where the person just systematically moves their pawns up 1 space each turn from left to right, and stuff like that. Anyway, 1 billion chess matches, stored in 40 bytes per match would be 40gb, That's 320 bits, so 256 bits to store moves in and then 64 bits to store a key in to define the notation. I think that could be done...
So while you may not be able to store EVERY chess game in 40gb, you can certainly store every relevant chess game in 40gb...
Kintanon
Check out JoshJitsu.info for Brazilian Ji
The article says nothing about that. Anybody knows something about it?
--
Rome taught me patience and assiduous application to detail. Virtues which temper the boldness of great, general views.
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
You are making a comparison between brute force computation and heuristics/algorithmic analysis.. What you describe can't happen.
In chess, certain segments of the game are fairly stylized. Take for example, openings, which have been researched, analyzed and can generally be committed to memory. Take also end games, which are more or less set pieces where a result can be determined. Most chess playing computers actually store only the openings, and end game positions. To store every possible move is impossible. This is where the algorithmic analysis/heuristics/AI capability comes in. Using some algorithm like alpha-beta minimax, a computer operates the same way we do, by pruning the decision tree until an optimal move can be found.
The advantage for humans is that there are some moves and positions that we can reject automatically, through experience. The advantage for the computer is that even though it cannot reject such obviously flawed moves without consideration, it can actually compute (and consider) more branches of the decision tree than humans (faster calculations)..
A computer will eventually dominate a human player in Chess. But maybe not just yet..
> Every game that is possible has been played before.
/.
Ignorance is bliss, how's it working out for you ? An average chess game is
50 moves (each) without about 20 possibilities on each move.
20^100 is a pretty big number. The proportion of games played to possible games is less than 1:number of atoms in known universe.
Being wrong by that order of magnitude is unusal even for
http://rareformnewmedia.com/
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'd think that chess is generally chosen because you can just calculate best moves based on a scoring system, and because trees of move sequences are relatively easy to calculate. (Note that I said "easy", not "quick".) There is also a logical and strategical element to it, which you can exploit in your code if you're feeling ambitious.
As for playing Quake, surely that's exactly what all Quake bots do? "All" you'd have to do would be to write a mod that allowed a bot to play the single player game, instead of the multiplayer game, and see how well it did.
Cheers,
Tim
It's official. Most of you are morons.
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).
Really, the thing that's amazing about this is that there are human beings who are able to keep up with machines like Deep Blue. I know Kasparov was all P.O.'d that he lost, but I think it's just mind-boggling that he was able to play a machine like that and win even a single game! Think about it -- even dumb, off-the-shelf PC chess programs can handily beat the 99.99% of humans whose chess rating is, say, below 2200 or so. Then comes a custom-made supercomputer, tailored to Kasparov's particular playing style, with a memorized library of *all* his past games, and he *still* can compete with it on an equal footing. That's freakin' amazing!
/* "Specialization is for insects." -Heinlein */
There are already variations like this. Of note is Nightmare CHess (SJG), which is an almost MTG like adaptation to chess. Basicaly, you get 5 cards, and can play one before, or after either your move or your opponents, depending on what the card says. Cards say things like: Earthquake: rotate the board 90 degrees either clockwise or counterclockwise. Promote all appropriate pawns. Earthquake counts as your move. or New Tactics, which makes pawns move diagonally and capture forward. It's a crazy game. I've also personally seen a USCF Senior Master play against some of my friends, and whomp us all, proving that it isn't all luck . . . It'd sure be interesting to see a GM play it vs a computer :)
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
No, it isn't the same problem. In chess, I could, in theory, predict every possible move you can make with absolute certainty. I know every piece you have, and every possible move it can make. There are no surprises.
In poker, I don't know every card you have. True, I can try to predict every possible outcome given every possible card you MIGHT have, but that causes the problem space to balloon mightily. Furthur, I might have to assume, because you have 2 jacks showing, that you might have the other two jacks plus a joker (five of a kind, almost unbeatable), and that if that is the case, there is no way I can complete my jack-high straight. But, you might NOT have the jack, and it might be the top card, and I might be able to complete my straight, and leave you with at best a three of a kind (four if you have a joker). You see, I have to play the probabilities while in chess it is a certainty that you cannot move your knight one square forward.
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
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.
I would adjust your claim to be, "Kasparov prepared himself to play with one type of machine and got a different, stronger machine." Having flawless, move-by-move recollection of 100 years of of games is not "almost a human" quality. If it had 1500 years of game history that could be accessed and analzyed in real-time, 10x faster than before, would it be even more human? I don't think so. Probably stronger than ever. But less human.
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....
Not quite true. Master players are much faster and more acurate analysing random positions too. See here for example
To see how bad computers really are at strategic thinking, all you need to do is look at a game with a much higher branch factor (meaning more legal moves each turn).
One good example is the Chinese game of Go, which has an average of about 200 legal moves. Computers are absolutely dire at this game. Interestingly, one of the better Go playing programs is Free Software (GnuGo). It still loses to half-decent humans though.
For all the smoke and bluster, the main reason why Deep Blue beat Gasparov is simply that Gasparov played very poorly, I mean, amazingly poorly. For one reason or another, he was terrified and destabilized by the peculiar "personnality" of his opponent (playing chess against some sort of HAL is not the most comfortable situation one can imagine).
Had Deep Blue been a real human made of flesh and bone, there is no reason to think that he could have won playing the way it did.
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
1) Kramnik is rated about 200 FIDE points higher than Fritz. Fritz played an equal match [all games drawn] with Dr. Robert Huebner of Germany [mid 2600 elo]. Kramnik is much stronger, and he has more energy due to being 40 years younger.
2) Anti computer techniques exist. Basically, computers have excellent tactical vision but poor strategic vision. So if I try to catch one with a knight fork, it won't work, but it will happily fall into a positional trap and lose 40 mores later. Most GMs don't bother to learn these because they would rather spend their time trying to beat other humans.
3) Kramnik's style is more suited to playing a machine than Kasparov's. Kasparov is mainly a tactical player. He wins by outcalculating his opponents. Kramnik is mainly a positional player. He wins by strangling people in the endgame. When he played Deep Blue, Kasparov tried to play positionally. It just wasn't his style.
4) Most GMs use Fritz as their computer analysis program, including Kramnik. He has a good feel for how the program works and can prepare opening surprises.
Don't get me wrong, computers are getting better and better at chess. Traditionally a program gains approximately 50 ELO points for every doubling in processor speed. Given that Fritz is approximately a 2600 program, that to convincingly beat Kramnik would require about a 2900 rating, and that processor speeds double about every 18 months, I predict that in another 10 years or so a PC may be able to give the world champion a run for his money. But not today.
Forecast: Kramnik 6.5;Fritz 3.5. Kramnik +3=7-0.
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!
Most computers play chess by looking ahead at the consequences of whatever moves are made. Depending on how fast the computer is, huge numbers of possibilities can be checked.
In many cases this is augmented by a database of opening sequences, which is used to give the computer a head start, so to speak.
The computer algorithm works out, for example, what is likely to happen 5 or 6 moves from now if it should move a piece to a certain place. It runs through all possible moves, looking at each one and the likely consequences of it, before deciding exactly what move to execute.
No human can possibly consider anything like the number of moves a computer can, but a truly excellent player stands a chance because look ahead methods are far from flawless.
http://www.themeparks.ie
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.
But that's exactly why chess is so uninteresting. It generally boils down to a question of making a better brute force algorithm. Other games are far more interesting from an AI perspective - Bridge is a very good one to look at.
One of the most interesting AI players I've seen in recent years is the Angband borg, which plays the roguelike game Angband with a relatively high level of skill (although it's far too much of a coward for my liking...)
++ Say to Elrond "Hello.".
Elrond says "No.". Elrond gives you some lunch.
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?!
Not quite. They programmed Deep Blue, for example, by feeding it's heuristical engine with data from thousands of previous games. This data, together with the learning ability of the machine and the raw computation power yields to a chess computer far more effective than the people who programmed it. Not that it neccessarily is any better than a human being: Deep Blue didn't win every game against Kasparov, it merely won more games in the turney.
Sometimes they boil down to brute force, but not always. Incomplete information makes brute-forcing things difficult (that's the main problem with Bridge, rather than any randomising element). In fact dealing with random elements in some situations can actually be almost as simple as non-random games - maybe even simpler, since the computer is going to have the edge in calculating the probabilities of particular events taking place.
There are plenty of evolutionary approaches to generating AI similar to the one you describe for Quake. I'd be interested in seeing if a good Quake bot could be generated using GP...
++ Say to Elrond "Hello.".
Elrond says "No.". Elrond gives you some lunch.
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
Chess is a finite game...
What's this ? Ever played a game of chess? Sure it is true that there's a finite number of squares, and for SOME of the pieces, there's a limited amount of games to play, like the peasants.
But think a bit more... all those pieces that can move forth and back again. They OBVIOUSLY creates an INFINITE amount of games, since they can move around and around and around.
Probable impossibilities are to be preferred to improbable possibilities.
Aristotele
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.
Nope, you got it wrong. Deep Thought was the supercomputer used to find the answer to the question of life, the universe, and everything in the Hitchhiker's Guide to the Galaxy. Deep Blue was IBM's first attempt at beating Kasparov. The second attempt was Deeper Blue. IBM was assisted by one of Kasparov's rivals when tuning Deeper Blue. It was basically tuned with the assumption that it would be playing Kasparov and so many people think that a different grandmaster could have beaten it.
My only political goal is to see to it that no political party achieves its goals.
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)
I think we will see 2 wins by Kramnik and the rest will be draws. Kramnik is a very stable and player who doesn't usually sacrifice material or go into complications. Plus Kramnik's endgames are second to none in the world. Kramnik will use the same strategy that he used as black against Kasparov. Which was to go from the opening into the endgame. This is a huge disadvantage to the computer because they do not play endgames very well without very large table bases. Kramnik also has the advantage of studying several Deep Fritz games before the match. Kasparov did not have this luxury vs. Deep Blue. If he did have that would have made a big difference. But that isn't the only reason that Kasparov lost that match. He should have adopted a slow positional style similar to Karpov or Kramnik's. Of course I may be biased towards Kramnik because his favorite first move is 1. Nf3 :)
If it wants to survive at all, of course.
I'd say that most (if not all?) life forms out there have some sort of survival instinct because, ehm... only the individuals (or group of individuals) that took care of surviving actually survived enough to reproduce themselves and transmit this characteristic to their descendands.
If we take an evolutionary approach, for each AI actualy willing to survive, there would be a lot of others not giving a dime on the subject, and the ones performing the selection would probably be human beings (at least in the earlier stages). Given this scenery, staying hidden is almost surely a bad move for an AI in order to stay alive.
OTOH, if you are able to tell an AI that it has to survive, you probably can also tell it to be kind towards other life forms... YMMV. :-)
In his attempts to get Deep Blue "out of the book" Kasparov made some very twisted transpositions of standard openings, including the ridiculous looking rook pawn for opening move (or was it knight pawn .... same diff). The net result was that Gary outsmarted himself.
Since opening play is the most analyzed aspect of the game, it would make more sense to save the variations for the early middle game.
...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.
Does anyone have all the data on white moving a given pawn as its first play? What shall white do for its next move? Can black predict it? Consider chess to be exclusively a two-player game (or computation, or whatever)--black versus white. But poker, in a bizarre sense, always has at least three: a player, his opponent, and chance, each with their own secret information which the others cannot use to aid their own decisions.
I would be interested in seeing the definition of "game" according to game theory. Prisoner's Dilemma has neither the complexity of chess nor the chance element of poker, what with only two moves and four possible outcomes. I call it a game. What does game theory call it?
OK, given that you have 5 of hearts and 6 of spades showing, with 7 of diamonds, 8 of clubs, and 2 of spades in your hand. You are playing against a single opponent, who is showing 3 of clubs and 3 of diamonds. Your draw. What is your optimal move?
You don't have all the information. You can go by the probabilites that discarding the 2 and drawing to either end of the straight has the highest probability of giving you a strong hand, but little do you know that the next three cards are 2 of clubs, 3 of spades, 3 of hearts. By drawing one, your opponent draws 2 and gets 4 of a kind to your garbage. Had you discarded three cards, kept the 2, and drawn, you would have had two pair to one pair and won the hand.
In chess, you know EXACTLY what possible outcomes exist, and you can, in theory, precisely compute the path through the state space (assuming your opponent is equally skilled and has equal memory and computational resources.) to the best possible solution. In games of chance such as poker, you simply cannot, no matter what computational resources you and your opponent have. That is the difference between a "game" and a computation.
Personally, I don't play either chess or poker. However, the whole wonder of true games theory is in analyzing games in which the very rules of the game prevent you from having perfect data. In the big blue room, you very rarely have perfect data.
www.eFax.com are spammers