Slashdot Mirror
4th Computer Chess Tournament
An anonymous reader writes: "The 4th computer chess tournament is being held online at Internet Chess Club over the next two weekends. Over 50 chess programs are involved, from commercial engines to amateur homebrews. Most will be operated by their authors. Details at CCT4 homepage. Last tournament (CCT3) there was live commentary by titled human chess masters. If you're a fan of chess or computer chess programming, login to ICC this weekend as a guest and watch the action."
As for the hardware, you are free to use what ever you want. It would be impossible to try to get all participants use the same computer-power and to make sure that they do.
Imagine....
Without equal hardware platforms, this will be hard to be more than just entertainment. It isn't much of a good benchmark of the programs involved.
This is especially true when you consider that certain processors are usually faster at certain critical operations in cases like this. It also apparently doesn't ban ASICs and other things that could make a huge difference. On the plus side, maybe we will start seeing PCI chess accelerator cards.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
It might be quite difficult to do ... how suitable is chess to being calculated in parallel.
Determining the best move at a single point in the game can't simply be split up among X computers because there are a heirarchy of moves - the first move available can be chosen from a small pool but each of those leads to more and more.
I suppose a monte-carlo like simulation would work - each machine picks a random move each time and returns the first move and the the final goodness. The master computer picks the best first move from the returned results.
USCL is better than ICC, and free for all US Chess Federation members.
Repeal the DMCA!
Are you serious? : )
I don't know the exact time controls for this tournament, but generally for human tournaments they are something like:
40 moves in 2 hours, 1 hours sudden death
Which means you each get 2 hours to make your first 40 moves, and then one more hour each to make the rest of your moves.
Computer chess tournaments use the same time controls (approximately, there are many variations, and they probably use "fischer clocks", where you get an additional 5 seconds (or some other amount) every time you make a move).
The games probably proceed along similar lines to human ones:
Lots of moves (more then 20 is not rare...) are played in about 5-10 minutes, because both players have played them all before, (and for the computer it's in it's opening book, and played instantaneously), until one of them decides to deviate. Then one takes a long think to evaluate the new position, play proceeds fairly rapidly after that, the computer will use most of it's time (why not? it can definetly find better moves the longer it thinks).
Besides, most of these engines will just run on somebody's desktop, which are a far cry from the power of Deep Blue (IBM's computer used in the matches against Kasparov).
Whereas most engines pick moves based on score, not very hard at all. Each machine would be given a move(and perhaps a reply, if enough machines existed), and would come back with the score of that move, with possible followup moves.
I think it could be done.
The previous has been a secret message to my comrades.
More details are at the site and at the FIDE's network site (Fédération Internationale des Échecs).
As far as this tournament is concerened, I welcome it entirely and enthusiastically. Finally there will be a way for the greatest chess programmers (in theory) to be under the "same roof" and possibly get together to swap secrets so that the mid-level bots on-line could actually dish out something other than four variations and stumble the rest of the way through.
And to any players on /. that are also on USCL drop me an email through my link and we'll see if we can get together for some games.
See you on board :o)
"From of old, there are not lacking things that have attained Oneness." - Lao Tzu
http://www.howstuffworks.com/chess.htm
(Is there anything that site doesnt have?)
python -c "x='python -c %sx=%s; print x%%(chr(34),repr(x),chr(34))%s'; print x%(chr(34),repr(x),chr(34))"
Calculating the whole game would take, on average, a few dozen orders of magnitude longer than the expected life of the universe, using current computers, so I'd call "much longer than a minute" a rather large understatement.
"From of old, there are not lacking things that have attained Oneness." - Lao Tzu
You must either be kidding or you don't know what you are talking about. No chess program can compute out an entire game is a minute.
The fastest chess program Deep Blue, a 32-processor parallel computer with 256 VLSI chess engines, was capable of 200,000,000 positions per second which meant that it was able to conduct an exhaustive 12 ply (or 12 half moves) search for every move.
Usually they do compete.
Chessmaster is not an engine per se. It uses "the King", which was written by König. If the King is not in the competition it is probably because it is a bit old and not up to the challenge of beating Fritz, Deep Junior, Shredder, Chess Tiger/Gambit Tiger, Ferret and the other really strong programs.
Opinions stated are mine and do not reflect those of the Illuminati
Chess computers are pretty boring. Every single one uses the standard alpha-beta algorithm, used in most games, with modifications for hashing. The difference comes in the evaluation of the leave positions, which position to "extend" (extensions mean that the position is deemed unstable, so you calculate a bit further), in which order the different moves in a position is evaluated, etc.
Opinions stated are mine and do not reflect those of the Illuminati
How to program a computer to play chess: ($0.10 version)
The underlying idea: you try an build an exhaustive tree of every possible move, and every possible response to that move, and every possible response to that response, and so on. This gives you a full tree of all possible games; You then choose a branch on the tree which results in you winning.
The problem: This tree is huge. After just a few moves, there are literally billions of potential board positions which must be considererd. Even Deep Blue (the recent Kasparov killer) wasn't able to perform full board evaluation, even with all it's specialised chess-playing hardware.
The solution: Rather than trying to exhaustively search the entire possible move tree, only search those branches which "look promising". This is assessed using a scoring system of some kind.
It is this scoring system (called a heuristic) which is the source of all the research. This is a source of interest to information theorists as the problem of finding a chess heuristic is easy to understand, but non-trivial to solve. Essentially, the problem is to reduce the "information" describing a board position into a single boolean "this is a winning position"/"this is a losing position".
If you're interested, seek out an introductory AI textbook (or website), and look up alpha-beta pruning. I can recommend "Artificial Intelligence: A modern approach" by Russell and Norvig. The website for the book is here
Russ %-)
... and never, ever play leapfrog with a unicorn.
Modern chess engines also do not just plow through every possible move... As that would take far, far too long. They use hash tables, and also do not only search through each line once, once they find moves that greatly change the evaluation of the position, they go back and try them again in other positions, and remember them to try first in future positions.
They also have algorithms for selecting which candidate moves should be examined first in a given position.
Also try to remember that the computer can only evaluate a position based on how the programmer told the computer to evaluate it. This depends on the chess strength and understanding of the programmer (well, programming team). And it takes years to aquire the chess knowledge required to evaluate a position accurately.
I should know, I've devoted a significant portion of my life to playing, studying and teaching chess.
Besides computer chess, Contract Bridge has also held its own Computer Bridge tournaments, of which the strongest has been Gibware. Would be interesting to see more different type of AI tournaments.... Maybe a tournament between the smartest Quake 3 or Counter-strike bots...
Hmm, where to start. My name is Mig Greengard and I run Garry Kasparov's website. I work with Shay Bushinsky, who is one of the programmers of Junior, the current world microcomputer chess champion. Just leaping at a chance to karma whore in my specialty. Let me cruise through the various questions and misperceptions I've seen so far.
This is an online tournament held in the biggest online chessplaying site, the ICC. The games are "60 + 10" time control, meaning each computer gets 60 minutes on its clock and 10 seconds are added for each move. So games can last up to 2.5 hours, tops. If you think this is long, this is what we call "rapid chess." Classical games can last up to seven hours.
Uniform hardware has pretty much been given up. They still distinguish between microcomputer and massive machines like those at NASA and Deep Blue, but everything is pretty much wide open these days. The programmers try to get the best hardware they can and usually know very well which platform is best for their program. (There WERE hardware chess accelerator cards, by the way. Back in the 80s when RISC and dedicated chess processors had better cost/chess performance ratios than CPUs. This hasn't been true since the Pentium, although various "Deep Blue on a chip" initiatives exist, including one by a member of the DB team.)
Anyone with a Slashdot account automatically forfeits the ability to call anyone else a nerd.
Move lists and online replay are both available on the site in the original post and at the ICC. Move lists are called "PGN" (portable (or player) game notation") which is an ASCII format used in databases but can be printed out and read easily if you know algabraic chess notation. Online java game viewer applets are quite common.
Both Shannon and Turing spent quite a lot of time on chess algorithms. Shannon actually wrote the first chess program before a computer existed. He 'ran' the program using slips of paper and generated moves this way.
The chess programming breakdown already posted is pretty good. The key concept these days is brute force speed versus knowledge. 20 years ago most programmers thought you needed to make the thing somehow think like a human because the brute force method was so slow. Intel and Moore won. The "fast searchers" now dominate thanks to the minimax algorithm. It just looks at one line after another and counts the beans to rapidly prune. Programs differ to an extreme degree in the amount of knowledge they apply. (HIARCS, for example, is one of the few "slow" programs at the top. It applies a lot of knowledge and looks at maybe 1% of the number of positions the fast programs like Fritz and Junior check.) A top level program, and the top 5-8 are roughly equal at a given time, will look at over one million positions per second. This sounds like a lot (well, it is a lot), but it only puts the program at a level equal to a top 100 level player at a classical time control. (At faster time controls, particularly blitz games of just minutes per side, computers are lethal. Humans just can't play mistake-free chess at that speed.) A program will look six-eight moves deep on the average, but extension will dive deeply into promising or unclear lines, sometimes up to 20 moves in a middlegame position.
Those who think chess is solvable should speak only theoretically. The number of positions is one of those great "million times the number of stars times the grains of sand in the world" numbers. The current method of tree and pruning adds less than one full move of search depth when you double processing power (node count). So the diminishing returns are very much here. The game of go is even worse for comps. Top programs still can't touch the human masters. Back-solving chess using massive databases starting with just a few pieces has had a big impact on computer chess in the past decade. Invented by Ken Thompson (yes, that Ken Thompson), endgame tablebases can now play any combination of five pieces (and many combinations of six) perfectly. This leads to humorous situations of a computer making optically stupid moves to reach a tablebase position it knows for sure is a mathematical win. (Tablebases allow the once-fantastical announcements of things like "checkmate in 45 moves.")
Most of the top commercial programs ARE playing in this event, but most people, particularly chess-ignorant Americans, only know Chessmaster. Fritz, Junior, HIARCS, and Shredder are all top commercial programs. In the chess world, Fritz is almost synonymous with chess program. Chessmaster has a very strong engine (called The King) by a well-known Dutch programmer. Various versions of The King have participated in these competitions and done just fine. Chessmaster has no reason to put its name brand on the line in these bloodbaths. An open tournament like this of only 11 rounds is not at all scientific, for one, but there mostly it's that since all these programs are so strong the power of the engine really isn't the most relevant thing when an amateur buys a chess program. Features like training materials, game databases, GUI, and graphics are much more relevant. Any decent program will kill you on even a low level unless you are an expert.
There are dozens of places to play online, and most of them have computer players as well. KasparovChess has multiple versions of the champion program Junior running and a new one generates when someone starts a game with one so you can always give it a try. (It's a dumbed-down version or it wouldn't be much fun.) The sites with the most players are, inevitably, Yahoo! and MSN. Their software and community suck, of course. Location, location, location. Of the specialist sites, the ICC, chess.net, and KasparovChess.com (my site, as disclosed above) are the largest and best. They have downloadable client software and administrated communities as well as live events, lessons, etc.
There have been many attempts at the holy grail of a massive online tournament. The biggest problem is simply cheating using these programs we're talking about. I could go on for a few dozen pages about methods and countermethods for catching cheats, but basically it's impossible at the end of the day. Don't get me started. KasparovChess hosted the first super-tournament to be played online, in the beginning of 2000. We had human observers with each Grandmaster, all over the world. We also hosted the largest online tournament so far, the world school chess championships. Thousands of kids from hundreds of schools around the world played. (Gotta trust the kids and teachers, right? Right? Actually there were several accusations made, but no decent cases.)
Yes, the ICC used to be free, and that free internet chess server (FICS) is still alive and well, although it is rapidly losing market share. There was a long and bitter battle about that split and the use of the FICS kernel, which is the foundation of just about every chess playing site in the world.
We cover top computer chess events, of which this one really isn't, but if you want to browse around some start here, at the last world championship. WMCCC
It sounds funny, but in the computer championships they have to play face to face and the programmer himself has to make the moves. The worry, of course, is HUMAN cheating, that is, a strong human helping the computer in an online event. The wisdom of a human Grandmaster combined with the accuracy of a computer program would be a devastating combination. (They have competitions of this, with GMs using computers while they play. It's called 'advanced chess' and was introduced by Kasparov. It's interesting, but not always dramatically superior quality chess.)
You can also stop by and play for free, either with an account and a rating or as a guest. We have a java applet if you don't want to download and install. We also have a lot of "learn to play" materials if you are one of the sad crowd that think it's just another board game.
Saludos, Mig
There have been many experiments in learning programs and most of today's top programs have at least a limited form of this.
Mostly it is simple database modification. Programs play the openings (the first 10-20 moves, usually) from massive databases of hundreds of thousands of games (human games) and variations. This is called the opening book. As bizarre as it might sound, chess programs don't usually 'think' at all in the first dozen moves or so; they simply play what's recommended in their book of human games. (Which sometimes leads to freaky events.)
When a program with book learning loses a game, or even gets a very negative evaluation during it, it will downgrade the evaluation of that opening line in it's book, so it won't play it again. This is why you can't just repeat an entire winning game against program again and again. (This is very hard to do even if the program doesn't have book learning. The timing has to be perfect and they usually have some randomizing algorythm either in the book, the engine, or both.)
Having an engine play endlessly against itself to learn and improve works to a certain extent. But remember that you run into a serious time factor. If those are two hour games, say, the quality of the moves will be lower than when the program plays a four-hour game in a tournament. So something it put down as good may turn out to be bad. And at longer time controls you'd need years to produce the quantity of checked variations to produce something practically useful.
But programmers do do what you say to test and tweak new versions. If your new beta isn't beating your old gold you need to find out why. Remember, however, that this doesn't necessarily produce a program that is much stronger overall, but one that is stronger than the other one. And when you increase the scope by introducing other engines and versions it again becomes very time-consuming.
This is why they use test suites of chess problems and just check to see which version scores best.
Most of the top programmers work in conjunction with professional players (Grandmasters) to 'tune' their opening books. This is not only weeding out bad lines but creating a book that will help the program get positions that it plays well. Many openings played by Grandmasters are completely incomprehensible to programs, while the comps play certain types of positions better than any human ever could.
Saludos, Mig
IMPORTANT: Please read the whole post
I'm sure many of you are aware of this thread already.
If you are interested in helping against the moderators who have been "editing" the thread, please read this.
Please do not moderate this post down. It is good for the long term, but if you still feel like being someone who denies the horrible truth, give me your best shot. You will help hold all of Slashdot users back in the long term.
For more info, read this piece from an apparently superior news site.
Do not support Israeli apartheid by helping their economy. Boycott Israel.