Evaluating Mappings for Cellular Automata Music

Alexis Kirke and Eduardo Miranda of the Interdisciplinary Centre for Computer Music Research (ICCMR) at the University of Plymouth discuss why selecting the right mapping is critical when composing music with artificial life and emergent algorithms. Emergent algorithms have drawn composers both for their striking visual patterns and their ability to produce intricate results from simple rules. Straightforward mappings to MIDI are often preferred because they give composers greater control and predictability. Yet a poorly chosen simple mapping can yield dull music and fail to translate the visual appeal of emergent behaviour into sound. Moreover, these mappings require a method for proper evaluation. To highlight these issues, the authors use the Game of Life (GL) as a case study. They introduce a polar-coordinate mapping and argue that it outperforms older GL mappings in terms of both simplicity and its ability to capture the visual aesthetic. The new mapping is assessed by comparing it to linear mappings with Zipf’s Law and a basic structurality measure.

The Game of Life

The Game of Life (GL) is a two-dimensional cellular automaton created by John Conway. He found it fascinating how a few simple rules could generate patterns that unpredictably expand, change shape, or die out, and he aimed to identify the simplest possible rule set that would produce such behaviour. The automaton consists of a finite m x n matrix of cells, each in one of two states: alive (1) or dead (0). On screen, living cells appear black and dead cells white.

A cell's state evolves based on its eight immediate neighbours:

• Birth: A dead cell becomes alive at time t+1 if exactly three of its neighbours are alive at time t.
• Death by overcrowding: A live cell at time t dies at t+1 if four or more neighbours are alive at t.
• Death by exposure: A live cell at time t dies at t+1 if it has one or zero live neighbours at t.
• Survival: A live cell at time t remains alive at t+1 only if it has two or three live neighbours at t.

If E is the number of living neighbours around a live cell and F the number around a dead cell, a live cell survives when 2 ≤ E ≤ 3, and a dead cell is reborn when 3 ≤ F ≤ 3. Transitional rules can be generalised as (E_min, E_max, F_min, F_max), making the original GL rules (2, 3, 3, 3). Many alternative rule sets are possible. Many intriguing initial configurations produce emergent behaviours that have made GL widely known.

Generative Music Composition and GL

Because cellular automata like GL generate substantial patterned data, and music can be understood as based on pattern propagation and formal manipulation of parameters, it is not surprising that composers began to suspect these automata might offer a useful musical representation. Iannis Xenakis was among the first, in the mid-1980s creating complex temporal evolutions for orchestral clusters in his piece Horos. Pioneering experiments with GL and music were later carried out by others, including one of the present authors.

There are two main reasons for the prominence of GL in algorithmic composition:

1. Complexity generation — reaching intricate textures in music.
2. Inspiration — capturing GL’s visual aesthetic in a non-visual art form.

Much previous work cites the first reason as the motivation, though the second — the beauty of GL — also clearly applies. These motivations should guide mapping choice. The authors propose a Radial mapping that reflects the visual aesthetic of GL.

Radial Mapping

GL’s rules allow a cell’s state to be influenced by its neighbours equally regardless of a 90-, 180-, or 270-degree rotation. This rotation invariance is why such symmetric patterns arise during GL iterations. Even in nonsymmetrical evolutions, the emergence of complex broken symmetries from simple symmetric rules appeals to the aesthetic sense.

Earlier mappings used Cartesian coordinates or linear pixel-location approaches. The current work instead uses polar coordinates (r, θ) to capture the radial symmetry in GL’s patterns. The origin is placed at the board’s centre; live cells produce musical notes based on their r and θ values rather than x or y. The authors’ specific algorithm follows:

1. Choose a beats-per-minute value, initialise a baseBeat to 0, and select a fixed note duration D.
2. Run one generation of GL.
3. For each of 127 radial steps r from the centre to edge, and for each of 127 angular steps θ from 0 to 2π (quantised for MIDI), examine the cell at (r, θ).
4. If alive, generate a MIDI note with pitch = 128θ / (2π) and duration D, placed at baseBeat + 16rD/H where H is half the grid width in cells.
5. After scanning the full grid, update baseBeat to follow the last MIDI note.
6. Repeat for the next GL generation.

To illustrate: for (x,y) = (2,2) converted to quantised polar (2, π/4), the pitch is 128(π/4)/(2π) = 16. With D = 0.5 beats and baseBeat = 0, the beat start is 4.

This algorithm is deliberately simple, giving the composer maximum control. A further decision: the GL universe is "clipped" at the grid edges rather than using the common toroidal wrap-around, so that radial symmetry is not diminished by toroidal symmetry.

Linear Mappings in GL

The authors compare the radial mapping with two linear variants:

Cartesian mapping — scan rows top to bottom, within each row scan left to right. The pitch is proportional to x, and rhythm derives from y.

Binary mapping — scan columns left to right, treat each vertical column as a binary number (top = least significant bit, bottom = most significant). The pitch is proportional to that number modulo 128 (to avoid very low pitches and limited pitch variety).

Evaluating Mappings

The demonstration of mapping importance required:

1. A set of GL starting states (seeds) for comparison.
2. A set of three mappings: radial, Cartesian, binary.
3. A technique for relatively evaluating the resulting music.

The selected seeds include:

• 21-cell row (symmetric)
• 11-cell row (symmetric)
• Exploder (symmetric)
• Circle radius 9 (symmetric)
• Square size 9 (symmetric)
• Concentric circles max 14 (semi-symmetric)
• Concentric circles max 6 (semi-symmetric)
• 4 gliders (groups placed in lower left quadrant)
• Random 5x5 grid, density ≈33%
• Random 15x15 grid, density ≈33%
• Random 25x25 grid, density ≈33%
• Random 25x25 grid, density ≈15%
• Random 25x25 grid, density ≈50%

Evaluating Generated Music

The evaluation methods were Zipf’s Law, which serves as a partial metric of musical "pleasantness," and an entropy-based measure.

Zipf’s Law

Statistical analysis based on proportion argues that naturally occurring (including human-made) phenomena often follow Zipf’s Law. In music, preliminary studies suggest some necessary but not sufficient conditions for aesthetics can be expressed as a power-law relation: let N(r) be the frequency of the r-th most common measured value (e.g., successive MIDI intervals in semitones). N(r) should be proportional to 1/r^n, with n near 1. In practical terms, when plot log(N(r)) against log(r), the result approximates a straight line. Performing linear regression on that log-log data yields an R² value; a well-formed piece should produce an R² close to 1.

Using Zipf’s Law

Though Zipf’s Law does not guarantee superior aesthetic quality—it has mostly been validated on "culturally sanctioned" music not listeners typically experience via MIDI, and discards timbre, rhythm, nuance, etc.—it provides a useful relative metric. For the authors’ comparative evaluation, it is hypothesised that music generated from radial mapping would yield higher R² values (closer to 1) compared to Cartesian and binary mappings.

Three metrics for measuring R² were considered:

1. Interval distribution between successive MIDI notes (N_mi)
2. Distribution of the 12 pitch classes (DPC)
3. Distribution of all 128 MIDI pitches (DMP)

Duration and deeper melodic analyses were not applicable because the algorithm generates fixed durations.

A pilot experiment examined these metrics for Chopin’s Revolutionary Étude and compared it with random music from the various algorithms under test (where GL cells were activated at random). Table 1 reports R² comparison averages across random music for each metric.

Table 1. Comparison of R² values for Chopin and random music

Measure / R²  Chopin …

It can be seen that the measure which most clearly differentiates the Chopin piece from Random music is the N _mi , and hence it became the Zipf-based metric chosen for this paper.

4.2 “Melodic” Entropy

It was considered important to also include some basic measure of “structurality” in evaluating an Alife musical mapping. In theory complexity can be increased by simply generating a “chaotic” interface between the Alife process (GL) and the music. If the mapping and the Alife process are sufficiently at odds, then a great deal of chaotic complexity may be generated. However, a balance between structure and chaos is often considered an important part of music.

To measure how structured a piece is, we use Shannon’s Information Entropy [15]. This measure can be interpreted as how much “structure” there is in a distribution. The more structure in the distribution, the less data is required to represent it, and hence the lower its “information content”. So one interpretation of a higher entropy value for a set of MIDI notes is that it suggests a less structured piece of music in note-to-note terms. Once again we need to make the qualification that using such a metric to evaluate musical aesthetics can only be indicative. For example, Information Entropy measures in music are based on the assumption that music is ergodic. However by combining this measure with the Zipf measure discussed earlier, and using it only as a relative measure, we then have a useful indicator for relative evaluation.

We will focus on the Melodic Entropy, since the generated pieces can have extremely complex harmonic progressions, and so there is no simple way of measuring harmonic entropy. However there is a heuristic way of approximating melodic entropy. This involves evaluating the “melody line” separately, as well as evaluating the full piece. The mappings demonstrated here do not explicitly generate melody lines. So to measure melodies the following approximation is used: the generated MIDI file is filtered so that for each tick, only the highest playing note is kept. Listening to such filtered files, it can be heard that this is the line of notes most often associated with “melody” by a listener. These lines are then measured by taking the MIDI beat and pitch data for the “melody line” and generating a vector with one element for each note. Each element in the vector is the MIDI pitch data for the note multiplied by its beat location. The Shannon Entropy of this vector was then calculated. This approach ensures the melodic entropy takes into account timing as well as pitch value.

5 Results

Each of the 13 seeds was allowed to grow for 15 generations (approximately 1.5 minutes of music), and music was generated using all three mappings: Radial, Cartesian and Binary. The average R² was calculated for each and the results are shown in Table 2. Included in these results are the Zipf R² for the approximated melodies as well (using our melody stripping algorithm).

Table 2. R² Results of the various GL mappings for different initial seeds, 15 generations run.

Mapping	Zipf R2	Melodic Entropy	“Melodic” Zipf R2
Radial	0.9	6.8	0.91
Cartesian	0.84	7.6	0.88
Binary	0.7	7.6	0.7
Random	0.55	9.7	0.54

5.1 Analysis

The first thing to note in Table 2 is the close correlation between Zipf R² and the approximated “melodic” Zipf R². This supports the idea that the heuristic melody stripping algorithm is in fact capturing an important aesthetic of the music. Given the nature of this algorithm’s output — a monophonic stream of the highest notes — it suggests that the algorithm may be a reasonable approximation of melody. Also in Table 2 it can be seen that the lowest Zipf R² is given by the random music, as would be expected. Similarly the random music gives the highest melodic entropy, which is compatible with it having the least note “structure”, also as would be expected. It can also be seen the highest R² and melodic R² occur for the Radial mapping, supporting the idea of using polar coordinates in an ALife system with radial symmetry. This is further underlined by the fact the Radial mapping has the lowest melodic entropy. The linear mappings (Cartesian and Binary) are both better than random, but still have higher entropy and Zipf R² than the Radial mapping.

It was decided to examine the effects of the life evolution on the Zipf R² value, to increase confidence that the Zipf R² value was a result of the mapping. To do this two measures were defined: the Average Density of Cells (ADC) and the Average Change of Cells (ACC). For a particular seed and mapping, the ADC is simply the average percentage of cells in the grid which were alive over the whole 15 iterations of the game. The ACC is a similar measure over all 15 iterations but measured the absolute difference in number of cells alive between generation i and generation i-1. This difference is averaged over all 15 iterations to give the ACC. A regression was run between the ACC and the Zipf R² for each seed/mapping combination. A similar regression was run for ACC vs. the Zipf R² values. The R² for these two regressions were 0.0002 for ADC and 0.0001 for ACC. This regression was also run against the melodic entropy, and the R² values were 0.27 for ACC and 0.0002 for ADC. These results support the idea that the Zipf R² and entropy values were determined more by the mappings than by the nature of the evolutions.

In spite of this it is also worth noting that if the average Zipf R² is found for each initial seed (across all mappings, but not including the randomly generated tunes) we get the following results in Table 3. The top 4 results (i.e. with the highest Zipf R²) are the four most symmetric seeds. The bottom 5 results are five of the least symmetric seeds, with the lowest Zipf R². These R² values of the mappings support the importance of considering symmetry when choosing a mapping for the creation of music from GL.

It is worth noting that the Radial mapping discussed here is actually an approximation, in the sense that the “radial aesthetic” of GL, upon closer examination, is actually a local phenomenon. It is quite common for GL seeds to eventually generate a number of islands of activity across the GL grid. Each island of activity often has a local symmetrical characteristic in itself (due to the radial symmetry of the GL rules). But there is not always a “grid-wide” or global symmetry in the behaviour of the whole board. It is interesting to note that when designing the Radial Mapping approach, one of the approaches considered by the authors was a mapping made up of multiple local

Radial Mappings across the board. Each local radial mapping would have its own polar coordinate origin, and methods were considered to self-organise these origins into appropriate positions. However it was felt that to take such a complex step without first evaluating the basic radial approach may add too much complexity at too early a stage.

Table 3. R² Results of the various GL seeds.

Seed	Zipf R2
Concentric circles max radius 6	0.815
Circle radius 9	0.7975
11 cell row	0.765
21 cell row	0.755
25x25 random, density 15%	0.74
Square side 9	0.7225
Concentric circles maximum radius 14	0.7025
Large Exploder	0.6975
4 gliders	0.6975
25x25 random, density 33%	0.685
5x5 random, density 33%	0.685
15x15 random, density 33%	0.6725
25x25 random, density 50%	0.6675

6 Conclusions and Further Work

In this paper we have discussed the importance of choosing the right mapping for music composition generated from underlying emergent and ALife algorithms. To illustrate these issues we used one of the most basic emergent ALife systems — Cellular Automata, specifically Conway’s Game of Life (GL). A simple mapping for GL was introduced, based on a polar coordinate system. We argued it was superior to previous GL mappings when both its simplicity and its visual-aesthetic capture were considered (since the visual symmetry in GL is a result of radial symmetry in its rule set). This mapping was evaluated by comparing it to linear mappings using Zipf’s Law and using a measure of melodic entropy. Based on certain limiting assumptions about the application of Zipf’s Law and Shannon’s Information Entropy to music — the evaluation supported the idea that the radial mapping provided some improvement. Thus we have demonstrated the process of looking at the effects that changing the mapping can have on the output of a generative compositional process in emergent systems, and shown ways of investigating the effects of various mappings, and basic ways of relatively evaluating those mappings.

Further work could include revisiting the set of measures. For example the melodic stripping algorithm, and the structurality measure were very basic and could be improved. Also the number of elements against which a Zipf R² value was calculated could be extended from N_mi to include others which measure further important

musical factors such as rhythm. Looking at the mappings themselves, the issue of non-local and multiple mappings could be addressed. For example having multiple polar coordinate origins to capture local symmetry. Further investigations could be done into perhaps dynamically adjusting mappings based on various objective measures — for example the ADC and ACC are actually part of the visual experience of GL, so could be incorporated into an extended mapping system. These are higher order mappings, and thus capture higher order experiences of GL. Overall it is hoped that this work has highlighted the importance of selecting and evaluating the correct mapping for turning a complexity-generating process into a musical process.