Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology Entertainment Games

Gridwars Parallel Programming Challenge 176

Posted by timothy from the your-base-all-ours dept.
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."
This discussion has been archived. No new comments can be posted.

Gridwars Parallel Programming Challenge More

Gridwars Parallel Programming Challenge

Comments Filter:

  • A strange game. (Score:5, Funny)

    by mrpuffypants ( 444598 ) * <mrpuffypants@gmailTIGER.com minus cat> on Saturday July 12, 2003 @12:33PM (#6423985)
    The only winning move is not to play. How about a nice game of chess?

    I couldn't resist!
  • A hundred thousand Beowulf jokes just collided in my head . . . What's a geek to do?!
  • that all beowolf cluster jokes below this reply are null and void.

  • Man.. (Score:1, Insightful)

    by tomakaan ( 673394 )
    Just like that junkyard wars where the crazy Brittish always beat the Americans!

  • OMG (Score:5, Funny)

    by The Bungi ( 221687 ) <thebungi@gmail.com> on Saturday July 12, 2003 @12:37PM (#6424010) Homepage
    An article where SOVIET RUSSIA *and* beowulf jokes are on topic. What's next? A Natalie Portman interview?

    • Re:OMG (Score:3, Funny)

      by Jellybob ( 597204 )
      Yeah... it'll be about here newly bought Russian beowulf.

      And it'll be posted twice, with the evil bit set on the dupe.

    • Re:OMG (Score:1, Funny)

      by Anonymous Coward
      IN SOVIET RUSSIA, a beowulf cluster of Natalie Portman clones imagines about interviewing YOU!

  • I might be good at this (Score:5, Funny)

    by Anonymous Coward on Saturday July 12, 2003 @12:39PM (#6424014)
    I've often been told my programs require more cpu, allocate more memory, and take more time than any other coder on the team. If I can scale up my special skillz to more than one processor at a time, I might have a chance here.

  • Next article prediction (Score:3, Funny)

    by LordOfYourPants ( 145342 ) on Saturday July 12, 2003 @12:41PM (#6424020)
    Scientific American has an article about Hellmouth, a challenging new game created by Junis that runs on large clusters of computers. Sponsorship from SCO looks to be confirmed and celebrities such as Natalie Portman promoting grits are in tow.

    Sadly, the death of Stephen King during the game's promotion at E3 and LinuxWorld (where no one showed up) put a damper on things, while in Soviet Russia the people controlled YOU.

  • The event is expired. (Score:1)

    by Anonymous Coward
    This article makes it seem like there is a NEW challenge. According to the Flash Demo on thier website, however, it appears that Grid Wars 2 was June 23-25, 2003.

    LOL HAHAHAHAHA

  • Everything old is new again. (Score:5, Informative)

    by Mordant ( 138460 ) on Saturday July 12, 2003 @12:46PM (#6424046)
    Anyone remember Core Wars [catb.org]?
    • Yep. In fact, there's a really nice interactive corewars server here [sourceforge.net].
    • Sure, I'm undefeatDEADBEEFDEADBEEFDEADBEEFDEADBEEF will never beat me.

    • Re:Everything old is new again. (Score:4, Informative)

      by rabidcow ( 209019 ) on Saturday July 12, 2003 @02:49PM (#6424564) Homepage
      It gets better.

      There was a game based on core wars called "CoreLife [google.com]", 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.
    • There was even a version for the BBC Micro called RAM WARS! (In The Micro User [tiscali.co.uk] magazine - listing [planet.nl] and full article (PDF) [planet.nl] both online). Ah, that brings back memories...
    • Another nice modern variant on the coreware there is found at IBM called RoboCode [ibm.com].
      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.
      • RoboCode is one of many of this genre of games, including C++ Robots [gamerz.net], Robot Battle [robotbattle.com], C Robots, and a number of other games using more or less common programming languages to control robots in an arena, including some sold commercially. You could even include Robot Odyssey in this genre in some ways, although the robots didnt fight and you "programmed" them with electronic circuits.
  • What was the name of the old game where two programs batteled for survival? Trying to shut each other down or something like that. I think it was back in the Vaxen days, but due to heavy memory fragmentation I'm not quite sure.
    This article just rings a bell... No wait, that's the tripwire. Gotta go.
  • Is this going to one day turn into a computer program which defeats its rival in the computer, then takes on civilisation as we know it and takes over the world?

    Its the beginning of the matrix people. We should stop it now!!!

    *twitch*
  • In Soviet Russia, parallel algorith writes you!

  • Close but not quite (Score:4, Informative)

    by loadquo ( 659316 ) on Saturday July 12, 2003 @12:56PM (#6424103) Homepage
    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*

  • Cool (Score:2)

    by MikeFM ( 12491 )
    This seems like a fun idea. It'd be more fun though if they had this web enabled and running all the time. Then we could keep submitting new code to play. Of course you'd want to limit how often new players were added.. or someone would cheat by just reentering the same code over and over until it overwhelmed the competition.
    • Well, if you're into regular old corewars, (and if the site ever comes back up) you might look here [csuchico.edu]. They were/are doing just that w/ the old corewars mars code.

  • Gridwars, the next Rogue-alike (Score:4, Funny)

    by smarthippy ( 528114 ) on Saturday July 12, 2003 @01:01PM (#6424128)
    Rogue: oh no! a 'C' is chasing my @! majick missle! majick missle! arghhll...
    • Rogue: oh no! a 'C' is chasing my @! majick missle! majick missle! arghhll...

      Nitpick from someone knowledgeable:

      A 'C' can either be a plains, forest, or mountain centaur. However, a 'c' can be a cockatrice, chickatrice, or pyrolisk, which are much more feared because of the danger of their insta-kill petrification attacks. Also, in later versions of Nethack, there is a patch option to change your character display symbol from a generic "@" into a race-specific symbol (if you're playing a human, 'h
  • Programs fight each other for supremacy in terms of the number of processors they . . . . . . a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA."

    hmmm
    I'm guessing that this guy works for the Russian mobsters that put together the porn/spam network [slashdot.org] reported earlier.

  • experience (Score:2, Funny)

    by Tablizer ( 95088 )
    The result of the last contest was somewhat of an upset, since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA.

    Perhaps their virus writing skills give them an edge

  • Craftmanship versus sofistication? (Score:5, Insightful)

    by WegianWarrior ( 649800 ) on Saturday July 12, 2003 @01:12PM (#6424166) Journal

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

    This is not the first time something craftmanslike can beat something sofisticated. Even thought the following examples are strictly hardware, the general idea is the same.

    Take, for instace the T34 [fas.org] vs the Tiger [tigertank-h-e-181.com]. The Tiger was one of the most sofisticated - if not the most sofisticated - tanks in production at the time, but were drowned by hordes of the more craftmanlike and easily manufactured T34.

    The battle between a simple, craftmanlike approach and sofistication was once again seen in the early sixties, in the race to get a man into space. The russians fielded the Vostok [astronautix.com], a design born more out of solid craftmanship than anything else. It's very simplicity was a strenght, allowing it to undertake missions up to five days long, while the american attemt at a longdurationflight in the highly sofisicated Mercury [astronautix.com] lasted just under a day and a half, leaving Gordon Cooper in a virtualy dead capsule (having to eyeball his attitude thru the windown and manualy fire the retros). Granted, one reason the US had to go for sofisication is that their rockets simply couldn't lift as much as russian rockets... but whereas derivatives of the Vostok still flies (as unmanned recoverable satelites), the line that breed the Mercury is dead.

    Sofistication is well and good, but many times a less sofisticated but better crafted designs / programs can outperform it. Sofistication for it's own sake is usually not worth the tradeoffs.

    • Pens versus Pencils (Score:1, Informative)

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

    • 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 n
      • I respectfully disagree.

        I used to use lot of Russian-made appliances and hold-house items like you mention. But the quality is crap to the level of quality faked from Hong Kong. Almost anything household items made by Russian was of very low quality compare to stuffs Made in Japan and U.S.A. And that was then, a little bit of 14 years since I have moved to the US.

        The funny thing is that now even with a "Made in the U.S.A." label, it does not mean it is of high quality. Many American companies, having to
    • Like Vladimir Lenin said "quantity has a quality all its own".

    • or one GA vs another? (Score:4, Insightful)

      by Chris Burke ( 6130 ) on Saturday July 12, 2003 @01:45PM (#6424284) Homepage
      i don't necessarily view it as craft vs sophistication. the sophisticated thing was the genetic algorithm, not the resulting program. that GA was competing in the contest with another GA -- the one that produced the Russian programmer. that second GA could be considered vastly more sophisticated than the first. it produced a general purpose intelligence that could defeat the first GA at what it was specifically designed to do.
      go nature! :D
    • RTSs bear that tendancy out, too. Sure, you can build a couple of overlord tanks and think you're tough, but all it takes is a couple dozen RPG troopers hiding in buildings to ruin your day. (sorry, i was up all night playing c&c generals)
    • What I remember hearing about the Tiger vs. the Sherman is that we beat them by sheer numbers - each Tiger usually took out a handful Shermans before being overwhelmed.

      When you're outnumbered, you either win by sophistication or not at all.

    • I've never felt compelled to comment on another's grammar and spelling before, but it's
      *sophistication* nagdammit!
    • The KISS principle is something all engineers should folllow when they can.
    • 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).
    • And the truly sophisticated can spell the word :)

      Full marks for consistency though.....

  • take heed (Score:2)

    by trb ( 8509 )
    The result of the last contest was somewhat of an upset, since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA.

    Therein lies the lesson. Craftsmanly usually defeats sophisticated. It is pompous to assume otherwise. (And yes, the comparison of the American and Russian space programs bears this out.)

    • Therein lies the lesson. Craftsmanly usually defeats sophisticated. It is pompous to assume otherwise. (And yes, the comparison of the American and Russian space programs bears this out.)

      How do you figure that the russian space program is any better than the American one?
      Sheesh, what is it with this story to bring all of the russians out of the woodwork to proclaim the power of their space program?

  • Content information (Score:3, Informative)

    by agentZ ( 210674 ) on Saturday July 12, 2003 @01:16PM (#6424174)
    Much more information is available at the GridWars II [gridwars.com] official site.

  • Deja vu? (Score:3, Funny)

    by WegianWarrior ( 649800 ) on Saturday July 12, 2003 @01:22PM (#6424192) Journal

    ...the ultimate way to debug their programs - let them compete against other programs in a gladiator-style tournament.

    Dont that sound awfully familiar [imdb.com]?

  • You mean... (Score:1, Insightful)

    by mritunjai ( 518932 )
    The result of the last contest was somewhat of an upset, since a craftsmanly Russian program defeated a sophisticated genetic algorithm from NASA."

    Not to troll, but do you mean you were upset last time because craftsmanly russian spacecrafts (e.g. Soyuz) ended up being cheap and safer than $2B NASA shuttles ?

    Remember, how exotic, things may look, the winner will always be one which is conceptually sound, fundametally strong and is architected by experienced engineers.

    • You might not have been purposely trolling but it felt like it....

      The Soyuz and the Shuttle are 2 completely different spacecrafts designed for 2 completely different purposes. There is no _winner_ nor is there a race (in the sense of who can build the best launch shuttle). The Soyuz may be craftsmanly and we may not have anything comperable, but that's just because we don't want to build anything like that. :)

    • The soyuz vs shuttle comparison is not one of craft vs sophistication, but one of specialist design vs generalist design. This is different from the programming contest, where both programs were specialists.
  • Anyone remember these programs? Had tons of fun in highschool writing PRobots algorithms, Gridwars sounds a lot like that.

    ~Berj
  • Games like this never have a *best* strategy. They are like rock-paper-scisors, or the prisoners' dilemma. I bet one of the next strategys to win will involve a an evovled behavior that has cetain probabilities on what to do next based on previous states and input.

    The reason the russian guy wan was *luck*. Tournements like this should be seeded randomly and played thousands of times. Only then could one player prove to be superior, and even then he would only be superior in his ability to beat up on th
    • Perhaps I am a cynic but I can't help wonder if you (or a typical American) would come post "The reason the American guy won was *luck*" if your guy had won.

      (This came to my mind because I remember when Donovan Bailey beat Michael Johnson in some stupid 1 on 1 100m challenge, but what was really stupid was some American being interviewed saying "oh for sure Michael Johnson is the superior athlete and should have won". Granted, she did seem like a funny middle-aged woman who probably had no good reason to
      • My motivation was not nationality based at all. My point was that in one tournament in this sort of game the winner is chosen by who they are seeded against.

        My personal bias is that one of the genetic algorithm evolved codes should have won, but the way the tournement was set up it was kind of hard to tell who the real "winner" was.

        Speaking of Johnson and Baily, I wonder 20 years from now what kind of blood doping and stimulants we will find they used. One doesn't just cut their 200m times from 19.8

  • bad programming (Score:3, Informative)

    by Traa ( 158207 ) * on Saturday July 12, 2003 @01:46PM (#6424288) Homepage Journal
    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.

    • Re:bad programming (Score:3, Interesting)

      by jonhuang ( 598538 )
      Wasn't the NASA program created by a genetic algorithm? It's bad style yes, but fairly decent for an automated programmer.
    • Keep in mind that it said Nasa's algorithm was genetic. This means that it had to dynamically evolve over time. The code you're looking at was likely grown "organically" by a genetic programming algorthithm--of course it's not going to be as clean and neat as your hand-optimized code.

      Genetic programming is often implemented by taking little branches of a program's parse tree and swapping them around. Using a switch statement allows that swapping to occur easily, whereas using a lookup table would not all

    • Remember that, as other mentioned already, the NASA program is the result of a genetic algorithm. It's not NASA doing the coding themselves, the program is the result of several generations of the algorithm being applied.

      Any questions? see here: http://www.google.com/search?q=genetic%20algorithm s [google.com]

    • Re:bad programming (Score:5, Interesting)

      by cpeterso ( 19082 ) on Saturday July 12, 2003 @03:23PM (#6424683) Homepage

      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/0304 .3/1367.html [iu.edu]


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

      • Genuinely curious: doesn't a switch statement suffer from a similar trade-off?

        If the switch statement is implemented with a jump table, then that table too must be in cache. If it doesn't use a jump table, but has a series of test/branches, then a missed branch prediction will also give a really nasty performance hit.

        Would it be the case that a jump table is more likely to be in the code cache than a lookup table is to be in the data cache?

        • As Sam pointed out, the switch statement does not have to use a jump table. A "computed jump" can be compute to figure out how far to jump in the switch statement body (i.e., to which case label). And the switch statement probably has good code locality, so the code pages are "hot" and kept in the processor cache. Add some help from the processor's branch prediction for the most common switch cases and your code (might) really be flying. The processor's branch prediction is absolutely no help if you are ind
  • Oh right the
    col^Hde war.
    phew.

  • Programming parallell algorithms are difficult.... (Score:3, Informative)

    by Homology ( 639438 ) on Saturday July 12, 2003 @02:19PM (#6424427)
    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

  • but once you apply all the rules to make it behave and play fair, it all seems rather boring! When I saw core wars years ago I had a notion of clever assembler programs running amuck ... but then they started with their special compilers and modified language, so it was pretty much all over (bar the shouting). This just seems ... bleech ... academic!!
  • 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.
    • The use of techniques such as genetic programming can produce programs that perform some task using a method that humankind (up to that point) was not aware of.

      Genetic programming (loosely speaking) simulates a population of programs that undergo a process of evolution, with those programs which seem to do the best at the task more likely to survive to the next generation. As such, it can be applied to problems where we can easily evaluate how good a heuristic is, but not necessarily know how to construct
  • And broadband internet recommended. When will people realize that we want te be able to access CONTENT quickly and efficiently, not watch the super spiffy animation you made in a plugin that I can't copy-paste text from?
  • The idea of having programs evolve and fight each other for computational resources is not new. It has been used for 5-10 years in Avida, software used in evolutionary research.

    The approach has been very successful, resulting in a better understanding of complicated topics such as the evolution of complex organs.

    Tor
  • United States should have used Windows... there would have been no chance of losing, it would have taken control of all the processors and crashed the computer too!
    No russian can beat that.
  • Ick. It turns out that the whole gig is just a publicity stunt for Engineered Inteligence's [engineered...igence.com] "CxC" parallel/clustering programming language/environment. Considering that it requires a '30 day free trial' (or paid licence) of the system to test, debug and play the game, I doubt this'll take off into much of a self-sustaining community.
  • Might not a problem solving algorythm be better served by a radical approach to AI? All this talk of programming to use more nodes in a cluster on a competitive basis is too simplistic.

    If a program can be developed to search for code snippets then test them in a protected environment of its own we might be able to develope a more effective self directing algorythm.

    What I am suggesting is like digital DNA but with the ability to search and test new code, then add desired functions to the core.

    The real le

  • "Any fool can make things bigger, more complex, and more violent. It takes a touch of genius-and a lot of courage-to move in the opposite direction."

    And yet, right above this, their page says 300kb+ connection recommended. Am I the only one who finds the humor in this?
  • I think this is the parent to Skynet!!
    It's happening!!!

    Noooooooooooooo!!!
  • I competed in the first GridWars contest. I didn't even place, but they did send me a couple undersized GridWars t-shirts for having competed. A lot of people found hacks, err, undocumented features, in the battle program that allowed their warriors to some interesting things, and many of the "features" were allowed to be used in the contest. Few well behaved programs survived the first round.
    • It looks like all the old warriors from the first contest automatically re-entered, so I've lost again. I wonder if I'll get another t-shirt out of this.
  • Isn't this how they created the AIs that blew up the world in Odyssey 5?

Slashdot Top Deals

For God's sake, stop researching for a while and begin to think!

Close