Hacker News new | past | comments | ask | show | jobs | submit login
Googling for "conway's game of life" gives a simulation in the results page (google.com)
399 points by huskyr on Oct 12, 2012 | hide | past | web | favorite | 78 comments



Here's the interview I published with the creator! http://www.readwriteweb.com/archives/how-a-google-engineer-b...


> So I made a demo and started showing my co-workers what it was and realized that some of them had never seen the Game of Life before.

So let me get this straight, there are Google software engineers, that passed all the 3 month interview process which some considered the toughest in the world, and they never have heard of conway's game of life.

this makes me feel a little better about myself now.


As a small counterpoint, when I interviewed at Google, one of the interviewers asked me how I might design an app to play the Game of Life, starting with simple cases and scaling up to boards with millions and millions of cells (so it was secretly about designing a distributed computation system, I think).


I would bet that 95% of Google SWEs have heard of the Game of Life, but you can be an exceptionally good software engineer without that knowledge. It's usually considered recreational mathematics, which is a small or non-existent part of most core university CS curriculums, and not everyone in the field explores such topics outside of their formal work or studies.

Also, their interview process is usually not 3 months. Most engineers have a 45-minute phone interview or two, followed by a day of onsite interviews lasting 4-5 hours.


It's possible that not all of the co-workers he showed were engineers.


'Knowing' algorithms is hardly great.

Most of them who cleared it might be kind of guys who read interview questions on programming forums every day and master the art of gaming interviews.


The only reason I've heard of it is that they had the Martin Gardner essay collections at my library growing up.


I find it interesting that your metric of smart is whether or not someone has knowledge of the Game of Life.


I think this is less about IQ and more about culture. (And probably not even about looking down on other people.)


The comment makes no mention of the word "smart", just that Google's interview process is long and hard.


It's hinted at by saying that the author feels better about himself now (implied superiority). Whether the particular trait that he feels superior about is "smart" is left up to your imagination!

I heard about the game of life, but I couldn't tell you the rules or describe it exactly. I never bothered to look into it. Judge away!


My interpretation would be that he saw Google-employees as omniscient demigods, and now has a more realistic view.


Hehehe


> I can’t talk about the way we actually implemented it.

It's all there, right? In obfuscated, minimized, but still-readable JavaScript.


I guess, in the same sense that the implementation of any local binary executable is "all there" because you could theoretically figure out what all the machine code does. (But granted, I'm sure that reverse-engineering obfuscated JS is generally much easier than reverse-engineering a binary.)


Found it and beautified is as much as I could. Really tough to read still: http://cl.ly/K74W


     RWW: So it took two months to do this?

     PD: It’s not a trivial problem. It’s tricky. 
         I’m quite proud of the way I did it. 
         I can’t talk about the way we actually implemented
         it.   (laughs)
I wonder how they implemented it so that it renders so efficiently.


I figured caching the results of common patterns appearing in blocks of 2x2, 3x3, 4x4, etc. pixels which are surrounded by all 'off' pixels, you can easily skip many repetitive calculations.

  ----    ----
  -oo- =\ -oo-
  -oo- =/ -oo-
  ----    ----

  -----    -----    -----
  --o--    -----    --o--
  --o-- =\ -ooo- =\ --o--
  --o-- =/ ----- =/ --o--
  -----    -----    -----

  ------    ------    ------
  -oo---    -oo---    -oo---
  -oo--- =\ -o---- =\ -oo---
  ---oo- =/ ----o- =/ ---oo-
  ---oo-    ---oo-    ---oo-
  ------    ------    ------
Since repeating patterns tend to turn up a lot on their own in CGoL they would end up cached, and large blocks of n cells could be computed in 1 move rather than requiring o(8n) time. That seems to be how Hashlife works: http://en.wikipedia.org/wiki/Hashlife


Here is a CoffeeScript implementation of Hashlife

https://github.com/raganwald/cafeaulife


That does not credit Bill Gosper.

http://www-users.cs.york.ac.uk/~jowen/hashlife.html


Where doesn't it give appropriate credit?

1. The description line for the Github package reads "Gosper's HashLife in CoffeeScript"

2. The readme says: "Cafe au Life implements Bill Gosper's HashLife algorithm."

3. The docs say "Cafe au Life is based on Bill Gosper's brilliant <a href="http://en.wikipedia.org/wiki/Hashlife>HashLife</a...; algorithm."


Well, I could be wrong but I swear did an 'F3' on the page earlier to search for Gosper and it seemed like it wasn't there then.

Apologies for not being able to use a browser and falsely accusing you!


Credit for ideas is important. I'd rather 100 people falsely accuse me than have one omission slip through. Thanks for caring.


FYI: It has its own home page: http://recursiveuniver.se


I think listlife is a simple and efficient algorithm: http://dotat.at/prog/life/life.html

Some years ago I implementend something similiar in javascript: http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/

The benchmark can be really slow in some steps.


I've seen a detailed explanation of a very sophisticated implementation of GOL in java (using caching, cycle detection and similar things), but I can't find it right now. Damn.

Edit: found it http://www.ibiblio.org/lifepatterns/lifeapplet.html

I tend to think of cellular automata optimization as being related to data compression. This is also a simple concept with no simple solution, and what solutions are best depends on the type of data being processed. In Conway's Life, patterns tend to be blobby.

For blobby universes, one should probably consider dividing the universe up into blocks approximately the size of the blobs. For Life, 4x4 to 8x8 seem reasonable. I chose the upper bound, 8x8, for reasons of convenience: There happen to be 8 bits in a byte. I strongly considered 4x4, but it didn't work out as nice....

You should put the blocks in some kind of list, so that you waste zero time in the empty parts of the universe.

Already, note a complication: New elements in the list must be introduced if the pattern grows over a block's boundaries, but we have to know if the block's neighbor already exists. You can either do a simple linear search of the list, or binary search, or keep some kind of map. I chose to make a hash table. This is solely used for finding the neighbors of a new block; each existing block already keeps a pointer to its neighbors, as they will be referenced often.

There must also be an efficient algorithm within the blocks. I chose to primarily blaze straight thru each block. There are no inner loops until all cells in a block are processed. Also, fast-lookup tables are employed. I look up 4x4 blocks to determine the inner 2x2.

Note: CA programs typically consist of 2 main loops (plus a display loop), because CA rules operate on the cells in parallel, while the microprocessor is conceptually serial. This means that there must be two copies of the universe, effectively, so that no important info is destroyed in the process of creating the next generation. Often these 2 copies are not symmetrical. It was a great struggle for me, since almost every time I took something out of one loop to make it faster, I had to add something else to the other loop! Almost every time, that is; the exceptions to that rule lead to the best optimizations. In particular, there are good tradeoffs to be considered in bit-manipulations: shifting, masking, recombining to form an address in the lookup table....

It can also be considered that sometimes the contents of a block may stabilize, requiring no further processing. You could take the block out of the list, putting it in a "hibernation" state, only to be re-activated if a neighboring block has some activity spilling into it. These blocks would take zero processing time, just like a blank region of the universe.

Period-2 oscillators might also not be very difficult to detect, and remove from the processing time. This might be worthwhile in Life, because the blinker is the most common kind of random debris. Higher period oscillators are much more rare. It is also possible that gliders could be detected and simulated. You will get diminishing returns from this kind of optimization, unless you take it to an extreme (cf. HashLife).

Also, a block of cells that's completely empty might not be worth deallocating and removing from the hash table for a while. That takes some processing time, which could be significant in the case of an oscillator moving in and out of its space repeatedly. Only when memory gets low should the oldest blocks from the "morgue" be recycled.

When the program is fast enough, it should be considered that it isn't worth displaying generations any faster than the eye can see, or at least not much faster than the refresh rate of the monitor. Especially in windowed environments, display time can be a real bottleneck.


Meeeeee, too. Me, too. Believe me, I tried.


Can you talk about what is difficult about it? I know that Windows game of life programs can use hashes of positions to compute new steps even for massive worlds very efficiently. Is the JS difficulty with the graphics on the canvas? Or something else?


He wouldn't give me any specifics at all, but I can tell you that the challenge was related to the extremely low tolerance for lag on a search result page that's treated as law company-wide. He had to do it without slowing down the search page AT ALL, for anybody. Check it out; it even works on mobile.


Oh, I thought you meant you tried to implement something like this and had trouble. LOL. Well, thanks.


Great read. Thanks. :)


Glad you liked it. I'm glad people are finding out about this and think it's as cool as I do.


There appears to be a semi-persistent "Google" text - when I cleared out the 'G' it was recreated within 20 steps by the neighbouring 'o'. Can't possibly be organic can it?

E: it seems to always appear like that; so probably not organic and I'm not up for searching minified sources to verify.


It always appears like that because he's written it so that when the "Google" cells are active, they appear darker than normal active cells. Whether these cells get activated or not follow the normal rules of Conway's game of live. So yeah, it's organic, but with a little trickery, the "Google" stands out as the pixels in the area blink on and off.

You can confirm this by pausing the simulation and clicking on all the cells in the region to switch them to the 'active' state: http://imageshack.us/a/img138/2751/71405409.png


It appears that there is some sort of spawning behavior near the darkened "Google" tiles. I paused, turned off all the cells in the region (taking into account wrapping from the other side) and let it go. Cells started activating near the 'e'.


I can confirm this. I wiped all tiles and stepped ahead a hundred frames, but nothing new appeared. As soon as I hit 'play' though, within a dozen or so frames a few random tiles appeared in the vicinity and the area was soon teeming with life again.


Could it be an easter egg?


Was under the impression the whole thing was - just didn't notice it at first and had a bit of a woah moment :)



There's a bunch more here: http://en.wikipedia.org/wiki/List_of_Google%27s_hoaxes_and_e...

Like "zerg rush", "kerning" and "keming", searching for bacon numbers, etc...


Search "number of horns on a unicorn", it gives a google calculator result of 1.


It's basically an alias for 1.

https://www.google.com/search?q=number+of+horns+on+a+unicorn...

I know there are a ton more phrases that work as calculator aliases, but I can't think of any off the top of my head.


Looks like "ascii art" and "comic sans" are retired :(


hey pixelbeat, another one for the list - looks like "octal" returns the number of search results in octal


Same for binary & hexadecimal. Man, those guys are engineers indeed. Always going the full mile...


Heh, I implemented the [binary]/[octal]/[hexadecimal]/[hex] ones, and was TL for [let it snow]. :-)


Predicting the next HN front page article in the near future: "Show HN: weekend project - open source Google's conway's game of life"


Peaking at #3: "Screencast: Learn Go by Implementing Google's Game of Life."

And from the 2010 archives: "Conway's Game of Life is a Monad."


Well, I was predicting the past, not the future, although this post got 2 points (1 is mine)

http://news.ycombinator.com/item?id=4314049

Here is the original: http://arcanis.github.com/trivia.gol404/404.html

3% CPU max


"Do you still want to be writing Game of Life easter aggs when you're 50?"


And the rebuttal, "Yes, I want to be writing Game of Life easter eggs"


What is it with all the Game of Life posts lately? There seems to be a new one every other day. Not that it's a bad thing, I think the GOL is a marvellous thing and the SmoothLife video was mesmerizing. I'm just wondering why they all pop up at the same time?


I'm sure there is a "game of life" like biological algorithm that can explain this and the flow of articles in the form of "X in GO" or "Don't use MongoDB" or "Y in pure CSS"

e.g. perhaps people see what's top on HN (a legitimate article) and search on the topic, and increase the probability of more posts in that topic, also, psychologically, if A is popular, then when seeing something that looks like A you might up vote it just by assuming it's popular too.


A Game of Life type visualization of this algorithm would be interesting. It might go something like:

  The seed of the system is a random cluster of N stories (cells)
  that represent the "front page".

  Each cell has votes and topics (Erlang, Apple, X in CSS, etc.).

  1. Any cell with fewer than N votes, 
     and fewer than two neighbors dies 
     (due to lack of interest and/or promotion).

  2. Any cell with two or three live neighbors,
     lives on to the next generation
     (riding along the front page wave).

  3. Any cell with more than three live neighbors,
     that share the same topic dies
     (due to overexposure of the topic).

  4. Any dead cell with exactly three live neighbors,
     becomes a live cell with a topic shared by one of the neighbors
     (the spread of interest of a topic).

  After any generation, votes and stories can be added. 

  The low threshold of votes (N), is determined to be
  some percentage of all votes in the system.
Tempted to make this for fun now...


Seeing one Topic-X post will trigger many people to think, "Oh, and I remember Y-related-to-Topic-X," as well as "Hey, I wonder if I could find out more about Y-related-to-Topic-X," and away you go.

Also, http://www.amazon.com/Bursts-Hidden-Pattern-Behind-Everythin... (even though it is not a great book; it is mediocre IMO).


Well, I personally saw a game of life post earlier today. Upon doing a google search I independently discovered this search result (slightly later than the OP). If I were so motivated I would have posted it myself.


Is it my imagination or does it spell out google at some point?

edit: I've realized that certain blocks are darker blue in the shape of the word Google.


It's funny. I simply Googled for 'conway's game of life' after reading all the posts here and was pleasantly surprised to find this nice easter egg. I submitted it, and now it has been #1 for the past couple of hours :)


I've implemented Langton's Ant, another example of cellular automata, using canvas aswell http://alecraeside.com.au/projects/langtons-ant/


First the knowledge graph, now the game of life animation.

It really seems Google is trying to be more and more like Wolfram|Alpha!

:)


I just checked Wolfram Alpha and couldn't find the Javascript animation of game of life. Could you link me to how you did it?


Every time you do a query on W|A you see a brief animation of the game of life while the result is loading. I was referring to that.

(and my comment was meant tongue in cheek)


I want this as a live-tile background for my phone. Beautiful


I am in Malaysia and it doesn't show up in FF or Chrome.


Cool! A glider crawled all the way across my browser.


just spent 10 minutes staring at it full-screen.. beautiful.. my wife looked at my twinkly eyes and asked befuddled: "what is this?"

How would you explain it?


Ha, my daughter asked the same question, so I tried explaining all 4 rules, but she didn't seem to be very impressed. So I quickly googled, found this http://www.bitstorm.org/gameoflife/ among the top result, and we went through all 4 rules, experimenting. That was a lot more interesting, especially when she found out about the 'objects'... :) So the page is bookmarked now :)


Hehe, yeah, I tried explaining too, with all my passion, she just stared at me and said: "I have a nerdy husband" -_-'

I'll give it another shot with that link, perhaps tomorrow :)


What a reminiscent moment :)


not for me


If you are on a big screen, it might not be obvious. It's in the upper right and it's very subtle.


Very, very subtle. I had to adjust the angle of the screen


It might be worth recalibrating your screen. This page ff. is a good start: http://www.lagom.nl/lcd-test/contrast.php


It might also be dependent on the angle at which one is viewing the LCD -- on my laptop at work, I often cannot distinguish some of the lighter shades, as I have the screen at a glare-reducing angle.


Didn't work in Firefox for me, but worked in Chromium.


working in FF for me:)


Don't forget to allow scripts :D


And set an inconspicuous user agent!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: