[SciShow intro plays]

Hank: The machines have won. Computers can now defeat humans at pretty much any game we’ve ever invented. And all because of some clever tricks we’ve come up with for programming artificial intelligence, or AI. The simplest definition of AI is a computer program designed to solve a problem.

Most programs, including probably all of the ones letting you watch this video right now, don’t solve problems. Instead, they execute instructions, that they were given by human programmers. They don’t try to come up with their own solutions for what they should do to accomplish a task. AIs do try to come up with their own solutions. The smarter an AI is, the more complicated the problem it can solve.

Since the dawn of computer programming, we’ve been teaching AIs how to play games. Things like checkers, and chess, and recently, the Chinese board game Go. We do that because games are a great way to measure how smart an AI actually is. Playing, and winning, a game requires problem solving.

And the ability to solve problems is one of the benchmarks of intelligence. It helps that the problems are very clearly defined, for both the human audience and the computer program. There are no ambiguous results: either the AI can play checkers, or it can’t. This makes games the perfect lab environment for creating new kinds of AI, which is why the history of AI is often the history of AIs playing games.

The first game an AI ever played and won against a human opponent was a checkers program, written in the 1950s by American computer scientist Arthur Samuel for the IBM 704 computer. This was a machine that you had to program by feeding magnetic tape into a big drum.

Checkers is a simple game. But the IBM 704 was a pretty simple machine. It couldn’t run the outcome of every possible move it could make by trial and error in order to find the best one. At least, not in a reasonable amount of time. If it could, that would be solving the problem of winning a game of checkers with brute force.

The brute force approach involves crunching a lot of numbers: the computer plays out every possible game that could take place after every possible move, then picks the move with the highest probability of leading to a win. That’s not very creative, but it’s definitely a valid way to solve the problem. And we’ll come back to it in a few minutes.

The problem is, the brute force approach uses a lot of computing resources to run all those numbers. Those resources just weren’t available back in the 1950s. So the first game-playing AI was made possible thanks to something called heuristics. And every AI since then has used them.

A heuristic is basically a rule of thumb. It may not always be exactly right, but it’s almost always mostly right. In computer science, a heuristic is an algorithm that limits brute force searching by selecting solutions that may not be the best, but are good enough.

So a checkers algorithm might say: okay, you found a move that lets you capture an opponent’s piece. You can stop now! Just go with that move. Simple heuristical programming like that was enough to conquer checkers.

The next game an AI faced was poker. In the 1970s, computer scientist Donald Waterman wrote a program that could play draw poker — the kind where you’re dealt five cards and can replace some of them, typically up to three cards. He did it by developing something called a production system, another thing that you’ll now find in AIs everywhere.

Production systems use pre-programmed rules to categorize symbols, like those on a card. Waterman's system sorted cards as more or less valuable depending on what other cards it already had in its hand. Like, on its own, a four of clubs isn’t much to write home about, but it has a lot more value if you already have the four of diamonds and the four of spades. The system could then calculate how good its hand was, and whether or not it should stay in or fold out, by comparing the value of its hand to its pre-programmed measures of what a "good" or "bad" hand was.

Heuristics and production systems. Algorithms that apply rules of thumb, and programs that apply complex and comparative systems of rules. Put those together, and creating AIs that could play basic board games became a walk in the park.

Chess is not a basic board game, though. It’s a grown-up board game, and winning it was going to take some grown-up technology. The first chess machines were built in the 1980s, at Carnegie Mellon University. The most successful of these early machines was Deep Thought, which could calculate the outcomes of 700,000 moves per second. And Deep Thought actually managed to defeat a chess Grandmaster, in 1988. But there’s a big difference between just some Grandmaster, and the greatest chess player in the world. That man, in the 80s, 90s, and actually still today, is Garry Kasparov.

Deep Thought was not on Kasparov’s level. Beating Kasparov meant getting stronger, and faster. Like, a lot. Upgrading Deep Thought involved a few improvements. Number one, more memory and more multiprocessors. That's raw computing power. Deep Blue, Deep Thought’s successor, was simply a more powerful machine.

Number two, better software. When you're dealing with millions of search results, all being compared to each other, slowdown is a big problem. So Deep Blue's software was streamlined for parallel processing. It was also taught to factor in some of the more nuanced measures of a favorable chess position. Better heuristics, in other words.

The search speed for the first version of Deep Blue was about 50 to 100 million chess positions per second. And when it was matched up against Garry Kasparov... it lost. Pretty decisively, with two wins against Kasparov's four. Calculating the outcomes of 100 million chess positions per second was not enough to beat the human world champion of chess.

So team Deep Blue more than doubled the number of chips in the system, and improved the software so that each chip was about 25% more effective. The version of Deep Blue that played a rematch tournament against Kasparov in 1997 could calculate over 300 million chess positions per second. And then it won.

Deep Blue was an incredible feat of computer programming. When it defeated Garry Kasparov, it was the most complex AI in the world. But it mostly won through brute force. It crunched the numbers for every possible move it or its opponent could make, then picked the one most likely to lead to victory. If it didn’t win, its programmers upgraded it so it could crunch even more numbers.

That approach was not going to work with the game of Go. We talked about Go here on SciShow when Google's AlphaGo program defeated world Go champion Lee Sedol, in March of 2016. But let's go over the factors that made creating a Go program such a daunting task.

If you grew up in the West, you might not be familiar with Go. It’s a Chinese game that's existed unchanged for thousands of years. It's sometimes described as "Eastern chess," but it’s much more complicated than chess, especially for a computer.

First of all, a Go board is bigger than a chess board. Go is played on a 19x19 grid, while a chess board is 8x8. But that's underselling the complexity of Go, because you don't play the stones — stones are what the pieces are called in Go — inside the grid tiles. You play them on the corners. Meaning that each tile actually represents four possible positions, which may or may not be shared with more of the surrounding tiles. Bottom line: there are more possible board configurations in a game of Go than there are atoms in the universe.

Secondly, no Go stone is inherently more valuable than any other stone on the board. This is different from chess, where a queen, for example, is much more valuable than a pawn. That kind of relationship is something you can program an AI to understand. You can feed that into a production system. But a stone in Go gets its value from its position on the board relative to the positions of all the other stones on the board.

The objective in Go is to use your stones to surround more territory than your opponent. So the value of any one move is often subjective. Even high level Go players sometimes have a hard time explaining how they know a good move from a bad one. And you know what computers are really bad at? Being subjective. Also, calculating positions that run into the trillions of trillions.

The Deep Blue brute force approach was not going to get anywhere with Go. So AlphaGo is not a brute force program. It uses deep neural networks: the same kind of technology that's used by facial recognition software. Instead of calculating stone positions piece by piece, it looks for patterns on the board. Just like facial recognition programs will search an image for things that might be eyes, noses, and mouths, AlphaGo looks for patterns of stones that might offer strong or weak tactical opportunities.

But how does it know what makes something a strong or weak opportunity? I mean, we said the value of any specific position is subjective, right? Here's where you need to know how deep neural networks work.

A deep neural network is made up of layers of different computer systems, called "neurons," all stacked up on top of each other and running in parallel. This allows the network to analyze the same problem from multiple different angles at the same time. Each layer judges the same image by different criteria.

So, one layer will look at the picture of the Go board and pick out all of the legal moves. The next layer might examine the board for areas that aren't under anyone's control yet. The layer beneath that could be keeping track of how long it's been since either player has made a move in any particular region of the board. That tells the program which areas are currently being fought over, and which ones might be safe to ignore for a while. The layer beneath that might be comparing the patterns of white and black stones to its internal database, to see if anything happening on the board looks like anything it's seen before. And so on, and so on.

AlphaGo has 48 layers of neurons, each with its own way of evaluating the board. Those layers send information up and down the stack to all of the other layers. So if one layer turns up something really promising, the other layers will all focus on that area of the board.

When all of the layers agree on a move as meeting their own criteria for what makes a "good move," AlphaGo plays a stone. By using a deep neural network in this way, the program can actually mimic human intuition and creativity. AlphaGo defeated Lee Sedol 4 games to 1. Sedol is the Garry Kasparov of the Go world. And AlphaGo is only going to get smarter.

So when it comes to game-playing AIs... there aren’t really any challenges left anymore. Go was it: the most complex board game people have ever devised. Though I kind of would like to see it play Arkham Horror. But we made AlphaGo.

We made Deep Blue. These programs are manifestations of our intelligence and curiosity. And if we can create an AI that can beat Lee Sedol at the most complicated and intuitive game ever played, then who knows what else we can do.

Thanks for watching this episode of SciShow, which was brought to you by our patrons on Patreon. If you want to help support this show, you can go to Patreon.com/SciShow, and if you just want to keep getting smarter with us, you can go to YouTube.com/SciShow and subscribe!