Slashdot Mirror
Chess: Man vs. Machine Debate Continues
Frederic Friedel sent in an interesting submission. It's an interview with the current world's chess champion, Vladimir Kramnik, in which they talk about the upcoming year in chess competitions, but also get into [Deep Blue] and where computer chess playing is versus several years ago, with a comparison between Deep Blue and Fritz. If you want more info, check out Chessbase for additional news.
if the human brain could be used to it's full potential, it'd be not contest i wonder if a divine being decided we should underclock....without any arctic silver between cells, maybe our heads would blow up
--fetch daddy's blue fright wig, i must be handsome when i release my rage
>Given an infinite amount of processing power and
memory, could someone "solve" the game of chess?
Yes. You can even argue it's solvable by an O(1) algorithm, similar to what you describe.
>If so, could someone use techniques such as
genetic programming or neural networks to learn the lookup table in a finite amount of time/space?
There's only a limited number of positions. You can enumerate them and then 'solve' the game in the same way we generate endgame tablebases. But we lack storage and processing power for many many many years to come.
--
GCP
Jesus Christ. Go read about alpha-beta pruning you moron. You piss in the wind and dress it up as if you've come up with some kind of fantastic insight. Of course the game is "solvable" and of course we have to trim the search space.
/. is all about. Eejits who proclaim they don't need a CS degree to program, who then enlighten us on subjects any CS course would cover in the first year. Worse still, the other eejits are actually impressed and mod-up these priceless pearls of wisdom.
The is what
>From someone who has played them, how does Chess
/. a few weeks ago) designed a complete ruleset that's only a few lines long. In practise, there are many rulesets, most of them because of tradition. This is somewhat problematic when making a program, because some rulesets are simply not complete.
:) I would have to check for the current state of the art, but I believe the top programs are quite competitive here.
>compare to Go or Shogi in terms of depth and
>style of play?
I've played all three and written strong programs to play two of them, but this still is a hard question.
Go is by far the deepest. The current top programs play at the level of a (rather weak) club player. It's got a huge branching factor (number of possible moves) which makes any brute or semi-brute force appraoch (what is used for chess) impossible. Most programs around right now are based on pattern recognition.
Funny thing is, the game is by far the simplest. John Tromp (the guy that wrote the 'shorter turing machine' that was posted to
Playing go is a very nice mixture of tactics and strategy. One other thing that's very nice about it is that there is a very good handicap system. The games can always be close, even against much stronger players.
Chess, well, it's mostly about tactics. Of course positional understanding matters a lot, but it's actually rather insignificant compared to the tactical part. Mostly due to continious small advances in technique and hardware, we've now got programs that are able to search about 16 half-moves (move by one side) deep. That'll nearly always take care of the tactical part. Programming strategical understanding is much harder, but a lot of progress is being made in the latter. Especially the latest generation of programs took a big step forward. We've got computers that can successfully compete with the very best humans.
Shogi I've only played once, but I've been working a lot on a chess variant that behaves like Shogi in the past. (captured pieces can be dropped) It's got almost double the branching factor of chess, and hence is somewhere halfway between go and chess. The big issue with it is that it is also very tactical, unlike go. Even though the brute force depth of current programs isn't great, they can extend mating lines very well. And mates are important in shogi/dropchess
--
GCP
sPh
Determining whether a player is a human or a computer is a very real problem that has been researched extensively.
Take the Internet Chess Club, for example. If you ever wanted to watch grandmasters play live, or even play against one, that's where you go. They offer a 7-day free trial (actually, it's 14 because you can extend your trial for another 7 days). Anyway, computer assistance is the most problematic form of abuse on the service. Normally, if you're going to be using a computer chess program to assist you while playing, you are required to create a "computer account". The ICC allows computer players on their service because it provides an inexhaustible source of very strong opponents. In fact, if you log on and take a look at the highest rated players, you might be surprised to find a long list of computers before a single grandmaster. Keep in mind, though, that we're talking about playing conditions very different from the famous Kasparov Vs. Deep Blue Games. The computers on ICC have extraordinarily high ratings due to the very fast time controls (most common are either 1 or 5 minutes per player per game), and the rating boost they get from all the games they win against weaker players--after all, they're practically playing 24 hours a day!
Now, I have no idea how many players are cheating by using a computer chess program, but I bet that many have. Imagine playing a game against a high rated opponent--meaning that, if you win, you'll gain a load of rating points--and having a grandmaster strength player at your disposal. Wouldn't you be tempted to ask for hints every once in a while;)?
The ICC has released a statement regarding dishonest computer assistance. In it they explain that they have a program that analyizes games to detect computer-like play. Of course, they protect the details of how the system works to prevent anybody from disguising their abuse. Also, they have chat-bot online all the time to whome you report any suspected cheating. Although, I imagine the majority of those reports are from unskilled players like myself after losing to a pro;)
Currently the world's number 15 human, Ilya Smirin, is playing against four of the world's top programs (info). He is well acquainted with the style of computer play, understands the strengths and weaknesses of the machines and prepared carefully for this match. In most of the games he has outplayed the programs, but is only one point ahead in the seven games played so far.
Tomorrow (Sunday) is the last game of the series. One has to be repeated after a very unusual incident: Deep Junior was winning but the Internet connection broke down and the computer could not process Smirin's move. So the operator offered him a draw. Smirin refused, saying he did not deserve to share the point. Instead he offered to resign. The Junior team refused because the program had not demonstrated the win. So they decided to repeat the game (info).