Creation

This chapter concerns the second time I created something smarter than me. The first such occasion, the birth of my only son, was not entirely my doing as my wife had a rather significant contribution too. But the second creation was all mine. It was a computer program that played the strategy board game Othello, also known as Reversi. (Note, the link provided leads to a different implementation of the game.) I wrote it as a semester project while doing research at the Artificial Intelligence Laboratory at the University of Texas at Austin.

I did this because back then, and still today, I was interested in finding answers to some deep questions about the nature of creativity and the creative process. Where do new ideas come from? What makes an idea clever? Imaginative? Inventive? How do humans create new things and can we program computers to do it too? And most generally, how does the Universe create order out of chaos?

It is clear that new ideas are not just mechanically derived from old ones, at least not the really good new ideas. There is usually a spark, a creative aha moment during which something completely new is dredged up from a place where few of us ever go. Ideas can be encoded as (possibly infinite) numbers, and we know (see The Divine Random in Computing) that not all numbers can be computed by any effective procedure. That means there are infinitely many new ideas, most of them in fact, that cannot possibly be derived from what we already know. One must assume that at least some of these infinitely many ideas are good ones. A good truly random number generator will, eventually, produce all possible numbers, including quite a few that encode good ideas. So there we have an answer to our questions: just wait around for the next good idea to come around on the random number generator. As we'll see in a later chapter, it can be shown that a random number exists that encodes the correct answers to all possible yes/no questions expressible in a given language. A single number that contains the answers to all our questions certainly seems to qualify as a good idea.

Of course, that's not very practical. The probability of our random number generator producing the answer to everything, or even a single good idea, in our lifetimes is minuscule, to say the least. And besides, we probably wouldn't recognize a good idea if it presented itself at our front door and brought nachos. It would be like working on a jigsaw puzzle, picking up a random piece and declaring, "Eureka! I've discovered something wonderful." A jigsaw piece or an idea isn't a great find unless it fits within the existing framework we have already constructed and understand. The greatest ideas are not just the ones that are unexpected and fresh, but also the ones that are most tightly constrained, by the rules of mathematics, art, language, etc. But randomness must play a role in the creative process. The close proximity between madness and creativity, genius and weirdness, eccentricity and insanity, has long been known and commented upon by philosophers and humorists through the ages. Genius, it seems, is the exact right admixture of crazy and constraint.

With all those general ideas about creativity, I set out to build a computer program that could surprise me by having a good idea, one that I myself had not built into its code. I chose to write a program that played Othello for several reasons — the rules are simple, the game is easy to play but non-trivial, and perhaps most importantly, I wasn't very good at it. Most of the Othello program consisted of my own implementations of several well-known game playing algorithms that had been and continue to be used for computer strategy games. At its core was the so-called mini-max tree search algorithm with alpha-beta pruning. The linked article has a pretty good explanation of what that is. Basically, it's a formalized way to imagine what will happen in the future. If I do this, my opponent will probably do that, after which I can do this other thing, and so on. Because a computer can do those kinds of things really quickly, it can enumerate through all possible legal moves it has to choose from at any point in the game, and through all the legal moves its opponent would have, through many levels of what-ifs. But the decision tree for Othello, like the ones for Chess and Go, is too big for any computer to completely traverse all the way down to the bottom (at which point it can simply ask which of my current moves leads to a win many moves down the road). So the computer stops searching the decision tree at some arbitrarily-chosen depth and simply looks at the resulting board positions asking itself which ones seem to be the most advantageous for it. This last bit is heuristic, of course. It's a guess based on who has how many pieces remaining and how they are distributed about the board. Game programmers call this a static evaluation function.

There are many, many different types of static evaluation functions for the game of Othello, from simple linear combinations of cell contents (0=empty, 1=mine, -1=opponent's), to more sophisticated heuristics based on pattern-matching. I chose a paradigm that looked for a certain fixed set of patterns on the board and weighted those patterns, when they occurred, to produce a simple number that could be compared against other positions. The choice of static evaluation function thus boiled down to a vector of small integers. Choosing the proper weights for the evaluation vector to make the program play well required deep insights into the game's winning strategies; insights I did not have. And despite its look-ahead capability, the quality of the game's play against me was very sensitive to the choice of static evaluation vector — for some vectors I could beat the program nearly every time, while others were more difficult to win against. Using trial and error, I was not able to find a vector that would make the game play consistently better than me, a poor player.

And then the light bulb came on. Why not have the computer play against itself, using different static evaluation vectors (SEVs), and search for the best one? To do this, I coded the following search algorithm. First, I randomly generated several thousand SEVs to form an initial population of alternatives. I let the computer randomly choose two of those SEVs and play a game, one strategy against the other. Each SEV also had a merit score attached to it, and when an individual SEV won a game against an opponent, the program would increment the winner's merit score and decrement the loser's. In this way, the computer would eventually filter through the initial population and find the best strategy found there.

But what if there was a really great idea, a winning strategy, that did not happen to be one of the few thousand initial, random SEVs? I needed to somehow interject new blood, fresh DNA into the gene pool in order to do a more thorough search of the whole space of all SEVs. To do that, I wrote a second process, in addition to the competition process described above, to periodically generate new individuals. But I didn't just pick a random puzzle piece and cry Eureka! Instead I had the computer choose two different individuals, randomly but with a distribution that favored SEVs with higher merit scores, and combine the vectors in a way that borrows from biology. To combine two SEVs, the computer chose a random position along the vector and split both parent vectors at that point. A new child vector was created by choosing the first segment of one of the parents and the second segment of the other parent and then, with small probability, adding or subtracting one from a randomly selected value on the vector. In biology, this is called chromosomal cross-over with mutation. Once a new individual SEV was created in this way, the individual with the lowest merit score in the entire population was "killed off" and replaced with the new offspring, who was then available for further competition and breeding.

Once the competition and the breeding processes were chugging along, new strategies were being created and the computer played one game after another with itself. I allowed it to run all night, and all day the next day, and all that week, searching for that good idea, that winning strategy that I could not have taught it even if I'd wanted to. Every once in a while, I would interrupt the search to play a game against the current best strategy evolved so far. At first, the randomly-chosen strategies were pretty terrible. After only a few hours, I found I could still beat the computer regularly and with little effort. After a day or two, it became noticeably more difficult to win, and I found I had to concentrate more carefully to avoid the strategic tricks pulled by the computer. After four days, the computer began to win regularly, and after about a week, I found I could no longer win even a single game against the computer program that I myself had created. Now let me assure you, that is a spooky feeling, to be outsmarted by one's own creation. It was definitely a Frankenstein moment for me.

The type of search algorithm I used in the Othello game is known as a genetic algorithm (GA) because it mimics natural selection. GAs typically include most of the elements I've described above: a competition process, a breeding process that uses genetic operators like cross-over and mutation, and a fitness function or merit score. Randomness plays a vital role in the successful operation of any GA, but it isn't just a random search. Applying the fitness function to select competitors and breeding partners ensures the algorithm as a whole behaves as a kind of a algorithmic ratchet, always making progress toward a more fit population. Random variation together with deterministic filtering, survival of the fittest, is the hallmark of GA. Another common characteristic is the distinction between a genome and a phenome. In the Othello example, the genome was the Static Evaluation Vector, which resembles DNA in function. The phenome, the organism itself, is the rest of the game playing machinery — the mini-max tree search with optimizations and the codified rules that prevent the game making illegal moves.

And so you see, evolution exists. It is, as they say nowadays, a thing. I've touched it, implemented it, and watched it create things that surprised me. Evolution is not simply a random number generator, but rather an algorithm that systematically trolls the vast ocean of randomness to make steady progress in the direction of survivability. It is not just a way to create useful new ideas and individuals, it may be the only such algorithm we know of. And so it worries and frustrates me to see results like the recent Pew poll on the Public's View of Human Evolution that suggests more and more people do not believe that biological evolution is a thing.

To be sure, random mutation without the rational, mechanical ratcheting of natural selection would make no progress at all. The probability of producing something useful, or more useful, from such a coin flip process is unimaginably small. But randomness is the seed of creation, the origin of species. It is the essence of humanity and certainty its antithesis. When a man is entirely reduced to numbers, he ceases to be alive.