Thread: Game of Life

  1. #1
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895

    Game of Life

    I just finished a program for university. It was a challenge where we had to create an implementation of John Conway's Game of Life and make it as fast as possible. Since I found the challenge to be fun and interesting, I'm posting it here for all of you.

    The basic rules of the game are explained here:
    http://en.wikipedia.org/wiki/Conway's_Game_of_Life

    Your objective is to implement a program that runs this simulation as fast as possible. Measure of performance is
    a) the number of CPU cycles used and
    b) the physical time used. (Mean of three runs.)
    The program will be executed for 3000 generations on two different patterns on two different machines. Each result will be given a score relative to the results of my reference implementation. (8 results: two measurements over two starting patterns and two machines) The mean of the score is the final result. Implementations that produce an incorrect result are disqualified. Implementations that need more than two minutes for a run are disqualified, too. I'm not that patient.

    The program must be able to read and write a simple textual file format. This file holds two whitespace-separated numbers per line, which form a coordinate pair designating a cell that is alive.
    Code:
    100 24
    -24 51
    The above specifies that the cell at (100,24) is alive, as is the cell at (-24, 51).
    Input to the programs will be given in this format, and the program must produce this format as output (either to stdout or a configurable file name). The order of points is irrelevant; the file will be sorted before any comparison is done.

    The machine specifications are:
    1)
    Intel Core Duo (32-bit instruction set, SSSE3 support, dual core)
    1 GB RAM

    2)
    AMD Athlon64 (64-bit instruction set, SSE2 support, single core)
    1 GB RAM

    The target compiler is GCC 4.1 or GCC 4.2 (depends on what I'll be using when the contest ends) on a Linux system. There is no need to make it portable to other platforms.
    The project must include a simple way of building. You can use GNU autotools/make, SCons, Boost.Build or a custom shell script (Bourne shell or bash). Compilations must be possible with one, at most two, simple commands. (e.g. "./configure; make" or "bjam").
    You may use C or C++. If you use C++, you may expect the Boost libraries to be available, both 1.34.1 and 1.35. (Hopefully it will be released by then.)

    Implementations based on hashlife are forbidden, sorry. This advanced algorithm is so superior that it would be pointless to compare it against the other possibilities.

    This is an optimization challenge. Optimize your algorithms, and optimize your instructions. Every cycle counts.

    The contest ends at 0:00, April 21th. Have fun!

    I will post a few test input/output files soon.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by mike_g View Post
    Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?
    Why do you assume there are bounds on the grid size?

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    I'm still waiting for the results of Wireworld.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    Quote Originally Posted by Dave_Sinkula View Post
    I'm still waiting for the results of Wireworld.
    I think Salem got too busy with work and then just forgot about it, and I have mixed feelings about it... I'm no more than a hobbyist programmer, so I'm a little afraid to hear how bad my entry was. )

    Quote Originally Posted by mike_g
    Sorry, I havent read through the entire Wikipedia page so maybe I missed this part, but what size are the grid dimensions meant to be?
    More important I think is, how large will the patterns be? Shall we assume they might be "of any size", or are you willing to tell us something like "the patterns are 200x100 and 40x60"?
    Last edited by jEssYcAt; 01-19-2008 at 10:37 PM. Reason: Making my post on topic
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    There is no actual boundary on the grid size. However, I will run no pattern for more than 3000 generations, and no starting pattern will be larger than a few hundred grid cells in any direction. Because the pattern cannot grow more than one cell per generation, you can assume that it will not grow beyond about 8000 cells in either dimension.

    However, I will give out bonus points for solutions that do not use fixed-size grids. I'll just have to think of a fair and balanced way of adding that in.
    Last edited by CornedBee; 01-20-2008 at 08:43 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    When you say you will run no pattern for more than 3,000 generations, are you suggesting that our program needs to have a way to let you choose how many generations it will run, or are we safe to hard-code the program running for 3,000 generations?

    And are you going to clock the entire program or are you going to modify the program to add your own timing functions around the update or something (meaning you are only timing the actual calculation of the generations, not loading and saving files)?

    I realize the overhead of loading and saving files is probably not going to be a significant bottleneck compared to calculating 3,000 generations of a board that might grow to a couple thousand cells in both directions, but I need to know how pointlessly to tinker with my file io operations.
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Let me put it this way: in profiling my reference, file I/O is not there. It simply takes up no noticeable amount of time.

    That said, the cycle count will clock the entire program. The physical time count will count only the core parts.

    And the program must be able to run for a configurable number of steps. Best would be a command line parameter.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Presumably this has to be in C/C++?

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    You can write it in Fortran if you want; I have that gcc variant too.

    The rule is that a GNU toolchain must support the code. So you can write it in pure assembly, too, as long as you use AT&T syntax.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Does it have to be for linux, or will Win32 console variants be allowed also?

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    My test computers run Linux only, sorry. I could run programs under Wine, but
    1) I can't compile them, and I don't accept executables and
    2) Wine is 32-bit only and
    3) you'd probably get a considerable performance penalty from Wine.

    However, if you don't have Linux, you could develop using MinGW GCC. I'd be willing to help you in the final stage.
    Last edited by CornedBee; 01-23-2008 at 10:36 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    My test computers run Linux only, sorry. I could run programs under Wine, but
    1) I can't compile them, and I don't accept executables and
    2) Wine is 32-bit only and
    3) you'd probably get a considerable performance penalty from Wine.
    You could use mingw. It's a Linux package (for Debian, presumably downloadable for other distributions) that apparently lets you compile Win32 executables under Linux.

    Or you could wine the compiler. But you're right, of course; performance would be significantly reduced.

    [edit] "April 21th"? Oh, and of course it looks interesting. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  14. #14
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by dwks View Post
    You could use mingw. It's a Linux package (for Debian, presumably downloadable for other distributions) that apparently lets you compile Win32 executables under Linux.
    Yeah, I could do that. But that still prevents me from testing the 64-bit compatibility of the program.

    "April 21th"?
    Hey, I posted this at 1:30 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  15. #15
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by CornedBee View Post
    However, if you don't have Linux, you could develop using MinGW GCC. I'd be willing to help you in the final stage.
    Well, I was planning on using assembly, multithreading and the GPU. Linux does threads differn't from win32 and im not sure if you have RapidMind installed.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Open-source Game Project
    By Glorfindel in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 03-24-2009, 01:12 AM
  2. 2D RPG Online Game Project. 30% Complete. To be released and marketed.
    By drallstars in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 10-28-2006, 12:48 AM
  3. C Programming 2d Array Question
    By jeev2005 in forum C Programming
    Replies: 3
    Last Post: 04-26-2006, 03:18 PM
  4. Game Of Life
    By din1983 in forum C Programming
    Replies: 20
    Last Post: 10-11-2005, 10:36 PM
  5. Please help with some coding..
    By stehigs321 in forum C Programming
    Replies: 2
    Last Post: 10-27-2003, 06:44 PM