John McCarthy – who, you may recall, coined the phrase “artificial intelligence” – has written a well-known article with the title, “Chess as the Drosophila of AI” (1990). In his introduction McCarthy notes:
One of the pressures I was under came from people in computer science. They sometimes urged me to tackle topics of practical importance and to concentrate on experimental and theoretical work in precisely these applicable areas, as opposed to a backwater such as computer chess. This echoes a remark that might have been made to Thomas Hunt Morgan in 1910: “Elephants are far more useful than fruitflies and who wants better fruitflies? So why don't you do your work in genetics on elephants rather than on fruitflies?” To which Morgan could have countered: “It takes no more than two weeks to breed a generation of fruitflies, you can keep thousands of them in a bottle and they are cheap to feed.”
It is in that spirit that AI researchers have invested so much time and effort in computer chess – though I fear they’re out over their skies when they claim, as some have done, that chess is the apex of human intelligence and thus, when we’ve beaten chess, we’ll have human intelligence licked – and it is in that spirit that I am taking it up in this series of notes:
- AI, Chess, and Language 1: Two VERY Different Beasts
- AI, Chess, and Language 2: Further remarks [SPSH]
I don’t understand chess well enough to follow McCarthy’s article, which is based on four examples, but I note that the first example involves search. That’s what I want to think about.
Searching is one of the fundamental tasks of practical computer programming and the study of search is fundamental to computer science. Chess is readily understood as a process of search through a large, but well-defined, space for good moves. In fact, when considered abstractly the chess space is like the tic-tac-toe space, but much larger.
Each game is played on a board of finite size; each game is played with a finite number of pieces; and the number of moves available at each point in play is finite. Tic-tac-toe ends either when one player has three counters in a row or all the board spaces are filled. Chess ends either when one player has been check-mated or when no pieces have been exchanged after a pre-specified number of turns. In both cases the game space takes the form of a tree, where the root is the game state before any move has been made and the leaves are game states where either one player has won or there is a draw.
In both cases the tree is finite. In the case of tic-tac-toe the game tree is relatively small and writing a program to play tic-tac-toe is easy enough that it can be included as an example in a first course in computer programming – I wrote such a program years ago when I was an undergraduate at Johns Hopkins. In the case of chess the tree is huge, much too large to construct even with the largest computer.
While it is thus impossible to draw a diagram of the complete tree, I’m a visual thinker and I like diagrams. In this case I think a diagram is helpful in making that point that we ARE talking about a space, even if it is impossibly large. So, consider this diagram:
 |
| Chess Tree |
The first player, White by convention, has 20 possible moves, one of two possible moves for each one of eight pawns and one of two possible moves for one of two knights. Thus there are 20 branches off of the root of the tree. Black has twenty possible moves in reply, for a total of 400 branches. Depending on White’s first move, it will have 20 or more possibilities for its second move, and so forth. The chess tree branches out very quickly.
A little reflection should make it clear that the chess tree, though very very large, very large indeed, it is (merely) finite. It is so very large that its finitude, unlike that of tic-tac-toe, has no practical value. The size of the chess tree is an example of combinatorial explosion, a concept we will consider again. for now, let us move on.
Consequently, chess has obsessed intelligent players for centuries and computer scientists for decades. Finding winning paths turns out to be a very difficult problem. Just how researchers have approached that problem is no doubt interesting, but not to me in the context of this essay. What interests me is the simple fact that we can conceptualize chess as a game involving the exploration of a well-defined mathematical object, a tree, whose properties are well understood, is difficult.
Chess in history and in life
Now, chess wasn’t invented in a day. It evolved over three millennia from roughly 1500 BC to 1500 AD, when it reached its present form. We can think of the game’s evolution since then as one of exploring the chess tree and accumulating knowledge about its properties. To become an expert chess player, not only must you play many games, you must also study the history of the game so that you can acquire some of that accumulated knowledge.
If you don’t mind, I want to go through that again, but a bit differently. It’s important. The chess tree is a real object, as real as that tree outside your window, but abstractly real, not concrete. Just as a child can explore a tree by climbing it, a chess player explores the chess tree by playing the game (and studying games played by others). People have been exploring the physical world ever since we parted ways with our primate ancestors; but it’s only in the last couple of thousand years that we’ve been able to think of the earth as a sphere. Similarly, it wasn’t until the mid-20th century that people began thinking of chess-world as being a finite, but very large, tree. You don’t need to have that conception explicitly in mind in order to explore multiple paths of game-state evolution from the current game state. The fundamental point is that the chess tree is a real object.
Does the ontogeny of AlphaZero chess-play recapitulate the phylogeny of human chess?
It's an idea in terms of which one can understand concepts, chess concepts. To explore the chess tree is to explore the world of chess concepts. A bit later I want to generalize this approach to think of ideas, any kind of ideas, as existing in some abstract space. Thus when working with those ideas, we’re exploring some space. But let’s get back to chess.
Traditionally, one builds a chess engine by painstakingly encoding chess concepts into a program by using traditional programming concepts. Roughly speaking we have two kinds of concepts:
- Search: how do you search through the chess tree? and
- Evaluation: how do you determine the value of a given position?
Those routines are programmed in consultation with chess experts. The program that beat Gary Kasparov, IBM’s Deep Blue, was programmed in that way. Until recently, Stockfish, one of the top-rated chess engines, was programmed in that way. You program the engine, put it into matches, and see how it plays. From time to time you update the engine.
Things changed in 2017 when Deep Mind released a paper, AlphaZero, an artificial neural network trained to play Go, Shogi, and Chess:
AlphaZero was trained solely via self-play using 5,000 first-generation TPUs [tensor processing units] to generate the games and 64 second-generation TPUs to train the neural networks, all in parallel, with no access to opening books or endgame tables. After four hours of training, DeepMind estimated AlphaZero was playing chess at a higher Elo rating than Stockfish 8; after nine hours of training, the algorithm defeated Stockfish 8 in a time-controlled 100-game tournament (28 wins, 0 losses, and 72 draws). The trained algorithm played on a single machine with four TPUs.
AlphaZero had learned to play chess simply by playing chess, game after game after lots of games. No humans supplied it with hand-coded routines for evaluating play.
Later, in 2021, researchers at DeepMind and Google Brain, along with Vladimir Kramnik (World Chess Champion, 2000-2007) published a paper, Acquisition of Chess Knowledge in AlphaZero. One of the things they investigated: “When looking at the evolution of chess understanding within a system like AlphaZero, one has to wonder whether there is such a thing as a natural progression of knowledge, a way of developing an understanding of the game that is specific to the game itself, rather than being purely arbitrary and left to chance – or is it a mix of both?” The latter turns out to have been the case.
Answer: Not quite.
For my present purposes, the details are irrelevant. What’s important is simply that the comparison could be made at all. That possibility depends on conceptualizing chess as a game that’s played in a space that takes the form of a tree. In the human history of the game, humans have explored that tree and left records of that exploration. Now we have a computer system that explores that tree without benefit of priming by humans. How one plays the game is constrained by the rules of chess, but how one explores the possibilities inherent in those rules, that is not dictated by those rules. Rather, it is a product of “discoveries” made in the process of games play. That there are similarities between the history of chess and AlphaZero’s learning history tells us that that process is not an arbitrary one, is not completely captured by local contingency after contingency. That there are differences, however, that there is some free-play in how things unfold.
If you know a bit of intellectual history, you may have recognized that I’ve just run a variation on an idea associated with Ernst Haeckel in the late 19th century who gave it a succinct formulation, “ontogeny recapitulates phylogeny,” meaning “that an individual organism's biological development, or ontogeny, parallels and summarises its species' evolutionary development, or phylogeny.” In the present context, one might paraphrase Haeckel’s formulation as: the ontogeny of AlphaZero chess-play recapitulates the phylogeny of human chess. It turns out that Haeckel’s formulation is not quite true in the biological case. Nor, it would seem, is my revision true of chess. Still, the parallel is not without interest.
[Note: Fans of Johns Barth may recall that he ran his own variations on Haeckel in Giles Goat-Boy: “ontogeny recapitulates cosmogeny” and "proctoscopy repeats hagiography.”]
Generalizing wildly, what, if anything, does that tell us about human cultural evolution over historical time? If the evolution of something as austere and tightly structured as chess has room for both determinism and free-play, what about something as luxuriant and open-ended as human life on earth?
But I’m getting ahead of myself. Let’s turn our attention to language.
Bonus: An exercise for the reader
In my penultimate paragraph I suggested an analogy between human cultural evolution and the historical evolution games-play in chess. Chess is a game played by human beings. In what way is cultural evolution also a game played by human beings, Homo ludens, it you will?
No comments:
Post a Comment