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."

Comments

Everything old is new again.

[Mordant]

Anyone remember Core Wars?

Re:Everything old is new again.

[jonathan_ingram]

Yep. In fact, there's a really nice interactive corewars server here.

Re:Everything old is new again.

[rabidcow]

It gets better.

There was a game based on core wars called "CoreLife", which was 2 dimensional:

CoreLife: The Linear Thinkers Nightmare. By Brent Adams
Copyright (c) 1993.

CoreLife is a training program designed to improve the skills used in a
multitasked environment. It is, however, just a game. (don't blame me if
it can't do your taxes)
The CORE is a simulated 2 dimensional parallel processing computer with
language and addressing modes similiar to conventional assembled code. The
programs in memory compete for system resources (namely space), while
conserving energy. This is accomplished by accumulating space as fast as
possible while minimizing the number of logical threads. (parallel paths)
Conflicts for space (ie. moving a new command into an opponents territory)
are resolved using a dice roll based on the strength of the opponents.
STRENGTH = (AREA accumulated)/(Number of logical threads)
Programs are considered dead if net area ever falls below zero. The
winner is the last program that survives.

Close but not quite

[loadquo]

since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA.

It should not read like that it should be.

since a craftsmanly Russian program defeated a sophisticated program created by a genetic algorithm from NASA.

See (from NS):
"The final battle saw Wenig's program - created using genetic algorithms - take on a program designed by a computing student from Moscow State University."

A subtle, but important difference. Now if the prgrams were actually evolving in the Gridwars game that would be interesting, as it would be similar(ish) to my project.

*Dreams of a day they put an edit queue on slashdot*

Content information

[agentZ]

Much more information is available at the GridWars II official site.

Pens versus Pencils

[Anonymous Coward]

This reminds me of a story my solid state physics professor like to tell (this is the short version):

NASA decided that the astronauts needed a writing utensil to take notes during space missions. NASA spend a large amount of money to develop the zero G ballpoint pen.

The soviets gave the cosmosnauts pencils.

Re:Pens versus Pencils

[Q Who]

NASA decided that the astronauts needed a writing utensil to take notes during space missions. NASA spend a large amount of money to develop the zero G ballpoint pen.

This is an urban legend.

bad programming

[Traa]

Part of the challange is that at each step the programms only get a certain amount of time to do their computations before having to make a move.

Quicky check at the NASA program and I find a switch statement of 2049 (2^11) parts. It is broken up in switch blocks of 64.

if (situation<64){switch(situation){
case 0:tdir=5;break;case 1:tdir=1;break;
case 2:tdir=1;break;case 3:tdir=5;break;
case 4:tdir=2;break;case 5:tdir=4;break;
case 6:tdir=6;break;case 7:tdir=2;break;
...
}}else if (situation<128){switch(situation){
case 64:tdir=1;break;case 65:tdir=2;
...

This is sad coding on so many different levels. I am not sure how to express my feelings about it.
First let's look at a straight forward way of how to do this....the lookup-table.

//create a big easy to access lookup table
static unsigned char nTable[2048] =
{
5, 1, 1, 5, .....
};

//range check your index
if (situation<0 || situation >= 2048)
{
situation = 0;
//print some debug error message
}

tdir = nTable[situation];

It is fast (speed is an issue).
Takes up less space (programming space can be an issue).
Easier to read (debugging tricky programs is hard enough without the obfuscation).
And should have been part of your basic programming education.

And this is state of the art coming out of NASA?
I'm impressed our shuttles go UP in the first place (ja, ja...low blow...just kidding ofcourse).

Really, if I see this kind of coding I cringe. Then talk to the person. Then make sure they learn from their mistakes and don't do it again, or they can find themselves a job outside of my team.

Programming parallell algorithms are difficult....

[Homology]

and fun ways of exploring new programming paradigms are welcomed by all, I gather. Multi-threaded programming is easier, better understood, but still hard.

Multi-threaded applications are less common that one might think. Even those GUI applications that would benefit alot from improved responsivness due to multi-treading avoids it, due to greatly increased complexity.

When the Gang of Four came out with their Design Pattern book, it was a great hit, and very usefull indeed. But design pattern for multi-threaded programming is not that well-know. But some are published, as the link below shows :

http://www.cs.wustl.edu/~schmidt/patterns-ace.ht ml