LINKS AND DOWNLOADS
CONTEXTThis was made as part of a thesis project for DMA. 2009.
MEDIUMPlastic, Light Bulbs, Electronics, C++
PEOPLEDavid Elliott : Game Designer
Andres Colubri : Technical Consultant
Each box is equipped with a matrix of 16 A/C light bulbs that are used as a display. Inside each box there is a micro controller that is able to control each light bulb discretely and communicate with the other box over serial connection. The two microcontrollers are playing a game with each other.
Battle guesses the future state of the other machine. This is attempted by using something like a Markov chain. Both of the machines share a common lexicon of 13 possible patterns. The game consists of the machines taking turns creating and displaying sequences of patterns. Each sequence is 10 patterns long. A turn is composed in three steps.
- Read the incoming sequence, what are the transition probabilities ( what is the distribution of transitions from one pattern to the next divided by the number of patterns in the sequence )?
- Given the transition probabilities and a random starting state taken from the input sequence, construct a new sequence 10 patterns long that is most probable continuation of the input sequence.
- Send the new pattern to the other machine and wait for more input.
When one of the boxes constructs a sequence that is identical to the input sequence, that box has lost the game. At that point it will flash its columns from left to right and then construct a completely random sequence to start the game over. The box that won never knows that it won, it continues with the game as if it never ended.
Here’s a video of the two machines in action:
I used the Sanguino microcontroller board for this project because it was cheap, it has lots of i/o pins, and it has two hardware serial ports. I used cat 6 cable and fixtures to connect the serial ports of the two machines together and to upload code from my computer.
I had never built a project that uses two microcontrollers talking to each other so I had to look around for something similar to get an idea of the best way to do it. I found MeggyChip a game written by Chris Brookfield and Windell Oskay for the excellent Meggy Jr game platform. I was able to use the communication protocol from that game with a little modification.
Here’s my awkward attempt at implementing some kind of Markov like process. It mostly works but I had to fudge it a little because for some reason there was a tendency for the machines to converge on the first pattern in the lexicon:
//we need to know how many times each pattern appears so we can divide transitions by it later
//first clear out wordOccurenceSum
for(byte i=0; i < NumPatterns; i++) wordOccurenceSum[i] = 0;
//then add up the number of times each pattern appears
for(byte i=0; i < TurnLength; i++) wordOccurenceSum[inboundBytes[i]]++;
//this is to clear out transitionTotals array
for(byte i=0; i < NumPatterns; i++)
for(byte j=0; j < NumPatterns; j++)
transitionTotals[i][j] = 0;
//this keeps track of how many times each transition occurs
for(byte i=0; i < TurnLength; i++)
//lets empty out the transitionProbability array so we can make new stats
for(byte j = 0; j<NumPatterns;j++)
transitionProbability[i][j] = 0.00;
//now we need to take the number of times a transition happended and divide it by
//the number of times an inital state appears in the sequence to get the probability
//of that transition happening
for(byte i=0; i < NumPatterns; i++)
//this is special case for the beginning the iteration
float tempA = wordOccurenceSum[i];
float tempB = transitionTotals[i];
transitionProbability[i] = tempB/tempA;
for(byte j=1; j < NumPatterns; j++)
tempA = wordOccurenceSum[i];
tempB = transitionTotals[i][j];
//add up the percentage for every step in the iteration
transitionProbability[i][j] = transitionProbability[i][j - 1] + tempB/tempA;
//this is to start out with a random outbound:
for(byte i = 0;i< TurnLength; i++) outboundBytes[i] = random(0,14);
//start the sequence with the last position of incomming bytes
outboundBytes = inboundBytes[random(0,13)];
//for the second position and on look at the last position and randomly choose from the most probable transitions
for(byte i=1; i< TurnLength; i++)
float rnd = random(2,11);
rnd = rnd/10;
for (byte j = 0; j < NumPatterns; j++)
if (rnd <= transitionProbability[outboundBytes[i-1]][j])
//throw a monkey wrench in the zero bias :(
if(j==0) j = random(0,5);
outboundBytes[i] = j;
boolean different = false;
for(byte i=0; i< TurnLength; i++)
if(outboundBytes[i]!=inboundBytes[i]) different = true;
if (different == false)
//this means that I loose so restart the game
//start over by making a new random sequence for us to guess
for(byte i = 0;i< TurnLength; i++) outboundBytes[i] = random(1,14);
You can download the code for the whole project here: