Slashdot Mirror
Distributed Chess Computing Project
jcarley writes "Just found an interesting project that is looking to capitalise on the power of unused computing cycles to develop a strong chess playing computer. Given the power in single and dual CPU chess programmes these days, if they can find a good way to efficiently parallel the anaysis this could be interesting. "
If playing a game (albeit an interesting one) isn't what you'd like to spend your spare CPU cycles on, there's a lot more than Seti@Home out there. Check out the Internet-based Distributed Computing Projects for more options...
The project looks interesting, but the guy brings up the whole "we only use 10% of our brain" myth
Writers imply. Readers infer.
I have thought of this myself, although I'm too lazy to implement it.
Chess is extremely parallelizable, since each of your N possible moves must be evaluated seperately, you can divide them among your K cpus which are participating... (Deep Blue had 256 CPUS, if I recall correctly)
The only major penalty for a distrubuted venture such as this that I can think of is that cached board information can't be shared across nodes... Most chess computers cache the results of evaluating different board positions, so that you don't need to (re-)evaluate everything for different move orders which end up with the same board position.
It's an old mistake.. Most everyone uses most of their brain. The misconception comes from some old paper where it said that people only use about 10% of their brain at any one time. You don't need that part that lets you ride a bike or that part that lets you talk when you're sitting down and typing in front of a computer.. Unless you have a really weird voice activated unicycle for a chair...
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
The problem is the algorithm in developing concurrently-processed chess calculations. The people on D.net couldn't get up enough interest to do the project, and ultimately it never got off the drawing board. Now most of those people have gone on to OGR.
"Mod, mod, mod...and another troll bites the dust."
I think it would be interesting to see a competition between human and computer teams in which this distributed project is pitted against a group of the world's most talented chess players working together in something like that distributed brain-cycles story that was on Slashdot a few weeks ago (sorry, I can't find the article).
There are probably some people out there who would say this is not really fair because people need time to adjust to a playing style and everyone is different, but I say if the computer can have a thousand different computers crunching numbers for it, then why not a thousand different brains working together?
Hell, I just came up with another idea...why not program the Cyc project to use a small database that deals only with chess? Certainly there are rules that can be conveyed to it and then have the Cyc AI compete against some chess programs to see how it does.
What is it actually doing? A complete tree-search for all the legal chess moves? That's a pretty big tree! Searching for conclusions to well-known games? Trying to crack into a Norwegian librarian's database?
There is no "if" in "if they can find a good way to efficiently parallel the analysis".
To play chess well, you recurse into a "deep" tree. You analyse say 10 moves, and then ten moves for the opponent. That explodes pretty quickly. So you end up evaluating millions of chess positions several moves down the road. But there are only a hundred or so "shallow" moves.
It's trivial to do the first 2 moves on the computer "distributing the work", and then to pass out the +/- 100 problems of recursing those resulting moves to 100 computers.
Sure, there is some optimization to be had by breaking off "useless" trees. That optimization will not run as good in parallel than it does on one computer. Then you may waste say half your compute nodes. But the other half is providing you with a 50-fold increase in performance.
Roger
There are something like 10^120 positions (nodes in the search space) (source: Introduction to Artificial Intelligence, Jackson) and something like 10^78 atoms in the universe (source: The Little Book of the Big Bang, Hogan).
So if every atom in the universe could do one chess position per say, nanosecond (10^-9 seconds), and had been computing since the Big Bang (15 billion years ago), the computation would still be in its earliest stages.
(Note: I stole this argument from somewhere, but can't find the exact quote or reference.)
Ryan T. Sammartino
"Ancora imparo"
This is really not that exciting, it's just brute forcing the problem. Human chess grandmasters don't run massive simultaneous mega power number crunching sequences to figure out how to win, they use a combination of strategy and intuition.
This is lame. A much more interesting story would be that someone had written a program that could play world class chess without world class CPU horsepower.
In a story long long ago on Slashdot, this topic came up, and here was one interesting reply. Apologies to RobertFisher for reposting this without permission.
Re:Hardware (Score:2)
by RobertFisher on Thursday January 17, @11:43PM (#2860138)
(User #21116 Info | http://astron.berkeley.edu/~bobf)
While I agree that this is strictly true, the hardware used does not vary dramatically -- most every one is a 1 GHz - 2 GHz machine. Considering that the branching in the tree of game possibilities is a combinatoral explosion, the differences in hardware alone will not allow researchers to explore to a significantly greater depth.
The main problem in computational chess playing is not so much in the brute force with which you can explore the tree, but in how one prunes a branch when the option starts looking unpromising. That is really an algorithmic question, and I would be willing to bet that the best algorithm will in fact win in a competition of this sort. It is a bit analogous to taking two comparable, but unequal hardware machines, and running bubble sort on one, and quick sort on the other. Quick sort will always win, hands down, because it is the far superior algorithm.
What did surprise me was that there were no parallel machines on the list -- not even an SMP. I do think that with enough processors and a reasonably sophisticated algorithm, an amateur team could in fact stand to beat a more sophisticated algorithm. But that isn't the case here.
Bob
I've had enough abrasive sigs. Kittens are cute and fuzzy.
One other consideration is, that while it seems likely (from our experience with master and grand master class players) that white has the advantage and thus whould be the likely winner if there is a winner in the solution, it has not been shown that this is the case, it could well turn out that in the "perfect" game black has the advantage as long as he makes no mistakes. It seems far more likely to turn out that the "perfect" game will be a draw, meaning that if either player makes an error and the other can play perfectly from there, the player to not make the error will win. (and error being any move that takes a branch on the tree that leads to a forced loss for the player who made the move). For example, tic-tac-toe can be easily proven to have this type of solution, and chess might has well.
I'm an American. I love this country and the freedoms that we used to have.
The alpha-beta algorithm, which _everybody_ use, is very hard to make massively parallell (effectively). You can't just brute force this kind of exponential game. You are right about the hash tables, they will also be a problem.
Opinions stated are mine and do not reflect those of the Illuminati
This is a shame, because there are many exciting things we could do with a global chess computer. The obvious "let's play it against Kramnik or Kasparov" would actually be a lot of fun. With my computer conspiring against the human, it wouldn't be clear who I'd be rooting for!
However, there are lots of other cool things we could do with this. I assume the code itself is some sort of open source--so maybe, we could set up a team tournament, where Team Slashdot plays Team AnandTech. The various teams could also do tweaks to the code to give themselves an advantage. Or, on a larger scale, we could play a America vs Europe game, where continental patriotism would encourage you to contribute your clock cycles to victory.
Another obvious modification that is not mentioned in the documents is human intervention. This sort of computing power would be great if you want to investigate a certain line of play, but this in combination with the human intuition of Grandmasters should be able to coax the computer to give privilidged analysis to certain lines over others. Otherwise, the computers would crank away on the unpromising lines just as much as the ones that might realistically be played.
It is this, the sort of human-directed chess machine that has the potential to show us some of the greatest chess games ever witnessed. This is some exciting stuff. ...
Well, potentially. However, the intentions of the ChessBrain authors is so far totally mysterious, and I think that's a shame. They seem like nuts-and-bolts people, and these distributed projects need "vision" people to attract a lot of CPUs. I don't have many clock cycles to spare, but I know I'd have a hard time resisting if I could contribute to my continent's victory over our transatlantic enemies. Apart from that, working out a system where this chess super-computer could serve as a tool to augment the play of teams of Grandmasters (or vice versa) would be genuinely interesting from a research point of view, as well as being perhaps the most exciting chess event ever.
Anyway, if ChessBrain doesn't turn into any of these things, I hope another distributed chess project does.
One thing about alot of distributed processing applications is that it doesn't matter how long it takes for node X to process a data unit. So if a 386 can't process a Seti@home data until in 3 months... no big deal, it can be assumed to be a lost unit and sent on to another machine, or it can just wait.
But for chess, I assume moves need to be made in a certain amount of time if you're playing by tournament rules. If you send off a processing unit, and it never comes back, there might not be time to send it again. It seems like this would cause important parts of the processing tree to be missed.
In this algoritm, it seems like there would need to be a priority assigned to units, and those units would be sent to machines assumed to be the fastest on the network to ensure that they would be processed in time. Of course, normal chess programs probably already do this when working under a deadline, but in this case you also have to factor in network connnection speeds, processing speeds, and the fact that certain machines may suddenly become unavailable and drop work units.
Why would humans want to interfere with the actions of a superior lifeform that possesses some amount of power over the world? Do lower animals interfere with the affairs of humans? If they have a modicum of intelligence, they don't. Neither would we interfere with our superior creations.
A more interesting question is, "What will the humans do with their time once they realize they are obsolete?"
This is however, completely off topic, since the distributed computation network is in fact constructed to be a brute-force application of computation for playing chess. So the only "human interference" this system will experience is some silly human trying to beat it at chess. And the machine's only "defense" is to beat that human into the ground in as few moves as possible. Soon, the human will decide that chess against the computer is no longer fun and will stop playing.
My other first post is car post.