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×1020 nodes, after eliminating all symmetries. For Go, the exact size of the tree is unknown - but it's greater than 10100!
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.