Moving on from simple zero-sum games, there are a bunch of directions in which

we can go. So far, the games we’ve looked at are very restrictive. Beyond the

zero-sum property, they’re built on a set of fundamental properties which ultimately

reduce to the idea that no player ever has an information advantage over any other

player: the complete payoff matrix is known by all players; no player gets

to see the other players strategy before selecting their own; and so on.

Moving on to more interesting games, we can relax those assumptions, and allow information to be hidden. Perhaps each player can see a different part of the

payoff matrix. Perhaps they take turns, so that one player gets to see the others

strategy before selecting his own. Perhaps the game isn’t zero-sum.

Non-zero sum games turn out to be disappointing from a game theory point of

view. Given a suitable set of restrictions, you can convert a non-zero-sum game to a

zero-sum game with an additional player. In the cases where you can’t do that,

you’re pretty much stuck – the mathematical tools that work well for analyzing

zero-sum games often simply don’t work once you relax the zero-sum requirement.

The more interesting ways of exploring different realms of games comes when you

allow things to get more complex. This comes about when you allow a players strategy

selection to *alter the game*. This general takes place in a turn-taking

game, where each players strategy selection alters the game for the other player. A

simple example of this is the game of tic-tac-toe. The set of strategies of the game

for a given player at any point in time is the set of open squares on the board.

Each time a player makes a move, the game is altered for the other player.

This makes things much more interesting. The easiest way to think of it is

that now, instead of a simple matrix for the game, we end up with a tree. Each move

that a player can make creates a new game for the other player. By making each game position a tree node, and adding children nodes for each position that can follow it, you can build a tree describing the complete set of possible game positions, and thus the complete set of ways that the game could play out.

As usual, it’s easiest to see this with an example. At the top of this post is the game tree for tic-tac-toe, assuming that “X” goes first.

There are really three moves that X can make initially – she can play a corner,

a center-edge, or the center. Which corner or edge she chooses is irrelevant – on an empty tic-tac-toe game-board, due to symmetries, the corners/edges are equivalent. If X plays the center, then the other player can choose either an edge or a corner. If X plays an edge, the O player can play a corner adjacent to X’s move; a corner not adjacent; an adjacent edge; the opposite edge; or the center. And so on.

How can you solve a game like this?

Ultimately, it comes down to utility functions. You can build up a utility

function describing the values of each possible move. This requires some of what I

talked about in my last post with lotteries: most moves produce not a specific

result (win or lose), but a new game. So to compute the utility value of a

particular strategy, you need to combine the utility values of the potential

subsequent strategies resulting from that move.

Computing the utilities in tic-tac-toe is easy: the utility of any move is the

probability of your winning the game if you make that move. You determine that by

analyzing the possible moves available to you. First, you can prune the tree: any

strategy that doesn’t include a potential path for you to win, you can just

eliminate from consideration: it has a utility of 0. For other moves, you look at

the potential paths: if move A leads into a subtree where 72% of the paths lead to a

leaf in which you win, then the utility of A is 0.72. Each turn, the best

strategy is the one with the highest utility; moves with equal utility are

equivalent.

The problem with this approach is that game trees grow incredibly quickly. Even with all symmetries eliminated, the game tree for tic-tac-toe has approximately 25,000 nodes! That means that for a human, the complete game tree isn’t really understandable, even for a trivial game like tic-tac-toe. When

you start looking at more interesting games, you get some really astonishingly large game trees. Checkers has a game tree with around 5×10^{20} nodes, after eliminating all symmetries. For Go, the exact size of the tree is unknown – but it’s greater than 10^{100}!

Obviously, we can’t compute the whole game tree for games like that. And without the full tree, we can’t calculate precise utility for every possible move. So we

to compute *approximate* utilities. We can compute approximate utility

values using a variety of techniques, including heuristics, prunings, board valuations, and partial trees.

Heuristics is the use of what you could call intelligent guesses. There

are moves or positions on most games that are usually sensible. In a game of checkers, if you have an opportunity to either jump and capture one opponents

piece, or double-jump and capture two, it’s generally smarter to capture two. Not

always – there are cases where the single jump (and subsequent sacrifice of one of your pieces) is the best move. But *most of the time*, the double-capture is

preferable. In the absence of any other information, you’d assign a higher

estimated utility to the double-jump. Heuristics also covers some things

based on your knowledge of the other player. People who’ve played chess with me know that I tend to over-use my queen and under-use my knights; if you use that

knowledge, you can make intelligent guesses that certain paths in the tree

are more likely than others, and use that to weight the likely paths higher

in your utility computation.

Prunings can be thought of as a sort of heuristic. The idea is that

if you look at the game tree, there are some parts of the tree that lead

into undesirable situations – that is, situations where your probability of

winning is reduced. If it appears that a particular subtree of the game

isn’t likely to work out well for you, you just eliminate that entire

subtree. It’s possible that if you searched that subtree, that you might find

a path that would let you win. But the odds of finding a great winning strategy

are small enough that you just cut the subtree away, and don’t search it.

Board valuations are ways of looking at a given game situation, and assigning

it a value. In chess, a board where your opponent has his king in an unguarded position, you’ve got your queen out on the board where it’s not vulnerable and it’s available to move, and your king is in a castled defensive position is better

than the same position where you’re queen was captured, or where your king is undefended. You don’t need to look further into the game tree to make a strong guess which of those positions is preferable. This comes down to assigning a valuation

to a board position without looking further into the tree to compute that

valuation. It’s based solely on immediate, observable properties of the state

of the game when you make the valuation.

Board valuations are particularly important when combined with partial trees. The idea of a partial tree is that the full game tree is impossibly large. So you only consider a small part of it. This is very common in chess-playing programs. The

program computes a partial game tree: for example, it may compute 9 levels of the game tree from the current position, which covers the next 9 moves. The states at the leafs of that partial tree are computed by board valuations; the states at internal nodes are computed by combining the values of their children.

So where do we go from here in our exploration of game theory? There’s more

to be said about game trees. For example, for most two-player alternative move games, there’s a very particular structure that can efficiently represent the game tree, and provide opportunities for analysis and pruning, called an and-or tree. There are also a set of optimizations based on the fact that in a typical game tree, there are multiple ways that a given board position can be reached. We can compact the game tree into a graph by taking advantage of that.