# What is the state-space complexity of Spades?

AI reached super-human level in many complex games, including imperfect information games such as six-player no-limit Texas hold’em poker. However, it still did not reached that level in Trick-taking card games such as Spades, Bridge, Skat and Whist. In a related question, I am asking Why Trick-Taking games are a challenge for AI.

An important factor that makes those games a challenge for AI is their size, to be precise lets talk about the State-space complexity which is define as the number of legal game positions reachable from the initial position of the game [Victor Allis (section 6.2.4)].

## What is the size of Spades?

I have calculated an upper bound and modified a calculation of a lower bound for a similar game. I assume the real size is closer to the upper bound.

# Upper bound

The State-space complexity of Spades can be computed by counting for each possible starting state (deal), all the possible sequences of actions. While that calculation could be hard, an upper bound is easy to achieve by multiplying the number of initial positions $$|S_0|$$ by an upper bound on the number of different possible histories $$|\bar{H}|$$. $$|SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |\bar{H}|$$

The number of possible starting positions $$|S_0|$$ is the number of different ways to deal a 52 cards deck into 4 players $$|S_0| = \frac{52!}{13!^4} \approx 5.3\cdot10^{28}$$

An information set in Spades contains two objects: the player's hand, and the sequence of actions each of the players have made from the start of the round. Before any card is played, each information set (a single hand) can be completed into a full game-state (4 hands) in the following number of ways $$|\bar{S}| = \frac{39!}{13!^3} \approx 8.45 \cdot 10^{16}$$

During a round, each player first decide upon a bid, then choose one out of her 13 cards, than choose one out of 12, etc. Thus, the size of the decision tree, which is the number of histories is bounded by $$|H| \leq {14!}^4 \approx 5.77 \cdot 10^{43}$$ This is an upper bound since some of those histories violates the rules of the game.

Therefore, the number of legal positions in Spades is bounded by $$|SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |H| \leq \frac{52!}{13!^4} \cdot {14!}^4 \approx 3.09 \cdot 10^{72}$$

# Lower bound

In the paper: Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search, Sturtevant et al. describe a loose lower bound for the size of Skat:

Skat is a 3-player card game with 32 cards, from which 10 are dealt to each player. There are $${32 \choose 10} = 364, 512, 240$$hands each player can have and $$H := {22 \choose10} \cdot {12\choose10} = 42, 678, 636$$ hands for the other players which is what constitutes an information set at the start of a game. At the beginning of each trick, the trick leader can choose to play any of his remaining cards. Therefore, there are at least $$10!H \approx 1.54 · 10^{14}$$ information sets. But, from an opponents perspective there are actually 20 or 22 unknown cards that can be lead, so this is only a loose lower bound on the size of the tree. This should clearly establish that even when using short decks it is infeasible to solve even a single game instance of a trick-based card game.

Using the same logic to produce a loose lower bound on the size of Spades tree produce the following:

$$H := {39 \choose 13} \cdot {26 \choose 13} = 8.45 \cdot 10^{16}$$

At the start of the round (before bidding has been made) the number of information sets is lower bounded by $$14!H \approx 7.36 \cdot 10^{27}$$