Thursday, August 8, 2019

What about chess? What does it tell us about history? [path dependence]

The late John McCarthy is said to have remarked once that if geneticists treated drosophila like AI researchers have treated chess, we’d have a lot of very fast fruit flies, but not much knowledge of genetics. Until quite recently I was sympathetic to that remark, though I note that I haven’t followed AI research on chess at all closely. But thinking about the success of AlphaZero has brought me to reconsider.

As an aside, I note that while a played a bit of chess when I was young, I am not a player. I know the rules of the game, more or less, but I am not a chess player in any robust sense.

By playing against itself and updating its neural network as it learned from experience, AlphaZero discovered the principles of chess on its own and quickly became the best player ever. Not only could it have easily defeated all the strongest human masters — it didn’t even bother to try — it crushed Stockfish, the reigning computer world champion of chess. In a hundred-game match against a truly formidable engine, AlphaZero scored twenty-eight wins and seventy-two draws. It didn’t lose a single game.

Most unnerving was that AlphaZero seemed to express insight. It played like no computer ever has, intuitively and beautifully, with a romantic, attacking style. It played gambits and took risks. In some games it paralyzed Stockfish and toyed with it. While conducting its attack in Game 10, AlphaZero retreated its queen back into the corner of the board on its own side, far from Stockfish’s king, not normally where an attacking queen should be placed. [...]

Tellingly, AlphaZero won by thinking smarter, not faster; it examined only 60 thousand positions a second, compared to 60 million for Stockfish. It was wiser, knowing what to think about and what to ignore. By discovering the principles of chess on its own, AlphaZero developed a style of play that “reflects the truth” about the game rather than “the priorities and prejudices of programmers,” Mr. Kasparov wrote in a commentary accompanying the Science article.
We’ve got two things: 1) AlphaZero played a new style of chess that was insightful and interesting and 2) it developed this style initially by playing against itself and only against itself.

So what? Recall that from a purely abstract point of view, and given an appropriate rule for converting a stalemate into a draw, chess, like the much simpler tic-tac-toe, is a finite game. That is, there are only a finite number of games possible. So, in point of abstract theory, one could list all possible games in the tree and label each path according to how it ends (win, lose, or draw). Then to play you simply follow only paths that can lead to a win or, if forced, to a draw. However the number of possible games is so large that this is not a feasible way to play the game, not even for the largest and fastest of computers.

But this is the space in which chess is played and that’s what’s important. Humans have been playing in this space ever since they’ve played the game. Cumulative human knowledge of the game is therefore knowledge about the structure of this space.

AlphaZero’s success implies that there are significant and interesting regions in this space that human players had not yet explored. That is not, I suppose, so surprising. The chess space, after all, is huge. But let’s put our science fiction thinking caps on. Are there alternative universes in which human knowledge of chess evolved in a way significantly different from how it evolved in our universe? To what extent is our current human knowledge of the game a function of “accidents” that have happened in the history of the game? If, say, the first 100,000 games had been different from what they were, would our current knowledge be different than it is? All of which is to ask, to what extent is our knowledge of the game historically contingent such that our knowledge would have been different if that history had been different? And what does that tell us about the nature of historical process itself?

I believe economists call this path dependence.

Consider what happens in learning the game. You play it with others – though, if you are serious, you may ponder the game alone in your study. At some point you will be playing against opponents who know the game well, and who have studied the game by reading books about it, studied hundreds or more classic games, etc. That is, you will inevitably be drawn into the history of the game. There is no escape.

But that’s exactly what AlphaZero did. By learning the game through playing against itself, it escaped the human history of the game and found its way into a new region of the chess space. Not only is this a region that humans have not explored, but it plays a style that humans nonetheless recognize as displaying “insight”, whatever that is. Is insight one of those things you can’t really define, but recognize it when you see it?

I assume, however, that AlphaZero’s run into chess space is historically contingent in the same way that the human history of the game is. So, could AlphaZero take a different run into chess space and arrive at a (somewhat) different region? (Does that question even make sense?)

So, here we’ve got a very large but finite space whose base level structure is given by a handful of rules. Opponents explore that space by playing against one another and in that process delineate a higher level structure. What’s in that higher level structure that isn’t in he base level structure? Sure, we can and do call it strategy and tactics, but what are they about? Human intention under conflict? But AlphaZero isn’t human. Are there different levels of these higher level structures?

Meanwhile I’ve been reading about Freestyle chess in Tyler Cowen’s Average Is Over (2013). Freestyle chess is played by teams that include one or more humans and one or more computers (p. 78):
A series of Freestyle tournaments was held staring in 2005. In the first tournament, grandmasters played, but the winning trophy was taken by ZackS. In a final round, ZackS defeated Russian grandmaster Vladimir Dobrov and his very well rated (2,600+) colleague, who of course worked together with the programs. Who was ZackZ? Two guys from New Hampshire, Steven Cramton and Zackary Stephen, then rated at the relatively low levels of 1,685 and 1,395, respectively. Those ratings would not make them formidable local club players, much less regional champions. But they were the best when it came to aggregating the inputs from different computers. In addition to some formidable hardware, they used the chess software engines Fritz, Shredder, Junior, and Chess Tiger.
Cowen later notes (p. 81):
The top games of Freestyle chess probably are the greatest heights chess has reached, though who actually is to judge? The human-machine pair is better than any human – or any machine – can readily evaluate. No search engine will recognize the paired efforts as being the best available, because the paired strategies are deeper than what the machine alone can properly evaluate.
And that was before AlphaZero entered the picture.

In that book Cowen is interested in the future of work and, in particular, the future of human-machine collaboration. Hence the interest of Freestyle chess.

I’m interested in history, in cultural evolution, in the way an evolutionary process learns about the world by ‘converting’ accidents arising in interaction with the world into internal perceptual and cognitive structures and thereby increasing its effectiveness in dealing with the world. Chess is played in a large finite space constructed from a small handful of basic elements. Life and human history, what are the basic elements here, how large is the space of possibilities?

* * * * *

Part 2 HERE.


  1. I like you know how to play chess and have played but I in no way consider myself a chess player. I am still trying at time to learn to play better but I'm not sure that will happen despite all the new tools for learning.

    I was very fascinated by your look at the game and what is happening.