Leaf-Value Tables for Pruning Non-Zero-Sum Games Nathan Sturtevant University of Alberta Department of Computing Science Edmonton, AB Canada T6G 2E8 nathanst@cs.ualberta.ca Abstract players scores, and secondly test to see if, given those bounds, it is provably correct to prune some branch of the Algorithms for pruning game trees generally game tree. This work focuses on the second part of this pro- rely on a game being zero-sum, in the case of al- cess. Alpha-beta and other pruning methods use very simple pha-beta pruning, or constant-sum, in the case of linear tests as a decision rule to determine whether or not they multi-player pruning algorithms such as specula- can prune. For zero-sum games these decisions are optimal. tive pruning. While existing algorithms can prune That is, they will make perfect decisions about whether prun- non-zero-sum games, pruning is much less effec- ing is possible. For non-zero-sum games, however, current tive than in constant-sum games. We introduce the techniques will not catch every possibility for pruning. idea of leaf-value tables, which store an enumer- In order to prune optimally in a non-zero-sum game we ation of the possible leaf values in a game tree. must have some knowledge about the space of possible val- Using these tables we are can make perfect deci- ues that can occur within the game tree. Carmel and Markov- sions about whether or not it is possible to prune a itch assume a bound on the difference of player scores. We given node in a tree. Leaf-value tables also make it instead assume that we can enumerate the possible outcomes easier to incorporate monotonic heuristics for in- of the game. This is particularly easy in card games, where creased pruning. In the 3-player perfect-informa- there are relatively few possible outcomes to each hand. Given that we can enumerate possible game outcomes, we tion variant of Spades we are able to reduce node can then make optimal pruning decisions in non-zero-sum expansions by two orders of magnitude over the games. In addition, these techniques can be enhanced by in- previous best zero-sum and non-zero-sum pruning corporating information from monotonic heuristics to further techniques. increase pruning. In section 2 we illustrate the mechanics of a few pruning algorithms, before moving to a concrete example from the 1 Introduction game of Spades in section 3. In section 4 we examine the computational complexity and the leaf-value table method In two-player games, a substantial amount of work has gone that is used to implement different decision rules for pruning, into algorithms and techniques for increasing search depths. followed by experimental results and conclusions. In fact, all but a small fraction of computer programs written to play two-player games at an expert level do so using the 2 Pruning Algorithms minimax algorithm and alpha-beta pruning. But, the pruning To prune a node in a game tree, it must be proven that no val- gains provided by alpha-beta rely on the fact that the game is ue at that node can ever become the root value of the tree. We zero-sum. Two-player games most commonly become non- demonstrate how this decision is made in a few algorithms. zero-sum when opponent modeling is taken into consider- ation. Carmel and Markovitch [1996] describe one method 2.1 Alpha-beta for pruning a two-player non-constant-sum game. We assume that readers are familiar with the alpha-beta prun- A multi-player game is one with three or more players or teams of players. Work on effective pruning techniques maxValue(state, , ) in multi-player games began with shallow pruning [Korf, IF cutoffTest(state) return eval(state) 1991], and continued most recently with speculative pruning, FOR EACH s in successor(state) [Sturtevant, 2003]. While a game does not need to be con- max(, minValue(s, , )) stant-sum for pruning to be applied, the amount of pruning IF ( - 0) RETURN possible is greatly reduced if a game is not constant-sum. RETURN Both two-player and multi-player pruning algorithms Figure 1: Alpha-beta pseudo-code. consist of at least two stages. They first collect bounds on (a) maxsum = 10 - (5, 5, (a) 1 5) 0 Figure 2: Alpha-beta pruning decision space. (c) (b) 2 2 (4, 6, 4) (5, 4, 1) ing algorithm. In Figure 1 we show pseudo-code for the maximizing player, modified slightly from [Russell and Nor- (e) (d) 3 vig, 1995]. The statement marked is where alpha-beta de- (?, ?, ?) termines whether a prune is possible. This is illustrated in (0, 6, 4) Figure 2. The x-axis is the value - , and we plot points Figure 4: Shallow pruning in a 3-player maxn tree. as they are tested. If a point, such as the solid one, falls to the left of 0, we can prune, and if it falls to the right, like the 2.3.1 Shallow Pruning hollow point, we cant. It is useful to think of this as a linear Shallow pruning [Korf, 1991] is one of the simplest pruning classifier, because it makes a single comparison with a linear algorithms for multi-player games. An example of shallow function to determine if a prune is possible. pruning is shown in Figure 4. The sum of players scores in each maxn value is always 10, so maxsum is 10. In this tree 2.2 Maxn fragment Player 1 is guaranteed at least a score of 5 at node The maxn algorithm [Luckhardt and Irani, 1986] is a general- (a) by moving towards (b). Similarly, Player 2 is guaranteed 6 ization of minimax for any number of players. In a maxn tree points at (c) by moving towards (d). Regardless what the un- with n players, the leaves of the tree are n-tuples, where the seen value is at (e), Player 2 will not select that move unless it ith element in the tuple is the ith players score or utility for gives him more than 6 points. Thus, before exploring (e), we that position. At the interior nodes in the tree, the maxn value can already guarantee that Player 1 will never get more than of a node where player i is to move is the maxn value of the maxsum - 6 = 4 points at (c). Because Player 1 is guaranteed child of that node for which the ith component is maximum. at least 5 points at (a), the value of (e) is irrelevant and can At the leaves of a game tree an exact or heuristic evalua- be pruned. tion function can be applied to calculate the n-tuples that are In this example we used consecutive bounds on Player 1 backed up in the game tree. and Player 2s scores to prune. As stated previously, the gen- We demonstrate this in Figure 3. In this tree there are eral idea is to prove that unseen leaf nodes cannot become the three players. The player to move is labeled inside each node. maxn value of the game tree. In Figure 4, for instance, we can At node (a), Player 2 is to move. Player 2 can get a score of 3 consider all possible values which might occur at node (e). If by moving to the left, and a score of 1 by moving to the right. any of these can ever become the maxn value at the root of the So, Player 2 will choose the left branch, and the maxn value of tree, we cannot prune. node (a) is (1, 3, 5). Player 2 acts similarly at node (b) select- To formalize this pruning process slightly, we construct a ing the right branch, and at node (c) breaks the tie to the left, n-tuple similar to a maxn value called the bound vector. This selecting the left branch. At node (d), Player 1 chooses the is a vector containing the lower bounds on players scores in move at node (c), because 6 is greater than the 1 or 3 avail- a game tree given the current search. While the maxn value is able at nodes (a) and (b). constrained to sum to maxsum, the bound vector can sum to 2.3 Maxn Pruning Algorithms as much as n·maxsum. In Figure 4, after exploring every node except node (e) our bound vector is (5, 6, 0). This is because Given no information regarding the bounds on players Player 1 is guaranteed 5 points at the root, and Player 2 is scores, generalized pruning is not possible. But, if we assume guaranteed 6 points at node (c). Existing pruning algorithms that each players score has a lower bound of 0, and that there prune whenever the sum of the components in the bound vec- is an upper bound on the sum of all players scores, maxsum, tor is at least as large as maxsum. we can prune. These bounds do not guarantee that a game is constant-sum, and existing pruning algorithms may miss possible bound vectors pruning opportunities if a game is not constant-sum. maxsum (6, 4, 0) (d) 1 x+y = maxsum Player 2 (a) (b) (c) (1, 3, 5) 2 (3, 5, 2) 2 (6, 4, 0) 2 possible maxn scores 0 3 3 3 3 3 3 maxsum 0 (1, 3, 5) (6, 1, 3) (6, 4, 0) (3, 5, 2) (6, 4, 0) (1, 4, 5) Player 1 Figure 3: A 3-player maxn game tree Figure 5: Shallow pruning decision space. (a) maxsum = 10 (5, , ) 1 bound vector space y (b) maxsum (, 3, ) 2 2 z (5, 4, 1) (c) maxn values, (, , 3) 3 3 x+y+z = maxsum (3, 3, 4) 0 (?, ?, ?) 1 x maxsum (3, 4, 3) Figure 7: Speculative pruning decision space. Figure 6: Speculative Pruning to at least maxsum we can guarantee that there will never be We show a visualization of the shallow pruning space a value at the right child of (c) which can become the maxn in Figure 5. The x- and y-coordinates are scores or bounds value of the tree. When pruning over more than 2-ply in for Player 1 and Player 2 respectively. The shaded area is the multi-player games there is the potential that while a value at space where possible maxn values for Player 1 and 2 will fall. (c) cannot become the maxn value of the tree, it can affect the All maxn values in the game must be in this space, because maxn value of the tree. Other details of the speculative prun- their sum is bounded by maxsum. Because shallow pruning ing algorithm prevent that from happening, but we are only ignores Player 3, Player 1 and Player 2s combined scores concerned with the initial pruning decision here. are not constant-sum, so they can fall anywhere to the left of We illustrate the pruning decision rule for speculative the diagonal line. Bound vectors, however, can fall anywhere pruning in Figure 7. In this case, because we are comparing in the larger square. If a bound vector is on or above the di- three players scores, the decision for whether we can prune agonal line defined by x+y = maxsum, we can prune, because depends on a 2-d plane in 3-d space, where each axis cor- there cannot be a maxn value better than those bound vectors. responds to the score bound for each of the 3 players in the Like alpha-beta, shallow pruning is using a linear classifier to game. Thus each maxn value and bound vector can be repre- decide when to prune. sented as a point in 3-d space. For a three-player constant- Ignoring Player 3s values, we plot the leaf values (5, 4, -) sum game, all possible maxn values must fall exactly onto and (0, 6, -) from Figure 4 as open points, and the bound vec- the plane defined by x+y+z = maxsum, which is also perfect tor (5, 6, -) used to prune in Figure 4 as a solid point. In this classifier for determining when we can prune. As in shallow instance, there is no gap between the gray region and the di- pruning, bound vectors can fall anywhere in the 3-d cube. agonal line, so the line defined by x+y = maxsum is a perfect classifier to determine whether we can prune. 2.4 Generalized Pruning Decisions 2.3.2 Alpha-Beta Branch-and-Bound Pruning In all the pruning algorithms discussed so far, a linear classi- Although shallow pruning was developed for multi-player fier is used to make pruning decisions. This works well when games, the basic technique only compares the scores from a game is zero-sum or constant-sum, but in non-constant-sum two players at a time. Alpha-beta branch-and-bound pruning games a linear classifier is inadequate1. [Sturtevant and Korf, 2000] is similar to shallow pruning, ex- When a game is non-constant-sum, the boundary of the cept that it uses a monotonic heuristic to provide bounds for space of maxn values is not defined by a straight line. We all players in the game. The bound vector in Figure 4 was (5, demonstrate this in the next section using examples from the 6, 0). Player 3s bound was 0, because we had no information game of Spades. To be able to prune optimally, we need to about his scores. But, supposing we had a monotonic heuris- know the exact boundary of feasible maxn values, so that we tic that guaranteed Player 3 a score of at least 2 points. Then can always prune when given a bound vector outside this re- the bound vector would be (5, 6, 2). This additional bound gion. We explain methods to do this in Section 4. makes it easier to prune, since we can still prune as soon as the values in the bound vector sum to maxsum. 3 Sample Domain: Spades 2.3.3 Speculative Pruning Spades is a card game for 2 or more players. In the 4-player Speculative pruning [Sturtevant, 2003], like alpha-beta version players play in teams, while in the 3-player version branch-and-bound pruning, takes into account all of the play- each player is on their own, which is what we focus on. There ers in the game. It does this by considering multiple levels in are many games similar to Spades which have similar proper- the game tree at one time. We demonstrate this in Figure 6. Further details on the relationship between constant-sum and In this figure, the important bounds are Player 1s bound at 1 non-constant-sum games are found in Appendix A, but they are not (a), Player 2s bound at (b) and Player 3s bound at (c). These necessary for understanding the contributions of this paper. together form the bound vector (5, 3, 3). If these values sum # Tricks Utility/Evaluation (bid) Ranked Taken maxn vals P1 (1) P2 (1) P3 (2) 4 (0, 0, 3) 0 0 19+6 (0, 0, 2) Player 2's score x+ y= (0, 1, 2) 0 10+3 20+3 (0, 2, 1) 4 (m (0, 2, 1) 0 9+6 0 (0, 4, 0) ax su (0, 3, 0) 0 8+6 0 (0, 3, 0) m ) (1, 0, 2) 10+3 0 20+3 (2, 0, 1) 0 (1, 1, 1) 10+3 10+3 0 (2, 2, 0) 4 0 (1, 2, 0) 10+3 9+3 0 (2, 1, 0) Player 1's score (2, 0, 1) 9+6 0 0 (4, 0, 0) Figure 8: Pruning decision space for Table 1. (2, 1, 0) 9+3 10+3 0 (1, 2, 0) value of each state, not the absolute value. So, in the last col- (3, 0, 0) 8+6 0 0 (3, 0, 0) umn we have replaced each players utility with a rank, and Table 1: Outcomes for a 3-player, 3-trick game of Spades. combined all players ranks into the final maxn value. As an example, the first possible outcome is that Players ties. We will only cover a subset of the rules here. A game of 1 and 2 take no tricks, while Player 3 takes 3 tricks. Since Spades is split into many hands. Within each hand the basic Players 1 and 2 both missed their bids, they get 0 points. unit of play is a trick. At the beginning of a hand, players Player 3 made his bid of 2 tricks, and took 1 overtrick. Since must bid how many tricks they think they can take. At the end we want to avoid too many overtricks, we evaluate this as 20- of each hand they receive a score based on how many tricks 1 = 19 points. But, since both Player 1 and 2 miss their bids in they actually took. The goal of the game is to be the first this scenario, Player 3 has a bonus of 6 points. This is the best player to reach a pre-determined score, usually 300 points. possible outcome for Player 3, so it gets his highest ranking. If a player makes their bid exactly, they receive a score For Player 1 and 2 it is their worst possible outcome, so they of 10×bid. Any tricks taken over your bid are called over- rank it as 0. tricks. If a player takes any overtricks they count for 1 point We graph the shallow pruning decision space for the first each, but each time you accumulate 10 overtricks, you lose two players of this game in Figure 8. In this game maxsum is 100 points. Finally, if you miss your bid, you lose 10×bid. So, 4. The 10 possible leaf values for the first two players are all if a player bids 3 and takes 3, they get 30 points. If they bid plotted as hollow points in the graph. If we use maxsum as a 3 and take 5, they get 32 points. If they bid 3 and take 2, they discriminator to decide if we can prune, it will indicate that get -30 points. Thus, the goal of the game is to make your bid we can only prune if a bound vector falls on or above the bold without taking too many overtricks. diagonal line. But, we can actually prune as long a bound If all players just try to maximize the number of tricks vector is on or above the border of the gray region. So, we they take, the game is constant-sum, since every trick is taken can actually prune given any bound vector for player 1 and 2 by exactly one player, and the number of tricks available is except (0, 0), (0, 1), (1, 0) and (1, 1). constant. But, maximizing the tricks we take in each hand As a final point, we note that in card games like Spades will not necessarily maximize our chances of winning the the number of tricks you have taken can only increase mono- game, which is what we are interested in. Instead, we should tonically, which can be used as a heuristic to help pruning. try to avoid overtricks, or employ other strategies depending This observation is the key behind the alpha-beta branch- on the current situation in the game. and-bound pruning technique. But, if we are using a utility In a game with 3 players and t tricks, there are (t+1)(t+2)/2 function like in Table 1, it is difficult to describe how the possible ways that the tricks can be taken. We demonstrate monotonic heuristic relates to the evaluation function. Leaf- this in Table 1, for 3 players and 3 tricks. value tables, however, make the task easy. Table 1 is an example of a leaf-value table. It contains all Assume, for instance, that Player 2 has already taken 1 possible leaf values and their associated utility in the game. trick. Then, we can ignore all outcomes in which he does not In Spades, we build such a table after each player had made take one trick. This gives us a reduced set of values, which their bid, but before game play begins. The first column enu- are marked with a in Table 1. Looking at the associated merates all possible ways that the tricks can be taken by each maxn values, we then see that Player 1 will get no more than player. The second through fourth columns evaluate the score 2 and Player 3 will get no more than 1. We show how this is for each player, that is their utility for each particular out- used in the next section. come. In this example, Player 1 and Player 2 have bid 1 trick 4 Leaf-Value Tables each, and Player 3 bid 2 tricks. If a player does not make their bid they have a score of 0, otherwise we use a heuristic The formal definition of a leaf-value table is a table which estimate for their score, 10×bid - overtricks + 3×(how many holds all possible outcomes that could occur at a leaf node in opponents miss their bid). As has been shown for minimax a game. Looking back to the pruning algorithms in Section 2, [Russell and Norvig, 1995], we only care about the relative results in a hash table. leaf-value table[] { outcome[], rank[] } GLOBAL Pseudo-code for using a leaf-value table is in Figure 9. This procedure is called by a pruning algorithm to decide 1 canLeafValueTablePrune(bounds[], heuristicUB[]) whether or not to prune given current bounds. A leaf-value 2 IF (inHashTable(bounds, heuristicUB)) table is pre-computed with each possible outcome of the 3 return hashLookUp(bounds, heuristicUB) game and the associated rank of that outcome for each player. 4 FOR each entry in leaf-value table We pass in the current bound vector, as well as any heuristic 5 FOR i in players 1..n upper bounds on players scores. If an entry in the leaf-value 6 if entry.outcome[i] > heuristicUB[i] table is inconsistent with the heuristic (line 6), we can ignore 7 skip to next entry; that entry, because that outcome cannot occur in the current 8 FOR i in players 1..n sub-tree. If there is an entry in the table for which every play- 9 if entry.rank[i] bounds[i] er does better than their value in the bound vector, tested on 10 skip to next entry; lines 8-9, we reach lines 11-12, indicating we cannot prune. 11 addToHashTable(false, bounds, heuristicUB) Every time we attempt to prune, we will pay at most 12 RETURN false; O(table size), but this cost is quickly amortized over the look- 13 addToHashTable(true, bounds, heuristicUB) ups, and doesnt add significant overhead. In a game with a 14 RETURN true; large number of outcomes there are a variety of other methods Figure 9: Leaf-Value Table Pruning pseudo-code. that could be used to reduce the lookup cost. Additionally, we can always use the standard linear maxsum check, as it will always be correct if it indicates we can prune. The heuristic we want to replace the linear classifiers with more accurate does not speed up the check for whether we can prune, but it classifiers, given a leaf-value table. Thus, we need an effi- can reduce the effective size of the leaf-value table, making it cient way to both find and compute regions like in Figure 8 to more likely that we do prune. determine when we can prune. Theorem: The information stored in a leaf-value table is suf- 5 Experimental Results ficient to make optimal pruning decisions. Proof: We first assume that we have a bound vector b = (b1, 5.1 Nodes Expanded in Three-Player Spades b2, ..., bn), where each bound in the vector originates on the We use the game of Spades as a test-bed for the techniques path from the root of the tree to the current node. We are introduced in this paper. Our first experiment will illustrate guaranteed that a player i with bound bi will not change his that leaf-value tables are quite effective for pruning, and will move unless he can get some value vi where vi > bi. Thus, if also help demonstrate when they will be most effective. To there exists a value v = (v1, v2, ..., vn) where i vi > bi then do this, we compare the number of nodes expanded using we cannot prune, because v is better than every bound in (1) previous pruning techniques and (2) a variety of evalua- the search so far. Given a leaf-value table, we know every tion functions in the 3-player version of Spades. One of these possible value in the game, and so we can explicitly check evaluation functions is actually from a different bidding whether some v exists that meets the above conditions, and game, called "Oh Hell!" thus we can use a leaf-value table to make optimal pruning For each method, we counted the total number of node decisions. expansions needed to compute the first move from 100 hands Because a leaf-value table gives us an exact descrip- of Spades, where each player started with 9 cards and searched tion of the boundary of the spaces where we can and cannot the entire game tree (27-ply). Our search used a transposition prune, the only question is how we can use this information table, but no other search enhancements besides the pruning efficiently. Given a bound vector, we need to quickly deter- methods explicitly discussed. Bids for each player are pre-de- mine whether or not we can prune, because we expect to ask termined by a simple heuristic. For these trees, the leaf-value this question once for every node in the game tree. tables contain 55 entries. We present the results in Table 2. For small games, we can build a lookup table enumer- The first column in the table is the average size of the ating all possible bound vectors and whether or not we can game trees without pruning, 2.7 million nodes. This is deter- prune. This will provide constant time lookup, but for a table mined by the cards players hold, not the evaluation function with t entries and n players, this table will be size O(tn) and used, so we will compare the other tree sizes to this value. take time O(tn+1) to compute. Including heuristic information The next two columns are the results using speculative makes these tables even larger. But, most of these entries will pruning with a linear classifier, the previous best pruning never be accessed in any given game. Instead, we can dy- technique. If we use a non-constant-sum (NCS) evaluation namically compute entries as we need them, and store the Full Tree NCS MT MoMB mOT smOT WL OH 2.7M 1.9M 1.1M 400k 37.2k 8.6k 788 40.7k nodes expanded - 1.36 2.37 6.6 71 308 3362 65 reduction factor Table 2: Overall reduction and average tree sizes in Spades. Full Tree Best NZS Zero-Sum LVT Avg. Points % Wins 481k 225k 14k 22k LVT 263 62.3% nodes - 2.14 34.4 21.9 226 37.7% reduction prev. methods Table 3: Reduction and average tree sizes in 2-player Spades. Table 4: Average score over 100 games of Spades. the search space, and thus increases pruning. function, speculative pruning is able to reduce the average The MoMB evaluation function is both monotonic and tree size by a factor of 1.36 to 1.9 million nodes. Maximizing only a slight simplification of the MT evaluation function, so tricks, MT, is the best-case evaluation function for specula- we should and do see the least gains when using this evalua- tive pruning, because it is constant-sum. In this case the aver- tion function. age tree size is reduced to 1.1 million nodes. Now, we replace speculative prunings linear classifier 5.2 Nodes Expanded in Two-Player Spades with leaf-value tables and use a non-zero-sum evaluation. We conducted similar experiments in the two-player game The first function we use is MoMB, maximizing the number of Spades. [Korf, 1991] described how deep pruning fails in of opponents that miss their bid. This is quite similar to the multi-player games. It is not difficult to show that the same strategy of maximizing your tricks, but the average tree size problem exists in two-player non-zero-sum games as we can be reduced further to 400k nodes, a 6.6 fold reduction. have described them here. The bottom line is that we cannot The next evaluation function we use tries to minimize prune as efficiently as alpha-beta once we use a non-zero- overtricks, mOT. This produces much smaller trees, 37.2k sum evaluation function. In these experiments we did not ap- nodes on average, a 71 fold reduction over the full tree. A ply every conceivable game-tree reduction technique, only similar evaluation function, smOT, allows a slight margin transposition tables and basic alpha-beta pruning, so in prac- for taking overtricks, because that is how we keep our op- tice we may be able to generate smaller two-player zero-sum ponent from making their bid, but tries to avoid too many game trees. overtricks. This evaluation function reduces the tree further In the two-player Spades games, we searched 100 hands to 8.6k nodes, over 300 times smaller than the original tree. to depth 26 (13 tricks) using a variety of techniques. The re- The smOT evaluation is what was used with speculative maxn sults are in Table 3. The full tree averaged 481k nodes. Us- for the NCS experiment. In the end, both algorithms calculate ing a non-zero-sum evaluation function and the best previous the exact same strategies, but with leaf-value tables we can methods produced trees that averaged 225k nodes. Using al- do it hundreds of times faster. pha-beta pruning and a zero-sum evaluation function reduced Finally, we show a very simple evaluation function, WL. the trees further to 14k nodes on average. Using leaf-value This function gives a score of 1 (win) if we make our bid and tables (LVT) for pruning produced trees were slightly larger, 0 (loss) if we miss it. In practice we wouldnt want to use this 22k nodes. As referenced above, these trees are larger than evaluation function because it is too simple, but it does give those generated by alpha-beta because we cannot apply deep an estimate of the minimum tree size. With this evaluation pruning, but they are still much smaller than previously pos- function the average tree has 788 nodes. sible given a non-zero-sum evaluation function. "Oh Hell!" (OH) is a similar game to Spades, however 5.3 Quality of Play From Extended Search the goal of this game is to get as close to your bid as possible. In the context of this paper, we can just view this a different Finally, to compare the effect of additional search on qual- evaluation function in the game of Spades. Using this evalua- ity of play, we then played 100 games of 3-player Spades, tion, the average tree size was 40.7k nodes, 65 times smaller where multiple hands were played and the scores were ac- than the full tree. cumulated until one player reached 300 points. Also, each Besides showing the effectiveness of leaf-value tables, complete game was replayed six times, once for each pos- these experiments help illustrate two reasons why leaf-tables sible arrangement of player types and orderings, excluding are effective for pruning in a non-constant-sum game. The games with all of one type of player. Each player was allowed first reason for large reductions is that the non-constant-sum to expand 2.5 million nodes per turn. One player used specu- evaluation may significantly reduce the number of unique lative pruning with leaf-value tables to prune, while the other outcomes in a game, which will be captured by a leaf-value used speculative pruning with a linear classifier. Hands were table. The best example of this is the WL evaluation function. played "open" so that players could see each others cards. But, smOT also reduces the possible outcomes over mOT, The results are in Table 4. The player using the leaf-value and thus reduces the size of the game trees. tables (LVT) was able to win 62.3% of the games and aver- The other factor that is important for pruning is having a aged 263 points per game, while the player using previous monotonic heuristic along with an evaluation function that is techniques averaged only 226 points per game. not monotonic with respect to the heuristic. Evaluation func- 5.4 Summary tions like mOT are non-monotonic in the number of tricks taken, because we initially want to take more tricks, and then, We have presented results showing that leaf-value tables, after making our bid, we dont want to take any more tricks. when combined with previous pruning techniques, can ef- fectively prune non-constant-sum games such as Spades or This allows a monotonic heuristic to more tightly constrain Oh Hell! naturally constant-sum and make it non-constant-sum by ei- Although we do not present experimental results here, ther adding a player which doesnt actually play in the game, we can predict the general nature of results in other games but receives a random score, or by applying an affine trans- form to one or more players scores. Neither of these trans- such as Hearts. In most situations in Hearts, our evaluation formations, however, will change the strategies calculated by function will be constant-sum. But, there will be some situa- maxn, because maxn makes decisions based on the relative tions where a non-constant-sum evaluation function is need- ed. Thus, if we use leaf-value tables for such a game, we will ordering of outcomes, which an affine transform preserves, have the same gains as previous techniques in portions of the and because any extra players added will not actually make decisions in the game tree. game that are constant-sum. But, when the game is non-con- stant sum, we will benefit from additional pruning, although If we are unaware of either of these changes, previous the exact amount will depend on the particular situation. pruning algorithms may treat the game as non-constant-sum and miss pruning opportunities. But, leaf-value tables are not 6 Conclusions and Future Work affected by either of these changes. Leaf-value tables com- pute the ranking of all outcomes, so any affine transform ap- In this paper we have shown how an enumeration of possible plied to an evaluation function will be removed by this pro- leaf-values in a game tree, called a leaf-value table, can be cess. Because no bounds will ever be collected for any extra used to change the linear classifier used in classical pruning players in the game, as they are not actually a part of the algorithms to an arbitrary classifier needed for non-zero-sum game, pruning decisions are unchanged. games. This technique works particularly well in card games Secondly, we can take a game that is non-constant-sum like Spades, where we see up to a 100 fold reduction of nodes and make it constant-sum by adding an extra player whose expanded over the previous best results using a constant-sum score is computed such that it makes the game constant-sum. evaluation function, along with gains in quality of play. Again, because this extra player never actually plays in the This work expands the limits of how efficiently we can game, no pruning algorithm will ever collect bounds for this search two-player and multi-player games. To a certain ex- player, and it is equivalent to playing the original game. No tent there is still an open question of how to best use limited extra pruning can ever be derived from such a change. resources for play. Recent results in applying opponent mod- Adding an additional player may also make a non-linear eling to two-player games have not been wildly successful classifier appear to be linear. But, because the extra player [Donkers, 2003]. In multi-player games, we have shown that never plays, we will actually need to use the non-linear clas- deep search isnt always useful, if there isnt a good opponent sifier to make pruning decisions. model available [Sturtevant, 2004]. But, given a reasonable Thus, while the difference between constant-sum games opponent model, this work allows us to use the best evalua- and non-constant-sum games can be blurred by simple trans- tion function possible and still search to reasonable depths in forms, the underlying game properties remain unchanged. the game tree. In the future we will continue address the broader ques- References tion of what sort of opponent models are useful, and what assumptions we can make about our opponents without ad- [Carmel and Markovitch, 1996] Carmel, D., and Markov- versely affecting the performance of our play. The ultimate itch, S., Incorporating Opponent Models into Adversary goal is to describe in exactly which situations we should use Search, AAAI-96, Portland, OR. maxn, and in which situations we should be using other meth- [Donkers, 2003] Donkers, H.H.L.M., Nosce Hostem: Search- ods. These are broad questions which we cannot fully answer ing with Opponent Models, PhD Thesis, 2003, Univer- here, but we these additional techniques will provide the tools sity of Maastricht. to better answer these questions. [Korf, 1991] Korf, R., Multiplayer Alpha-Beta Pruning. Arti- Acknowledgements ficial Intelligence, vol. 48 no. 1, 1991, 99-111. [Luckhardt and Irani, 1986] Luckhardt, C.A., and Irani, K.B., This research benefited from discussions with Jonathan An algorithmic solution of N-person games, Proceed- Schaeffer, Michael Bowling, Martin Müller, Akihiro Kishi- ings AAAI-86, Philadelphia, PA, 158-162. moto and Markus Enzenberger. The support of Albertas [Russell and Norvig, 1995] Russell, S., Norvig, P., Artificial In- Informatics Circle of Research Excellence (iCORE) is also appreciated. telligence: A Modern Approach, Prentice-Hall Inc., 1995. [Sturtevant, 2004] Sturtevant, N.R., Current Challenges in A Game Transformations Multi-Player Game Search, Proceedings, Computer and In this paper we have often made distinctions between games Games 2004, Bar-Ilan, Israel. or evaluation functions based on whether they are constant- [Sturtevant, 2003] Sturtevant, N.R., Last-Branch and Specu- sum or not. These distinctions can be blurred through minor lative Pruning Algorithms for Maxn, Proceedings IJCAI- transformations, however such transformations do not change 03, Acapulco, Mexico. the underlying nature of the game. In this appendix we ex- [Sturtevant and Korf, 2000] Sturtevant, N.R., and Korf, R.E., plain this in more detail, but the details are not necessary for On Pruning Techniques for Multi-Player Games, Pro- understanding the technical contributions of this paper. ceedings AAAI-2000, Austin, TX, 201-207. First, we can take a game or evaluation function that is