In a later post I’m going to introduce a new artificial life system which I’m working on. This new system is based on Markov Network Brains so I figured I’d take a little time to talk about them. Markov Brains use binary variables and arbitrary logic to implement deterministic or probabilistic finite state machines. They have been used to study behavior, character recognition and game theory among other topics. The majority of the work with Markov Brains has been done in Chris Adami’s lab.
A Markov Brain consists of 3 parts :
- a set of binary variables called the Brain State
- a collection of logic gates
- connections between the variables and the gates
When a Markov Brain runs, it passes bits from the Brain State though the logic gates. The output of the logic gates are combined using OR. This is one update. The resulting (Time T + 1) Brain State is then used as the Brain State for the next update.
The Logic gates can take 1 to 4 inputs and deliver 1 to 4 outputs. They are basically lookup tables. The inputs get their values from the Time T brain state while the outputs write in the the Time T+1 Brain States.
While the size of the Brain State is determined by the user, the logic gates and connections are defined by a genome – a list of numbers from 0 to 255. This genome is usually generated randomly and then progressively modified by selection and mutation.
A “42” followed by a “213” in the genome signifies the beginning of a logic gate. The next two numbers define the number of inputs and outputs. The next numbers define which values from the brain state will be used for inputs and outputs. Finally, a number of the values in the genome define the lookup table.
Say for instance, this is part of the genome:
… 17 89 45 202 98 |42 213| |40 8| |23 201 90 81| |12 37 109 231| |72 143 2 211 170 60 32 122 …
|42 213| define the beginning of the logic gate.
|40 8| define the number of inputs and outputs. To find the number of inputs we just mod by 3 and add 1. In this case there would be two inputs (40 % 3 + 1) and three outputs (8 % 3 + 1).
|23 201 90 81| define which values in the Brain State will be used for inputs. Lets say that there are 16 values in the Brain State. To find the inputs we mod by the number of values in the Brain State. In this case we find that the two inputs are 7 (23%16) and 9 (201%16). The next two values are not used, but might be if there is a mutation which increases the number of inputs to this gate.
|12 37 109 231| define the outputs in the same way.
The logic (lookup table) of the gate is defined by the next series of numbers in the genome.
Markov Brains can have deterministic or probabilistic logic. In the case of deterministic logic, the lookup table is simply a mapping from input to output. In the case of probabilistic logic, a random number is generated to determine which set of outputs will be returned for a given set of inputs based on a table of probabilities. Here are examples of both deterministic and probabilistic logic tables for 3 input, 2 output gates.
Lets say the input was 010. The Deterministic gate would return 01. The Probabilistic gate on the other hand would have a 25% chance to return 00, no chance to return 01, etc.
Using Markov Brains
How you use a Markov Brain depends on the questions you are asking. Generally though there are three steps: program the inputs, update the brain, read the outputs.
A model system that I have been working with consists of a 10 x 10 grid world. There is a wall around the edge. The rest of the world is randomly populated with food and poison. An agent controlled by a Markov Brain is inserted into this world and allowed to run for some number of updates. This agent can sense its surroundings, move, and eat. In this case I wanted to evolve behavior where the agent would attempt to eat all the food while avoiding poison.
The agent has the ability to sense objects in front of it, in front to the right, and in front to the left. Since the Brain State consists of bits, one bit must be committed for each possible value in each sensed location. Some of the bits in the Brain State are assigned to the sensors. Before each update, the sensor bits are calculated and written into the Time T Brain State. Then one update is run. Just like some bits in the Brain State are assigned to the sensors, so bits in the T+1 Brain State can be assigned to outputs. In this case the outputs determine if the agent moves, turns, eats, or does nothing.
It is worth noting that programing the sensor bits deletes whatever information they are holding. Hence anything written to these locations by the brain will be lost. This artifact can be simply coded out of the system if that is desired. Another feature worth mentioning is the idea of hidden values in the Brain State. These are values that do not interact directly with the outside world and will allow the Markov Brain to do more complex operations and maintain memory.
By running the agent for a number of updates and tracking a score based on how much food the agent eats (less some value each time the agent moves on to poison), we can assign a score to that agent. This score can then be used to determine which agents will be used to generate a new generation.
Mutations in Markov Brains are achieved by altering the genome and then reevaluating to generate new gates. Point Mutations, random insertions and deletions, and copy mutations are therefore simple. Sexual reproduction is achieved by selecting cut points in the genome of both parents and swapping sections.
I want to take a moment and thank Arend Hintze whose taught me everything I know about Markov Brains (aside from what I’ve figured out on my own!)
You can find more information about Markov Network Brains here along with a working version of the code:
Thanks for reading!