Slashdot Mirror
Gridwars Parallel Programming Challenge
Peter_Pork writes "New Scientist has an article about GridWars, a challenging new game that runs on large clusters of computers. Programs fight each other for supremacy in terms of the number of processors they control, and the main point of the contest is to develop better parallel algorithms. It seems a nice idea: have fun while you improve the state-of-the-art in cluster computing. The result of the last contest was somewhat of an upset, since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA."
Sounds rather typical for russian stuff. I used to live there 12 years ago. Most things, like household items like irons and mixers weren't very pretty, but they were definitely were solid and lasted years and years. Some were even left from the previous generation.
I also remember seeing a magazine explaining the construction of an electric razor, and being able to buy all the components it was made of in a shop. Now unfortunately things seem to have "modernized" though, and all the crap that is produced now is becoming common there.
It's even kind of sad. If previously it was possible to have something working for 10 years without failing, now we have to replace things like mixers and vacuum cleaners very often.
Wasn't the NASA program created by a genetic algorithm? It's bad style yes, but fairly decent for an automated programmer.
We, as humans, cannot create anything to do comething better than we can (providing we have the same tools).
This is why AI is not more intellignet than humans, why we haven't found a fast way to factor products of large primes with computers, and why humans can still beat computers at chess.
Computers are good ate one thing. Doing mundane calculations over and over again ad.infinitum. They do this very fast. They cannot, however, compute something that (with enough time) could not be calculated by a human. We code (create/invent) based on what we know. We know how to calculate the path of a rocket, factoring in initial acceleration, wind, etc... so we can make a computer do it really fast.
We know how to play chess... so we can make a computer do it really fast.
We know how to calculate interest, so we can make a computer do it very fast. We do not know how to make cold fusion work, therefore we cannot get a computer to figure it out for us.
Until someone figures out a way to teach any human to beat every other human every time, we cannot develop a computer that is 'smarter' that we are.
There was even a version for the BBC Micro called RAM WARS! (In The Micro User magazine - listing and full article (PDF) both online). Ah, that brings back memories...
Ceterum censeo subscriptionem esse delendam.
Considering the paralllels already drawn between this and Corewars, it's no suprise that GA-derived programs don't work. For most things, GA-derived algos are seldom the best or most cost-effective way of developing a solution, but numerous people have tried using GAs to develop CW code, and they've not been able to build anything more successful than a variant of hand-crafted programs (and generally do far worse).
my sig's at the bottom of the page.
People are noting that NASA's program was created using genetic algorithms, but there is nothing preventing the use a data table to store the genetically evolving data. In fact, that might be a much better host because the evolving data is located in a single section of data.
Anyways, the table lookup is NOT necessarily faster than huge switch statement. The table lookup requires the data table to be loaded. If the table is large and has poor reference locality, then your program could end up thrashing the processor cache. The switch statement(s), however, can compute the jumps without loading stuff from the data segment (and flooding the processor cache).
And Linus Torvalds seems to agree with me: http://www.ussg.iu.edu/hypermail/linux/kernel/030
>
> gcc 3.4 will have a __builtin_ctz function which can be used for this.
> It will emit special instructions on CPUs that support it (i386, Alpha
> EV67), and use a lookup table on others, which is very boring, but
> also faster.
Classic mistake. Lookup tables are only faster in benchmarks, they are
almost always slower in real life. You only need to miss in the cache
_once_ on the lookup to lose all the time you won on the previous one
hundred calls.
"Small and simple" is almost always better than the alternatives. I
suspect that's one reason why older versions of gcc often generate code
that actually runs faster than newer versions: the newer versions _look_
like they do a better job, but..
Linus
cpeterso
Another nice modern variant on the coreware there is found at IBM called RoboCode.
You write Java robots that battle each other by controlling movement, gun turret and radar turret. A great way to learn Java, be mentally stimulated and is entertaining to watch.