Monday 28 March 2016

The inner workings of the game

Like many, I just released some games. Like not so many, they let you contribute to science. And since it's all for science, I have opened up the source for all to see. Here it is, on Dropbox. There are both Xcode and Unity projects here. Witness my coding and despair!

My games are pretty simple. It's all just buttons and text and pictures. Someone more competent than I could probably knock it out in a day or two. In fact, I plan to make a video where I will build one of the games pretty much from scratch, live!

This blog post explains what is going on in the code for version 1 of the Game Decodoku. Everything else is built on very similar principles.

How the game works

The game is basically an L grid of numbers, with L=8 for iPads and L=7 for iPhones. You push the numbers around and they add up (mod 10). Every so often, more of the buggers will come. The game ends when it all gets a bit messy. You can check out an extended tutorial here. I'll wait here while you read it.

So the main things to know are:
  1. How are the numbers generated and changed?
  2. What is the 'Game Over' condition?
Before we answer these, we should get to know a couple of arrays that describe what's happening on our grid

    int anyons[8][8], clusters[8][8]

Probably we should really have made these L×L arrays, but L is never larger than 8 so there's always room in these arrays to do what we need.

The purpose of the anyons array is to store all the numbers. If there is nothing on the square at (x,y), then

    anyons[x][y] = 0;

If there is a 7, for example, then

    anyons[x][y] = 7;

The array clusters deals with what we've called 'groups' of numbers in the tutorial. But we'll call them 'clusters' here. Each number in anyons that isn't 0 is assigned to a cluster. The first cluster ever to be created is called 1, and so on. For every non-zero entry of anyons, the corresponding entry of clusters will tell us what group it belongs to. Wherever there is a 0 in anyons, the entry in clusters is also 0.

Changing the numbers

Now we know where all the necessary info lives, let's get on with question 1. For this, we look at the generateNoise function in GameViewController.m.

The numbers always change in pairs. These pairs are always neighbouring squares. The amount that the numbers on the two squares will be changed by always adds up to 0 mod 10. Other than this, it's a random process.

To pick our random pair of squares, first we randomly pick one square by generating random x and y. Then we randomly pick one of its four neighbours, (x,y+1), (x,y-1), (x+1,y) or (x-1,y). We also have to remember that, on the edge, not all squares have four neighbours. So best not to choose a neighbour that doesn't exist.

Once we have the squares, we choose how much to change the one at (x,y) by. This will be a random number from 1 to 9 that we call a.

    anyons[x][y] = (a + anyons[x][y])%10;

The other one is similarly changed by aa=10-a to ensure that the sum of the changes is a multiple of 10.

This gives us things like this, where colours are just for emphasis.
Once generateNoise has done a pair of changes, it'll go back and do it again. So when does it stop?

Each pair of changes is assigned a different weight, depending on what kind of changes were made. Those that create two new numbers (meaning that there were only zeros in those squares before) have weight 1. Those that create one new number, and either change or remove a number on the other square, also have a weight of 1. Those that don't create anything new, just changing or removing what's already there, have a weight of 0.1.

The function generateNoise keeps adding changes until a weight of 6 is reached. Then the player is allowed to actually do something at last.

What the player can do is move a number from one square to a neighbour. When this happens, they add up mod 10. So we are basically trying to undo what the errors have done. However, we only have 5 moves before generateNoise returns and does another bunch of changes with total weight of 6.

Since this function basically does 6ish bad things and we only have time for 5 good things, the numbers are going to build up over time. In quantum error correction, this is called operating above the noise threshold and is bad. In gaming it is called not having a game that goes on too long and gets boring, and is good.

When do we lose?

The losing condition is all about the clusters. Once a cluster spans from top to bottom or left to right, you lose.

Actually, that's not quite true, if it's generateNoise that grows the clusters until they span the grid, you are still given your 5 moves to try fixing it. But if you fail, you fail.

To check, we do this

    int spanners = 0;
    for (int J=0;J<L;J++){
        for (int K=0;K<L;K++){
            spanners += (clusters[J][0]==clusters[K][L-1])*clusters[J][0];
            spanners += (clusters[0][J]==clusters[L-1][K])*clusters[0][J];
        }

    }

If spanners ends up anything but 0, it's Game Over.

But how do we work out what cluster a number should belong to? That's all done by generateNoise. There's 4 cases to consider when each pair of changes is made.
  1. If neither of the pair of squares is part of a cluster (because neither had a non-zero number before the changes), they become part of a brand new cluster.
  2. If only one is part of a cluster, all resulting numbers become part of that cluster.
  3. If they are both part of the same cluster, all resulting numbers become part of that cluster.
  4. If they are part of different clusters, these clusters are combined. All resulting numbers become part of that cluster.
Also, always remember that squares stop being part of a cluster if their value ever goes back to zero.

Easter Egg

There's an undocumented feature in the game. Since you can (obviously) see it in the source, I'd better tell you about it. Note that it did not make it over to the Unity versions.

What if you want to go back a few moves to remind yourself what was going on? To do this, long press on the grid. If the time between touch down and touch up is long enough, you'll go into 'back-in-time' mode.

At first it'll just move you back one move. The variables secs counts the number of moves that have been made, and secsShown keeps track of the move you are looking at. So secsShown = secs - 1 when we enter this mode. To look at earlier moves, tap on the left side of the grid. To move forward again, tap on the right side. If you get back up to secsShown = secs, you move back into normal mode and can start moving the numbers around again. As a shortcut, swiping anywhere in back-in-time mode will bring you straight back into normal mode.

Have fun!

Now you have the code, distributed under the MIT license. You can make improved versions, release them yourselves and get far more downloads than us. We won't even be mad, but make sure you point your users back to this blog so that they can learn about the science and share their results, should they wish.

Tuesday 22 March 2016

Game

The post that should be here is now here. It was those ruddy Gremlins, I shouldn't wonder.

Saturday 19 March 2016

The Science Behind the Games

Quantum computers suffer from errors, as do we all. But for quantum computers we have quantum error correction to help fix them. As complicated as this sounds, it's just about solving puzzles. We get clues about the errors, and have to figure out how to get rid of them.

To find the best methods, we need you! We are packaging the puzzles up in two puzzle games: Decodoku and Decodoku:Puzzles. Now you can have a go, and help build a quantum computer just by getting a high score.

This article is an extended version of the tutorial here. If you just want to know how to play, that would be the place to go. But here we will take an approach that is closer to the science.

You can do science!

Our games aren't just an attempt to teach you about the science and maths behind quantum stuff (that's what this blog is for). You are not just generating data to help someone else do their research. Instead it lets you do the research yourself. It doesn't matter who you are or what qualifications you have. You can make discoveries in the field of quantum error correction.

The science in the game is not only being researched in universities, but companies like MicrosoftIBM and Google are throwing money at it too. If you want to keep your results secret and try to sell them to those guys, that's fine by us. It's your research, after all. But we'd rather you tell us about them using our survey, or by email at decodoku@gmail.com@decodoku on Twitter or the /r/decodoku subreddit, and we can pass it on to your fellow player/researchers. For science!

This blog and the app were developed by me, Dr James Wootton. I'm a scientist at the University of Basel, where I do research on quantum error correction. The project is supported by the NCCR QSIT, which supports research on quantum technologies in Switzerland.

We give you everything you need to tackle a problem from quantum error correction by just playing the game. If you find a way to get great scores almost all the time, then you'll know more about how to do this kind of quantum error correction than we do.

Maybe you won't be able to explain exactly what your method is. Maybe you'll just have a few tips and tricks you've found do some good. That's great! Even the smallest thing could help us, or your fellow players/researchers.  

You don't need to write a big complicated research paper with graphs and figures to help us out. Tradition dictates that us normal scientists and mathematicians need to write papers and send them to journals, but that's not what science and maths are all about. It's about discovering things, solving problems and then telling people what you've done. You are free from the bounds of tradition, and can use whatever means you want to tell people about your results, from a long technical PDF to a Let's Play or gif. Just remember to stay safe on the internet.


One scientific tradition that you should uphold is to cite your sources: If you've been inspired by someone else's work, give them a bit of credit for it. If us normal scientists use your results in our work, we'll make sure to acknowledge it too.

Both Decodoku and Decodoku:Puzzles have two versions called 10 and Φ-Λ. They are two different ways of doing error correction that we need your help for. You don't need to read this blog to do the science. There are much smpler tutorials in the links above. But if you want to know more about the games and the science behind them, read on.


The following is all based around Decodoku, though Decodoku:Puzzles is based on the same science.


The Game 10

The game is based on the grid shown below.


The little white squares here represent qudits. These are the basic building blocks of quantum computers. They are like the bits that we use in normal computers, but we can do cool quantum things with them. The simplest kind of qudit is called a qubit. We are already pretty good at solving the puzzles required for qubit error correction. But error correction for other qudits is a lot harder, and that's why why need your help.

No qudit is ever perfect. They are always noisy, and so errors will happen. We need a way to find these errors and remove them so that our quantum computation doesn't get messed up. That is what quantum error correction is all about.

There's a whole bunch of ways that we can do this. They are called codes. Our games use particular kinds of codes called surface codes. This is where the grid comes in.

The grid is made up of big white squares with qudits in the corners. Each qudit is shared between a couple of neighbouring squares.

For each big white square we set a rule that the qudits must follow. These rules don't tell each individual qudit what to do. Instead they tell the qudits around each square how they should play together. We can then set the grid up so that all the rules are being obeyed.

Then, like some sort of quantum police, we go around the grid checking up on all the squares. We look at whether or not the rules on each square are being obeyed. If we find some that aren't, we know that something has gone wrong. We know that at least one of the qudits has made an error.

There's more than one way that the rules can be broken. In fact, there are nine. We label these with the numbers from 1 to 9. When we find a square that's not doing what it should, we can then look at which of these nine types of crime has been committed.

Here's a couple of examples of qudits that have gone bad. One is blue and the other is dark red. All squares that now violate the rules have a red border.



The blue qudit leads to broken rules for the two squares that it is a part of. When we look at the numbers, we find that error made by the qudit is one that causes a type 6 violation on one square and type 4 on the other. We would have found different numbers if the qudit had made a different type of error.

The dark red qudit also messes up its two neighbouring squares. Here one has a 9 and the other has a 1.

In both of these examples, the numbers add up to 10. This is not a coincidence. Whenever a qudit goes bad it will break the rules on its two neighbouring squares, and the numbers for these broken rules will add up to 10.

What happens when more qudits go wrong? In the example below there is a new bad qudit, also shown in dark red. Here we've only put the red border around squares whose numbers have changed because of the new one.


This new error happens near one of the old ones. So near, in fact, that one poor square is now affected by crimes of both. We can no longer see the individual effects of each error, and so have to think of them as working together in a gang.


The dark red gang has caused three squares to break the rules, with numbers 9, 5 and 6. These numbers add up to 20, which is a multiple of 10. Again this is not a coincidence. Any team of errors, no matter how big or weird looking, will always lead to numbers that add up to a multiple of 10.

Now here's some more broken qudits. This time in green.



Again these share a square, and so form a gang. The numbers they generate are 8 and 2, which again is a multiple of 10 (10 itself, in fact). Interestingly, the square in the middle doesn't break the rules. This is a clever gang that has managed to cover its tracks a little.

If we don't do anything, this is going to continue. More qudits will turn to a life of crime and the gangs will get bigger.



What can we do? It's possible for us to make the squares follow the rules again, but this comes at a price. One of the neighbouring squares will have to break the rules instead. This means that we are basically moving the numbers around, like the green 2 below.



The other numbers being moved here end up bashing into something else. When two numbers meet, they add up. What happens if they add up to 10? There is no such thing as a type 10 violation of the rules. Only 1 to 9. It turns out that a 10 actually means that the rules are being followed. So adding numbers up to a multiple of 10 makes them disappear.


What about if they add up to more than 10? Since 10 basically acts as if it were nothing, 11 acts as if it were 1. 14 acts as if it where 4. 26, which has two lots of nothing, acts as 6. So when the numbers add up, we can ignore any multiples of 10.


As we saw earlier, all the numbers made by any particular gang of errors will add up to a multiple of 10. So pushing all these numbers together and adding them up will make them all disappear. The errors will then have been corrected, and the bad qudits will be back to being productive members of society.1 This is the aim of the game.

There are two things that will make it difficult for us to do this. Firstly, we don't know which qudits have messed up. We don't know which ones are working together in gangs. We only know which squares suffer from their crimes and what all the numbers are. The colours in the pictures above were just to make things clear for you. You won't be able to rely on their help in the game. You'll just see something like this.



This then gives you the puzzle you need to solve. Given this set of numbers, which groups of numbers were caused by the same gangs of errors? Once you've found these groups, you move them together so they add up to 10 and disappear. The damage done by the errors will have been removed.

The second thing making your life difficult is that more errors will come over time. New errors come after every five moves you make. This means that more rules will get broken, gangs will grow and change, and everything will become more complicated. You have as much time as you want to think about each move, though.


These troubles might lead to the most feared part of all games: Game Over! When does this happen, and how can you tell whether you are doing a good job?

Most importantly, we don't want the gangs to get too big. We want to keep them small, or get rid of them all together. This means that we need to stop the numbers they create from spreading too far. You do this by moving them together, adding them up and getting rid of them. The game ends once a gang has gotten its numbers to go all the way across the grid (top to bottom or left to right). That could mean something like the red team has done in this example that follows on from the examples earlier.



Or it could be something simpler, like this.


This was a pretty clever gang of errors. They somehow managed to get all the way across without leaving any mess in the middle. How did they manage such a feat? Sometimes it wasn't their cleverness that did it, it was your mistakes! For example, look at what the red and blue gang have done here.


If you look hard enough, you'll probably work out what you should do (even without the helpful colours). But if you are lazy and just look at the numbers in the middle, you might think “Hey, an 8 and a 2. Let's make a 10 out of those!” By doing this you close the gap between the gangs. They join forces to become the purple gang, which stretches from top to bottom. And then you lose.

The aim of the game is to go as long as possible before one of these big teams of errors comes and stretches across the grid. Your score is the number of moves you managed to make before everything messed up. This is basically the time that your quantum computer survives before the errors overwhelm it. 

To be useful for quantum computation, we'll need a method that gets scores that are as high as possible, and get them as reliably as possible. It's your job to find this! Your method should get a great high score, but also have a good average score too. You can find all your statistics on the 'Results' screen in the game.


A method for doing this job is called a decoding algorithm: it takes the information about what rules have been broken and it deciphers what must be done to get rid of the errors. So if sometime tells you to stop playing games, you can tell them that you are actually developing decoding algorithms for quantum error correction


Anyons

Before I move onto the other game, I will let you in on a little insider information about what is going on here. The numbers that we get when a rule is broken can be thought of as particles. They aren't really real particles, like apples or balls. But we can still move them around as if they were real things, as we have seen. So we can pretend that they are particles. To make it more sciency, we refer to pretend particles like these as quasiparticles.

They aren't just any quasiparticles. They are an exotic kind of particle that could not exist in our universe. No matter how hard they smash things together at CERN, these particles are never going to pop out. They are called Abelian anyons. Our error correcting code is like a new little universe we've made that lets us play with impossible particles.

The Game Φ-Λ

The other game is called Φ-Λ. Φ is the Greek letter Phi, and Λ is the Greek letter Lambda. We scientists and mathematicians like to use Greek letters because they make us look clever.

In 10 we did error correction with some pretend particles called Abelian anyons. These are pretty fun, but not as fun as their even more exotic cousins: non-Abelian anyons. Using these we might be able to build a quantum computer that is completely different from the boring normal computer that you are using to read this blog. We would do computations by making the anyons dance around each other. This would be called a topological quantum computer.

We would still need to do error correction. Noise will create a bunch of anyons that shouldn't be there, and we need to get rid of them. But error correction for non-Abelian anyons is quite different to that for the Abelian ones in 10. We can get a taste of this using a rather simple bunch of non-Abelian anyons, that are related to the Abelian ones in 10.2

All we need to do is take the same grid as in 10, use the same qudits and the same rules. The only difference is that we are not allowed to know as much about how the rules were broken. Before we would look exactly which of the 9 possible violations of each rule happened. Now we are only allowed to know whether it was type 5 (which we call Λ), or something else (which we call Φ).

This means that something like this from 10.




Will look like this in Φ-Λ.

This is going to make our life harder. In 10, when we think a bunch of numbers come from the same gang of errors, we can see whether they all add up to a multiple of 10. If they don't, we know that we were wrong and so we think again.

In Φ-Λ, if we think that a bunch of Φ's and Λ's came from the same gang of errors, it's not so easy to disprove our theory. We have to try moving them all together and see what happens. If they all disappear, maybe we were right. If not then we were wrong. In that case, we have to hope that we didn't mess everything up too much!

We are not completely helpless. We know that moving two Λ's together means moving to 5's together, and so these will always add up to 10 and disappear. Moving a Λ and a Φ together means adding a 5 to a 1, 2, 3, 4, 6, 7, 8 or 9. This will give 6, 7, 8, 9, 11, 12, 13 or 14. None of these are 10 or 5, so they won't disappear or become a Λ. It will always end up just being a Φ. Moving two Φ's together could make them disappear (if they were 2 and 8, for example). It could also make them become a 5 (if they were 1 and 4, for example). It could even make them become a single Φ (if they were 1 and 3, for example).3


For some concrete examples, take a look at the picture below that we saw before in 10. If this same thing were to happen in Φ-Λ, we'd have to replace the numbers with Φ's and
Φ-Λ. Moving the blue Φ's together annihlates them: they both disappear. Moving the red
Φ into red Λ results in them combining to become a Φ. Only when we move that into the remaining red Φ will we get annihilation.



Combining non-Abelian anyons is an uncertain business: we don't always know what is going to happen. This uncertainty is one of the things that would make them so useful for quantum computation. Unfortunately, it also makes it pretty hard to do error correction for them. In fact, no-one has proven that error correction for these non-Abelian anyons can be done well enough to use them for quantum computation. You can help me prove this. Playing Φ-Λ and finding out how to consistently get high scores is just the beginning.

Go forth and science!


This is all you need to know to get on and do some science. In fact, it's more than you need to know. So check out either Decodoku or Decodoku:Puzzles to get going.


If you want to know even more, check out the rest of this blog. Here is a good place to start (everything before that post is a prequel).


Attack of the Clones


When a mobile app gets successful, it often gets cloned. That would not be a problem for us. Why aren't in it for the money. There's no charge or ads for anything we do. We are doing it for science! If someone takes something that a scientist or mathematician has produced and does something new with it, it's never anything but awesome.


Soon we will release the source code to the game. With that, you'll be able to see how I hacked it together. If you'd like to see a few new features, you can of course let us know. But you can also try to implement them yourself, and have your own personal version of the app. If you think that others would enjoy them, you could also release it to the public. It's all for the good of science, so it can only be a good thing. Just make sure to follow the normal scientific conduct by acknowledging for giving you the idea.

Footnotes


This is not entirely true. If you let the gang get too big before correcting it, the effects of their crimes may remain. Check out the rest of this blog if you want to know all the details. Here is a good place to start.


2 Non-Abelian anyons aren't usually so closely related to Abelian ones like this, especially the ones that can do quantum computation. But the Φ-Λ type of non-Abelian anyons are, so they let us try out doing error correction for non-Abelian anyons without straying too far from the 10 problem.


3 This was the most horrible and technical paragraph in the post. Well done for not skipping it!