Chinook and the Fossilization of Play
In the Summer of 2007 a team of computer scientists at the University of Alberta announced that they had “weakly solved” the game of checkers (aka English draughts). Their computer program, called Chinook, had reached the point at which it was demonstrably unbeatable at the game. If you are particularly bloody minded you can play against Chinook online. The solution took 18 years of number-crunching by banks of computers (sometimes as many as 200 at once) running around the clock. Their achievement was widely heralded as a great triumph for artificial intelligence research.
At first blush the whole endeavour seems like a complete waste of time and energy. The team used a “brute force” approach to the problem: essentially, they went through every potentially good combination of moves, one-by-one, recording the outcomes in a huge database. By consulting this database, Chinook can always steer clear of those moves that result in it losing.
Chinook got me thinking about what it means to master a game. Most competitive strategy gamers would consider solving a game to be the apotheosis of skill and prowess, and yet most would also agree that solving a game ruins play. For example, most people (well, most nerds) solve Tic-Tac-Toe at a fairly young age. When I first discovered the perfect moves at Tic-Tac-Toe I was thrilled—I was suddenly invincible—but when my excitement wore off I discovered that the game had become insufferably dull. Mastery of the game had broken the game. I could no longer really play it at all. I found myself just going through the motions. It had been the process of discovering better and better strategies that constituted play, not the strategies themselves. It was the tension caused by wanting to win, but being uncertain if I would. I soon abandoned Tic-Tac-Toe in favour of more complex games.
Here we have something of a paradox. The desire for mastery is an important part of playing a game and yet attaining mastery ruins play. Having that summit to climb towards is important, but it is the climb itself that is primary. Play is a utopian process of striving towards an unreachable goal. To put it another way, games are things that can be used up.
Mastery of the game had broken the game.
Even before Chinook came along, human players were, arguably, too good at checkers. Players were so close to mastering the game that a huge percentage of high-level checkers games ended in ties. To solve this problem many tournaments will randomize the first three moves of the game in order to force players into unfamiliar positions. This makes it impossible to fall back on memorized sequences of moves and forces players to deal with new situations, inventing strategies on-the-fly. To put it another way, too much knowledge fossilizes play and the injection of some randomness brings it back to life.
Something similar is apparent in chess. Centuries of analysis have served to boil the early portion of the game down to a fairly limited set of standard “textbook” opening sequences known to produce good midgame positions. Learning these sequences will give a player a large advantage against an opponent who does not know the corresponding defensive moves and almost all serious chess players have studied them. Using these openings, the early portion of the game can be played almost by rote. The real play doesn’t start until the midgame, once the memorized sequences have run their course.
World Chess Champion Bobby Fischer considered this kind of rote memorization antithetical to the spirit of the game and invented a version of chess in which the back rows of pieces are positioned randomly. This variation forces players into new and unfamiliar positions from the start and makes their memorized textbook openings useless. Again, when too-much-knowledge fossilizes play, a bit of randomness reanimates it.
A computer, made out of Tinkertoy, that can play Tic-Tac-Toe perfectly
Play always exists at the horizon of understanding, a point between incomprehension and mastery at which the player’s ability to predict the outcome of her actions begins to founder. To play is to confront the unknown or unpredictable. In order to facilitate play, therefore, the structure of a game must contain an element of autonomy and extend beyond the limits of the player’s mastery, or contain mechanisms for disrupting or thwarting the player’s intentions. Complexity is one mechanism of this kind; randomness is another.
Poor old Chinook has used up the entire structure of Checkers. It can no longer play it, just go through the motions. So how can we reanimate Checkers for Chinook? Well, one way is to add complexity to the game. International Draughts is played on a 10X10 board instead of the 8X8 used in English Draughts. According to Wikipedia this increases the game-tree complexity of checkers from 1031 to 1054. Quite a jump. Canadian Draughts is (allegedly—I’ve never seen a set) played on a 12X12 board, and therefore even more complex.
Play always exists at the horizon of understanding, a point between incomprehension and mastery at which the player’s ability to predict the outcome of her actions begins to founder.
We could also add randomness. Because Chinook excluded a priori certain suboptimal moves from its databases, there are certain opening sequences it does not know how to deal with. In a normal game, Chinook would simply never get into these situations. Chinook’s solution to checkers, therefore, does not apply to the aforementioned variant in which the first three moves of the game are randomized. In such a game Chinook might just find itself in an unfamiliar situation and have to once again strategize on-the-fly instead of relying on its databases. Being forced into such a situation might just put some of the joy back into the game (that is, if Chinook were a conscious being capable of feeling joy and not just a bunch of numbers).
It is perhaps best to think of the quest undertaken by certain computer scientists to solve games as something of a game in itself, or a meta-game. The actual finished product, a program that can never lose at checkers, is nothing special, but the process of creating such a program is valuable in itself: it takes skill and ingenuity and experimentation and exploration of the unknown. Success with Chinook was far from certain, but there was a clear goal to work towards. The only flaw in the project was that it succeeded. Play is a process that has to be sustained, and it can only be sustained as long as there is new ground to tread. With English draughts the end of the road has been reached. Fortunately there are much more complex games still awaiting a solution. Go, for instance, has a game-tree complexity of 10360.
It is unlikely that computer scientists will run out of summits any time soon.
What’s interesting is that human game playing ability doesn’t seem to be limited by game tree complexity. For example, if you take a human master of English Draughts and you move her to Canadian Draughts, I imagine she would still be pretty good. Not as good as a master of Canadian Draughs, but better than novice and intermediate players. On the other hand if you stick a brute-force computer AI like Chinook on Canadian Draughts, it would fall back to novice play.
This shows a major flaw in the whole idea that solving a game with brute-force methods amounts to intelligence or mastery of the game. Human game-playing skill (and perhaps human intelligence more generally) is characterized by an ability to fluidly apply understanding from one problem space to other related problem space. What we learn in one domain is never entirely irrelevant to our abilities in other domains. I’m not saying it’s impossible to make an AI system with this kind of skillful mastery, but it will never happen with the kinds of methods used by the U of A researchers.
Play more Go. Problem solved (new problems introduced).