An Investigation into the Properties of Goofspiel (GOPS: Game of Pure Strategy)

By David Kerr

 

 

 

Back to my home page.

Background

Goofpiel (also called GOPS) is a fun, easily learned card game amenable to analysis using classical game theory. The following material derives from the senior thesis requirement of my undergraduate degree program in mathematics at the University of Washington. Stumped for an idea for this thesis, I recalled the many card games I had played with my family as a child and remembered Goofspiel as being a perfect candidate for mathematical analysis.

Rules

From a standard 52-card deck, the thirteen clubs are given to Player I, the thirteen diamonds to Player 2, the thirteen hearts are discarded, and the thirteen spades are shuffled and placed face down in the middle. From this middle pile one card is turned up. The two players then 'bid' on the upturned card, each player choosing one card and then simultaneously displaying it to the other player. The player showing the highest card (ace low, king high) wins the value of the upturned card (ace=1, jack=11, queen=12, king=13). If both players display the same card, the point value is split between the two players. These three cards are then discarded, a new spade from the middle pile is turned over, and the game continues. After thirteen rounds, all cards have been played. In this case, it is the first player who scores 46 points.

Sample Round

The intuitive solution to scoring well is to play a card valued at one above what the opponent discards. However, neither player knows what the other will play. This leads to thought processes similar to the following. Say the first upturned card is a seven.. Player I 'feels' as though Player II might play high for the card, and so plays a two, electing not to try to also play high. Player II 'feels' as though Player I might play a card near a seven, and so hopes to go slightly over and therefore plays a ten. Player II then wins seven points, as the ten is larger than Player I's two. However, it is not clear which player has the advantage after this first round. Although Player II now has seven points 'in the bank', Player I has higher valued cards remaining and so is therefore likely to score more points than Player II in the following twelve rounds.

Simple Game-Theory

Let us use a slightly different scoring system for the remainder of the analysis. This scoring system is simply for mathematical conventions and will not affect the strategies of the players. In the variation on scoring, the owner of the higher card wins from the other player the value of the upturned card, or nothing in the event of a tie. The player with positive winnings at the end is declared the winner. This two-player game is non-cooperative, symmetric, and zero-sum. By the symmetry involved, each player's optimal strategy will be identical and result in zero profit. The strategy must be such that the knowledge of it by the other player will not allow a profit to be made. Such a strategy will in all likelihood depend upon what cards have been already played from both players' hands and the middle pile, and what the current upturned card is. It might be pure, meaning that a particular card should always be played, or it might be mixed, meaning that two or more cards each have a positive probability of being played. This optimal strategy must maximize the expected profit to both players; by symmetry, it gives each player an expected profit of zero. (An important note to consider: we really should maximize the probability of winning. I will be doing analysis which instead maximizes the expected point total. There is a subtle difference which in reality should not make too much difference to the strategy employed.)

The difficulty in enumerating all possible games quickly becomes apparent. Assuming an N-card game is being played, the number of unique ways the game could be player out is (N!)^3. These numbers get large extremely fast: for f(2) = 8, f(3) = 216, f(4) = 13,824, and f(5) = 1,728,000. f(13) will be an astronomically large number. It is therefore not feasible to write down all possible pure strategies and calculate the payoffs. Instead, the problem can be examined as a super-game consisting of N subgames. This is done recursively until only two-card games are solved. This results in the need to only solve j*(N choose j)^3 jxj matrices for j = 2, ..., N. For the 3-card case, we need to solve 3 three-by-three and 54 two-by-two games. The four-card case requires 4 four-by-four, 192 three-by-three, and 432 two-by-two games. (Actually the number of two-by-two games required to be calculated can be reduced in half.)

Solving the Payoff Matrices

I did not have linear optimization tools at my disposal to solve the payoff matrices.  Instead, an iterative approach originally proposed by J.D. Williams in “The Compleat Strategyst” was employed.  I modeled 1000 rounds for each matrix, where each player sequentially picks the most optimal choice, given the cumulative choices of the opponent.

Solving the Two-Card Case

The one-card problem is trivial, neither player has any choice and both are guaranteed a payoff of zero. The standard two-card problem is also straightforward, but now a choice must be made. Different decisions will be made, conditional upon the initial card upturned. The two relevant matrices, in terms of payoff to Player I and with Player I's first card played indexed on the left and Player II's first card played indexed on the top, are:

'1' is first

 

Player II

 

 

'2' is first

 

Player II

 

 

 

1

2

 

 

 

1

2

Player I

1

0

1

 

Player I

1

0

-1

 

2

-1

0

 

 

2

1

0

So a pure strategy for Player I exists, which will guarantee at least a payoff of zero. This optimal strategy is to match the upturned card; to play a '1' when the initial card is a '1', and likewise to play a '2' if the initial card is a '2'. The symmetry of the game applies to Player II, who will follow suit, resulting is a payoff of zero to both. Deviating from this strategy can only be detrimental.

Solving the Three-Card Case

A similar situation occurs in the standard three-card problem. The computations are not as obvious, however. Each of the nine elements in the three matrices (corresponding to the three possible initial upturned cards) must be calculated by adding the payoff of the first play to the expected payoff of the subsequent two plays. The value of the susequent plays is the average value of the payoffs of the subgames determined by each of the possible next two upturned cards. In this case, however, these are the same. (When there are two cards remaining in each player's hand, it doesn't matter for the expected payoffs what order the two middle cards are in.) The payoff matrices of the three-card case are:

'1' is first

 

Player II

 

 

 

 

1

2

3

Player I

1

0.00

0.40

2.80

 

2

-0.40

0.00

0.40

 

3

-2.80

-0.40

0.00

 

'2' is first

 

Player II

 

 

 

 

1

2

3

Player I

1

0.00

-1.00

1.25

 

2

1.00

0.00

0.00

 

3

-1.25

0.00

0.00

 

'3' is first

 

Player II

 

 

 

 

1

2

3

Player I

1

0.00

-2.00

-0.67

 

2

2.00

0.00

-2.00

 

3

0.67

2.00

0.00

Some interesting properties emerge. As expected, the matrices are skew-symmetric, with zeroes along the diagonals. If the '1' or the '3' is the initial card upturned, the optimal strategy is a pure one; both players will match the upturned card. If the '2' is the first card upturned, then an equilibrium is seen. Both players are indifferent between playing their '2' and '3' cards. An optimal strategy is to match the first upturned card, and all subsequent cards. Any deviations from this strategy will lead to negative expected payoffs. This same strategy of both players matching the upturned card is trivially true in the one- and two-card problem. But is the strategy of matching the initial upturned card optimal for the N-card problem?

Solving the Four-Card Case

Solving the four-card case is computationally more difficult than the three-card case, but the theory is the same. The payoff matrices are:

'1' is first

 

Player II

 

 

 

 

 

1

2

3

4

Player I

1

0.00

0.01

1.97

4.26

 

2

-0.01

0.00

0.16

2.53

 

3

-1.97

-0.16

0.00

0.60

 

4

-4.26

-2.53

-0.60

0.00

 

'2' is first

 

Player II

 

 

 

 

 

1

2

3

4

Player I

1

0.00

-1.19

0.31

3.16

 

2

1.19

0.00

-0.76

2.29

 

3

-0.31

0.76

0.00

-0.18

 

4

-3.16

-2.29

0.18

0.00

 

'3' is first

 

Player II

 

 

 

 

 

1

2

3

4

Player I

1

0.00

-2.00

-0.67

1.58

 

2

2.00

0.00

-2.00

0.67

 

3

0.67

2.00

0.00

-0.82

 

4

-1.58

-0.67

0.82

0.00

 

'4' is first

 

Player II

 

 

 

 

 

1

2

3

4

Player I

1

0.00

-3.28

-2.07

-0.30

 

2

3.28

0.00

-3.17

-1.20

 

3

2.07

3.17

0.00

-2.62

 

4

0.30

1.20

2.62

0.00

Unlike the earlier cases, a strategy of always matching the upturned card is not optimal. In the cases of a '2' or '3' initially up, Player II could respond by playing the card valued at one higher than that of the upturned card, resulting in Player I making negative expected winnings. It is still true that an initial '1' or '4' results in the matching strategy being optimal the first round, but the strategies on an initial '2' or '3' are mixed. The exact probabilities for the first round are:

 

 

First Card

 

 

 

 

 

1

2

3

4

Prob.

1

1.000

0.335

0.266

0.000

 

2

0.000

0.137

0.000

0.000

 

3

0.000

0.528

0.514

0.000

 

4

0.000

0.000

0.220

1.000

If the first card is a '2', half the time play a '3', one-third of the time play a '1' and the remaining time play a '2'. Never play a '4'. If the first card is a '3', half the time play a '3', and the remaining times split between playing a '1' and a '4'. Never play a '2'.

Solving the Five-Card Case

I do not include the payoff matrices here, but the probabilities for what to play on the first card for the five-card case are:

 

 

First Card

 

 

 

 

 

 

1

2

3

4

5

Prob.

1

0.05

0.20

0.11

0.12

0.11

 

2

0.84

0.00

0.14

0.09

0.03

 

3

0.11

0.73

0.00

0.18

0.00

 

4

0.00

0.07

0.75

0.21

0.00

 

5

0.00

0.00

0.00

0.40

0.86

Some interesting patterns emerge from studying the above solution. In general, on the first play of the game the players discard a card valued at one higher than the upturned card, or match in the case of the ‘5’. Very rarely will they match the upturned card (except in the case that the highest valued card is upturned).

Conclusion

At first glance, Goofspiel seems a relatively simple children's card game. As has been seen, there is much more to this game. The main computational project is to expand the analysis of the game up to its proper 13-card case, and look for any patterns that emerge.

The specific order of the cards in the middle deck seems to only slightly affect the resulting payoffs of the subgames, so perhaps a fixed order of cards can be presumed without hurting the accuracy of the computations terribly much. This would dramatically decrease the number of required calculations and could make the 13-card problem tractable.

It would be interesting to see if any economic or industrial applications can be represented by Goofspiel. For example, it might be possible to model the activities of a duopsony (two firms competing to buy a particular good) by this method. Another example might be two architectural firms with finite resources competing for a series of projects, where each must decide the amount of time and money it should spend preparing plans for each job, and where the company with the best design gets that particular job. A similar situation could exist with two generals deciding on the number of troops send to each in a series of battles.

References

Dror, "Simple Proof for Goofspiel", Advances in Applied Probability, 21 (1989), pps. 711-712.

Epstein, Theory of Gambling and Statistical Logic, (1977), p. 331.

Gale, The Theory of Linear Economic Models, (1960), pps. 184-186, 189.

Luce and Raiffa, Games and Decisions, (1957), pps. 44-47, 52.

Nakai, "Generalized Goofspiel", Journal of Operations Research in Society - Japan, 23 (1980), pps. 156-170.

Owen, Game Theory, 2nd Ed., (1982), pps. 3,4.

Ross, "Goofspiel - The Game of Pure Strategy", Journal of Applied Probability, 8 (1971), pps. 621-25.

Williams, The Compleat Strategyst, (1954), p. 180.

Ross is one of the few to publish an in-depth look at Goofspiel. In his paper, he demonstrates three points: if Player II is playing cards randomly, Player I's optimal strategy is to match the upturned card; if both players must discard before the middle card is overturned, then the randomizing strategy is optimal for both players; and Goofspiel is a stochastic game, with interesting recursive properties for solving.

A site of interest is Dan Drake's page which has a computer program for playing Goofspiel.

 

 

 

Back to my home page.