Game Trees

Back in high school (not that many years ago, I'd like to think), I was in a programming competition that pitted a program I wrote to play a 2-player game against those of all of my classmates in a single-elimination tournament. I made it to the finals and eventually won, though after discussion with the other finalist we both realized that based on our PASCAL code (ok, that many years ago) the winner would have been the program that went first. More importantly, both of us wrote very shortsighted code; that is, we set up a series of rules like "look for a winning move first" and "look for a block second". It was only a matter of time before I learned the more traditional computer science approach to creating algorithms for 2-player games: game trees.

A game tree is a symbolic representation of all the possible outcomes of a game where nodes are the "states" of the game at a given time and the connecting arrows are the possible "moves" (called "plys" in game theory). Think of it as an inverted tree where the root node represents the start of the game and all its branches representing a player's first turn.


The common example for explaining game trees is the well-known game of tic-tac-toe. Player 1 starts out with a blank grid and 9 possible squares to click in. After a spot is chosen (and an "X" is placed), there are 8 other squares from which player 2 can choose (and place an "O"), which then leaves 7 squares for Player 1, and then 6 for Player 2, and so on. You can guess that even a game as simple as tic-tac-toe, guaranteed to be over in 9 moves, can have a pretty large number of possible ways it can be played. At first glance you may even calculate the number of nodes in the game tree to be 9! (362,880), though luckily there are several factors we can use to trim this number down (to 26,830 nodes, in fact).

The first way to trim a game tree is to consider all of the branches that never make it to ply number 9 because the game has already finished. For example, imagine Player 1 winning with 3 spots still on the grid (however unlikely, it's still possible); the last 3 plys for that branch never need to be calculated. Another important way to "prune" the trees is to recognize any kind of symmetry (rotation, reflection) across branches and represent each by one and only one branch. For example, if Player 1's first move is to a corner, any corner, our game tree only needs to have one branch as each of the other 3 nodes where Player 1's first move is a corner can be rotated to look like the first. The same is true of Player 1's first move if to a side spot. Add in the branch that stems from Player 1's first move to the center spot and you now have 3 branches coming out of the root node, not 9...now that's some good and efficient pruning.

In the project below, I've recreated the commonly seen 2-ply game tree for a tic-tac-toe game. Playing with this visual and interactive model may give you a better understanding of how game trees are constructed. The sitemap of the workBench project is what the (beginning of the) game tree would look like. Look at the number of branches each node spawns and see if you can figure out why none of the 2nd-tier nodes spawn 8 branches. Also, there are lots of other, more sophisticated ways of pruning game trees if you are interested, but they are beyond the scope of this post.



So why are game trees important anyway? Why would knowing about them have changed how I made that program all those years ago? The answer is simple: if you can make a model of all possible outcomes, you can choose the path that helps you the most. In a 2-player game tree, this can be done in a variety of ways, though an easy example is to "rate" each node, started from the end of each branch, or leaf nodes. If a node gives Player 1 a win, assign a rating of 1 to that node. If it gives Player 2 a win, rate it -1, and if it is a tie, rate it 0 (this is how I was taught, though you can use any rating system you'd like, such as colors or shapes). Once all of the leaf nodes have been rated, the nodes in the ply above them can be rated as well, all the way up to the top using the following rules:

1. For each node X on ply Z, look at the parent node Y one level up on ply (Z-1).
2. If all of node Y's children are rated the same way, give node Y that rating.
3. If any of node Y's children are rated as a win for the player whose turn is on ply Z, rate node Y a win for that player.
4. If neither condition applies, rate node Y a tie.

This may seem hard to understand, but in a nutshell all it means is that if you have to choose between a bunch of moves, all of which have ratings already, you don't want to choose one that has at least one outcome where your opponent wins, assuming your opponent will see that opportunity and take it (that's the crux of step 3).

If you are an educator and involved in anything that revolves around game theory, recursion in programming, or even symmetry in high school Geometry, constructing (or filling in already started) game trees for simple 2 player games may be a fun and productive activity.

It may even be the key to you winning a programming tournament in your high school computer class...