Agent-Based Models (Part 10)

We’ve been hard at work here in Edinburgh. Kris Brown has created Julia code to implement the ‘stochastic C-set rewriting systems’ I described last time. I want to start explaining this code and also examples of how we use it.

I’ll start with an easy example of how we can use it. Kris decided to implement the famous cellular automaton called the Game of Life, so I’ll explain that. I won’t get very far today because there are a lot of prerequisites I want to cover, and I don’t want to rush through them. But let’s get started!

Choosing the Game of Life as an example may seem weird, because I’ve been talking about stochastic C-set rewriting systems, and the Game of Life doesn’t look stochastic. There’s no randomness: the state of each cell gets updated once each time step, deterministically, according to the states of its neighbors.

But in fact, determinism is a special case of randomness! It’s just randomness where every event happens with probability 0 or 1. A stochastic C-set rewriting system lets us specify that an event happens with probability 1 at a fixed time in the future as soon as the conditions become right. Thus, we can fit the Game of Life into this framework. And once we write the code to do this, it’s easy to tweak the code slightly and get a truly stochastic variant of the Game of Life which incorporates randomness.

Let’s look at the program Kris wrote, called game_of_life. It’s in the language called Julia. I’ll start at the beginning.

# # Game of Life## First we want to load our package with `using`using AlgebraicABMs, Catlab, AlgebraicRewriting

This calls up AlgebraicABMs, which is the core piece of code used to implement stochastic C-set rewriting models. I need to explain this! But I wanted to start with something easier.

It also calls up Catlab, which is a framework for doing applied and computational category theory in Julia. This is the foundation of everything we're doing.

It also calls up AlgebraicRewriting, which is a program developed by Kris Brown and others that implements C-set rewriting in Julia.

# # Schema # # We define a network of cells that can be alive or dead (alive cells are in # the image of the `live` function, which picks out a subset of the vertices.)@present SchLifeGraph <: SchSymmetricGraph begin   Life::Ob  live::Hom(Life,V)end

This code is defining a schema called SchLifeGraph. Last time I spoke of C-sets, which are functors from a category C to the category of sets. To describe a category in Catlab we use a ‘schema’. A schema consists of

• a list of objects • a list of morphisms between these objects • a list of equations between composites of the morphisms in our list.

The objects and morphisms are sometimes called generators while the equations are sometimes called relations, and we say that a schema is a way of presenting a category using generator and relations. If a schema presents some category C, a functor from C to the category of sets is then called an instance of this schema.

The command @present SchLifeGraph <: SchSymmetricGraph says we're going to present a schema called SchLifeGraph by extending a previously defined schema called SchSymmetricGraph, throwing in more objects, morphisms and equations.

The schema SchSymmetricGraph was already defined in CatLab. It's the schema whose instances are symmetric graphs: roughly, directed graphs where you can ‘turn around’ any edge going from a vertex v to a vertex w and get an edge from w to v. The extra stuff in the schema SchLifeGraph will pick out which vertices are ‘live’. And this is exactly what we want in the Game of Life—if we treat the square ‘cells’ in this game as vertices, and treat neighboring cells as vertics connected by edges. In fact we will implement a more general version of the Game of Life which makes sense for any graph! Then we will implement a square grid and run the game on that.

More precisely, SchSymmetricGraph is the schema with two objects and two morphisms and a morphism obeying

So, an instance of this schema is

• a set of edges, • a set of vertices, • two maps from the set of edges to the set of vertices (specifying the source and target of each edge), • a map that ‘turns around’ each edge, switching its source and target, such that • turning around an edge twice gives you the original edge again.

This is a symmetric graph!

We want to take the schema SchSymmetricGraph and throw in a new object called and a new morphism We do this with the lines

Life::Oblive::Hom(Life,V)

Now we’ve defined our schema SchLifeGraph. I hope you can see what an instance of this schema is! It’s a symmetric graph together with a set and a function from this set to the set of vertices of our graph. This picks out which vertices are ‘live’. And this is exactly what we want in the Game of Life, if what we usually call ‘cells’ are treated as vertices, and neighboring cells are connected by edges.

The schema SchLifeGraph presents some category C. A state of the world in the Game of Life is a C-set, i.e. an instance of the schema SchLifeGraph. This is just the first step in describing a stochastic C-set rewriting system for the Game of Life. As explained in Part 9, next we need to specify

• the rewrite rules which say how the state of the world changes with time,

and

• the ‘timers’ which say when it changes.

I’ll do that next time!