Thread: Game of Life

  1. #61
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah, don't worry about getting mine to work the way its meant to (as in reading from a file and printing output). Since it dosent meet the criteria I'm fine with just saying it comes in last, but it would be nice to see how the other guys did it.

  2. #62
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by mike_g View Post
    Yeah, don't worry about getting mine to work the way its meant to (as in reading from a file and printing output). Since it dosent meet the criteria I'm fine with just saying it comes in last, but it would be nice to see how the other guys did it.
    I'd post my source code here but the board won't let me attach a .tar.gz or .zip file. So, hopefully I'm not breaking any rules by doing this, but here's a link where you can download my submission (there is no binary, you'll have to compile it)

    http://www.codepsycho.org/brewbuck/brewbuck-gol.zip

  3. #63
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Congrats, I think its safe to say that that will beat my version Now we just have to see what jessycat comes up with.

    Tbh I expected someone would come up with a gridless version using some sort of data structure. I kinda got myself stuck with a grid from the start. That said I dont know if I would have been able to come up with a gridlees version anyway. Never really expected it to use a hashmap, but then I don't know exactly what a hasmap is yet. I only used one once in a java project, mostly because I wanted to avoid using array lists for everything, but it also seemed good for pairing strings. This is the first time I have seen one used for ints tho.

    I was planning on limiting the iterations on my grid by looping from the minimum active y pos -1 to the maximum +1; same for x. Never got around to it though so mine would be hideously slow. I also never got around to packing the cell states into bits (instead of bytes), it looks like you did. I think it would have been easier for me to do this in C++, shame i know so little about it. When college is over I'll try spend some more time learning it.

  4. #64
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by mike_g View Post
    I was planning on limiting the iterations on my grid by looping from the minimum active y pos -1 to the maximum +1; same for x.
    Yes, limiting the scope of where you are looking can give you a huge gain, because it lets you allocate a very large grid without necessarily having to check it all. In my first implementation I used a grid with this scope-limiting optimization. It was almost as fast as the gridless version, but of course uses tons of memory. The gridless version solves the challenge while using less than a megabyte of RAM.

  5. #65
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    I went with a combination of a specialized linked list for the live cells, and a malloc'd "2-d array" for fast neighbor access. It tries to limit the amount of memory malloc'd at any given time for the array by incrementally malloc'ing only as the pattern grows. The test pattern that CornedBee posted ended up using like 3MB as I watched it unscientifically in Sysinternals Process Explorer, but the entire 3,000 generation run of the program only took about 10 seconds. My test computer is an AMD 1700+ 1.4Ghz, 512MB Ram, development in Cygwin under WinXP Pro.

    I'm pretty proud of my program and would like to show it off, but I don't know where I could put it to make it available for download. I can e-mail my .rar to someone if you want to post it like brewbuck did for others to download and play with, or if someone shows me where I can easily upload it for public distribution I will do that. It's a whopping 29k .rar file, which includes the source files and a Makefile, a few test patterns and documentation for how the different parts of the program work. The compiled executable is 46k under gcc (program is in C).

    I got stuck on grids too because my algorithm relies on accessing x,y coordinates. I did think of a few ways to modify the abstraction of a "grid" while not changing how my algorithm works.

    One idea to limit memory use was to use a linked list of linked lists (2-d linked list if you will) which is a linked list of structures to represent the y coordinate (rows), with each row a linked list of structs to represent the x coordinate. So then if there were only 2 cells on the board, one at (-1000000,-1000000) and the other at (+1000000,+1000000), the grid would only need to use memory for 2 cells: 2 entries in the y list (+1000000 and -1000000) and each of those entries having a single entry in the sub-list. The cost of traversing the linked list to look for neighbors however seemed like it would take my program out of competition.

    I then thought about using a 2-d Binary Search Tree in place of the 2-d linked list so that access time would be reduced a bit (no need for a linear search when a binary search is faster and relatively simple). And given that input files are likely to have cells added in a more or less sequential manner which is bad for a basic BST, a 2-d AVL tree or R/B Tree. I never got around to implementing this method though, so I have no idea if it would have been a disaster or something viable, or if I would have had to go further and use an AVL or R/B Tree.

    Just please, when you do finally see my program, don't laugh too much at my code... I only do this as a hobby.
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  6. #66
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by jEssYcAt View Post
    I'm pretty proud of my program and would like to show it off, but I don't know where I could put it to make it available for download. I can e-mail my .rar to someone if you want to post it like brewbuck did for others to download and play with, or if someone shows me where I can easily upload it for public distribution I will do that.
    If you want I can host it on codepsycho.org -- PM me and I'll PM you back an email address to send it to, and I'll put it up.

    I went with a combination of a specialized linked list for the live cells, and a malloc'd "2-d array" for fast neighbor access. It tries to limit the amount of memory malloc'd at any given time for the array by incrementally malloc'ing only as the pattern grows
    So, your grid basically holds pointers to the cells in the linked list? That is conceptually similar to how my version works (fast iteration over active cells + quick lookup of neighbors), except that the list and the grid are both represented in a single data structure (hash table).

    Sounds cool.

  7. #67
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    Actually the grid holds integers (unsigned char, so 0..255) that keep track of whether a cell is alive or dead, and a sentinel value dictates how those numbers are interpreted during an update. Between updates, if you wanted to print the grid for example, it is universal that an odd value (board[x,y] & 1) is a live cell and !(board[x,y] & 1) is a dead cell. During an update it gets a little more complicated, but only involves one more comparison than this to determine whether it is alive or dead.

    The list of cells is a specialized singly-linked list. During an update, it iterates over the linked list from the head to the tail, and as it goes it deletes cells from the list in the normal way, but a new cell added to the list is added at the head of the list so we can continue traversing this one list to the tail without re-processing the new cells on this update. It also allows us to not need more than this one list throughout the run of the program.

    The grid is a mirror of the list for neighbor lookup only. The grid is updated as we traverse the list, but when we do a reset after the 63rd generation, we don't need to do anything except wipe the board to 0's and re-stock it from the list with 1's for live cells. Since we are only doing this 1/63 of the time, we can do a few complex operations without a significant time penalty, such as re-centering the pattern by shifting each cell in the list.

    It is conceptually simple (to me anyway, probably because I came up with it) but I don't know how to explain it without taking a few pages. I looked all over the place for ideas on how to implement something like this, but I did not find anything, so as far as I am aware this is an original idea. I invite comments, critiques, criticism and suggestions. I know this can be improved.

    I will PM you now but I won't be able to e-mail it until I get home (I'm at work... *innocent whistle* Don't tell anyone!).
    Last edited by jEssYcAt; 05-08-2008 at 01:34 PM.
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  8. #68
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    My entry is now up, courtesy of brewbuck (thanks!!!), at http://www.codepsycho.org/jessycat/ver2.1.rar if anyone wants to look at it. Be brutal, tell me how bad it is, I can take it!
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  9. #69
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    Quote Originally Posted by CornedBee View Post
    Seems to me like you have out-of-bounds memory accesses and you check them after the fact in livingcell and deadcell. Also, the upper bound check in those functions is incorrect.
    ...
    So, does this mean you are thinking about the Game of Life now? ;o)
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

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


    Sorry, but there's a slight difference in the amount of time invested here.
    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. #71
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    *childishly impatient* Fine! :P~~~

    (I learned that from my 5 year old, and my 1 year old is learning that from him too!)
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  12. #72
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    OK, I made a preliminary test, using only the 64-bit machine and one of the input patterns (the one with many live cells, which probably gives brewbuck's solution a penalty).

    jessycat's makefile compiled in debug mode by default. The program sped up by a factor of three when I changed that.

    The rough results, using time to time 3000 generations:

    brewbuck:
    Code:
    time ./gol 3000 ../../f0.l > f3000.l
    
    real    0m6.863s
    user    0m6.810s
    sys     0m0.032s
    jessycat:
    Code:
    time ./life.exe ../../f0.l 3000 -o f3000.l
    
    real    0m2.614s
    user    0m2.578s
    sys     0m0.023s
    my team:
    Code:
    time ./bin/gcc-4.1.2/release/gameoflife --init-module=ertl --init-file=../../../f0.l --snapshot-module=ertl --steps=3000
    Initialization done.
    
    real    0m0.004s
    user    0m0.002s
    sys     0m0.002s
    The reference program given to us in our course (note: only 500 steps - 3000 take just about forever):
    Code:
    time ./life 500 < f0.l > out.l
    841 cells alive
    
    real    0m24.835s
    user    0m24.430s
    sys     0m0.009s
    I ran the tests several times, and the results were pretty much consistent. All programs generate the correct result.


    Should I still do more precise tests?

    Edit: mike_g, I'm not quite sure what to do with your submission.

    Edit 2: You can download my program here:
    http://www.cornedbee.com/files/cornedbee_gol.zip

    It's very complex, but most of the files are just fluff (like writing the result to a PNG instead of the output format - if I hadn't written that feature, we'd have never found some of the more tricky bugs). The real work is done in gameoflife.cpp, most importantly in step() and compute_block().
    Unfortunately my colleagues had a tendency to write the (sparse) comments in German. Also, all the external documentation we have is in German.

    By the way, if you want to compile this thing, you'll need a 64-bit Linux and Boost 1.35 or trunk. I never got around to making our last-minute changes portable; instead we just optimized for the target machine (a Core2). Given a correctly set up system, just type
    bjam release
    in the expansion directory, then write
    ./bin/gcc/release/gameoflife --help
    to get an overview over the options. See the command I used above for the way to do the real computation.



    Anyway, thanks for participating. I won't pretend I actually understand your code.
    Last edited by CornedBee; 05-19-2008 at 04:20 PM.
    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. #73
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Way to go JessyCat!

  14. #74
    verbose cat
    Join Date
    Jun 2003
    Posts
    209
    D'oh, I forgot about the Makefile compiling with -g. Did you just remove the -g or did you add other things? I haven't messed much with the optimization options (-O1, -O2 and -O3, right?) and don't know if there are any others that would be applicable.

    Thanks brewbuck! I like how your program works. It gave me some ideas on how to "improve" my own solution, though it remains to be seen whether it would actually improve it or not.

    Thanks for holding the contest, CornedBee! I kinda wish there were more entries just to see other solutions (I never even came close to thinking along brewbuck's idea in my own brainstorming), but I am happy that mine was the fastest.

    Well, between mine and brewbuck's anyway. GOOD GRIEF!!! 0.004 seconds?!?! It takes longer for me to blink! I'm going to have to dissect that... and how about the reference program? Does it just do something like allocate an array and iterate over every cell, live or dead? Or does it optimize anything anywhere?

    Quote Originally Posted by CornedBee
    It's very complex, but most of the files are just fluff (like writing the result to a PNG instead of the output format - if I hadn't written that feature, we'd have never found some of the more tricky bugs).
    I wrote a utility (show.exe) that turns the output into a text grid. I found several of my own issues using that and notepad.
    Last edited by jEssYcAt; 05-19-2008 at 06:25 PM.
    abachler: "A great programmer never stops optimizing a piece of code until it consists of nothing but preprocessor directives and comments "

  15. #75
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    The reference program uses a linked list of all live cells without any ordering. Counting the live neighbors of a cell thus involves iterating over the entire list. The runtime is quadratic in the number of live cells.

    I'll see if I can translate our presentation about the program.
    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

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