Transcription
This is a video about Brainfuck, a programming language you can't even talk about without swearing. Brainfuck is an esoteric programming language, which means that it wasn't designed to be practical, but to be fun.
There are lots of esoteric programming languages, but what makes Brainfuck special is that it is extremely simple. There are only eight possible instructions. It's a little bit like programming in assembly, except even the simplest assembly languages have dozens of instructions, and most of those instructions take arguments or addresses, which means that the op codes are actually quite long.
There's even something called a single instruction computer, which, as the name suggests, has only one instruction. That instruction is "subtract and branch if less than or equal." It is a Turing-complete instruction set, but it's operating with direct memory access, which means that that single instruction takes an argument, which, depending on the size of your address space, could be quite large.
In Brainfuck, there are no arguments, there are no addresses. There are just eight valid characters. Everything else is treated as a comment. Brainfuck is Turing-complete, but Turing-complete means that we can calculate anything, not that we can program anything. Turing completeness says nothing about interactivity or timing, and certainly makes no mention of interrupts. We could add some of these things through the use of memory-mapped peripherals, but that's outside the scope of this video.
Brainfuck operates on one single address space, and its memory goes on to infinity, or at least as close to infinity as we can be bothered to implement. We have a single pointer to this memory. Our first two instructions are plus and minus, and these simply add one or subtract one from the current memory location. Then there are the left and right arrow instructions, which say to move our pointer to the left or move it to the right.
Then there are the loop controls. This is where the logic of our program really happens. The opening brace means if the current memory cell is zero, jump ahead to the corresponding closing brace. And the closing brace means if the current memory cell is not zero, jump back to the corresponding opening brace. The effect of this is that any code between these brackets will continue to run until the memory cell pointed to at the end is zero. The brackets can, of course, be nested, and this is where programs start to get complicated.
The other two instructions are our input and output. The dot or period takes the value in the current memory cell and prints it as an ASCII character to the output terminal. Similarly, the comma takes one byte of input from the keyboard and stores its ASCII value in the current memory cell. If there's nothing in the input buffer, most implementations will wait for a key press, but it's not guaranteed.
So, taken straight from Wikipedia, here is "Hello World" in Brainfuck. Lots of people write interpreters and compilers for Brainfuck. I myself have written many of them. Brainfuck is so simple that most people can write an interpreter for it in an afternoon. If you've always wanted to impress people by saying, "Hey there, I've written my own optimizing compiler," then Brainfuck is a language for you.
There are compilers for Brainfuck to machine code, and there are compilers from Brainfuck to C, and to Python, and others. There are compilers to Brainfuck. There are even compilers for Brainfuck written in Brainfuck. But very few people actually write programs in Brainfuck. There's a classic Brainfuck program that prints the Mandelbrot set in ASCII art, but I'm pretty sure this was compiled to Brainfuck from some other language. There is "Game of Life" in Brainfuck, written by Linus Åkesson, which is extremely impressive, but in the true spirit of Brainfuck, we have no information at all about how this program works.
Almost everything else I could find was very short or very simple. I want you to write a program in Brainfuck, something non-trivial, something long enough that it wasn't possible to just wing it. The title of this video is, of course, "Artificial Intelligence in Brainfuck," but by that, I don't mean machine learning or deep neural networks. When I think of artificial intelligence, I think of Deep Blue, the chess computer that defeated Garry Kasparov, a machine opponent in a strategy game.
I figured that a chess computer was a little bit ambitious for my first Brainfuck program, so instead, I went with the slightly simpler game of Noughts and Crosses, also known as Tic-Tac-Toe. Let's think about the structure of our program. We want to plot the board in ASCII art, then we want to take input from the keyboard so that the human user can make their move. Next, we make a decision of where we want to move and plot the board again. All the while, we need to be checking if the human has won, if we've won, or if it's a draw.
I thought I'd start with the easiest part: taking input from the human. The simplest way to do this is to accept a number between one and nine that corresponds to the grid location of where you want to place an X. The Brainfuck program means to listen to the keyboard and check that the input is greater than ASCII zero and less than or equal to ASCII nine. It turns out that doing this in Brainfuck is really hard. Even doing an equality in Brainfuck is hard. The only way to check if one cell is equal to another is to decrement both of them and see if they hit zero at the same time.
So, before we even begin, we need to copy the data to another cell so that we don't destroy the original data. And just to copy the data to another cell is tedious. You have to copy it to two cells, destroying the original in the process, and then copy one of those cells back to the original location. So our simple "choose a number" script that keeps reading input from the keyboard until it's between ASCII one and ASCII nine is not simple at all.
Here's what I came up with. I don't expect anyone to follow what's going on here. Even looking back on it, despite the fact it's commented, I can't quite remember what I was thinking. The rough idea is about counting both numbers down and breaking out of the loop by shifting across if one of those numbers hits zero before the other. I wrote this in the same way I think most painful programs are written: I just kept fiddling around in the interpreter until it worked. And while it does work, it's not exactly a scalable approach to writing software. Remember that this is just selecting a number, and already the program is looking pretty unintelligible. Having said that, it does work, and we know exactly how much memory it uses and where it leaves the pointer, so we can minimize it. Consider it a black box and just drop it into our main program as a module.
Onwards, then, to the main program. We have to store the state of the game board in memory, and I thought this would be easy. There are only three possible states for each grid location: empty, naught, or cross. So let's have nine memory locations and give them values zero, one, or two depending on their state. I did not get very far with the program before realizing that this was completely unworkable. I found it so difficult to do even the simplest logic, such as testing if a given grid location has an X in it. The only comparison that's easy to do in Brainfuck is to ask, "Is this cell zero?"
So I started over. I decided to use three cells per grid location, so 27 in total, and used them as boolean flags. By making sure our program only ever sets these memory locations to zero or one, our program logic can be so much simpler. The first cell is set to one if the grid location is empty, the second cell is set to one if there is an X there, and the third cell is set to one if there's not there. So long as the program behaves correctly, this shouldn't ever go out of sync.
Okay, we've accepted a number from the keyboard, and we want to move our pointer to the array cell that corresponds to that grid location. Basically, this is an indirect jump, and we can do it by writing something like this. This continuously decrements the current cell while opening loops, then moves the pointer a fixed amount in each loop. So if the user had typed five, the outer five loops will run, and the pointer will be shifted fifteen cells to the right. You have to admit that this is a rather elegant bit of code.
Afterwards, we then move the pointer another fixed amount of cells across because the number-choosing script operates in a different part of memory to where our array is. Then we can see if the cell is empty, put an X there, or if not, we can head back to the "choose a number" script. Except now we don't know where we are. The pointer is somewhere in the array. We have no way of knowing how many cells we have to move by in order to get back to a known memory location. Even if we'd copied that number to somewhere, we wouldn't have any point of reference to look for that number.
There's a technique I came up with that turned out to be very useful for getting out of situations like this. An open bracket lets us check if the cell is zero. If we decrement the cell beforehand, we're essentially checking if it's one. So long as we increment the cell afterwards, and we make sure that this happens regardless of if the condition was true or not, it'll be left how we found it. Instead of checking for exactly one, I decided to check for minus one. This might be represented as 255 in memory, but it doesn't really matter, just so long as when we add one to it, it becomes zero. By surrounding a pointer shift with this checking code, we come up with this. I feel like this is a lot like the glider in "Game of Life." It says, "Keep moving left in memory until you hit a value of minus one." Now we can set the first cell before the array to be minus one and use it as a reference point to get back to after our indirect jumps. I ended up using this technique a lot.
Here's part of the check for if X is one. We need to see if all of the top row of the grid is set to X. We move to the first array cell, then shift along by one to get to the X flag. Now, three conditions can check if each of those grid locations are X's, and if they are, the middle two lines will run. At this point, we want to go back to an earlier part of memory and set a flag to say that X is one. The fastest way to do this is to use the glider again, once to head back, and then again to head forwards to the start of the array so that the code afterwards will run correctly regardless of if the condition was true. Here it is again. This time, we're checking if it's a draw. We start by setting a flag which denotes that the board is full, then go through each cell, and if we find that it's empty, clear the flag. The glider is used repeatedly for jumping back and forth between reference points. Not only is the code shorter than it would have been otherwise, it's also a lot easier to read.
So this technique, along with booleans everywhere, turns what was a rather daunting task into something quite manageable. All that's left to think about is how our computer opponent is going to decide where to go. I took a very human approach to this, thinking along the lines of how a person would play. The very first priority is to take a winning move if it's available. So if there are any two naughts in a row, take that move. Otherwise, the next thing to do is to block the opponent from winning. If there are any two X's in a row, we can block them there. This alone generates a surprisingly viable opponent, and from here, all we need to add are a series of priorities of where to go under different conditions.
It is possible to write a perfect AI for Tic-Tac-Toe, one that will always either win or draw, but honestly, I think that's rather boring. In my program, I deliberately left one or two ways in which the human can win, otherwise no one would bother playing. The final code from my program was minimized into a huge block of unreadable characters, and I put up an online interpreter so it can be played in a browser. I've also put the full, mostly commented source code up on GitHub. If you stick this into my debugging interpreter, you can slow it down, follow along, and watch what it's doing to the memory in real time.
Despite what you might think, I found writing a program in Brainfuck a really enjoyable experience, and hopefully, I've convinced one or two people to give it a go. I've put links to everything in the description. Thanks for watching.