Generating and Solving Imperfect Information Games

1 Introduction

The idea of getting a computer to play a game has been around since the earliest days of computing. The fundamental idea is as follows : When it is the computer's turn to move, it creates some part of the game tree starting at the current position, evaluates the 'leaves' of this partial tree using a heuristic evaluation function , and then does a minimax search of this tree to determine the optimal move at the root. This same simple idea is still the core of most game-playing programs. This paradigm has been successfully applied to a large class of games, in particular chess, checkers, othello, backgammon, and go [Russell and Norvig, 1994, Ch. 5]. There have been far fewer successful programs that play games such as poker or bridge. We claim that this is not an accident. These games fall into two fundamentally different classes, and the techniques that apply to one do not usually apply to the other.

The essential difference lies in the information that is avail­ able to the players . In games such as chess or even backgam­ mon, the current state of the game is fully accessible to both

Avi Pfeffer

University of California Berkeley, CA 94720 ap@cs.berkeley.edu

players. The only uncertainty is about future moves. In games such as poker, the players have imperfect information: they have only partial knowledge about the current state of the game. This can result in complex chains of reasoning such as: "Since I have two aces showing, but she raised, then she is either bluffing or she has a good hand; but then if I raise a lot, she may realize that I have at least a third ace, so she might fold; so maybe I should underbid, but .... " It should be fairly obvious that the standard techniques are inadequate for solving such games: no variant of the minimax algorithm duplicates the type of complex reasoning we just described.

In game theory [von Neumann and Morgenstern, 1947], on the other hand, virtually all of the work has focused on games with imperfect information. Game theory is mostly intended to deal with games derived from "real life," and particularly from economic applications. In real life one rarely has perfect information. The insights developed by game theorists for such games also apply to the imperfect information games encountered in AI applications.

It is well-known in game theory that the notion of a strat­ egy is necessarily different for games with imperfect informa­ tion. In perfect information games, the optimal move for each player is clearly defined: at every stage there is a "right" move that is at least as good as any other move. But in imperfect information games, the situation is not as straightforward. In the simple game of "scissors-paper-stone," any deterministic strategy is a losing one as soon as it is revealed to the other players. Intuitively, in games where there is an information gap, it is usually to my advantage to keep my opponent in the dark. The only way to do that is by using randomized strategies. Once randomized strategies are allowed, the exis­ tence of "optimal strategies" in imperfect information games can be proved. In particular, this means that there exists an optimal randomized strategy for poker, in much the same way as there exists an optimal deterministic strategy for chess. Kuhn [1950] has shown for a simplified poker game that the optimal strategy does, indeed, use randomization.

The optimality of a strategy has two consequences: the player cannot do better than this strategy if playing against a good opponent, and furthermore the player does not do worse even if his strategy is revealed to his opponent, i.e., the opponent gains no advantage from figuring out the player's strategy. This last feature is particularly important in the context of game-playing programs, since they are vulnerable to this form of attack: sometimes the code is accessible, and in general, since they always play the same way, their strategy can be deduced by intensive testing. Given these important benefits of randomized strategies in imperfect information games, it is somewhat surprising that none of the AI papers that deal with these games (e.g., [Blair et al. , 1993; Gordon, 1993; Smith and Nau, 1993]) utilize such strategies.

In this work, we attempt to solve the computational problem associated with imperfect information games: Given a concise description of a game, compute optimal strategies for that game. Two issues in particular must be addressed. First, how do we specify imperfect information games? Describing the dynamics of the players' information states in a concise fashion is a nontrivial knowledge representation task. Second, given a game tree with the appropriate structure, how do we find optimal strategies for it?

We present an implemented system, called Gala, that ad­ dresses both these computational issues. Gala consists of four components. The first is a knowledge representation language that allows a clear and concise specification of imperfect in­ formation games. As our examples show, the description of a game in Gala is very similar to, and not much longer than, a natural language description of the rules of the game. The second component of the system generates game trees from a game description in the language. These game trees are aug­ mented with information sets, a standard concept from game theory that captures the information states of the players.

The third component of the system addresses the issue of finding good strategies for such games. Obviously, the stan­ dard minimax-type algorithms cannot produce randomized strategies. The game theoretic paradigm for solving games is based on taking the entire game tree, and transforming it into a matrix (called the normal or strategic form of the game). Various techniques, such as linear programming, can then be applied to this matrix in order to construct optimal strategies. Unfortunately, this matrix is typically exponential in the size of the game tree, making the entire approach impractical for most games.

In recent work, Koller, Megiddo, and von Stengel [1994] present an alternative approach to dealing with imperfect in­ formation games. They define a new representation, called the sequence form, whose size is linear in the size of the game tree. They show that many of the standard algorithms can be adapted to find optimal strategies using this representation. This results in exponentially faster algorithms for solving a large class of games. In particular, they present an effective polynomial time algorithm for solving two-player fully com­ petitive games (such as poker). We have implemented this algorithm as part of the Gala system, and tested it on large examples of several games. The results are encouraging, sug­ gesting that, in practice, the running time of the algorithm is a small polynomial in the size of the game tree.

The final component of Gala presents the optimal strategies in a way that is comprehensible to the user. For any decision point in the game, it tells the user which actions should be played with which probability. The system also provides other information, such as one player's beliefs about the state of another agent, or the expected value of a branch in the tree. This functionality makes Gala a useful tool for game­ theory researchers and educators, as well as for users who wish to use Gala as a game-theory based decision support system. Finally, Gala can also play the game according to the computed strategy, making it a basis for a computer gameplaying system for imperfect information games.

2 Some basic game theory

Game theory is the strategic analysis of interactive situations. Several aspects of a situation are modeled explicitly: the players involved, the alternative actions that can be taken by each player at various times, the dynamics of the situation, the information available to players, and the outcomes at the end. Given such a model, game theory provides the tools to formally analyze the strategic interaction and recommend 'rational' strategies to the players.

The standard representation of a game in computer science is a tree, in which each node is a possible state of the game, and each edge is an action available to a player that takes the game to a new state. At each node there is a single player whose turn it is to choose an action. The set of edges leading out of a node are the choices available to that player. The player may be chance or 'nature', in which case the edges represent random events. The leaves of the tree specify a payoff for each player. This representation is inadequate for games with imperfect information, because it does not specify the information states of the players. A player cannot distinguish between states of the game in which she has the same information. Thus, any decision taken by the player must be the same at all such nodes. To encode this constraint, the game tree is augmented with information sets. An information set contains a set of nodes that are indistinguishable to a player at the time she has to make a decision.

Figure 1 presents part of the game tree for a simplified variant of poker described by Kuhn [1950]. The game has two players and a deck containing the three cards 1, 2, and 3. Each player antes one dollar and is dealt one card. The figure shows the part of the game tree corresponding to the deals (2, 1), (2, 3), and (1, 3) . The game has three rounds. In the first round, the first player can either bet an additional dollar or pass. After hearing the first player's bet, the second player decides whether to bet or pass. If player 1 passes and player 2 bets, player 1 gets one more opportunity to decide whether or not to bet. If both bet or both pass, the player with the highest card takes the pot. If one player bets and the other passes, then the betting player wins one dollar. Let ( c, d) denote the hands dealt to the two players. Initially, player 1 only knows his own card, so for each possible c, he has one information set Uc containing two nodes; each node corresponds to the two possibilities for player 2's hand. In her turn, player 2 knows d as well as player 1 's action at the first round. Hence, she has two information sets for each d-VJ and Vj-corresponding to player 1 's previous action. Finally, player 1 has an information set u~ at the third round.

Given a game tree augmented with information sets, one can define the notion of strategy. A deterministic strategy, like a conditional plan in AI, is a very explicit "how-to-play manual" that tells the player what to do at every possible point in the game. In the poker example, such a manual for player 1 would contain an entry: "If I hold a 3, and I passed on the first round, and my opponent bets, then bet 1." In general , a deterministic strategy for player i specifies a move at each of her information sets. Since the player cannot distinguish between nodes in the same information set, the strategy cannot dictate different actions at those nodes.

Deterministic strategies are adequate for games with per­ fect information, where the players always know the current state of the game. In those games the information sets of both players are always single nodes, and a deterministic strategy s; for player i is a function from those nodes at which it is her turn to move to possible moves at that node. The fact that deterministic strategies suffice for such games is the basis for the standard minimax algorithm (and its variants) used for games such as chess. In such games, called zero-sum games, there are two players whose payoffs always sum to zero, so that one player wins precisely what the other loses. As shown by Zermelo [1913] , the strategies produced by the minimax algorithm are optimal in a very strong sense. Player i can­ not do better than to play the resulting strategy if the other player is rational. Furthermore, she can publicly announce her intention to do so without adversely affecting her pay­ offs. A generalized version of the minimax algorithm shows the existence of optimal deterministic strategies for general games of perfect information. The resulting strategy com­ bination (si ' ... ' sn) has the important property of being in equilibrium: for any i, player i cannot pick a better strategy than s; if the other players are all playing their strategy s j . This is a minimal property that we want of a "solution" to a game: Without it, we are drawn back into the web of second guessing that characterizes imperfect information games. (If she plays the "orthodox" strategy, then I should do X, but she will figure out that this is better for me, so she'll actually do Y, but then ... . )

It should be fairly obvious that deterministic strategies will in general not have these properties in games with imperfect information. Deterministic strategies are predictable, and pre­ dictable play gives the opponent information. The opponent can then find a strategy calculated to take advantage of this information, thereby making the original strategy suboptimal. Unpredictable play, on the other hand, maintains the informa­ tion gap. Therefore, players in imperfect information games should use randomized strategies.

Randomized strategies are a natural extension of determin­ istic strategies. Where a deterministic strategy chooses a move at each information set, a randomized strategy (formally called a behavior strategy) specifies a probability distribution over the moves at each information set. In our poker example, a randomized strategy PI for player 1 can be described by defining the probability of betting at each information set Uc and U~, c = 1, 2, 3. A combination of randomized strategies PI, ... , Pn, one for each player, induces a probability distri­ bution on the leaves of the tree, thereby allowing us to define the expected payoff h; (PI , .. . , Pn) for each player i.

In his Nobel-prize winning theorem, Nash showed that the use of randomized strategies allows us to duplicate the suc­ cessful behavior that we get from deterministic strategies in the perfect information case. In general games, there is al­ ways a combination PI, . . . , Pn of randomized strategies that is in equilibrium: for any i, and any strategy Pi,

That is, no player gains an advantage by diverging from the equilibrium solution, so long as the other players stick to it.

Just as in the case of perfect information games, the equi­ librium strategies are particularly compelling when the game is zero-sum. Then, as shown by von Neumann [von Neumann and Morgenstern, 1947], any equilibrium strategy is optimal against a rational player. More precisely, the equilibrium pairs PI, p2 are precisely those where PI is the strategy that maximizes max 11 ; min 11 ~ hi (p;, p~) and pz is the strategy that maximizes max11 ~ min 11 ; hz(p;, p~) (which, since hz = -hi, is precisely min 11 ~ max 11 ; hi (p; , p~)). Intuitively, PI is the optimal defensive strategy for player 1: it provides the best worst-case payoff. It is these strategies that we will be most concerned with finding.

3 Gala: a game description language

As we mentioned, the first component of Gala is a knowl­ edge representation language for describing games. This is a Prolog-based language, that uses the power of a declara­ tive representation to allow clear and concise specification of games. The idea of a declarative language to specify games was proposed by Pell [1992], who utilizes it to specify

game(blind_tic_tac_toe, [players : [a, b], objects: [grid_board: array('$size', '$size')]. params : [size], flow (take_turns(mark,unless (full) ,until(win))), mark: (choose('$player', (X, Y, Mark), (empty(X, Y) , member(Mark, [x, o]))), reveal ('$opponent', (X, Y)), place ((X, Y), Mark)), full : (\+(empty(_, _)) - > outcome(draw)), win : (straight_line(_, _, length = 3, contains(Mark)) -> outcome(wins('$player') ))]) .

symmetric chess-like games-a class of two-player perfect­ information board games. Our language is much more gen­ eral, and can be used to represent a very wide class of games, in particular: one-player, two-player and multi-player games; games where the outcomes are arbitrary payoffs; and games with either perfect or imperfect information. As we will show, the expressive power of Gala allows for clear and con­ cise game descriptions, that are generally of similar length to natural language representations of the rules of the game.

To illustrate some of the features of Gala, Figure 2 presents an example of a complete description for "blind tic-tac-toe," an imperfect information version of standard tic-tac-toe. The players take turns placing marks in squares, but in his turn a player can choose to mark either an x or an o; he reveals to his opponent the square in which he makes the mark, but not the type of mark used. As usual, the goal is to complete a line of three squares with the same mark.

A game description in Gala is a list of features, each one describing some aspect of the game. For example, players : [a, bl indicates that the game is to be played between two players named 'a' and 'b'.

The Gala language has several layers: the lower ones pro­ vide basic primitives, while the higher layers use those primi­ tives to provide more complex functionality. The lowest layer provides the fundamental primitives for defining the structure Of a game. The choose(Player, Move , Cons traint) primitive describes the possible moves available to player at a given point in the game. It allows Player to make any move Move satisfying constraint. This last argument can be an arbitrary segment of Prolog code. In our example, Move consists of a square, specified by its coordinates x and Y, and a mark Mark; constraint requires that the square be empty and that Mark be either x or o. The first argument to choose can also be nature, in which case one of a number of events is chosen at random. By default, these random events have uniform probability, but a different probability distribution may be specified. The outcome primitive describes the outcome of the game at the end of a particular sequence of moves. This will often be a list of payoffs, one for each player; but, as the example demon­ strates, Gala allows other possibilities. The reveal(Player, Fact> primitive describes the dynamics of the players' infor­ mation states. It adds Fact to Player's information state. The information added can be simple or an arbitrary Prolog ex­ pression. In blind tic-tac-toe, a player chooses both a square and a mark but reveals to his opponent only the mark.

At a somewhat higher level, the flow feature describes the course of the game. The game can be divided into phases: some may take place just once, while others can be repeated until a goal is reached. In blind tic-tac-toe, for example, the players take turns executing the sequence of actions specified in the mark feature, until the condition specified in the full or the win feature is satisfied. The unless condition is tested before the turn. Gala also allows gameflow to be nested recursively. Each phase can be described by its own series of features, which may include flow. The flow of bridge, for example, can be described as follows:

flow : (play_phase(bidding), play_phase(take_tricks)) , phase(bidding, [flow : (take_turns(bid, until(contract_reached) )) , phase(take_tricks, [flow : (play_rounds (trick, 13) , . . .

In order to allow a natural specification of the game, Gala provides a separate representation for the game state, where relevant information about the current state of the game is stored. In blind tic-tac-toe, the game state contains the current board position. This information is accessed, for example, by choose in order to determine which moves are possible: only those squares that are empty are legal moves. The game state is maintained by modifying it appropriately, e.g., by the place operation, when the players make their moves. Much of the functionality in the higher levels of the Gala language is devoted to accessing and manipulating the game state.

The intermediate levels of Gala provide a shorthand for concepts that occur ubiquitously in games. These include lo­ cations and their contents, pieces and their movement patterns, and resources that change hands, such as money. In blind tic­ tac-toe, the statements that deal with the contents of squares are an instance oflocations and their contents. Other examples of functionality supported by this level are move (queen (white) , (d,1), (d,8)) andpay(gambler, pot, Bet).

On a more abstract level, we have observed that certain structures and combinations appear in virtually all games. While these are usually sets of one sort or another, they come in many flavors. For example, a flush in poker is a set of five cards sharing a common property; a straight, on the other hand, is a sequence of cards in which successive elements bear a relation to one another; a full house is a partition into equivalence classes based on rank in which the classes are of a specific size. A word in Scrabble and a 21 in Blackjack are another type of combination: a collection of objects bear­ ing no particular relationship to each other but forming an interesting group in totality.

The Pro log language provides a few predicates that describe sets and subsets. We have supplemented these with various predicates that make it easy to describe many of the combi­ nations occuring in games. For example, chain(Predicate, set> determines whether set is a sequence in which succes­ sive elements are related by Predicate; partition(Relation, set , classes) partitions set into equivalence Classes based on Relation. For a more elaborate example, consider the fol­ lowing code, which concisely tests for all types of poker hand except flushes and straights.

detailed_partition(match_rank, Hand, Classes, Ranks, Sizes),

associate(Sizes, Type, [([4 , 11. four_of_a_kind), ([3, 21. full_house) , ([3, 1, 11. three_of_a_kind) , ([2, 2, 11. two_pai rs), ( [2, 1, 1, 1], one_pair), ( [1, 1, 1, 1, 1], nothing)])

The predicate detailed_partition takes two inputs, a set­ in this case Hand-and an equivalence relation-in this case match_rank, which relates two cards if they have the same rank. It partitions the set into equivalence classes, and pro­ duces three outputs: a list classes of the equivalence classes in decreasing order of size; a corresponding list of the defin­ ing property of the equivalence classes, in this case the Ranks present in the hand; and a list si zes of the sizes of the dif­ ferent classes. In this example, if Hand is [90, 6·, 9·, 60, 60J,thenclasseswouldberr6· . 60, 60] , [90, 9·JJ,Ranks would be [6, 9], and sizes would be [3, 2]. In poker, sizes contains the relevant structure of the hand, and it is used to classify the hand using an association list. The above hand, for example, is immediately classified as a full house.

The high level modules of Gala build on the intermediate levels to provide more specific functionality that is common to a certain cla~s of games, such as boards that form a grid, playmg cards, d.Jce, and so on. In the blind tic-tac-toe example, we d.eclare a ~nd-board object. This makes a whole range of predicates avmlable that depend on the board being rectilinear. ~e st raight-line predicate is an example; it tests for a straight ~me of thre.e squares containing the same mark. This predicate IS defined In terms of chain. In general, high-level predicates are typically very easy to define in terms of the intermediate level concepts, so that adding a module for a new class of games requires little effort.

A useful feature of Gala is that it allows some parameters of the game to be left unspecified in the game description and provided when the game is played. In blind tic-tac-toe the board size is such a parameter. This makes it very ea;y to encode a large class of games in a single program. These parameters can actually be code-containing features. Thus, it is possible to provide the movement patterns of pieces in a game at runtime. This allows a simple interface between Gala and Pell's Metagame program [Pell , 1992], which generates symmetric chess-like games randomly.

Given a description of a game in the Gala language, Gala generates the corresponding game tree with information sets as described in Section 2. The tree is defined by the choose, reveal and outcome primitives. The Gala interpreter "plays" the game and constructs the game tree as it encounters these ?perations. When it encounters a choose primitive, a node IS ~dded to the tree, and an edge is added for every option avrulable to the player. The interpreter then explores each branch of the tree corresponding to each of the options. If the first argument to choose is a player, the system also adds the node to the appropriate information set of that player: the one that contains all the nodes where the player has the same information state. The information state consists of all facts revealed to the player by the reveal primitive, the list of choices available to the player, and all decisions previously taken by the player. If the first argument to choose is random, then the node is marked as a chance node, and the probability of each random choice is recorded. When the interpreter encounters the outcome primitive, it adds a leaf to the tree and backtracks to explore other branches.

4 Solving imperfect information games

How do we find equilibrium strategies in imperfect informa­ tion games? This is, in general , a very difficult problem. ~onsider the poker example from Section 2. There, we spec­ Ified a strategy for each of the players using six numbers. When trying to solve a game, we need to .find an appropriate set of numbers that satisfies the properties we want. That is, we want to treat the parameters of the strategy as variables, and solve for them. The general computational problem is:

Maximizex miny h(x, y) subject to x represents a strategy for player 1 ( *)

y represents a strategy for player 2

where h( x, y) denotes the expected payoff to player 1 if the strategies corresponding to x, y are played.

It turns out that the heart of the problem is finding an appropriate set of variables for representing the strategy. The first attempt is to use the move probabilities in the behavior strategy. In the poker example, we would then have x = { Xc, x~ : c = I , 2, 3} representing player 1 's strategy, and Y = {if,; , y~ : d = 1, 2, 3} representing player 2's strategy. The problem is that this payoff is a nonlinear function of the x's andy's. In order to avoid this problem, which would force us to use nonlinear optimization techniques, the standard solution algorithms in game theory do not use game trees and behavior strategies as their primary representation. Rather, they operate on an alternative representation called the normal form. In the two-player case, the normal form is a matrix A whose rows are all the deterministic strategies of the first player and whose columns are all the deterministic strategies of the second. The entry in the ith row and jth column is the expected payoff to the players when player 1 plays strategy sj and player 2 plays strategy si. A randomized strategy can now be viewed as a probability distribution over all the d~te':Tl1in.istic strategies. Hence, x is simply a probability d1stnbut10n over rows: it has a variable x; for each row, such that x; 2 0 for all i, and 2::::; x; = 1. If player 1 plays x and. player; plays y, then .the expected. payoff of the game IS simply x. Ay. U~der this representatiOn of strategies, (*) takes a particularly Simple form. It is then fairly easy to show that that appropriate vectors x and y can be found from A using standard linear programming methods.

For non-zero-sum games, the normal form also forms the basis for essentially all solution algorithms. Gala provides access to the normal form algorithms using an interface to the GAMBIT system, developed by McKelvey and Turocy [McK­ elvey, 1992]. GAMBIT provides a toolkit for solving various classes of games, including games with more than two players and g~mes w~ere the interests of the players are not strictly op~osmg. Smce Gala allows a clear and compact specifi­ catiOn of such games, the combined system provides both a repre~e?tation l.anguage and solution algorithms for games descnbmg multi-agent interactions.

Unfortunately, the normal-form algorithms are practical only for very small games. The reason is that the normal form is typically exponential in the size of the game tree. This is easy to see: A deterministic strategy must specify an action at ~ach information set. The total number of possible strategies IS therefore exponential in the number of information sets which is usually closely related to the size of the game tree: Consider our poker example, generalized to a deck with k cards. For each card c, player 1 must decide whether to pass or bet, and if he has the option, whether to pass or bet at the third round. There are three courses of action for each c, so the total number of possible strategies is 3k. Player 2, on the other hand, must decide on her action for each card d and each of the two actions possible for the first player in the first round. The number of different decisions is therefore 2k, so the total number of deterministic strategies is 2 2 k = 4k. Since the normal form has a row for each strategy of one player and a column for each strategy of the other, it is also exponential ink, while the size of the game tree is only 9k + 1. In general , the normal-form conversion is typically exponential in terms of both time and space.

This problem makes the standard solution algorithms an unrealistic option for many games. Due to the large branch­ ing factor in many games, even the approach of incrementally solving subtrees would not suffice to solve this problem. (This approach also encounters other difficulties in the context of imperfect information games; see Section 6.) Recently, a new approach to solving imperfect information games was developed by Koller, Megiddo, and von Stengel [1994]. This approach uses a conversion to an alternative form called these­ quence form, which allows it to avoid the exponential blowup associated with the normal form. We will describe the main ideas briefly here; for more details see [Koller et al., 1994].

The sequence form is based on a different representation of the strategic variables. Rather than representing proba­ bilities of individual moves (as in the non-linear representa­ tion above), or probabilities of full deterministic strategies (as in the normal form), the variables represent the realiza­ tion weight of different sequences of moves. Essentially, a sequence for a player corresponds to a path down the tree, but it isolates the moves under that player's direct control, ignoring chance moves and the decisions of the other players. In our poker game, for example, player 1 would have 4k + 1 sequences. In addition to the empty sequence (which corre­ sponds to the root of the game) he has four sequences for each card c: [bet on c] (in which case there is no third round), [pass on c), [pass on c, bet in the last round], and [pass on c, pass in the last round] . Player 2 also has 4k + 1 sequences: the empty sequence, and for each card d, the four sequences [bet on dafter seeing a pass], [pass on dafter seeing a pass], [bet on dafter seeing a bet], [bet on dafter seeing a bet]. Given a randomized strategy, the realization weight of a sequence for a player is the product of the probabilities of the player's moves encoded in the sequence. Essentially, the realization weight of the sequence corresponding to a path down the tree is a conditional probability: the probability that this path is taken given that the other players and nature all cooperate to make this possible. The probability that a path is actually taken in a game is therefore the product of the realization weights of all the players' sequences on that path, times the probability of all the chance moves on the path.

The sequence form of a two-player game consists of a pay­ off matrix A and a linear system of constraints for each player. In a two player game, the ith row of A corresponds to a se­ quence a-{ for player 1, and the jth column to a sequence a1 for player 2. The entry a ; j is the weighted sum of the payoff at the leaves that are reached by this pair of sequences (they are weighted by the probabilities of the chance moves on the path). If a pair of sequences is not consistent with any path to a leaf, the matrix entry is zero. So, for example, the matrix entry for the pair of sequences [bet on 2] and [pass on 1 after seeing a bet] is 1. The matrix entry for the pair [bet on 2] and [pass on 1 after seeing a pass] is 0, since this pair is not consistent with any leaf.

We now solve(*) using realization weights as our strate­ gic variables. We will have a variable Xa 1 for each sequence a-1 of player 1, and a variable Ya 2 for each sequence a-2 of player 2. Using the analysis above, we can show that the expected payoff of the game h(x, y) is xT Ay. This is precisely analogous to the expression we obtained for the normal form. It remains only to specify constraints on x and y guar­ anteeing that they represent strategies. For the normal form, these constraints simply asserted that these vectors represent probability distributions. In this case, the constraints are de­ rived from the following fact: If a- is the sequence for player i leading to an information set at which player i has to move, 1 and m1 , ... , mk are the possible moves at that information set, then we must have that X a = Xam 1 + · · · + X am k. The only other constraints are that the realization weight of the empty sequence is 1 (because the root of the game is reached in any play of the game), and that X a 2 0 for all a-.

Note that the sequence form is at most linear in the size of the game tree, since there is at most one sequence for each node in the game tree, and one constraint for each information set. Furthermore, it can be generated very easily by a single pass over the game tree. The format of the sequence form resembles that of the normal form in many ways, and it appears that many normal-form solution algorithms can be converted to work for the sequence form. The work of [Koller et al., 1994] focuses on the two-player case. They provide sequence­ form variants for the best normal-form algorithms for solving both zero-sum and general two-player games. The result which is of most interest to us is the following:

Theorem 4.1: The optimal strategies of a two-player zero­ sum game are the solutions of a linear program each of whose dimensions is linear in the size of the game tree.

The matrix of the linear program mentioned in the theorem is essentially the sequence form. The resulting matrix can then be solved by any standard linear programming algorithm, such as the simplex algorithm which is known to work well . in practice. We can also use a different linear programming algorithm whose worst-case running time is guaranteed to be polynomial. Hence, this theorem is the basis for an efficient polynomial time algorithm for finding optimal solutions to two-player zero-sum games.

5 Experimental results

The sequence-form algorithm for two-player zero-sum games has been fully implemented as part of the Gala system. The system generates the sequence form, creates the appropriate linear program, and solves it using the standard optimization library of CPLEX. We compared this algorithm to the tradi­ tional normal form algorithm by using GAMBIT to convert the game trees generated by Gala to the normal form, and CPLEX to solve the resulting linear program. We experimented with two games: the simplified poker game described in Section 2, increasing the number of cards in the deck; and an inspection game which has received significant attention in the game theory community as a model of on-site inspections for arms control treaties [Avenhaus et al., 1995]. The resulting running times are shown in Figure 3. They are as one would expect in a comparison between a polynomial and exponential algorithm.

These results are continued for the sequence form in Fig­ ure 4. (It was impossible to obtain normal-form results for the larger games.) There, we also show the division of time be­ tween generating the sequence form and solving the resulting linear program. For the poker games, we can see that gener­ ating the sequence form takes the bulk of the time. Solving even the largest of these games takes less than 10 seconds. This leads us to believe that these techniques can be made to run considerably faster by optimizing the sequence-form generator. Finally, note that the algorithm is much faster for poker games than for the inspection games. In the full paper, we explain these results, and define certain characteristics of a game that tend to have a significant effect on the running time of the sequence-form algorithm.

1 This formulation requires that the players never forget their own moves or information they once had. This implies that there is at most one sequence u leading to this information set.

As we remarked above, the final component of the Gala system reads in the strategies computed by this algorithm, and interprets them in a way that is meaningful with respect to the game. In particular, it allows the strategies to be ex­ amined by tbe user, who can then use them as part of the decision-making process. We have discovered that examin­ ing these strategies often yields interesting insights about the game. Figure 5 shows the strategies for both players in an eight card simplified poker. Consider the probability that the gambler bets in the first round: it is fairly high on a 1, some­ what lower on a 2, 0 on the middle cards, and then goes up for the high cards. The behavior for the low cards corresponds to bluffing, a characteristic that one tends to associate with the psychological makeup of human players. Similarly, after see­ ing a pass in the first round, the dealer bets on low cards with very high probability. Psychologically, we interpret this as an attempt to discourage the gambler from 'changing his mind' and betting on the final round. In more complex games, we see other examples where "human" behavior (e.g., underbidding) is game-theoretically optimal.

6 Discussion

As in the case of perfect information games, game trees for full-fledged games are often enormous. Although we expect to solve games with hundreds of thousands of nodes in the near future, full-scale poker is much larger than that and it is unlikely we will be able to solve it completely. Of course, chess-playing programs are very successful in spite of the fact that we currently cannot solve full-scale chess. Can we apply the standard game-playing techniques to imperfect information games? We believe that the answer is yes, but the issue is nontrivial. Even the concept of a 'subtree' is not well­ defined in such games. For one thing, the program cannot simply create the subtree starting at the current state, since it does not know precisely which node of the game tree is the actual state of the game; it knows only that the node is one of those in a certain information set. In addition, information sets belonging to other players may cross the "subtree boundary," as was the case in Figure 1. It is not obvious how to deal with these problems. We hope to address this issue in future work. Another approach that may well prove fruitful is based on the observation that there is a lot of regularity in the strategies for small poker games: the player often behaves the same for a variety of different hands. This suggests that in order to solve large games, we could abstract away some features of the game, and solve the resulting simplified game completely. For the game of poker, we could abstract by partitioning the set of possible deals into clusters, and then solve the abstracted game. Our experimental results indicate that the resulting strategies would be very close to optimal.

Most of the techniques we discussed in this paper also apply to more general classes of games. Gala provides the function­ ality for specifying arbitrary multi-player games. Currently, these can only be solved using the traditional (normal-form) algorithms accessed through our GAMBIT interface, and these are practical only for small games. However, the sequence form can be used to represent any perfect recall game, and the results of [Koller et al., 1994] indicate that many of the stan­ dard techniques could carry over from the normal form to the sequence form. We hope to use the sequence form approach for more general games, and show that the resulting expo­ nential reduction in complexity indeed occurs in practice. If so, the resulting system may allow an analysis of multi-player games, a class of games that have been largely overlooked. Perhaps more importantly, the system could also be used to solve games that model multi-agent interactions in 'real life'.

We believe that the Gala system facilitates future research into these and other questions. Its ability to easily specify games of different types and to generate many variants of each game allows any new approach to be extensively tested. We intend to make this system available through a WWW site (http : I / www. cs .berkeley . edurdaphne / gala / ), in the hope that it will provide the foundation for other work on imperfect information games.

Acknowledgements

We are deeply grateful to Richard McKelvey and Ted Turocy for going out of their way to ensure that the GAMBIT functional­ ity we needed for our experiments was ready on time. We also thank the International Computer Science Institute at Berke­ ley for providing us access to the CPLEX system. We also wish to thank Nimrod Megiddo, Barney Pell, Stuart Russell, John Tomlin, and Bernhard von Stengel for useful discussions.