Slashdot Mirror
Kasparov Wins Game 3 Against X3D Fritz
Vulcao writes "Garry Kasparov just brilliantly won game 3 in the Kasparov vs. X3D Fritz chess match, which pits man against machine. Kasparov created a positional advantage on the queen side with a very strong pawn structure to which Fritz didn't have an answer. The result is now 1.5 - 1.5, and the last game will be this Tuesday, Nov. 18."
When a human player take a look at the chess board, he rejects the vast majority of the possible moves and concentrate only on very few of them.
This is called pruning the search tree. Computer chess players do this too; see a description of alpha-beta pruning.
Will I retire or break 10K?
For those who receive ESPN/ESPN2, the sports network has televised all three matches and will televise the fourth on Tuesday at 1:00pm. I've watched all three games on there, and it's actually very entertaining, if only for the humor of seeing history's greatest chess player in action and wearing those stupid X3D goggles. I just hope Garry can pull off Game 4 with a win.
porp
I wrote an email to chessbase two months ago and actually got a response from Fred Friedel (the Chessbase president). I then replied to him about two classic articles I'd seen on chess as I was interested in seeing more of such in regard to the current match. They did some interesting statistical analysis (here's part five of a series, it links to the other parts) but, of course, I'm still hoping for more more more. Here's some of what I wrote in my email:
F 5-D9D7-1CF6-93F6809EC5880000
In replying to my original email you asked if I had any specific thing I miss. I can reply that over time I've seen two really good articles on computer chess. The first was the cover story from Scientific American in 1990:
http://www.sciam.com/article.cfm?articleID=0005CC
It was about Kasparov vs. Deep Thought. The second was in 1997 from Byte Magazine:
http://www.byte.com/art/9707/sec6/art6.htm
The thing that stuck in my memory from the second article was this information:
"Hsu told BYTE that his team chose the RS/6000SP because it was the best available IBM system for the job, even though its P2SC processors don't have the best integer performance. Although the P2SC lags in raw integer horsepower, the RS/6000SP largely makes up for it by uniting 32 of the processors in a parallel system architecture with high-speed, low-latency connections."
I would be very interested to see the above sort of coverage of the current chess match. To put it in colloquial terms I'd like to see a big fat writeup of the workings of fritz, how it's design is broken down, how it makes tradeoffs between one kind of technique vs another, how it works with the intel architecture, how it uses null-move ordering, RAM caching, and how it fits into the history of human-chess matches.
This gives a nice introduction to Go and AI and why it is so hard to play for a computer.
To quote (from memory) the online commentator Mig Greengard:
"If X3D Fritz lacks a clear target it plays like a braindamaged lemur"
As Fritz moved its pieces back and forth throughout the game, Kasparov could make several free moves. That isn't brilliant, that's just making use of the other guys mistakes. Kasparov dominated the whole game, while Fritz had no clue at all what to do. According to one of its makers, X3D Fritz reached a new record of reading deeply (19 ply if I'm not mistaken) since the number of possible moves was so small in the cramped space they were building up their positions. This, however, didn't help a bit and I had a few giggles over bishops and knights moving away and then back again to the very same place they were coming from.
Only at the very end did Fritz realize it was losing, throughout the whole game it couldn't see what was glaringly obvious to the audience.
I've been told that this was proper anti-computer chess. The cramped position makes it tremendously difficult for a computer program to play properly while a human can easily see what's to be done.
All in all, it wasn't brilliant, Fritz just didn't have a clue
What am I discussing all this chess for? Let me get back to KGS...
"We live in our minds, and existance is the attempt to bring that life into physical reality" Ayn Rand
http://www.chesscenter.com/twic/twic.html#news130 This Week in Chess
Playing the game is most necessary - computer programs(GNUGo and Igowin are both worth checking out) can challenge any new player these days, but humans will usually be more helpful to learn from because they play less predictably and if they're polite will review the game with you afterwards to help point out mistakes.
If you can join a local club, do so. While you can get an online game almost any time of day, it's far better to play with a real board and stones and people you can see.
Once you have a few months of experience you should be able to understand what's going on in a lot of higher-level games. They are excellent to learn from.
In game two, Kasparov played the Berlin defence, which is a more closed game than the traditionally sharp Sicilian that Kasparov usually employs. It is well known that the sheer number crunching ability of the computer puts it significantly above the very best human tacticians. So yes, I think Kasparov has changed his strategy somewhat.
[Event "Man-Machine World Championship"]
[Site "New York"]
[Date "2003.11.16"]
[Round "3"]
[White "Garry Kasparov"]
[Black "X3D Fritz"]
[Result "*"]
[ECO "D45"]
[WhiteElo "2830"]
[Annotator "Greengard,M"]
[PlyCount "89"]
{61MB, DELL8200} 1. Nf3 Nf6 2. c4 e6 3. Nc3 d5 4. d4 c6 5. e3 a6 {
Diverging from game one.} 6. c5 Nbd7 7. b4 a5 8. b5 e5 9. Qa4 Qc7 10. Ba3 e4
11. Nd2 Be7 12. b6 Qd8 13. h3 O-O 14. Nb3 Bd6 15. Rb1 Be7 16. Nxa5 Nb8 17. Bb4
Qd7 18. Rb2 Qe6 19. Qd1 Nfd7 20. a3 Qh6 21. Nb3 Bh4 22. Qd2 Nf6 23. Kd1 Be6 24.
Kc1 Rd8 25. Rc2 Nbd7 26. Kb2 Nf8 27. a4 Ng6 28. a5 Ne7 29. a6 bxa6 30. Na5 Rdb8
31. g3 Bg5 32. Bg2 Qg6 33. Ka1 Kh8 34. Na2 Bd7 35. Bc3 Ne8 36. Nb4 Kg8 37. Rb1
Bc8 38. Ra2 Bh6 39. Bf1 Qe6 40. Qd1 Nf6 41. Qa4 Bb7 42. Nxb7 Rxb7 43. Nxa6 Qd7
44. Qc2 Kh8 45. Rb3 *
The telecasts have begun on ESPN2 at the start of play, but so far all of them have been kicked over to sister network ESPNews because they ran longer than their allotted airtime. Today's game, however, got bumped off of ESPNews to make room for NFL highlights today, so the chess coverage was regulated to two-minute live updates during the football coverage. Why did ESPN allow a match to be scheduled for today knowing that they would have run out of networks on which to put the full telecast unless an early blunder would be made?
It's fully expected that Tuesday's match will also spill into ESPNews territory as well, but at least they should be able to air the conclusion live since it will be weekday with no major sports events scheduled for the daytime.
Actually, no it won't, because it would still have to use a regulation-sized tennis raquet. If it couldn't move the racquet to hit the ball fast enough, it would actually lose all the points, since a tennis player loses the point if the ball strikes any part of their "body".
Uh.. mods might want to check this link again before modding it up 'interesting', seeing as the article isnt even real. Other headlines on that site include "POWER OUTAGE HID MARTIAN INVASION" and "SCI-FI FANBOYS WANT HUMAN RIGHTS FOR ROBOTS".
Give me a break.
GK was born in Baku, the capital of Azerbaijan. While Azerbaijan was once a member state of the Soviet Union, this does not make him Russian.
I think you're onto something here, but there's still some confusion to be worked out. It's more conceivable to say that the computer is "playing chess" than to say Kasparov is "programming." Admittedly the programmers have to understand chess thoroughly, but Kasparov could wipe the floor with the lot of them. Meanwhile, any of them could "Hello, World" Kasparov into a quivering mass of jelly, if the battle were waged on their own field of expertise.
So what is actually going on? The programmers have been given a problem (chess) to solve, and have created a system that is very good at solving it. Kasparov is also good at "solving" chess, and he's putting his expertise in that field up against the best automated chess-solving system that can be devised. Meanwhile the programmers are improving the rules governing the automated system as the game progresses.
AI requires some level of situational awareness, but what you describe is a form of self-awareness. Admittedly, a program able to analyze its own rulesets and tactics for weaknesses is higher on the AI scale than a program which slavishly follows them.
But I don't think it's worthwhile to draw a sharp line separating "true AI" from imitators. Chances are, the program currently has some limited "self-adaptation" built in; it's just not robust enough to allow the programmers to exit the loop entirely. If a sharp line could be drawn, then one would have to point out which of the thousands of potential improvements would push the system over the line.
I'm of the opinion that chess programs have been demonstrating rudimentary intelligence at least since my 486 first beat me.
You want the truthiness? You can't handle the truthiness!
Nine Men's Morris has been solved by Ralph Gasser in 1996 (Draw).
So has Qubic (4x4x4 Tic-Tac-Toe) by Patashnik O in 1980. (First Player Win)
Connect Four by James Allen in September 1998. (First Player Win)
Let's see John W. Romein and Henri E. Bal from that wonderful games research group in U of Alberta solved Awari in 2002. (Draw)
Read Victor Allis' PhD thesis for a good overview on finding game theoretic results of games. He invented the proof-number search technique that he used to (re)solve Qubic and Connect-Four. http://www.cs.vu.nl/~victor/thesis.html
Nine Men's Morris is not researched actively anymore, but Ralph Gasser's paper is often cited in any paper that deals with artificial intelligence in games.
Of course, even though the game might already be solved, that does not mean that it is not fun to play...
Its not so much a matter of computers doing things one way and humans doing things another way, but a matter of both being bound to the rules of computational theory. There is a large solution space, and both humans and computers have to decide what parts of the solution space to search and what parts to ignore. They have to do this, even if they do not do this in the same way. That's all that pruning the search space really means.
Now, just because you don't do it conciously doesn't mean you don't do it. Your brain does an incredible amount of processing behind your back. Think about visual processing or auditory processing. All of that goes on completely outside of your concious thought.
A deep unwavering belief is a sure sign you're missing something...
Actually I would disagree against the statement that human and computer are doing essentially the same thing. For one, computer will actually simulate every possible move to ensure there will be no mistaks. Human mind, on the other hand, once they have a general strategy in mind, they only focus on critical pieces. This is also the part where human make mistakes, since mentally, a human cannot possibly anticipate every possible move and prune it. Consciously or sub-consciously.
In US, you can easily buy enough major firearms to wipe out your neighbourhood but a few little fireworks are banned.
However, Kasparov won't be able to reproduce this exact game in the next game for two reasons:
1) He has the black pieces in the next game, and
2) Even if he would be playing white again, Fritz chooses opening moves and variants from his database with a random element. So it's very unlikely that two of the games will turn out exactly the same. In one of the previous matches, the Fritz developers were even allowed to change Fritz's opening preferences between the matches. So you can be sure they'll eliminate this line from Fritz's choices.
Ladders, one tactical aspect of go, have been proven to be PSPACE-complete. http://homepages.cwi.nl/~tromp/lad.ps
Are you trying out an application of your .sig here?
Because (1) the axiom of choice only applies to infinite sets, whereas the number of possible games of GO is huge, but not infinite, and (2) The axiom of choice is not an open question that may "happen" to be true or not; it has been proven to be independent of the other typically used axioms. You can declare it to be either true or false, and either way, develop an interesting branch of math that depends on your choice -- as many mathematicians have done.
In other words, your .sig philosophy of "if you can't dazzle
'em with brilliance, baffle 'em with BS"
isn't cutting it this time around. :-)
Professional Wild-Eyed Visionary
Sorry for the bad links.
Here is the Scientific American article.
Here again is the Byte Magazine article.
Here are some excerpts from the first article that talk about how to develop the algorithm:
We also began to consider ways of tuning the evaluation function's 120 or so parameters, specified in software. Traditionally, programmers had hand-tuned the weights that programs assigned to material--pawns and pieces-- and to positional considerations. We believe ours is the only major program to tune its own weights automatically.
We acquired 900 sample master games and arbitrarily defined the optimum weights as those that produce the best match between the moves the machine judges to be best and those that the masters actually played. The software part of the evaluation function was completely rewritten by Campbell and Nowatzyk to reflect this strategy. Instead of just assigning a final numerical value to each position, the evaluation function--in its tuning mode--returns an equation containing a string of linear terms. In other words, it produces a vector.
Two tuning mechanisms were used. The first, which is called hill climbing, simply sets a given evaluation parameter at an arbitrary value and then performs, say, a five- or six-ply search on every position in the game data base to find the moves that the machine would play. It then adjusts the parameter and recalculates. If the number of matches between the computer's choices and the grandmaster's choice should increase, then the parameter is adjusted again in the same direction. The process continues until all the parameters have reached their highest level of performance. It would take years to optimize all the parameters by this method, however, and so we used it only in a few diffcult cases.
The second tuning mechanism, proposed and implemented by Nowatzyk, was much quicker. It evolved from the simple notion of finding the best fit between the function of the machine's evaluation of positions and their presumed true values. The best fit provides the lowest average squared value of the error between the model and the true value. True values can be approximated, for these purposes, by the results returned from deep searches (if a known concept is being fine-tuned) or by comparing machine decisions with those of first-rate human players.
When humans play they rely primarily on pattern matching rather than searching a tree (unless they suck). Computers tend to be very poor at pattern matching, and humans tend to be extremely good-that's why a small child can look at photographs and categorize them instantly, but the most advanced computers have great difficulty with that kind of task.
Most skilled human chess players apply pattern matching by looking at the board and identifying interesting things. They start with nothing and add new options to the list until they feel they have a sufficiently comprehensive understanding of the situation.
Search tree pruning, by contrast, starts by including the entire space of potential moves and identifying courses of action that can be eliminated. Alpha-beta pruning is a particularly poor example here since it has the useful property that all a-b pruned subtrees are guaranteed not to be optimal. However, humans often ignore superior courses of action and choose suboptimal ones that "feel right" or match prior experience.
There have been various experiments on the limits of raw pattern matching ability with chess pieces. An interesting one involved asking participants to memorize an arrangement of pieces and reconstruct it a minute after the arrangement is removed. Participants included people with little or no chess experience and masters.
Those without experience memorized it as raw data, and did as well as they would have if asked to memorize random numbers instead of chess arrangements. The masters were more interesting. They did about the same as the beginners on random arrangements that could never actually happen in a game, but they were infinitely better at reconstructing realistic arrangements that often show up in games. The experiments proved that masters can recognize groups of pieces and evaluate them collectively.
In a game situation this means the master looks at the board, and certain parts of it just stand out. The master will pay no attention to areas that don't grab his attention, and doesn't need to evaluate whether any of those individual pieces are worth moving. Interestingly, this means that playing with nonstandard rules (such as changing piece movements) will likely devastate a master's ability while only slightly reducing an amateur's skill level and leaving the computer's ability unchanged.
Even though I think the parent is a troll, here's an academic article detailing some other experiments on the topic.
The game of chess has been around so long that opening moves and their variations have been cataloged, categorized, and analyzed in great detail. It's been a while since I was a serious student of the game, but I think Modern Chess Openings is still the standard reference for opening play.
In any event, X3D Fritz has a database of analyzed opening moves, including, for this match, a database of Kasparov's opening moves. It's called the opening book. Opening books save the computer time at the start of the game, since it doesn't have to reinvent the wheel every time it plays.
As for deciding the first move to play, the computer has a randomizer to select a move from its opening book. For this match, though, I wouldn't be surprised if X3D's programmers didn't pick its first move for it.
The trouble with practical jokes is that very often they get elected. -- Will Rogers
I should note that IANAGM though.
I think it was more like three years ago he played Kramnik with the world championship at stake.
Most people also think that the reason he lost that was that he accepted Kramnik's challenge to play shorter games than standard: Kramnik thinks faster than Kasparov, but not as deeply, and hasn't beaten him in any matches with normal time rules.
He doesn't get many one-on-one matches any more, because no-one wants to be beaten repeatedly. He does enter tournaments, and tends to win those.