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.
It's not known whether the game is a win for the first player. My guess would be that perfect chess played by both sides would result in a draw. It'll be a few million years before we know for sure.
Reality is defined by the maddest person in the room
... sooner or later something completely amazing and worthwhile will come up that runs across multiple machines... and the client will only end up installed on 2 PC's, one of which is a broken 386 that's turned on twice a week :)
a grrl & her server
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
Chess algorithms are almost all brute force. There will be no more intelligence in using a massive network of computers to solve chess than there would be in using a massive network of computers to calculate Excel spreadsheets.
My other first post is car post.
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.
Here it is:
Artificial Intelligence, 3rd edition, Patrick Henry Winston.Ryan T. Sammartino
"Ancora imparo"
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.
at last... now we know what those silly mice were trying to compute. Apparently the perfect choss game can be reduced to the number 42.
I live in a giant bucket.
It's all fun 'n games, till someone cracks the client.
-Adam
You are neither well formed, nor valid.
10^120 is an estimate of the realizable positions in a game of 40 moves. The number of possible games is estimated at 10^10^50. See here for other numbers and references.
Ryan T. Sammartino
"Ancora imparo"
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.
Chess algorithms generally do an optimised version of a minimax tree search. It's easy to distribute different parts of the tree to different clients. The problem is that the number of calculations vs. the number of moves ahead you are searching is exponential. So if you have 10,000 processors, you can only search say 2-5 extra levels deep.
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.
Well, nature *is* parsimonious. I guess that proves it then.
why do people always compare the usefullness of the differing distributed computing projects?
lets face it somebody will join a project only if they find it interesting. not everybody is interested in the same things, and while searching for a cure to cancers is a very noble goal, perhaps it doesnt appeal to everyone. Some people consider searching for intelligent life like SETI a waste of time, but perhaps one day communications with other lifeforms could solve cancer quicker than the UD DC project aimed at cancer can, you never know.
Admittedly a chess DC project does not aim to do anything like that, but if it's interesting to some people who are not involved in any other projects and gets em started with the addiction that distibuted computing can become, then i think it's great. Maybe it will end up being the gateway to them someday helping you in your favorite project.
That's my guess too. If there was a way for white or black to force a win on the other, I'm sure somebody would have figured out how to do it by now. Chess is so well balanced, it's unlikely that a guaranteed win by one side is the final outcome.
Also, think of the draw outcome as being that you can play a 'perfect' game such that you will never lose. You (probably) won't win either. But forcing your opponent into a draw seems much easier than forcing them into a win. Especially if you plan for a draw from the first move. Such a 'perfect' game could easily lie undiscovered for centuries simply because nobody tries to play to a draw from the very beginning! I have no doubt that such a strategy would result in a rather undramatic game. Especially if both sides were going for a draw. I'm pretty certain that we will eventually find that the 'perfect' chess game has no winners, no losers, and is perfectly boring.
My guess would be that perfect chess played by both sides would result in a draw.
Personally I think the very first move is a zugzwang, and black wins in perfect chess.
Ok, ok, I don't actually think that, but I'll give you $10,000 if you prove me wrong.
If you distribute the tree you can store every possible wining strategy and just store the thing with 128 byte keys. (64 squares & 2 byte piece definition with algorithm to define the next optimal move in black & white.
Chess is an uninsteresting problem when you have a wide enough word length.
MSBPodcast.com The opinions expressed here are my own. If you don't like 'em... Think up your own stuff.
And that doesn't even factor the number of moves without progress, whether or not each side has castled, and the entire list of those previous moves without progress, all of which are technically unique positions (due to the moves without progress, castling, and repitition rules).
My impression was that mtd(f) is just an interesting novelty and that none of the commercial programs use it.
Can you present some evidence to the contrary?
Opinions stated are mine and do not reflect those of the Illuminati
So, two nodes in the (10^120) search space may have the pieces in the same positions, but one might (for example) be one move away from stalement and the other not. (Also, one might be "black moves next" and the other might be "white moves next").
Make sense?
Ryan T. Sammartino
"Ancora imparo"
Another question in my mind is how much the net-computing model applies to other parts of the computation besides the computation of look-ahead trees. For instance, one has to have a way to assign a numerical rating to a particular board position, based on material, control of the center, pawn structure, etc. Maybe there are algorithms that can do this much better, but are 10,000 times slower, so they'd only be practical with this computing model. Another thing is that openings and endgames require specialized treatment. It may be that on a net-wide application, you could make your book of openings 10,000 times bigger, or maybe you could perfectly solve certain endgame situations that traditional software might have a hard time managing.
Find free books.
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.
I am working on just such a project. It's called Animal.
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.
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.
Well, you could cut down on a little that time by using smart programming (I.E. it's not too bright to move your King to the front line early in the game) and I think a purely mathematical approach ignores things like this. But what about Quantum computing? Assuming we ever get it working to it's full potential we could solve for the perfect game of chess in less than a second.
Remember "Bring 'em on"? *sigh
I'm not sure if a distributed computing solution is going to work against a machine along the lines of Deep Blue and is descendants.
You must remember Deep Blue is computer running several thousand processors in massively-parallel fashion to compute chess moves--and all of it closely-coupled to reduce computing times. You try computing chess moves over a distributed network and by the time you get the solution over the distributed network (even if it's the faster Internet2) a Deep Blue class machine would have computed the equivalent of 2-4 moves already.
Raymond in Mountain View, CA
Screw that. I'm not helping out some multinational pharmacutical company while the same people sit on their hands and let millions of people die of AIDS, and refuse to sell them treatment pills unless they pay 10X what it costs to make them. I'd rather work for the RIAA than contribute anything to pieces of shit like that.
Here's the link:
http://members.ud.com/projects/cancer/
The research is being conducted by the Department of Chemistry at the University of Oxford in England and the National Foundation for Cancer Research, with the help of United Devices and others.
Donate background CPU time to fight cancer.
You can't just brute force this kind of exponential game.
People too often discount brute force. Computer speed has been increasing exponentially. Internet connectivity has also been increasing exponentialy. Expontenial force can attack an exponential problem.
Yes, I realize how huge the tree becomes. I'm just saying that throwing N times as many computers at the problem is like slashing the tree by f(N). You trade-off *some* of your efficencies for raw power. It is an interesting alternative to explore.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Personally I prefer medical/science projects like the Distributed Folding Project.
They have a really nice and stable client and it is available for a lot of platforms. They are working on adding support for even more platforms - among them, support for the PS/2 Linux kit :)
In regards to performance, the Linux ICC client is a bit faster than the Windows client. This is also one of the few projects where the Intel P4 is actually doing pretty well (In the GIMPS project, the P4 is much faster than any Athlons). For most project, the Athlon is the best choice, in this project, the Athlon doesn't have any big advantage.
... considering that you used the word 'beated', I can't say that I'm surprised.
here.