On the Complexity of Trick-Taking Card Games

1 Introduction

Determining the complexity class of games is a popular research topic [Hearn, 2006], even more so when the problem has been open for some time and the game is actually of interest to players and researchers. For instance, the game of AMAZONS was proved PSPACE-complete by three different research groups almost simultaneously [Furtak et al., 2005; Hearn, 2006]. In this paper, we investigate the complexity of trick-taking card games. The class of trick-taking card games encompasses numerous popular games such as CONTRACT BRIDGE, HEARTS, SKAT, SPADES, TAROT, and WHIST. 1

The rules of the quintessential trick-taking card game are fairly simple. A set of players is partitioned into teams and arranged around a table. Each player is dealt a given number of cards t called hand, each card being identified by a suit and a rank. The game consists in t tricks in which every player plays a card. The first player to play in a given trick is called lead, and the other players proceed in the order defined by the seating. The single constraint is that players should follow the lead suit if possible. At the end of a trick, whoever put the highest ranked card in the lead suit wins the trick and leads the next trick. When there are no cards remaining, after t tricks, we count the number of tricks each team won to determine the winner. 2

1 A detailed description of these games and many other can be found on http://www.pagat.com/class/trick.html.

Assuming that all hands are visible to everybody, is there a strategy for the team of the starting player to ensure winning at least k tricks?

Despite the demonstrated interest of the general population in trick-taking card games and the significant body of artificial intelligence research on various trick-taking card games [Buro et al., 2009; Ginsberg, 2001; Frank and Basin, 1998; Kupferschmid and Helmert, 2006; Luˇstrek et al., 2003], most of the corresponding complexity problems remain open. This stands in stark contrast with other popular games such as CHESS or GO, the complexity of which was established early [Fraenkel and Lichtenstein, 1981; Lichtenstein and Sipser, 1980; Robson, 1983].

There are indeed very few published hardness results for card games. We only know of a recent paper addressing UNO [Demaine et al., 2010], a card game not belonging to the category of trick-taking card games, and Frank and Basin's result on the best defense model [2001]. They show that given an imperfect information game tree and an integer w, and assuming the opponent has perfect information, determining whether one has a pure strategy winning in at least w worlds is NP-complete.

As for tractability, after a few heuristics were proposed [Kahn et al., 1987], W¨astlund's performed an in-depth combinatorial study on fragments of perfect information two-hands WHIST proving that some important fragments of trick-taking card games are polynomial [W¨astlund, 2005a; 2005b].

Note that contrary to the hypotheses needed for Frank and Basin's NP-completeness result [2001], this paper assumes perfect information and a compact input, namely the hands and an integer k. There are several reasons for focusing on perfect information. First, it provides a lower bound to the imperfect information case when compact input is assumed. More importantly, perfect information trick-taking card games actually do appear in practice, both among the general population in the form of DOUBLE DUMMY BRIDGE problems, but also in research as perfect information Monte Carlo sampling is used as a base component of virtually every state-of-theart trick-taking game engine [Levy, 1989; Ginsberg, 2001; Sturtevant and White, 2006; Long et al., 2010].

2 There are more elaborate point-based variants where tricks might have different values, possibly negative, based on cards comprising them. We focus on the special case where each card has the same positive value.

It is rather natural to define fragments of this class of decision problems, for instance, by limiting the number of different suits, the number of hands, or even limiting the number of cards within each suit. We define the lattice of such fragments in Section 2. In Section 3, we show that the general problem is PSPACE-complete and it remains so even if we bound the number of cards per suit. The proof is a rather straightforward reduction from Generalized Geography (GG). Our main result is a more involved reduction from GG to address the fragment with bounded number of hands; it is presented in Section 4. In Section 5, we provide a new tractability result for two hands and four cards per suit. We conclude by providing a graphical summary of the complexity landscape in trick-taking card games and putting forward a few open problems.

2 Definitions and notation

2.1 Trick-taking game

Definition 1. A card c is a pair of two integers representing a suit (or color) s(c) and a rank r(c). A position p is defined by a tuple of hands h = (h1, . . . , hη), where a hand is a set of cards, and a lead turn τ ∈ [1, η]. We further assume that all hands in a given position have the same size ∀i, j ∈ [1, η], |hi| = |hj | and do not overlap: i ̸= j ⇒ hi ∩ hj = ∅.

Definition 2. Playing a trick consists in selecting one card from each hand starting from the lead: cτ ∈ hτ , cτ+1 ∈ hτ+1, . . . , cn ∈ hη, c1 ∈ h1, . . . , cτ-1 ∈ hτ-1. We also require that suits are followed, i.e., each played card has the same suit as the first card played by hand τ or the corresponding hand hi does not have any card in this suit: s(ci) = s(cτ ) ∨ ∀c ∈ hi, s(c) ̸= s(cτ ).

An example position with 4 hands and 12 total cards is given in Figure 1. The position is written as a diagram, so for instance, hand h3 contains 3 cards {(s1,A), (s1,J), (s2, 2)}.

Definition 3. The winner of a trick is the index corresponding to the card with highest rank among those having the required suit. The position resulting from a trick with cards C = {cτ , . . . , cτ-1} played in a position p can be obtained by removing the selected cards from the hands and setting the new lead to the winner of the trick.

In the example in Figure 1, the lead is to 1. A possible trick would be (s3,A), (s1,Q), (s2, 2), (s3,Q); note that only hand h4 can follow suit, and that 1 is the winner so remains lead.

Definition 4. A team mapping σ is a map from [1 . . . η] to {A, B} where η is the number of hands. A (perfect information, plain) trick-taking game is pair consisting of a position and a team mapping σ.

For simplicity of notation, team mappings will be written as words over the alphabet {A,B}. For instance, 1 ↦→ A, 2 ↦→ B, 3 ↦→ A, 4 ↦→ B is written ABAB.

Definition 5. A trick is won by team A if its winner is mapped to A with σ. The value of a game is the maximum number of tricks that teamA can win against teamB.

The value of the game presented in Figure 1 is 3 as team A can ensure making all remaining tricks with the following strategy known as squeeze. Start with (s3,A) from h1 and play (s2, 2) from h3, then start the second trick in the suit where h2 elected to play.

2.2 Decision problem and fragments

The most natural decision problem associated to trick-taking games is to compute whether the value of a game is larger or equal to a given value ν. Put another way, is it possible for some team to ensure capturing more than ν tricks? We will see in Section 3 that the general problem is PSPACE-hard, but there are several dimensions along which one can constrain the problem. This should allow to better understand where the complexity comes from.

Teammappings only allow team mappings belonging to a language L ⊆ {A, B}∗ , typically L = Li = {(AB)i} or L = = {A,B}∗ .

Number of suits the total number of distinct suits s is bounded by a number s = S, or unbounded s = .

Length of suits the maximal number of ranks over all suits l is bounded by a number l = L, or unbounded l = .

Symmetry for each suit, each hand needs to have the same number of cards pertaining to that suit.

The fragments of problems respecting such constraints are denoted by B(L, s, l) when symmetry is not assumed. If symmetry is assumed, then we denote the class by BM(L, s, l). The largest class, that is, the set of all problems without any restriction is B( , , ).

Example 1. The class of double-dummy Bridge problems is exactly B(L2, 4, 13).

Proposition 1. B( , , ) is in PSPACE.

Proof. The game ends after a polynomial number of moves. It is possible to perform a minimax search of all possible move sequences using polynomial space to determine the maximal number of tricks team A can achieve.

2.3 Generalized Geography

Generalized Geography (GG) is a zero-sum two-player game over a directed graph with one vertex token. Players take turn moving the token to an adjacent vertex and thereby removing the origin vertex. The player who cannot play anymore loses. Figure 2 presents an instance of GG on a bipartite graph.

Deciding the winner of a GG instance is PSPACEcomplete [Schaefer, 1978], and GG was used to prove PSPACEhardness for numerous games including GO [Lichtenstein and Sipser, 1980], OTHELLO [Iwata and Kasai, 1994], AMAZONS [Furtak et al., 2005], UNO [Demaine et al., 2010]. Lichtenstein and Sipser have shown that GG remains PSPACE-hard even if the graph is assumed to be bipartite [1980].

3 Unbounded number of hands

We present a polynomial reduction from bipartite GG to B( , , ). An instance of GG on a bipartite graph is given by (G = (VA ∪ VB, EAB ∪ EBA), v1) where v1 ∈ VA denotes the initial location of the token. Let m = mAB +mBA the number of edges and n the number of vertices. We construct an instance of B( , , ) using m+ 2 suits, and n + 2 hands as follows. Each vertex v ∈ VA (resp. ∈ VB) is encoded by a hand hv owned by team A (resp. B). We add two additional hands, hand hA for teamA and hB for teamB.

Each edge (s, t) ∈ EAB (resp. EBA) is encoded by a suit ss,t of length 5, for instance {AKQJT}. The cards in suit ss,t are dealt such that hand hs receives JT, hand ht receives A, and hand hA (resp. hB) receives KQ. We add two additional suits sA and sB. sA (resp. sB) is dealt such that hA (resp. hB) receives 2mBA + 1 (resp. 2mAB + 1) cards of highest rank. Each hand hv, v ∈ VB (resp. v ∈ VA) is filled with low-rank cards in suit sA (resp. sB) until a total of t = 2m+ 1 cards. Low-rank cards are written x when the exact rank matters not.

The game starts in the hand hv1 and team A wins if it makes 2mBA + 1 tricks, or equivalently, team B wins if it makes t - 2mBA = 2mAB + 1 tricks. We denote that instance of B( , , ) by φ(G, v1). Figure 3 shows the reduction of an instance of GG to a trick-taking card game in B( , , ).

Lemma 1. Team A can ensure that as long hB does not win a trick, the sum of the number of tricks won by team A and the number of cards in suit sA in hand hA is greater or equal to 2mBA + 1. The converse holds for team B.

Proof. Hand hA only discards when a suit sv′ ,v is lead with v ∈ VA, in that case hv plays an ace and wins the trick.

Thus, as soon as hand hA gets the lead, team A achieves its goal. As a result, playing in suit sA is a losing move for team B. Also, if hand hv, v ∈ VA ever gets the lead again after having played in suit sv,v′ , then it can give the lead to hand hA through playing sv,v′ once more. Therefore, after hand hv is in the lead, playing in any suit sv′ ,v effectively becomes a losing move for any v′ ∈ VB.

Lemma 2. If the first player has a winning strategy in G, then team A can make 2mBA + 1 tricks in φ(G).

The same result also applies to team B. Therefore team A has a winning strategy in φ(G, v1) if and only if the first player has a winning strategy in the instance (G, v1) of GG. The reduction is thus complete, leading to PSPACE-hardness.

Note that the previous reduction can be slightly adapted so that the number of cards in each suit is at most 5. Suits sA and sB can indeed be split into multiple equivalent suits of length at most 5 without essentially changing the reduction.

Theorem 2. B( , , 5) is PSPACE-complete.

4 Bounded number of hands

The trick balance in an intermediate position is the number of tricks made by team A so far minus the number of tricks made by team B so far.

The basic idea of this reduction is that we have a termination gadget that allows both team to end the game by splitting the remaining tricks evenly. However, using the termination gadget comes with a small cost. So each team tries to achieve a sufficiently high trick balance before terminating the game. The termination gadget involves two suits sA and sB and four hands h3 through h6 that do not otherwise influence the game.

Besides the termination gadget, we have two hands, one per team, and one suit sv for each vertex v of the GG instance. A team, say A, can threaten to increase the trick balance in their favour by playing in the attacking gadget of a suit sv. This can only be defended by having the opponent team, say B, counter-attacking in a suit sv′ . B can choose sv′ , but for the defense to be successful, v′ needs to be a neighbor of v in GG. After this exchange is performed, team B has priority to attack but can only attack in suit sv′ 's attacking gadget. The same process goes on until the defending team cannot find an appropriate counter-attacking suit. At that moment, the attacking teammanages to increase the trick balance enough to safely terminate the game in their favour. We see that picking the counter-attacking suits emulates a game of GG on G.

Let G = ((V = VA ∪ VB, E), v1) be a directed bipartite graph and one of its vertices, v1 ∈ VA, be an instance of GG. Let n = nA +nB be the number of vertices, and N(v) denote sB 2t - 5ω/2 +1 2

Figure 4: The termination gadget. x 2 -- x′ is a shorthand for x, x - 2, . . . , x′ + 2, x′ , and x--x′ is a shorthand for x, x - 1, . . . , x′ + 1, x′ . Only the suits involved are displayed.

the neighbors of a vertex v, {v′ , (v, v′ ) ∈ E}. We construct in polynomial time an equivalent instance of B(L3, , ) using 6 hands and s = n + 2 suits. In the instance we create, the seating order does not have any influence so we will represent gadgets and positions simply by listing the cards in each hand in a table. In the following, we will set ω = 24n and use t to represent the total number of tricks to be made. 3 TeamAwins if they make strictly more than k = t/2 + 3ω/8 tricks.

4.1 Presentation of the gadgets

Unless the gadgets are not symmetric, we only describe one team's version of the gadgets. Assume an arbitrary ordering on the vertices in VA and in VB, that is VA = {v1, v2, . . . vnA } and VB = {v′1 , v′2 , . . . v′nB }.

The termination gadget. The suit sA is possessed only by hands h1 , h3 and h4. Hands h3 and h4 have 2t interleaved cards, and hand h1 has just enough cards of lowest ranks so that h1 has a total of t cards after all other gadgets have been taken into account. Thus, hands h3 and h4 have only cards in the suit sA. The suit sB is owned only by hands h2, h5 and h6. and is displayed similarly for hands h2, h5, and h6, except that h5 has 5ω/2 top cards to cash before 2t - 5ω/2 cards are interleaved (see Figure 4).

The following two lemmas allow us to focus on hands h1 and h2 in the remaining of this reduction.

Lemma 3. If h1 leads and the trick balance is at least 3ω/4, then team A can ensure winning the game.

Proof. Team A can play in the suit sA then the rest of the game will hold between hands h3 and h4. Hence team A wins half of the remaining tricks for a total greater than k.

Lemma 4. If h2 leads and the trick balance is at most -7ω/4, then team B can ensure winning the game.

The e|w-block. An e|w-block in a suit s for team A is a gadget allowing that team to cash (win) w tricks by first sacrificing (establishing) e tricks in the suit. In other words, hand h2 has the e top cards, h1 has the e +w following top cards, and h2 has w cards of lowest ranks x to avoid any discarding. Figure 5 provides an example of a 3|4-block.

3 t's exact value can be computed and is polynomial in the input.

We can concatenate several e|w-blocks for the same team in the same suit. For instance, Figure 6 shows how blocks are concatenated and provides a more concise notation.

Given a vertex v ∈ V , a concatenation of e|w blocks with various values for e allows to encode the index of v in an attacking gadget. It also allows to encode which vertex v′ , v is adjacent to in a counter-attacking gadget via their indices. If v ∈ VB (resp. VA), the (counter-)attacking gadgets will be for team A (resp. B) and we say that the corresponding suit is a defensive suit for team B (resp. A). The e|w-blocks we need in the following have e an integer in [1, . . . , 6], and w a fraction of ω.

The counter-attacking and attacking gadgets. Consider two words over {0, 1} for each suit sv with v ∈ VA. The attacking word for suit svi is a such that a(0) = 1, a(nA + 1) = 0, and for each j ̸= i, j ∈ [1, nA], a(j) = 0 and a(i) = 1. The counter-attacking word for suit svi is c such that c(0) = 1, c(nB + 1) = 1, and for each j ∈ [1, nB], if vi ∈ N(vj) then c(j) = 1 else c(j) = 0.

The gadgets can be built by looking at adjacent letters in these words. If these letters are 11 or 00, put a 2|ω-block. If they are 10, put 3|ω-block, and if they are 01, put 1|ω. We thus define for each suit sv, a counter-attacking gadget C(v) and an attacking gadget A(v). The words and gadgets for the GG instance in Figure 2 are given in Figure 7.

Figure 7: Counter-attacking and attacking gadgets in the instance corresponding to Figure 2.

Hand Suit Ranks

parts of the A(v) gadgets is equal to 2(nA + 1) + 1 and that of the C(v′ ) gadgets is 2(nA + 1). Similarly, the sum of the w parts is ω(nA + 1). The same holds for A(v′ ) and C(v), replacing nB with nA.

In the next two lemmas, we assume optimal play from both teams subject to leading from a single suit.

Lemma 5. Assume the initial trick balance is b, teamB starts, team A only leads cards from A(v), and team B only leads cards from C(v′ ). The trick balance remains ≥ b - ω. If v′ ∈ N(v), it remains ≤ b + 1, else it reaches b + ω.

Proof. It is optimal to play blocks from the highest to the lowest ranked when in lead, and to take any trick offered when not in lead. Let i be the index of v. Observe that teamA needs to 2j+1 tempi to establish the jth block if j ̸= i, and 2i tempi for the ith block. 4 TeamB needs 2j tempi to establish the jth block if v′ ∈ N(vj), and 2j + 1 tempi otherwise.

Lemma 6. Assume the initial trick balance is b, teamA starts, team A only leads cards from C(v), and team B only leads cards from A(v′ ). The trick balance remains ≤ b + ω. If v ∈ N(v′ ), it remains ≥ b - 1, else it reaches b - ω.

When team A attacks in suit sv and team B does not play in an admissible counter-attacking suit, team A wins ω tricks (Lemma 5) and wins the game by termination (Lemma 3). Conversely, if team A does not play in a neighboring suit when team B attacks, team A loses (Lemma 4, 6). Thus, Lemmas 5 and 6 give the graph structure to the suits.

Combining the attacking and counter-attacking gadgets. We now complete the picture so that the assumptions of Lemmas 5 and 6 are met.

In each suit sv of hand h1 (resp. h2) but the one corresponding to the starting vertex v1, we start by the counter-attacking gadget C(v) surrounded by the fixed sequences 5|ω 1|3ω/2 and 2|ω (resp. 4|ω/2 3|2ω and 2|2ω) and call it first part of the suit. We then add to each suit, including sv1 , the attacking gadget A(v) surrounded by the fixed sequences 4|ω 3|3ω/2 1|3ω/2 and 1|ω (resp. 6|ω 1|3ω/2 and 1|3ω/2) and call it second part of the suit. Figure 8 displays the combination resulting from the GG instance in Figure 2; h1 also has cards in suits sv1 , sv2 , and sv3 but they are not displayed as per the notation of Figure 5.

These fixed starting sequences ensure that once a team leads in suit sv, they will continue leading only in sv until the suit is emptied. They also ensure, that while one team chooses the attacking suit first, the opponent actually starts leading in the counter-attacking gadget.

4 We use the expression use a tempo as short for lose a trick lead.

The ending sequences, on the other hand, ensure that after the attacking suit sv and the first part of the counter-attacking suit sv′ have been emptied, the situation corresponds to the reduction from the GG instance with the edges adjacent to v removed and v′ as a starting vertex.

Lemma 7. Leading in defensive suits can never help to win.

Proof. A team cannot cash more than 6n tricks in defensive suits. As the fractions of ω are all discretised by 1/4, and 6n = ω/4, this cannot participate in winning.

Ensuring the teams simulate GG. Let P be a position resulting from one constructed from a GG instance. Assume there exists a suit sv (and v the corresponding vertex in the original GG instance), such that for any suit s different from sA, sB, and sv, s is dealt among hands h1 and h2 so as to form a first part and a second part in h1 or in h2. If sv forms only a second part in h2 (resp. h1), h2 (resp. h1) is on the lead, and the trick balance is ω/2 (resp. 0), then we say that P is A-clean (resp. B-clean) and sv is the current starting suit.

Lemma 8. Let P be a B-clean position with starting suit sv, and a suit sv′ such that v′ ∈ N(v). Assume teamA can ensure winning with optimal play from P. If team B only leads from suit sv′ and teamA only leads from sv until sv is empty, then we reach a A-clean position P ′ with sv′ as the starting suit. Moreover, team A can ensure winning from P ′ .

Proof. As P is a B-clean position, the trick balance is 0 and the lead is on h1. Suppose team A plays in a suit su with u ̸= v and u ∈ VA, before having established and cashed the ω tricks of the 6|ω-block of the color sv (first block of the second part of that color). After 6 tempi, teamB has had time to cash the 5ω/2 tricks of the two first block 5|ω and 1|3ω/2 of the color sv′ , while team A has at most cash the ω/2 winners of the first block 4|ω/2 of su. Consequently, the balance trick takes a value smaller than -2ω and team B wins accordingly to Lemma 4. Thus, team A has to use the 6 first tempi to play in sv. At this point, teamB threatens to enter in C(v′ ) while team A cannot yet enter A(v). That forces team A to play again in v. Then, teamB enters C(v′ ) immediately followed by team A cashing 3ω/2 tricks (the trick balance is now 0) and entering A(v). Note that if teamA plays in another suit than v, team B will win by persisting in C(v′ ) since the trick balance will go be beneath -7ω/4. According to Lemma 5, if team A plays solely in A(v), the trick balance is never losing for any team. In the end, the balance is -ω, the lead is in h2 and the only remaining cards in h1 in the color sv are 3ω/2 winners. So the trick balance is virtually ω/2 and we reach a A-clean position winning for team A.

Lemma 9. Let P be a A-clean position with starting suit sv′ . Assume team A can ensure winning with optimal play from P. Then there exists a suit sv such that v ∈ N(v′ ) and such that if teamB only leads from suit sv′ and teamA only leads from sv until sv′ is empty, then we reach a B-clean position P ′ with sv as the starting suit. Moreover, team A can ensure winning with optimal play from P ′ .

Lemma 10. Let G be a GG instance, and consider the corresponding B(L3, , ) instance B. If teamA can win in B, then the second player in G does not have a winning strategy.

Proof. Let σ bet a strategy for the second player in G and let us show that σ is not winning. Assume team B plays according to σ in the B instance. Team A can answer by keeping simulating GG and still ensure winning (Lemma 8 and 9), thereby generating a strategy in GG. Since there are only finitely many suits to be emptied, we will reach a B-clean position with starting suit sv and without any suit sv′ such that v′ ∈ N(v). This shows that the corresponding GG situation is lost and that σ is not a winning strategy.

Lemma 11. Let G be a GG instance, and consider the corresponding B(L3, , ) instance B. If teamB can win in B, then the first player in G does not have a winning strategy.

Proof. Similar proof with the dual to Lemmas 8 and 9.

These two propositions lead us to our main result.

Theorem 3. The B(L3, , ) fragment is PSPACE-hard.

5 Tractability results

In this part, we present a positive result when there is only one hand per team and when the number of cards in any suit is bounded by 4. Only a few positive results on trick taking card games are known. The two following are the main ones.

Theorem 4 (W¨astlund [2005a]). B(L1, 1, ) is in P.

We now focus on the B(L1, , 4) fragment. Assume for the sake of simplicity and wlog, that after each trick a normalization process takes place so that suits with 4 and 3 cards have ranks in {A, K, Q, J} and {A, K, Q} respectively.

A suit s is controlled by a player, if they can play in the suit s and make all tricks in s.

We define a strategy σ as follows. When a player is not leading and can follow suit, they play the lowest card ensuring the trick is made if any, or the lowest card overall otherwise. Otherwise suits are categorized and priority are associated to each category for leading as well as for discarding. The categories, their priority and the associated card to lead/discard is displayed in Table 1.

Lemma 12. The strategy σ is optimal.

The strategy σ can be computed in polynomial time. We can compute the total number of tricks a team can make by having both players apply σ. This leads to the desired result.

Proposition 2. B(L1, , 4) is in P.

6 Conclusions and perspectives

In his thesis, Hearn proposed the following explanation to the standing lack of hardness result for BRIDGE [2006, p122].

There is no natural geometric structure to exploit in BRIDGE as there is in a typical board game.

Theorem 3 achieves a significant milestone in that respect. The gadgets in the reduction indeed show that it is possible to find a graphical structure within the suits. From all, the attacking and counter-attacking gadgets stand as the central idea, giving an adjacency list structure to suits, by means of a precise race to establishment. Termination gadgets make those races decisive.

Finding a PSPACE-hardness proof necessitating only 2 hands is very appealing. Another interesting problem is to find a hardness proof with a bounded number of suits. These two new open problems along with W¨astlund's tractability results, and the results derived in this paper are put in perspective in Figure 9 which displays the complexity landscape for noteworthy fragments of B(L, s, l).

Many actual trick-taking card games also feature a trump suit and potentially different values for tricks based on which cards were involved. Such a setting can be seen as a direct generalization of ours, but remains bounded. Therefore our PSPACE-completeness results carry over to point-based tricktaking card games involving trumps.