I don’t play chess – as cerebral as the game is supposed to be, it somehow never really appealed to me, perhaps because the level of abstraction in chess was to high for my tastes. Sure there are kings and knights and such locked in mortal combat. But, I’ve always reasoned, at its heart, Chess is really a math problem. The kings and queens and knights and bishops are just trappings. You could call those pieces anything you want, and the math works out the same. In theory, chess can be solved.
And I never really found that particularly inspiring.
Well, now I’ve started a new semester, and one class – called “Strategic Decision Analysis” – has really caught my interest. Considering that one of the primary topics of study in the class is Game Theory, I suppose that comes as no surprise.
Game Theory, as the term is intended to be applied, is meant to be a study of the competitive actions taken by two or more “players” whose interactions are, well, interactive, such that the actions of one player affect the decisions and actions of another, each trying to get to some desired outcome or result. Wow, that’s a lot of words… but what it boils down to is: game theory isn’t about games like you or I know them, it’s about nations, corporations, and individuals struggling to get what they want in a world where other people are trying to get what they want. In MBA school we study it for its effect on business.
But even so, the concepts of Game Theory can be applied, no surprise here, to actual games. You know, the ones you play for fun.
And that includes Chess – a game, incidentally, which I typically don’t play for fun – vis-à-vis the aforementioned distaste for the math of it all – but about which I am fascinated nonetheless.
In class this week, we began looking at an application of Decision Trees in “Sequential Games”. Sequential Games, boiled down really simply, are games where one player takes a turn then another player takes a turn. (That’s not really the definition – it’s a lot more complicated than that, and turns don’t necessarily instantly pass to other players, etc. – but it’s close enough for our purposes here. ) Chess, obviously, is a great example of a Sequential Game. As the class went, I began imagining the Decision Tree for a game of Chess. This, I realized, is how you solve Chess.
What does a Decision Tree for a Sequential Game look like? Well, you have but to ask, and Wikipedia doth provide:
A Decision Tree for a Simple "Battle of the Sexes/Bullfight" Game
In this “game”, a husband and a wife are trying to decide where to go for the evening. They are both away from each other with no means to communicate, so each will drive to one of the events – either a “Bullfight” or an “Opera”, separately, and simply expect the other to be there. (In reality, as presented in the description on Wikipedia, this game would be a Simultaneous Game, not a Sequential One, but since we’ve got this handy tree, we’ll treat it as Sequential.) Each has a decision. The Wife knows the husband prefers the Bullfight and the Husband knows the Wife prefers the Opera. How much they enjoy their evening depends on where they end up – indicated by the scores on the right hand side of the tree (higher scores are better). So, for example, if the Wife decides to go to the Opera, the Husband, to maximize his score, ought also to go to the Opera – even though he would prefer the Bullfight, we prefers time with his Wife even more. Likewise if the Wife decides to go to the Bullfight, the Husband ought happily to go as well. If he ends up at the Opera instead, both Husband and Wife will be at their least-favorite destination alone, and both lose.
That’s a rather simple game. There are only two moves, one to each player.
So, what would the Decision Tree for Chess look like, I wondered? I began to imagine.
It turns out, there are about twenty possible opening moves in Chess. White goes first, and can move any of 8 pawns (each with two possible moves) or 2 Knights (each also with two possible moves). So, where you see the Wife’s first move in that tree above, the gray box labeled “a”, imagine that with twenty lines coming out of it. In response, the Black player has another twenty possible moves. So those twenty lines go to twenty decision boxes for Black’s move. Each of those twenty boxes has twenty lines coming out as well.
And so it goes. Back and forth. The math gets pretty complex pretty quickly – some moves, once taken, invalidate the possibility for other moves. Other moves, like crossing the board with your Pawn, open up a whole new universe of possible moves. In fact, my professor postulated this week, there are more possible combinations of moves in Chess than there are stars in the universe.
Yes, Chess is a math problem, and it can be solved. In theory. But in practice, you would need a super-computer the size of the entire universe to do it.
So, how is it that Chess Champions do what they do? How is it that Deep Blue – a super computer not the size of the Universe – beat Chess Champ Garry Kasparov?
Well, they’re not solving the whole tree. Not even Deep Blue. Instead, man and computer both have typically developed heuristic models of the game – they memorize positions and relate them to other positions in the game, either favorable or unfavorable, and try to maneuver the pieces to their advantage. Even Deep Blue, which was capable of brute-force calculating the game to a farther degree than any other computer, couldn’t solve for the entire game – it lost to Kasparov in several bouts.
So, why has this exploration fascinated me that I’ve written such a long blog post about it? Honestly, it’s hard to pin down. In some way, a part of me wants to like Chess – but even knowing that as a practical matter Chess can’t really be solves like an equation does little to lessen my distaste for actually playing the game. And neither does getting beaten at it, over and over, by my laptop (Deep Blue it is not). In other ways, though, I guess I see Chess as analogous to the history of all games, and in another way, as analogous to the history of the Fantasy genre. Chess was once the Kingly game. Is there not certain to be such a game that is common and popular in a fantasy world not only of Kings and Knights but also of Wizards and Dragons?