In this post we’re going to do something crazier and more original than usual. We thought that it would be interesting to execute Conway’s Game of Life in Hadoop using Pangool (for those who don’t know what Pangool is, it is an open-source project that we have developed for facilitating low-level development with Hadoop). Through a parallel execution we’ll be able to calculate sequences of the game from multiple initial configurations. The ultimate purpose of the execution will be to find curious sequences, such as sequences that need a lot of iterations to reach convergence even with a small, finite space.

Conway’s Game of Life

Conway’s Game of Life is a superb example of a cellular automaton with a very simple set of rules through which an enormous complexity emerges. Let’s remember its rules:

• Any dead cell with exactly 3 live neighbors becomes a live cell.
• Any live cell with either 2 or 3 live neighbors lives on to the next generation. Otherwise, it dies.

An example of the astonishing results that we can achieve with the Game of Life is the following automaton (Glider gun):

It is possible to find complex and interesting patterns in the Game of Life through analytical methods. It is even possible to build a Turing machine with it (see this link and also this one). Who would have imagined that two simple rules would lead to 40-page-long mathematical proofs?

In this page, you can find some curious patterns.

The Game of Life in Hadoop

We’ll use a rather ordinary method for finding patterns in the Game of Life. You’ll obviously know it: it is called brute force. Using Hadoop, we’ll calculate multiple sequences and we’ll emit the initial configuration of each of them together with the number of iterations that they need for reaching convergence.

In order to calculate multiple sequences of the Game of Life, we have used the following method:

• Initial configuration encoding: Given a nxn matrix, how many initial configuration sequences can we calculate? A simple approximation would be to consider that each cell in the matrix may, or may not, be alive. In this manner, for a matrix of size “n” we have 2^(n*n) possible initial configurations. Actually, this first approximation is a bit over-sized because some of the configurations die in one iteration or are equal to others because they have been scrolled through the matrix, but it is good enough. For n= 2:



• We’ll encode each initial configuration as a “long” (8 bytes). This would allow us to calculate all the possible initial configurations in an 8×8 matrix – which is a computation that would never be completed, even in the largest Hadoop cluster in the universe (as there would be 2^64 things to compute). The way to encode an nxn matrix would be by taking each cell as a bit with a value of 0 or 1 and deriving a numerical value from the resulting 8 bytes.



• Convergence detection: While we execute the Game of Life, how do we know if the automaton reached convergence? There are several possible endings for the game. In one case, all the cells disappear and the grid becomes empty (this is quite easy to detect). In another case, each cell collapses into a stable structure and they don’t move further anymore (this is also easy to detect). In a less likely case, the cells return to a previous state, which will produce an infinite loop. Therefore, we need to have memory with all the states the game goes through. In addition, we need to be able to detect equivalent states – scrolled states. For that we’ll center the automaton in (0, 0) after each iteration and we’ll save the current state as a set of bits in a finite state memory.



• In order to execute the game we’ll use a fixed-size grid so that we do not run out of memory and a maximum number of iterations (both things being configurable). For instance, a 32×32 grid and 1000 iterations (note that the size of this grid has nothing to do with the size of the matrix that we used for calculating all possible initial states). These restrictions pose a limit on what we will be able to calculate, since, on one hand, the automaton may want to expand beyond a 32×32 grid, in which case we’ll return GRID_OVERFLOW and, on the other hand, convergence may take more than 1000 iterations to reach, in which case we’ll return MAX_ITERATIONS. The following diagram shows an example of “GRID_OVERFLOW” where the red cell should be born in the next iteration, but it is not possible to save the next state in the fixed-size matrix:



• Work distribution: In order to distribute and parallelize the calculations, we’ll use previously computed numeric ranges. For instance, if we want to calculate all possible initial configurations of a 5×5 matrix (33554432 possibilities) and we have 4 machines, each of which has 2 CPUs, we can divide 33554432 into the following 8 numeric ranges:
  

  min	max
  1	4194304
  4194305	8388608
  8388609	12582912
  12582913	16777216
  16777217	20971520
  20971521	25165824
  25165825	29360128
  29360129	33554432

  Implementation

  We have implemented, on one hand, the code needed to be able to execute the Game of Life, as mentioned above, in a class called GameOfLife and, on the other hand, a Pangool task in GameOfLifeJob which makes use of the code for calculating multiple games. This code is available in Pangool’s repository from version 0.43.0 on.

  The task Mapper reads an input that we have generated previously with the ranges to compute, and it emits them straight away. The Reducer reads each range and calculates all the possible combinations between “min” and “max”. Below, you can see the most important fragment of the code. In this case Pangool helps us to have a more concise and compact code by using Mapper and Reducer instances instead of static classes. Because we serialize the whole task, parameter passing through it is simpler and more compact.

  		TupleMRBuilder job = new TupleMRBuilder(conf);
  		job.addIntermediateSchema(schema);
  		job.setGroupByFields("min", "max");
  		job.setCustomPartitionFields("min");
  		// Define the input and its associated mapper
  		// The mapper will just emit the (min, max) pairs to the reduce stage
  		job.addInput(new Path(input), new HadoopInputFormat(TextInputFormat.class), new TupleMapper<LongWritable, Text>() {
  
  			Tuple tuple = new Tuple(schema);
  
  			@Override
  			public void map(LongWritable key, Text value, TupleMRContext context, Collector collector) throws IOException,
  			    InterruptedException {
  				String[] fields = value.toString().split("\t");
  				tuple.set("min", Integer.parseInt(fields[0]));
  				tuple.set("max", Integer.parseInt(fields[1]));
  				collector.write(tuple);
  			}
  		});
  		// Define the reducer
  		// The reducer will run as many games of life as (max - min) for each interval it receives
  		// It will emit the inputs of GOL that converged together with the number of iterations
  		// Note that inputs that produce grid overflow are ignored (but may have longer iteration convergence)
  		job.setTupleReducer(new TupleReducer<Text, NullWritable>() {
  
  			public void reduce(ITuple group, Iterable<ITuple> tuples, TupleMRContext context, Collector collector)
  			    throws IOException, InterruptedException, TupleMRException {
  
  				int min = (Integer) group.get("min"), max = (Integer) group.get("max");
  				for(int i = min; i < max; i++) {
  					try {
  						GameOfLife gameOfLife = new GameOfLife(gridSize, GameOfLife.longToBytes((long) i), maxX, maxY, iterations);
  						while(true) {
  							gameOfLife.nextCycle();
  						}
  					} catch(GameOfLifeException e) {
  						context.getHadoopContext().progress();
  						context.getHadoopContext().getCounter("stats", e.getCauseMessage() + "").increment(1);
  						if(e.getCauseMessage().equals(CauseMessage.CONVERGENCE_REACHED)) {
  							collector.write(new Text(Arrays.toString(GameOfLife.longToBytes((long) i)) + "\t" + e.getIterations()),
  							    NullWritable.get());
  						}
  					}
  				}
  			};
  		});
  
  		job.setOutput(new Path(output), new HadoopOutputFormat(TextOutputFormat.class), Text.class, NullWritable.class);
  		job.createJob().waitForCompletion(true);
  

  To execute GameOfLifeJob, we need to pass the following parameters: [output-path] [input-grid-size] [parallelism]. The first is the HDFS folder in which we’ll save the results. The second is size “n” from which all possible initial configurations will be derived (2^n*n). For n=4 the program will finish quickly. For n=5 the program must calculate more than 33 million combinations so it will take many hours to finish in a single machine. Finally, the last parameter is the parallelism level, which will indicate how many ranges we’ll divide the space of possible combinations into.

  The following example executes the Game of Life with all the possible initial configurations of a 4×4 matrix (which are 65535) and divides them into 10 ranges:

  hadoop jar pangool-examples-*-job.jar game_of_life out-1 4 10
  

  If we also want to specify a specific number of reducers:

  hadoop jar pangool-examples-*-job.jar game_of_life -D mapred.reduce.tasks=5 out-1 4 10
  

  We can also change default configurations, such as the size of the grid used for executing the game (which is 32×32 by default). The bigger the grid size, the slower the calculations will be, but also fewer configurations will produce GRID_OVERFLOW:

  hadoop jar pangool-examples-*-job.jar game_of_life -D gol.max_x=64 -D gol.max_y=64 out-1 4 10
  

  Finally, we can also change the maximum number of iterations for each game (which by default is 1000):

  hadoop jar pangool-examples-*-job.jar game_of_life -D gol.iterations=300 out-1 4 10
  

  Results

  We have executed GameOfLifeJob for n=5 in a 10-m1.large-machine EC2 cluster with 2 CPUs for each machine (parallelism=20). The calculation of the 33,554,432 initial configurations took 1 hour and 38 minutes. We have used default values (32×32 grid, 1000 iterations). This is the grid of cases according to the ending reason:

  Final	Casos
  GRID_OVERFLOW	7.478.858
  CONVERGENCE_REACHED	17.850.211
  NO_ALIVE_CELLS	8.225.331

  As we see, a 32×32 grid is not enough to calculate at least 1000 iterations in 22.2% of the cases that produce GRID_OVERFLOW. We also see that 24.5% of the cases “die” (all of the cells disappear) in less than 1000 iterations. The rest of the cases (53.3%) reaches convergence at some point.

  As a result we have extracted some curious configurations. The following configurations are the ones that took longest to reach convergence, 433 and 414 iterations, respectively:

  

  You can test these patterns in this applet. You can draw them in the “Big” grid and then switch to the “Small” grid before running the simulation, otherwise results won’t be the same. You’ll see that the automaton takes a lot of movements to reach convergence (be patient – it is better to execute the simulation in Fast or Hyper mode).

  This has been our small tribute to Conway and Turing (especially because this year marks 100 years since he was born), in which we have shown one of the common use cases of Hadoop in a fun and enjoyable way: distributed computation.