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. "
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.
While i apreciate these distributed processing projects, wouldn't the time/cpu usage be better used at something like United Devices?
www.ud.com
Do something good for humanity and contribute to the different projects available.
http://members.ud.com/projects/cancer/
Although there is no linux version there is a Microsoft version and I know, at least in my case, my Windows machine is more idle than my linux ones. At least they are "in the process" of making a linux/unix version.
Also see SNOPES.
It's hard to respect a project that plops an urban legend right down in the first paragraph, regardless of the validity or merit of the project. So now it's pretty hard for me to evaluate this project fairly. Presentation matters!
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 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.
With human chess it's a case of too many cooks spoiling the broth: one person plays better than a team of people. In fact, a common handicap method is to get two players to alternate moves. I have also noticed in my own play that if I listen to someone else's suggestions then I lose more (even if the suggestions are good).
I would guess that this is due to the fact that when playing, I develop all my own plans, and view any moves in context of my plans, but somebody else will have different plans in mind, and even if a move is good (and would even fit with my plan), it hasn't been part of my subconscious thought, so it has side-effects which I haven't had time to subconsciously consider.
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
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.