What Does It Mean For a Computer Program To Be Creative?

Last week I was at the ACM Creativity & Cognition Conference and in one of the workshops we got into an argument about the nature of creativity (no surprise there).

Some people were saying that for a program to be creative required that it change the search space it was using. To understand this point of view, it's important to understand what artificial intelligence researchers mean by "search space."

For any given task, the search space is a theoretical graph of states of the world that can be reached through action. For example, in chess, each move you can make puts the board into a different state. If you were to link all of the possible moves going from one state to another, then you'd have a description of the search space. In chess, you can't legally move a pawn backwards. So there is no link between the two states of the board that would require that move.  Typically we picture the search space as a graph, which is a bunch of nodes connected by links. The nodes are the states, and the links are the actions. However, the picture of a graph that we might have in our heads or on paper can be misleading, because for any serious domain the search space is unimaginably large. In chess, the number of board configurations is commonly thought to be ten to the 120th power. That means a 1 with 120 zeros after it.

Playing chess is often viewed as navigating this search space.

So, back to the creativity question. When people talk about true creativity expanding the search space, they mean adding states and actions to the space itself.  The classic tale of the Gordian knot is a great example of this. The Gordian knot was a fiendish knot that baffled all of those who tried to unravel it. Legend has it that Alexander the Great solved the puzzle by chopping the knot with his sword (pictured.) He expanded the search space, which had been assumed by everyone else to include only pulling at rope. Personally, I find this about as creative as winning a chess game by strangling your opponent, but I guess I can see the allure of this tale.

Although expanding the search space is undoubtedly creative, requiring an expansion of the space to qualify a thing or process as creative is setting the bar far too high.

For one thing, the search space that human chess players use is the same search space that computer programs use. If expanding that space is required for creativity, then it's impossible for any human to be creative in chess either. The same holds for music composition. If you think of musical notation, there are a finite, albeit enormous, number of ways notes and rests can be arranged on a single page. But nobody would think that creating a new piece of music was not creative.

As for chess-playing computers, they are teaching things about chess to chess experts.

“They make a lot of counterintuitive, even absurd-looking, moves that on closer inspection can turn out to be outrageously creative…By generating countless new ideas, they are expanding the boundaries of chess, enabling top players to study the game more deeply, play more subtly.” –John Watson, international chess master, Quoted in Best American Science Writing 2006, p13, from Mueller’s New Yorker article on AI chess “Your Move.”

Pictured: Alexander the Great cuts the Gordian knot. A public domain image from wikimedia commons.