Rats of the Maze

Opening title So the lights are about to dim. But before we do, what are we gonna see? Well, I'm not gonna tell you specifically. I'm gonna tell you who it is, it's Simon Swain. Many of you will know, last year we had the cold war simulator, emulator experience. Well, it's something in the same vain. I think it's also very important to note as those lights dim, feel like I'm at the Oscars and I've worn out my welcome, that everything that you're about to see is coming live out of the browser, there's nothing pre-canned, so this is on top of everything else, an example of the kind of real time capabilities of the web browser, so I'm not gonna tell you anymore. I'm simply going to introduce Simon Swain. (audience applause) - The year is 2048. 30 years ago, we outsourced the very runnings of our lives to Machines. Machines that learn. The Machines learnt too well. Today, all computing resource on the planet has been consolidated in a vast maze hewn out of solid rock. No humans have access to The Maze, but the warm glow of its reactors make an ideal home for millions of flesh-eating rats. (audience laughing) Your mission is to enter The Maze, sabotage the power source of the Machines, and free the human race from its self-inflicted, automated prison. You are our last best hope. But until today, no human has survived The Maze of the Rats. To defeat the Machines, first we must understand The Machines. Computer memory is the meeting point between the real and the virtual. We implement memory using a capacitor. A capacitor is a passive electronic component that holds a charge. We apply a charge to our capacitor, and the charge decays over time. If we nominate a charge above a certain threshold as representing a binary one, and below a certain threshold as representing a binary zero, we can store the value of one bit of information in our capacitor. If we automate the process of periodically refreshing the charge on our capacitor, we can store the value of our bit, in memory. For as long as we have a supply of power. Now, one bit on its own is only so useful. So, typically, we arrange our bits together on a collection of eight, called a byte. A byte can hold any one of 256 possible values. You could use this value to represent a number. A letter of the alphabet, a shade of grey. The possibilities are almost limitless. By manipulating the bits within our byte, we can perform some interesting operations. If we shift all our bits in our byte to the left or the right by one position, we can multiply or divide the value of our byte by two. With almost no effort. But a single byte on its own is not so useful. So, typically we arrange our bytes together into a collection we call a bank of memory. We use that memory to store representation of whatever problem we happen to be working on. Now, bank of memory is not so useful, unless you can individually access the bytes within that memory. To do this, we use a technique called the address bus. We index our memory from zero up to the number of bytes we have. We place the index of the byte we wished to access on our address bus, and we can read or write that byte at our leisure. Modern computers use the same principle, but with a much wider address bus, giving us access to an almost incomprehensible amount of memory. We have a bank of memory, we use it to store our representation of whatever problem we happen to be working on. We apply algorithms to that representation in the hope of finding a solution. Logically, our memory is linear, arranged in one dimension. Indexed from zero up to the number of bytes we have. But the problem space we wish to operate on, may not be one dimensional. We wish to operate on a two dimensional grid, with each cell on the grid being referenced by an x, y coordinate. In this case, we can use a simple formula to translate between the x, y coordinates that refer to the cells on the grid, and the zero indexed memory location that holds the information about each cell. This allows us to effectively abstract away the underlying implementation of our memory. And refer to the problem space in our own terms, making it much easier for us to reason about the algorithms we're going to apply. Some of the earliest algorithms we taught the Machines were pathetically trivial. This example is called a drunken walk. We start in the center of our memory space, and we move in a random direction, up, down, left, or right. As we enter a memory location, we clear out its value. Much like if you were digging out rocks from a cavern under the ground. If you leave it running long enough, you will clear out all of your memory. There is a veritable smorgasbord of algorithms we taught the Machines. But they all converged on one point. They taught our Machines to be effective predators. (audience laughing) The representation we've used so far has a major drawback. We're using one memory location to hold the information about each cell. We're using that cell's position to determine which its neighbors are. Now, this seems fine, but it denies us the ability to say two cells are not connected together. We can make a small change to our representation. As well as storing information about the content of each cell, we can store a list of the indexes of the neighbours each cell it's connected to. This gives us the ability to have runs of cells that are connected together, and cells that are completely isolated from their neighbours, giving us access to a whole new class of powerful algorithms. Teaching the Machines these algorithms was our worst mistake. Start with a grid of unconnected cells. Pick a cell at random, any cell will do. Pick a neighbour of that cell at random, ensuring that that neighbour has no connection to any of its neighbors. Create a mutual connection between the two cells, place our starting point onto a list of places we visited. And repeat the process for our neighboring cell. As we work through our grid, we'll build up a list of places we visited. Eventually, we will get to the point where there are no more cells to explore. We work back along our list, following up in any unconnected cells we find. When there's nothing left on our list, we know we have formed a perfect maze. This little algorithm works on a grid of any size. And gives us a perfect maze, every time. So, if we have a maze, how do we solve a maze? We must have an ingress, and an egress, an origin and a destination. We expand the search frontier from our origin, through every connected cell we can find. As we explore, we recall the place we came from. And calculate the score for each cell, based on the distance we traveled. If for a given path, there are no more cells to explore, we terminate the search on that path. If we reached our destination, our search is complete. And we used the list of places we came from to determine our route. We can enhance the cell algorithm by adding a heuristic to the score for each cell, based roughly on the distance from that cell to our destination. By searching on the path with the lowest overall score, we can complete our search quickly. This is what we taught the Machines. And now, we pay the price. Human hackers have penetrated the Machine's networks and obtained some basic information on the configuration of their defenses. Before you enter The Maze, we'll provide you a brief overview of what we know so far. The machines hide deep in their maze from where they control our world to save all their power, to free all humans. Each maze has a reactor, find the reactor! Sabotage it. Escape! Follow markers to reach your goal. Follow markers to reach your goal! Follow markers to reach your goal! We have identified three primary variants of vermin inhabiting The Maze. The killer rat, the breeder rat, and the baby rat. Superior machine engineering creates rat breeding factories. Destroy rats! Have no mercy. In a tight situation, you're super as ever, will help you survive. Before you enter The Maze, we will provide a brief training simulation to enhance your skills. Are you ready? You look ready. (audience laughing) Maze number one, this is the easy one. Maze number two. (audience laughing) You're in a long maze of twisty passages, all alike. There's an exit to the east. Maze number three. (audience laughing) Follow markers to reach your goal. Could this be our goal? Uh oh. Silly humans, you will never defeat the Machines. (audience laughing) Thank you.