<a title="Conway's Game of Life" href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Conway's Game of Life</a> is a popular zero player cellular automaton devised by the John Horton Conway in 1970. Each cell has 2 states: live or dead. There are 4 simple rules that determine this:
<ul>
<li>Any live cell with fewer than two live neighbours dies, as if caused by under-population.</li>
<li>Any live cell with two or three live neighbours lives on to the next generation.</li>
<li>Any live cell with more than three live neighbours dies, as if by overcrowding.</li>
<li>Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.</li>
</ul>

The game makes for a fun evolution as the player sets the initial condition and then observes the evolution of the game.

From a programmer's perspective, the game is closer to an image processing algorithm. The "world" is a 2D image, where each pixel is a cell.
The state of a cell at a time is solely determined by the number of neighbours at the previous step. Hence this makes for an embarrassingly parallel image processing algorithm. Ting Ting Ting. GPUs!!!

The number of neighbours can be computed using a convolution kernel:
<a href="http://sandbox.arrayfire.com/wp-content/uploads/2014/12/kernel_CodeCogsEqn1.png"><img class="size-full wp-image-7582 aligncenter" src="http://sandbox.arrayfire.com/wp-content/uploads/2014/12/kernel_CodeCogsEqn1.png" alt="kernel_CodeCogsEqn" width="159" height="67" /></a>

Since the value of the a cell can be represented as 1 (live) and 0 (dead), using convolution will give us the number of neighbours of any cell. The center value of the kernel is 0 as we do not want to count the cell itself.

Here is a general overview of a convolution operation:
<a href="http://sandbox.arrayfire.com/wp-content/uploads/2014/12/convolve_CodeCogsEqn.png"><img src="http://sandbox.arrayfire.com/wp-content/uploads/2014/12/convolve_CodeCogsEqn.png" alt="convolve_CodeCogsEqn" width="978" height="150" class="alignnone size-full wp-image-7588" /></a>

Plugging in 1s or 0s into the A matrix, we can see that this convolution operation will give us the neighborhood of each cell.

The next step is to compute the next state of the cell. Lets convert the rules into psuedocode.
<pre>
if(cell == 1 && neighbours < 2)                       -> cell = 0
if(cell == 1 && (neighbours == 2 or neighbours == 3)) -> cell = 1
if(cell == 1 && neighbours > 3)                       -> cell = 0
if(cell == 0 && neighbours == 3)                      -> cell = 0
</pre>

But we can optimize these as below:
<pre>
if((cell == 1 || cell == 0) && neighbours < 2)  -> cell = 0 // Since this does not make a difference to dead cell
if(cell == 1 && neighbours == 2)                -> cell = 1
if((cell == 1 || cell == 0) && neighbours == 3) -> cell = 1 // Since in both cell cases, the cell is alive in the next state
if((cell == 1 || cell == 0) && neighbours > 3)  -> cell = 0 // Since in dead cell can't become live with more that 3 neighbours and an alive cell would die
</pre>

Removing redundant conditions:
<pre>
if(neighbours < 2)                  -> cell = 0
if(cell == 1 && neighbours == 2)    -> cell = 1
if(neighbours == 3)                 -> cell = 1
if(neighbours > 3)                  -> cell = 0
</pre>

Lets say A is the current state of the cell and neighbourhood values are in matrix NHood.
We can compress the conditions into the following code:
<pre>
NHood = convolve(A, kernel);
cond0 = (NHood < 2 ) // All cells with less than 2 neighbours will have value 1, others will be 0
cond1 = (NHood == 2) // All cells with exactly 2 neighbours will have value 1, others will be 0
cond2 = (NHood == 3) // All cells with exactly 3 neighbours will have value 1, others will be 0
cond3 = (NHood > 3 ) // All cells with more than 3 neighbours will have value 1, others will be 0
</pre>

But here is the best optimization - Only 2 of these conditions matter: cond1 and cond2.
Using psuedocode:
<pre>
(NHood < 2 || NHood > 3) is equivalent to !(NHood == 2 && NHood == 3)
//Or
!(cond0 + cond3) = cond1 * cond2.
</pre>

Let see how we can compute the next state using just these two conditions.
For cond2 it is straight-forward. Any cell that is 1 in cond2 will be 1 in the next state irrespective of its value in A.

For cond1, all alive cells in A with 1 in cond1 will remain 1. All cells become dead if the corresponding value in cond1 is 0. This condition can be satisfied by doing (A * cond1).
That is, if(A && cond2) = A, else A = 0.

Hence the next state can be computed by:
A = A * cond1 + cond2;

And this is what ArrayFire is best at. Given is powerful API of element-wise operations and image processing algorithms, implementing the Game of Life is a breeze. Below is the entire ArrayFire code that is required to run Game of Life.

<pre>
// Initialize the kernel array just once
static const float h_kernel[] = {1, 1, 1, 1, 0, 1, 1, 1, 1};
static const af::array kernel(3, 3, h_kernel, af::afHost);
int wId = -1;

// Generate a random starting state
static const int game_w = 100, game_h = 100;
array state = (af::randu(game_h, game_w, f32) > 0.33).as(f32);  // Generates a 0s and 1s array based on random values
while(wId != -2) {
     // Convolve gets neighbors
     af::array nHood = convolve(state, kernel, false);

     // Generate conditions for life
     af::array C0 = (nHood == 2);
     af::array C1 = (nHood == 3);

     // Update state
     state = state * C0 + C1;
     
     // Display
     wId = image(state, wId, "Conway Using ArrayFire");
}
</pre>

<iframe src="http://gfycat.com/ifr/ChiefCheeryChrysalis" frameborder="0" scrolling="no" width="448" height="360" style="-webkit-backface-visibility: hidden;-webkit-transform: scale(1);" ></iframe>

This code is fully platform independent as it uses ArrayFire.

Let us know if you have made any cool applications using ArrayFire.