Slashdot Mirror
Kasparov OpEd On His Latest Match
molrak writes "Garry Kasparov has written his thoughts and observations on the difference between his recent battle with Deep Junior as opposed to his battle against Deep Blue, including some of the fundamental differences between the two programs. If you missed out on the event, you can catch up with it at the site of the event's sponsor, including both 2d and 3d viewing options. (Note, viewing options require both site registration with x3dworld and proprietary Microsoft software.)"
GameTab - Game Reviews Database
Coming up with a chess program to beat Kasparov mercilessly just isn't fun anymore. I say we put more research into writing a chess program that will make him cry while beating him mercilessly
Bowie J. Poag
I guess you never heard of flash.
If you mod me down the terrorists will have won
"Note, viewing options require both site registration with x3dworld and proprietary Microsoft software."
Even if I already have my own 3d specs?
Kasparov seems to think that making a powerful chess machine would constitute creating a machine with the power to "think." I hardly believe that to be correct, and moreover .. with enough proccessing power, a computer could map out chess moves far further into the future than kasparov could ever hope to.
.. where does one go after they realise that chess is only a little game?
I guess the real question has more to do with
If it were as simple as "the computer is no better at chess than those who programmed it" well then those folk be better than Kasparov. I'm guessing even that whole Deep Jr. team might not be so convincing playing (collectively) as humans against Kasparov.
What do you think of as a practical application, by the way? (Serious question)
Perhaps a better reason is so that once you've given away all your personal information just to register to the site you don't get surprised by the fact that it won't work on your Mac or Linux box. And seriously, Flash has been able to do 3D representations with 3rd party rendering software a long time.
I don't "get" the fascination people have with computers playing chess. Searching a game tree is not something I find overly impressive. The root problem (the tree searching algorithms and such) is somewhat interesting, but the computer isn't playing chess in the same way as a person. I don't really care how far down into a tree a modern processor has time to search. It doesn't indicate any sort of "intelligence" in the holy grail sense of AI. Chess is a very limited, structured problem.
My calculator can find nth roots faster and with greater precision than I can...should I be fascinated by that as well?
I'll be truly impressed when a computer can show the creativity necessary to beat Bobby Fischer at developing crackpot political theories.
-- "The reward of suffering is experience." - Aeschylus
The submitter didn't scour the web properly. You can view the games with professional commentaries with nothing more than a Javascript enabled browser at these links:
Amir Ban annotation
Karsten Müller et al
Kasparov really socks it to IBM in that article. I'm surprised at this reaction, considering that they probably paid him a LOT of money to go toe-to-toe with Deep Blue.
On the other hand, it was pretty shallow of IBM to barely beat Kasparov, brag about it, and then DISMANTLE the historic machine! Considering the would-be artifact status of Deep Blue, I would have expected more from these people.
At any rate, I'm just glad to see that the brute force approach is being abandoned for better heuristics. Anyone can write minimax for chess, the only special that IBM did was dump a couple million into hardware.
njord
Chessbase has an interesting interview with Shay Bushinsky, one of the programmers of Junior.
I'm not a nerd, nerds are smart!
For instance, there are more lines for 1. e4 than any other and some of those lines, if played right, can go 40 moves and more. At that point the opening overlaps the middle and the only way to be win by suprise (read creativity) is to find a new line. But in creating the new line - which can amount to one different move throughout the sequence that creates new possibilities, or lines - you are, as a byproduct, creating a new opening.
So I want to offer this - The game of Chess is where humans will always have the advantage. But machines can help us by figuring out which lines are well thought out and which ones have flaws. The counter to that is that we are the only ones that can think out the lines in the first place!
"From of old, there are not lacking things that have attained Oneness." - Lao Tzu
You assume that there is such a thing as an "unsolvable" game. This is not, as far as I know, established. This is not, as far as I know, established.
:) But that doesn't take away from the fact that an intelligent human could look at a source printout and figure out if it halted or not, but no general algorithm can be deduced that would do so. Thus, for a computer to win at this game, it would actually have to show intelligence, and not raw computational skill.
Sure it has. I'll give you an unsolvable game right now.
The source code to an entire program is written out by a game master. Two copies of the source are printed out. Two players are then each given an identical copy of the source, and a set of arguments that would be passed to the source were it compiled & executed. The goal is to determine if the program will exit correctly, or if it will halt in the middle. The first player to show either a) where it will halt or b) that it won't halt, wins.
This is a game version of the halting problem. It's been mathematically proven intractable; that is, there's no deterministic (e.g., algorithmic or procedural) method of doing this. You cannot write a computer program that will execute a set series of steps every time and determine what's the case here.
Is this game fun? Probably not.
Heh .. seriously.
Back in November 1996 the IBM Research guys exhibited DeepBlue at the IBM CasCon conference in Toronto. They had the program play a "top Canadian GM" and it dutifully defeated him.
It was an exhibit in the demo section and anybody could play against it. While it was the very same software it was on a much slower RS/6000 hardware.
I played against it, and of course got defeated very soon. I think around 17 moves but I don't recall correctly.
This was after the Philadelphia match that Kasparov won 4-2 but before the rematch that was marred by controversy. The IBM guys said that on game 1 they had somehow or the other omitted to bring the "opening book" and had to ftp it over a slow connection. They only got it in time for game 2. Still believe Deep Blue won game 1 ! Apparently Kasparov was shaken and then walked the streets of Philadelphia all night long and promptly won the next game.
http://www.research.ibm.com/deepblue/watch/html/c. 10.html
As an IBMer (although I joined IBM about 1.5 years since) and a chess fan I am disappointed that the team refused to open up the project to more scrutiny. I still hope and believe that there was nothing inappropriate.
Because we have a sense of humor?
Thanks.
The Turk was a machine from the 18th century.
A magician had apparently created a machine that could beat anyone at a game of chess. Before the match he would open up the machine and show everyone an array of complicated gears and machinery.
The machine would then beat the person at chess.
People believe that it was actually a very talented midget who would sit inside the machine and watch the game played via magnets. Unfortunatly no one has been able to study the machine because it was destroyed in a fire.
Maybe Deep Blue is the modern day Turk.
The reason that computer chess fascinates so many people is exactly because brute force doesn't work. The possibilities are so enormous that you can't even begin to look at them all.
In the most recent Man vs. Machine match, the computer was actually slower than Deep Blue. Yet it played amazingly good chess. Unfortunately Deep Blue isn't still around, so we can only speculate that Deep Junior is the superior program.
Humans are slower still; MUCH slower. And yet we can, in many cases, play better chess than computers. The difference is that chess masters know instinctively which moves to consider while machines are stuck looking at a huge number of moves. The holy grail of chess AI would be to finally come up with program that can cut down the number of moves to consider just like the human brain can. Such a breakthrough would be a landmark achievement in AI and would have tons of practical applications outside of playing chess.
I can agree with you on one point, though... chess "technology" probably puts too much effort into the game tree searching aspect of the problem.
Most of the effort is being put towards better position evaluation algorithms, etc... In this way, chess programs are being improved by basically tweaking algorithms we already have and hard-coding in the programmer's own knowledge about the strategic value of certain positions. Things like "doubled pawns are bad" and "in a locked pawn structure a knight is worth more than a bishop".
If we're going to make real progress we definitely need to move away from those approaches and start trying to get at the previously mentioned "holy grail" of chess. Brute-forcing human players to death shouldn't be the goal. We should instead focus on how the human mind approaches such an impossibly huge problem, and still manages to kick the computer's ass.
If a computer could be taught to fish, there'd be people saying that because the computer couldn't catcha fish 100% of the time, or because he was programmed to do it that way it's not intelligent. But... if we could find the perfect chess algorithm and the perfect 'catch a fish' algorithm and put them in a computer... could we say it had some real intelligence? heh, nice
Hey guys, see if you can get Gary to consent to an interview on /.
I know the question I would ask:
Given that "they" say computers own the opening and the endgame, while masters own the middle, what would you think of a match up of 2 chess programs and 2 grand masters (yourself being one) - with the computers to advise, but the master to make the final decision? Who would you want to play against (man and machine), and what program would you choose to be your assistant?
www.eFax.com are spammers
Is this game fun? Probably not. :) But that doesn't take away from the fact that an intelligent human could look at a source printout and figure out if it halted or not, but no general algorithm can be deduced that would do so. Thus, for a computer to win at this game, it would actually have to show intelligence, and not raw computational skill.
I was with you right up to the end. However it is most certainly not shown that a human can solve the halting problem. It is proven that (in the general case) no algorithm can say whether a program halts. The only way a human can prove whether an algorithm halts is by using mathematical formalisms that are also limited.
What people can often do is make an "intelligent" guess about whether a program halts. In fact computers can do this too: you can provide a machine with a set of heuristics (rules of thumb) that it can use to estimate the likelihood that a program will halt. That program could do better than random, just as a human could. But that is not the same as proving the program does or does not halt.
I have never seen any evidence to suggest that humans can solve the halting problem for the class of unsolvable programs.
Nevertheless you are right that there are unsolvable games. In fact there are an infinite number of them.
Sailing over the event horizon
I'm not convinced that a human is capable of solving the halting problem in the general case. In a case where the human can trace all possible execution paths, or deduce other things about the program's behavior, it's solvable, but a computer can solve the problem in these cases as well. In short, give me any particular program that a human can solve the halting problem for, and I'd bet you can codify the logic used so that a computer can do so just as well (and given enough samples, code a general computer program with the same power as the human in this domain).
Basically, to prove your point, you'd need to show that humans have some processing power strictly greater than that of a Turing machine, which is a somewhat controversial thesis.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
...because it kept insisting Fischer had a computer in his shoe while playing!! It wouldn't shut up, and they had to put it down... all very embarrassing for IBM. No wonder they kept it quiet.
"There is more worth loving than we have strength to love." - Brian Jay Stanley
Which single OS are you talking about? According to InternetWeek.com Windows XP is on little over 20% of all computers with an internet connection. Windows 98 is around 35%. Or could you be talking about Cisco's Catalyst OS, because man there's a heck of a lot of Cisco switches out there that are "on the internet".
So what, he's arrogant? He's also done a lot for the chess world. And, quite frankly, he's the best chess player since B. Fischer (yes, still better than that upstart Kramnick).
The simple fact is, that when people talk about the best chess players ever, there are two candidates for #1: Bobby Fischer and Gary Kasparov. Since they've never played each-other, we don't know who's better than who, and it's a topic of unsubstantiated speculation.
Regarding Bobby Fischer, I'm tired of hearing about his anti-semitism. Bobby Fischer is himself half-Jewish, and is friends with several Jewish people, despite his anti-semitic beliefs. Irrelevant of the man's political beliefs -- which he's entitled to, like the rest of us, think whatever the fuck he wants -- he's still one of the greatest chess players of all time.
social sciences can never use experience to verify their statemen
There are some pretty good machine learning techniques that can do things like that. Some start with more hints than others, and some work better than others. It's definitely a very open area of research.
I'd also note that if computers can do this, however, it's imposing stronger requirements on them than on humans -- most humans learn a great deal of things from others rather than deducing them on their own from basic rules or first principles, which is in some ways akin to programming a computer with strategies.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
But that doesn't take away from the fact that an intelligent human could look at a source printout and figure out if it halted or not, but no general algorithm can be deduced that would do so.
Complete, utter, and unmitigated bullshit.
If it can't be solved algorithmically, humans can't solve it either. Even if a human came up with the right solution, in the general case, you would never be able to prove it!
Simple example: I write a program which "solves" chess. In other words, it loops through every possible game configuration and determines whether, say, white can always force a win. If so, it halts. Otherwise, it just drops into an infinite loop. Now, naturally, this game would take longer than the universe's lifespan to run, but that's not the point. The point is that determining whether or not this program halts is equivalent to solving the problem in the first place! To know whether or not it halts, you have to know whether or not white can always force a win. The halting problem is equally unsolvable for both man and machine. We both use algorithms, even if we don't understand our own algorithms. The fact that we do use algorithms means that we're just as subject to the rules of what is and is not computable.
Put in other terms, a computer simulating a human brain would be able to solve the exact same problems as a human, and in the same ways. If a human can solve a problem (and prove it, not just make an intelligent guess), then it's by definition computable. The only counter to that is to assume that it is impossible to build a computer that simulates a human brain, but you're on shaky ground making such a claim.
ZFS: because love is never having to say fsck
...is the write up that Deep Junior made on its observations of the match. It really tore Kasparov up, I think it was bitter, claiming a computer was feeding Kasparov answers. I heard Kasparov blew Deep Junior off at a chess match some time ago, preferring to go play with its old friend HAL instead...
So as computers slowly overtake the best players, will Fischer random chess draw more attention. In this randomc chess variation, the inital piece configuration is randomly determined (within certain parameters to make it still have some of the same strategic elements of chess) and the same for both players (much as the way it is will regular chess). Bobby Fischer developed it to get rid of the the opening advantage the is gained with massive studying and memorization. It basically eliminates the idea of an opening sequence since there are thousands of different initial boards. However, good opening principles still dominate (piece development, king protection, pawn structure, etc).
I think it is a great idea. It also leaves a huge advantage for good master level players over machines, since an opening book is virtually eliminated.
Isn't that like saying that because you taught a guy how to fish, he's not intelligent just becuase he was taught? Just as the guy senses bites on the line, the computer sees offensive moves and counters.
If all the guy could do was fish just like you taught him then yes he's not all that inteligent. The key difference is that from you teaching him how to fish, the guy might extrapolate a totally different way of fishing. A computer won't ever do that unless you explicitly program that extrapolation algorithm.
I guess the point I am trying to make is that the computer won't make any discoveries unles you taught it HOW to make this discovery. Once you figured out a process, you can take advantage of the computer's computational abilities to calculate a result (chess moves, etc) better than a human can. How about the computer inventing something totally new, unprompted?
THAT is inteligence, and that is (bad or good, your call) impossible given current tech.
Ecce Europa - Web Design for Business
Here's an interesting exercise that one of my professors pointed out:
int n = 4;
while (n is the sum of two primes) n = n + 2;
The question "is n the sum of some two primes?" is of course always computable in finite time; just try all the prime numbers less than n/2 until you find one that is different from n by another prime number.
If you can show whether this program halts or not, then congratulations, you've solved the Goldbach conjecture, one of the most famous open problems in mathematics.