My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Reply
 
LinkBack Thread Tools Display Modes
December 2nd, 2007, 05:56 PM   #1
 
Joined: Dec 2007
Posts: 138
Conway's Game of Life

I'm beginning work on a Scheme implementation of John Conway's Game of Life.

I'm wondering: Should I use a n x m binary grid, with n and m defined at initialization, and anything that falls off the edges ignored, or should I use a list of points that are occupied, enabling me to do simple arithmetic, rather than probing a large list.

The grid would be easier to work with and easier to display, but it would need a memorization function or it would be horribly slow.

If I used the list, it would be the memoization function. I would just have to make sure I started deleting things before a gun or puffer crashed my computer. Also, display would require conditionals, that may slow a visible implementation down to the same speed or slower than a grid. However, if I'm just interested in automaton theory, I wouldn't see this as that grand of a problem.
cknapp is offline  
 

My Computer Forum is free to register and we welcome everyone!

December 6th, 2007, 07:24 AM   #2
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

I don't think a grid would be bad at all, especially since I don't think it would be all that sparse. A 500 x 1000 grid would be what, 62 kB?

Another possibility would be to block the grid into, say, 3x3 or 4x4 squares and store each as a unit. The interaction between blocks would be more complex, but you'd have only 1/9 or 1/16th the number of blocks vs. cells. This would really only be worthwhile if you found a way to store them that lets interaction be calculated quickly.

On that subject, perhaps it would be worthwhile to store the cells less efficiently if it would let you calculate generations more quickly. I can imagine storing two binary grids (vertical and horizontal) redundantly, then using offsets and boolean relations on them to calculate "in parallel" the next generation. Obviously this is only fast if the grid is small enough so two copies fit in the cache and large enough that naive methods for computing further generations are slow.
CRGreathouse is offline  
December 6th, 2007, 09:37 AM   #3
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Quote:
Originally Posted by CRGreathouse
I don't think a grid would be bad at all, especially since I don't think it would be all that sparse. A 500 x 1000 grid would be what, 62 kB?
I'm not too worried about space, but a 500 x 1000 grid would take 500k tests just to find where the live cells are. Granted, they're already boolean values, but still. Then you'd still have to go through the process of figuring out how many to change. I could store the grid and the list of occupants.

Quote:
Another possibility would be to block the grid into, say, 3x3 or 4x4 squares and store each as a unit. The interaction between blocks would be more complex, but you'd have only 1/9 or 1/16th the number of blocks vs. cells. This would really only be worthwhile if you found a way to store them that lets interaction be calculated quickly.
inter-cell interactions sounds like a nightmare to me... although it may be fun...

Quote:
On that subject, perhaps it would be worthwhile to store the cells less efficiently if it would let you calculate generations more quickly. I can imagine storing two binary grids (vertical and horizontal) redundantly, then using offsets and boolean relations on them to calculate "in parallel" the next generation. Obviously this is only fast if the grid is small enough so two copies fit in the cache and large enough that naive methods for computing further generations are slow.
This might be difficult to code, but it actually sounds pretty fun...

A professor suggested I store the adjacent cells, in place of (or maybe in addition to) the occupied cells. I'm wondering how this would work...


Maybe I should stop thinking and start doing... Oh! Finals week! Right!
cknapp is offline  
December 6th, 2007, 12:10 PM   #4
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

Quote:
Originally Posted by cknapp
I'm not too worried about space, but a 500 x 1000 grid would take 500k tests just to find where the live cells are. Granted, they're already boolean values, but still. Then you'd still have to go through the process of figuring out how many to change. I could store the grid and the list of occupants.
Sure, but what if 200,000 cells are alive? Then it's the list would be horrible, taking up 780 kB at two 4-byte ints each and taking 8 million comparisons to find adjacent cells using binary searches (assuming only 2 searches are needed instead of 8 for each cell).

Quote:
Originally Posted by cknapp
A professor suggested I store the adjacent cells, in place of (or maybe in addition to) the occupied cells. I'm wondering how this would work.
I have no idea how it would work, let alone efficiently.
CRGreathouse is offline  
December 6th, 2007, 04:05 PM   #5
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Quote:
Originally Posted by CRGreathouse
Sure, but what if 200,000 cells are alive? Then it's the list would be horrible, taking up 780 kB at two 4-byte ints each and taking 8 million comparisons to find adjacent cells using binary searches (assuming only 2 searches are needed instead of 8 for each cell).
200,000 live cells in a 500,000 cell board? As I'm sure you know probability theory than I am, could you please lead me in the correct direction for finding out the chances of such a configuration being formed and the chances of such a configuration being even remotely stable? Intuitively (which admittedly doesn't say much...), a configuration with a density that high will will almost certainly collapse. Either way, the average case is going to be much less than this.

Since I'm doing this in large part to learn Scheme, I checked the R6RS; A quick search found nothing concerning operations with less than 1 byte of data, which means I'll assume all data (including #t and #f) is stored in bytes. Which means even with two 4byte ints (which isn't necessarily the size in which they're handled), you'll need an average of 1/8 of the cells to be filled in order to take up the same space as a grid. This would require conscious use of the whole board, or an extremely intricate configuration, since all "notable" patterns either move directly in one of 8 directions, or stay still.
cknapp is offline  
December 7th, 2007, 06:11 AM   #6
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

Quote:
Originally Posted by cknapp
Quote:
Originally Posted by CRGreathouse
200,000 live cells in a 500,000 cell board? As I'm sure you know probability theory than I am, could you please lead me in the correct direction for finding out the chances of such a configuration being formed and the chances of such a configuration being even remotely stable? Intuitively (which admittedly doesn't say much...), a configuration with a density that high will will almost certainly collapse. Either way, the average case is going to be much less than this.
First, it doesn't need to be stable -- a chaotic configuration can stay fairly dense for a while, though 40% would be tough to keep. But even 10% density would favor a bit array.

Quote:
Originally Posted by cknapp
Since I'm doing this in large part to learn Scheme, I checked the R6RS; A quick search found nothing concerning operations with less than 1 byte of data, which means I'll assume all data (including #t and #f) is stored in bytes. Which means even with two 4byte ints (which isn't necessarily the size in which they're handled), you'll need an average of 1/8 of the cells to be filled in order to take up the same space as a grid. This would require conscious use of the whole board, or an extremely intricate configuration, since all "notable" patterns either move directly in one of 8 directions, or stay still.
Who cares? Just store 8 cells in a byte. Now you'd only need 1/64 to be filled to break even sizewise, and even then I think the bit array would be faster.

Of course you could just write it both ways. Then you could test it with both and find out how good they are in your implementation, and if you were courageous you could even have it toggle between them when some threshhold is met. (If you do this, be sure to use an asymmetric threshhold: change to the sparse representation at < 2%, say, and change to the bit array at > 3%, so you aren't wasting lots of resources toggling between when density is around the critical figure.) Best of both worlds! Of course that's considerably more challenging to write.
CRGreathouse is offline  
December 7th, 2007, 08:15 AM   #7
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by cknapp
Of course you could just write it both ways. Then you could test it with both and find out how good they are in your implementation, and if you were courageous you could even have it toggle between them when some threshhold is met. (If you do this, be sure to use an asymmetric threshhold: change to the sparse representation at < 2%, say, and change to the bit array at > 3%, so you aren't wasting lots of resources toggling between when density is around the critical figure.) Best of both worlds! Of course that's considerably more challenging to write.

Yeah... I think that's what I'm going to do... write both and test. Because at this point I'm intrigued to see them compared.
cknapp is offline  
December 10th, 2007, 06:26 AM   #8
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

So, any progress so far? I'm curious to see how the theory performs in practice.
CRGreathouse is offline  
December 10th, 2007, 02:27 PM   #9
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Quote:
Originally Posted by CRGreathouse
So, any progress so far? I'm curious to see how the theory performs in practice.
Well... it's finals week, so I "don't have much time" to program... except I've worked more on this than studying :shock:
Right now, the most obvious solution is sort of something in between the two. Once I start seeing what's happening a little more, I'll fork it, and edit it accordingly. I should have "something" before Christmas, and be "finished" with both implementations by the end of break, but I'll let you know once I have something.
cknapp is offline  
December 15th, 2007, 10:15 PM   #10
 
Joined: Dec 2007
Posts: 2
Re: Conway's Game of Life

In order for the game to work correctly, you'd have to go through two cycles of cells. The first would be to check whether the cells need to die, or live, and the second would be to actually kill off cells. I would first, in the name of OOP, create a class which represents a single cell, which can have a field of "what to do next generation". Then just implement a 2d array of these cells and just loop through, giving them the condition check. If you ignore the edges and give a legality for bounds, then the program will run fine and the edge won't really change the function of the game.
XTTX is offline  
December 16th, 2007, 09:30 AM   #11
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Quote:
Originally Posted by XTTX
In order for the game to work correctly, you'd have to go through two cycles of cells. The first would be to check whether the cells need to die, or live, and the second would be to actually kill off cells. I would first, in the name of OOP, create a class which represents a single cell, which can have a field of "what to do next generation". Then just implement a 2d array of these cells and just loop through, giving them the condition check. If you ignore the edges and give a legality for bounds, then the program will run fine and the edge won't really change the function of the game.
While I could, and may, go with an object oriented design, I'm doing this primarily as an experiment in Scheme, which means an OOP design isn't necessarily the most natural. While that is an interesting, and seemingly effective OOP design, this seems to be a problem where OOP isn't the most effective approach, especially if I'm using a multiple-paradigm language.
cknapp is offline  
December 16th, 2007, 03:52 PM   #12
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

Quote:
Originally Posted by XTTX
I would first, in the name of OOP, create a class which represents a single cell, which can have a field of "what to do next generation".
That would typically require 8 bytes per cell (since on most 32 bit machines a boolean value is stored in a 32-bit word) which might be a lot to ask.
CRGreathouse is offline  
December 24th, 2007, 02:13 PM   #13
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

I finally get what I'm doing with the language, so I should be finishing both implementations within a week...
However, I'll be in Hawaii until the 2nd, so one week may mean "1 week from January 2nd"; it just depends on how much free time I have in the evenings.

I'll then test them and see.
Although I am now seeing how it may be cumbersome to use a list to store values... updating the list is angry
I still need to figure out the arithmetic to use to avoid the large list, but that won't be difficult; it'll just take a little bit of time.

Cheers
cknapp is offline  
December 26th, 2007, 01:55 PM   #14
 
Joined: Dec 2007
Posts: 232
Re: Conway's Game of Life

I look forward to seeing your code when you get back.
CRGreathouse is offline  
January 5th, 2008, 11:53 AM   #15
 
Joined: Dec 2007
Posts: 138
Re: Conway's Game of Life

Update: So... It is actually remarkably easier to code, and rather simple your way... I haven't actually worked on the way I was going to do it, but I would essentially have to change everything from a location reference to a dotted pair, and then use much more complicated procedures...

I have no doubt that it will be more computationally intensive; thus, I admit defeat

Anyway, I'll have the code done in a day or two; I need to go through my code and handle empty lists and such... I forgot to do that as I wrote the algorithm, and am paying for it now while I try to run the program. I also need to automate the process and add the ability for the user to actually seed the system.

I'd do it today, but I'm at a cafe and by battery is about to die, and this has been a rather busy break.

On another note, I used mit-scheme, which has a bit-string library. I tacked the following library onto it, to make it less annoying to actually call the procedures. In order for the code I eventually publish to run, you need mit-scheme (or an implementation with the same bit-string procedure calls... scheme48 does not have these) and the following code. I would put them into a file named something like "bitstring.scm" and add the statement (load "[path]/bitstring.scm") to your scheme init file (read documentation for init file on your OS)

anyway, here's code:
Code:
 (define (bit-set string bit)
   (if (< bit (bit-string-length string))
     (bit-string-set! string bit)
     )
   )
 
 (define (bit-clear string bit)
   (if (< bit (bit-string-length string))
     (bit-string-clear! string bit)
     )
   )
 
 (define (bit-flip string bit)
   (if (bit-string-ref string bit)
     (bitclear string bit)
    (bitset string bit)
     )
   )
 
 (define (bit-length string)
   (bit-string-length string)
  )
 
 (define (next-bit string start)
   (bit-substring-find-next-set-bit string start (bit-length string))
   )
cknapp is offline  
Reply

  My Computer Forum > Computer Science Forum > Theory of Computation

Tags
conway, game, life



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Intels new game online JohnnySaur Computer Science 4 July 11th, 2012 03:30 AM
Which Computer Game do you like ? Imanuel4u New Users 12 December 2nd, 2010 10:14 PM
Game problem, pleas help! chetanbhasin Computer Science 0 August 11th, 2010 11:57 PM
Game- ready model shops Tinlau New Users 2 April 6th, 2010 01:29 AM





Copyright © 2018 My Computer Forum Forum. All rights reserved.