Conway’s Game of Life with a Knowledge Graph and Raspberry Pi: How to use semantic reasoning on an edge device
Conway’s Game of Life is an extraordinary example of the beauty in simplicity, showing how complexity can emerge from a basic set of principles. Despite, or perhaps because of this simplicity, it has captured the imagination of millions since its invention, securing its place in the pop-culture hall of fame.
At its inception it was a groundbreaking creation, so today we’ve combined it with another pioneering innovation — RDFox on edge. You might be asking — why should I run Game of Life using RDFox on an edge?
It is important to know how to use your data to extract valuable insights — even more so when that data sits on-location in a device that fits in the palm of your hand. Running any graph database on a small computer such as an edge device or smartphone comes with its own set of challenges. Very few enterprise databases are capable of running on an edge device and those that can are notoriously slow. As a uniquely in-memory solution, powered by patented technology born at the University of Oxford, RDFox solves this problem.
RDFox is also the first knowledge graph built with a lightning-speed semantic reasoning engine at its core. Rules — the language of reasoning — infer new facts, encapsulating complex concepts and optimising query speeds, ultimately turning your raw data into knowledge. RDFox’s unique incremental reasoning algorithms ensure that the knowledge stays up to date at all times with every addition, removal, or update to the data. In the mutable world of IoT, this has never been more relevant.
With fixed rules and an ever-changing environment, running Game of Life on an edge device gives us the perfect candidate to show how far semantic technology has come, especially in business applications.
What is the Game of Life?
Invented by John Conway in 1970, the Game of Life is a fascinating zero-player game known as a cellular automation. This means the game consists of a regular grid of cells, each taking the value ‘off’ or ‘on’, 0 or 1, dead or alive. From this initial state, the game then plays itself, progressing over time according to a set of rules — just as RDFox reasons incrementally based on the data coming in and the rules set, allowing the user to take a step back. The Game of Life has become iconic due to its carefully crafted minimal rule set, making it easy to understand yet endlessly captivating. In fact, the Game of Life is Turing-complete, so the most dedicated of ‘players’ have discovered incredible initial states that create functioning computers or even a self-emulating Game of Life. However, most of us just use it to make cool patterns!
The Game of Life Rules
The game exists on an infinite 2-dimensional grid of cells, each one dead or alive, affected by its neighbours — the 3-by-3 sub-grid that surrounds it. This is known as a cell’s neighbourhood.
Due to the unfortunate limitations of reality, for this demo, we’ve had to restrict this endless space to a much smaller, finite grid.
The state of any individual cell (after the initial condition) is determined by a set of three rules. These rules are applied to the whole grid simultaneously at every incremental time step. Each new interval in time represents the next generation of life.
The Rules of the Game of Life
In the next generation…
Birth: Any dead cell with three neighbours becomes alive.
Survival: Any alive cell with two or three neighbours survives.
Death: All other cells die or remain dead.
Birth comes about through repopulation — the mating of three cells — and death occurs either by overpopulation (more than 3 neighbours), or underpopulation (less than two neighbours). Over and under population are sometimes represented as separate rules (instead of survival) to highlight the intricacies of the living system.
How to Set Up the Game of Life on a Raspberry Pi with RDFox
RDFox is a high-performance knowledge graph and semantic reasoning engine, often used for large scale data manipulation or intensive reasoning operations. However, due to its efficient memory-optimisation and ability to run on embedded devices, many of our clients use it for edge applications such as vehicle automation, personalised recommendations on phones, and clinical decision support in medical devices.
With our setup, we wanted to demonstrate another edge use case that will feel familiar to those with an interest in IoT. The key components in this configuration are a central hub (a Raspberry Pi) and connected devices (in our case, just one device — a Cube of LEDs powered by an Arduino). On the Pi we run RDFox, the database and rules engine; Node-Red, a programming tool that manages the application processes; and Mosquitto, an MQQT broker that handles communications. On the Arduino, a simple C application manages the LED lighting.
RDFox computes the cell state for each generation in the Game of Life, sharing the results with Node-Red via a series of SPARQL queries. We then use a publish-subscribe mechanism running on top of Mosquitto so that when Node-Red publishes on the topic dedicated to the LEDs, the cube receives the instructions and sets the lights accordingly. With this setup, we could have a whole fleet of cubes, each running its own Game of Life, all powered by RDFox.
Other than being really cool, why create hundreds or thousands of Game of Life cubes that can all communicate and interact? The answer lies in the IoT. Where a plethora of light-up cubes may not be helpful, an army of sensors, motors, and controllers certainly is — by enabling these devices to talk to one another, to conduct analysis and complex computation with each other in mind, we have just created an incredibly powerful device network. Suddenly, with this technology, some of the largest IoT challenges become trivial.
How to Create the Game of Life with Semantic Reasoning on Device
Laying the groundwork, we set up a coordinate system to identify the LED nodes and their neighbours, plus the concept of time that incrementally increases allowing us to generate progressing states.
When the next generation is calculated, we start with a blank slate to be populated according to the game rules. Cells whose state is not ‘Alive’ are assumed to be dead so that we can cover our ruleset with just two Datalog rules. The first for birthing new cells, and the second for surviving cells, each assigning life where appropriate.
Datalog is the language of rules used by RDFox to encode knowledge. These logical rules are, at their core, just if-then statements, telling RDFox what to add under which conditions — both sides of which can range from the insatiably simple to the vastly complex, depending on the needs of the user.
The Birth of a Cell
The conditions under which a cell is born are that in the previous generation it was dead and that it had exactly three alive neighbours. The following Datalog assigns the cell’s next state (in the increment of time that immediately follows) to be ‘Alive’, provided it meets the requirements.
[?state, :nextState, :Alive]:-
[?state, a, :State],
NOT [?state, a, :Alive],
[?state, :aliveNeighbours, ?alive_neighbours],
FILTER( ?alive_neighbours = 3) .
The Survival of a Cell
Similarly, the conditions required for a cell to survive into the next generation are that it was already alive, with no more than three alive neighbours, and no less than two. As with the last, this rule sets the next state to be ‘Alive’ so long as those conditions are met.
[?state, :nextState, :Alive]:-
[?state, a, :State],
[?state, a, :Alive],
[?state, :aliveNeighbours, ?alive_neighbours],
FILTER(?alive_neighbours = 2 || ?alive_neighbours = 3).
And just like that we have a framework for the Game of Life!
Time is increased by Node-Red, and in each interval, it queries RDFox for the cell states and sends them to the cube to be displayed by the LEDs. An INSERT query is used to add the next generation’s information to the graph while incremental reasoning ensures the game rules are automatically applied to the new data. The current board state can then be retrieved with a simple query.
PREFIX : <https://rdfox.com/demo/GOL#>
SELECT ?state ?board ?x ?y
WHERE {
?state a :Alive ; :location ?pos ; :frame ?frame.
?frame :time 1.
?pos :partOf ?b; :x ?x; :y ?y.
?b :number ?board.
}
The Game of Life in Colour
Looking to push our application a little further still, we added one more layer to the game — colour! We included RGB properties to the initial state of an alive cell which it retains for the rest of its existence. When a cell is born, it takes the average colour of its parents, forming a beautiful and diverse display.
[?state, :nextRed, ?nextRed]:-
[?state, a, :State],
[?state, :aliveNeighbours, ?count],
BIND(ROUND(?redSum / ?count) AS ?nextRed),
NOT [?state, a, :Alive],
AGGREGATE(
[?state, :location, ?pos],
[?state, :frame, ?frame],
[?pos, :neighbour, ?neighbour_pos],
[?alive_state, a, :Alive],
[?alive_state, :red, ?red],
[?alive_state, :location, ?neighbour_pos],
[?alive_state, :frame, ?frame]
ON ?state
BIND SUM(?red) AS ?redSum
) .
PREFIX : <https://rdfox.com/demo/GOL#>
INSERT {
?state :red ?red; :green ?green; :blue ?blue .
} WHERE {
?state a :State ;
:location ?pos ;
:frame ?frame;
:previousState ?previousState.
?previousState :nextRed ?red; :nextGreen ?green; :nextBlue ?blue.
?frame :time 1.
?previousState :nextState :Alive.
}
The Game of Life is an incredible showcase of mathematical ingenuity and creativity, but that’s not really what this article is about. At the heart of the colourful patterns and charming evolution is the technology driving it all — a knowledge graph and reasoning engine capable of powerful analytics and computation, even on a tiny device. For sensor and device networks spanning factories, cities, or entire globe, enabling calculations at the edge makes all the difference. Whether constrained by an unwelcoming environment too hot, too cold, or too pressurised; disconnected from the world in remote locations in the skies above, the depths below or all around us; or on the move in a fleet of cars, drones, or mobile phones: RDFox provides a solution.
We highly recommend that you give the Game of Life a go for yourself, and if you would like to get started with RDFox on edge, check out our article ‘The 5 Simple Steps to Running the World’s Fastest Graph Database on The Edge’.
Team and Resources
The team behind Oxford Semantic Technologies started working on RDFox in 2011 at the Computer Science Department of the University of Oxford with the conviction that flexible and high-performance reasoning was a possibility for data-intensive applications without jeopardising the correctness of the results. RDFox is the first market-ready knowledge graph designed from the ground up with reasoning in mind. Oxford Semantic Technologies is a spin-out of the University of Oxford and is backed by leading investors including Samsung Venture Investment Corporation (SVIC), Oxford Sciences Enterprises (OSE) and Oxford University Innovation (OUI).