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. "
Isn't this one of the logical precursors to a global, thinking, machine?
How long will it be before the unused cycles are used to become self-aware? How will the new intelligence defend itself from human interference?
I don't know much about chess, but I thought this would be a good time to ask. Is it possible to solve chess such that the 1st player will always win? I know that it would take a huge amount of resources, if possible at all, so it would be a good distributed project.
I used to think that they'd solved Checkers, but while googling for my answer, I found that it hasn't been perfectly solved yet either.
I don't know about the author of the article, but I'm pretty sure I'm using more than 10% of my brain.
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.
you need to get a serial number to participate... get the command line version, no registration required.
__________________________________________
Take comfort in your ignorance.
Grandmaster Plague
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.
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.
I, for one, would love to see how many Athlons it takes to stomp Deeper Blue. (or whatever the current monolithic champion is) Guesses? Guessing this would be an interesting lottery/raffle idea. :)
This too shall pass.
Chess is mostly a bunch of recursive procedures; i.e. if I move here he can move here here or here. So, given that, splitting up the workload wouldn't be too difficult at all -- just tell another node to score this board layout and keep crunching. Excellent application for distributed computing.
My only concern with a distributed chess processing thing is security. What's to stop someone from making their node return random results?
Isn't this a brute force method of playing chess? Just keep throwing more processor cycles at the problem. Wouldn't it be cooler to develop this into a global neural net and have it learn from its mistakes?
I've got a fever and the only prescription is more COBOL.
... 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
Hrmm...odd...I've never seen a chessboard with shrimp pieces on it. :-)
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
What is this distributed chese program?
[]'s Victor Bogado da Silva Lins
^[:wq
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.
It's all fun 'n games, till someone cracks the client.
-Adam
You are neither well formed, nor valid.
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.
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.
10^120?
How is that? I would think that the absolute maximum (ignoring all chess rules) would be:
there's 2*6 different kind of pieces (black&white)
that makes 2*6+1(empty) different possible values for one square
so that's 13^64~0.2*10^72
probably flawed somewhere, but this figure is much smaller than 10^120???
"We live in our minds, and existance is the attempt to bring that life into physical reality" Ayn Rand
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.
Since the idea is to generate a tree of all possible moves, this does seem easily parallelizable with perhaps a little performance loss tradeoff depending on how many messages sent.
Given a tree, generate enough layers/nodes to fill up all the processors then set each one to a separate task.
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
Will someone solve someday the chessgame? I thougth that possible diferent chess games that can be played are about: 10^10^ 50, and the possible different chess possitions on a board are about 10^44, if there are only 10^18 atoms on universe, could it be really solved? Maybe by quatum computers?"
how can cellular automata be applied to this project?
Coming first is not always such a good thing, or at least not always appreciated!
"I see lots of Pengins, is that good?" "Thats good Dad, click yes."
I hereby take occasion to assert that the highest powers of the human intellect are more decidedly and more tasked by the unostenratious game of Draughts, than by all the elaborate frivolity of Chess. In the latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound."-"Murders of the Rue Morgue."
http://www.acfcheckers.com/poeben.html
Checkers _is_ better than chess.
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.
You know, Kasparov has been beaten by Deep Blue.
Why do you want to create ultimate playing computer?
It's just not interesting!
Better try to create computer that can make interesting mistakes and play as ordinary human with rating 1400-1600. It's harder than you think.
God damned, I really don't need that! :) always even in the lowest level!
I remember when I played chess with my 486, it beated me (sure, still beats me
I really don't need to be more frustrated against a opponent stronger than Deep Blue!!! 8-)
The beowulf joke is made every single time a story about a computer is posted. Believe me this is not the first guy to thing of it.
Hacker Media
Screw that, Put you used cpu cycles towards something worthwhile, like helping cancer researchers cure cancer, more info here: http://paul.playuh.com
If you don't prune the tree at all, then certainly I'd buy the hypothesis that it's exponential. But any good algorithm is going to prune.
For the most part, in the mid-game, I would think it would be exponential, because there's usually multiple moves with roughly equivalent scores. Although the whole concept of scores is kind of silly. In reality there are only three scores: you can force a win, you can force a draw, or you can't do either.
I'm also not sure that 2-5 extra levels is anything to sneeze at -- it may be the difference between a program that can play at the master level and one that can beat Kasparov.
Or more interestingly, one that never loses to Kasparov. In any case, I don't think it'll make that huge of a difference. Top computer opponents generally lose because they misinterpret the score at a certain level, not because they miss a trick by a few levels. The mistake doesn't become clear to the computer until many moves down the road.
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 pretty much doesn't make sense to know how to increase the accuracy of the scoring algorithm (without going down a level) and not put that into your software.
I'm basing what I say mainly on watching computers play chess (and watching the search trees in action). After a short period of time the scores of the possibilities generally stabilize, and except for a few rarities it doesn't matter if you wait for the computer to complete 2-5 more levels of depth. Either the scoring algorithm worked, or it didn't.
The branch factor for checkers is too low. Current computers can defeat the strongest players in the world fairly consistently, and in a couple generations, it won't even be a contest.
In other words, Chinook ownz you.
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
And how long before Arnold is sent back in time to kill Hemos' mother before Hemos can post this on slashdot?
And will Hemos' mother escape, and will john dogget be sent back to kill Hemos?
We all know Hemos' mom is tough.
Computers are already better at chess than Gary Kasprov, and as we go along in time they will solve problems in medicine, and chemistry that humans could never solve.
Linux has a bright future because the future computing systems will be so robust and functional that it would not be practical or economical for companies to create their own OSs.
Everyone will settle on Linux eventually because it is free and everyone can improve it. Remember a lowely patent clerk reinvented modern physics and if the Physics world operated on the same model as Microsoft we would still be operating on Newton's principles.
How many moves can a grand master think ahead? 5? 10? 20?
How many moves can a computer think ahead?
People fall into this....trap of thinking that if you can think, or rather, project, farther ahead than a grand master, you can beat them.
This is an incorrect assumption.
The problem lies in *how* positions are analyzed. Every beginer's chess book tells you that a pawn is worth one point, and a queen is worth nine and a rook is work five. But these values change depending on the unique circumstances of any given game, and until a computer is adept enough to discern those little changes, a computer that thinks a three hundred moves ahead is little better off than one that thinks ten.
So, in summation, I guess what I'm trying to say is, throwing more horsepower at the problem doesn't nescessarily help the situation.
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
beowulf eh?
Nice - key aspects:
probabable movements and skill interpretation
stratigizing and counterstrat
intigrate perspectives of traps
logistical performance
blah, blah, blah
If programed well, i'll bet 1/938 of chess masters will not be able to trick the comp
And I mean programed WELL
Believe it or not, there is a Winboard/XBoard chess engine named Beowulf.
It's open source, too.
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.
Would be interesting to see Gary Kasparov play against an off-the-shelf SMP server...
I am almost sure that you do not need a supercomputer to beat human chess players today - something like a p690 or a Fire 15k should have enough cpu power to win most chess games.
I simply want to remind you, that mathematics knows other methods than brute force too, which is just to say "I don't know if it can be solved, but you didn't prove anything either"
Nevertheless thank you for your post, it shows how great/sick chess is.
This sig is a true statement, but I cannot prove it.
How many checkmate positions are there, and are they all reachable with legal moves?
Reality is the ultimate Rorschach.
We already have human beating chess programs, why do we need another one? They can't make a Go playing program that can beat even a beginner, why not try that?
I would not conclude that SETI was a meaningless project.
I will readily admit that to this date we have not heard one peep from other intelligent worlds. However, it is much more likely that we will be in communication with other worlds a very long time before any does any visiting in person.
Maybe some do not care whether we are living on the only planet with intelligent life. And, maybe it will not matter to most people if we discovered we could communicate with others. But, there is absolutely no doubt that such a finding would be the most significant in the history of the human race.
Well SETI be the way to make that discovery? No one knows. But, it makes a lot more sense than sending up astronauts in space ships never to hear from them again. And, then looking for additional volunteers for the next flight. That ain't gona work well.
NexuSys - Linux support by the best
I have a application for potential distribution on a grid of PCs.
It is a game of course. So, if you are not into games, read the next post and save your time.
I have taken a look at the Grid Engine put out by SUN and distributed by SuSe. And, I help out SETI. The use of distributed computers to accomplish a very large computational task is intriging to say the least.
The problem is a difficult one however.
The game relies upon a very large data base of information which is not easy to distribute in the normal sense. The reason is that the game is designed to support many players simultaneously and each of those players may make moves that could affect any collection of that data.
I have done a lot of data base work over the years and I have not come up with a way in which the data base itself could easily be distributed. And, since it is just a game, the idea is to use the client PCs playing the game to provide all the horsepower. That makes it difficult because most of the clustered data base solutions otherwise applied to such a problem would rely upon a series of data base servers. And, in this game, that approach would never work. For one the game runs in real time and 24/7 even if a particular player does not. So, in addition to the normal problem of distributing a data base among many machines, the game must also function when any combination of those machines "go away" for awhile at their own discretion.
Complicating it even further is the fact that the versions of the game to date have placed the entire data base in memory in order to maximize performance. And, that means that transactions that take place are not making SQL calls but rather sharing quick access and quick switching of access to the common data base while the game is underway. And, yes, that kind of action is necessary for the game to be realistic.
If you happen to be interested in a real time, space war game that would rely upon a computer grid of some kind please let me know.
By the way, it will be linux based. Maybe I should say "linux only".
NexuSys - Linux support by the best
Tablebases are the closest thing to a solution. These are pre-solved endgame positions. The "three man" tablebases cover games like king v king/rook. All the tablebases up to five man are about 7GB, and to add the six man is over (not sure by how much) 60GB.
Oh, nothing could be further from the truth! Sure, "leapfrog" chess is a handicap, where two guys alternate moving the white pieces, without any conversations among them. But if they are allowed to share, discuss and think together, the result is greater than either could have done individually, most of the time. It's called Consultation Chess, and it's rare, but not dead.
Andy Soltis (IM or GM, I forget), the writer of the "Chess to Enjoy" column of Chess Life magazine, wrote several columns about it long ago (compiled in "Karl Marx plays Chess", a wonderful book about the coolness of chess, not about how to play better). Including a game where the top ten soviet GMs of the 70s (IIRC) broke off in two teams and played a game, while locked in separate rooms (a gopher carrying the moves back and forth). It's one of the greatest games I've seen.
It's rare, but lots of fun, and produces masterpieces. I have no links, but google should be your friend. I think the book I mentioned is out of print, but PowellsBooks should have it.
I'll go back to lurking now...
... considering that you used the word 'beated', I can't say that I'm surprised.
I hadn't thought of that, thnx for the info
"We live in our minds, and existance is the attempt to bring that life into physical reality" Ayn Rand
...it's at www.qoopy.net.
Hence why it was made. Even though it is a tired, old joke, I thought that in this case it was fairly amusing.
Apparently 2 people agreed with me, but 3 didn't.
Feel the fear and do it anyway.
What about a distributed project for playing Go? Go is much more complex than chess, because there is even more parallelism, see this page.
Don't drink and su! antidisestablishmentariazationally
No, you can calculate the nodes as you go along.
Ken
I'm working on a project to reproduce the complete works of William Shakespeare using a distributed network of monkeys typing. So, if chess isn't your bag, adopt a monkey.
In fact the scientific beauty of chess algorithms is to find the cleanest solution without trying all the others. What is happening here is not very inteligent, not even new. You had Seti@Home showing you could do massive distributed computing, so nothing new here.
The chalenge should be in creating good algorithms to find solutions, like people do. When a human plays a game of chess, he doesn't think of *ALL* possible moves, not by far. He automaticaly focuses on some major moves that seem likely to lead to a victory. This is what makes us different from (most) machines.
The chalenge is here, not in building bigger and bigger machines...
Lay
Weakly typed languages will bring us armageddon
here.