Answers.Body: <p>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.</p>
  <h2><span class="math-container">$$ 7.36 \cdot 10^{27} \leq |SPADES| \leq 3.09 \cdot 10^{72} $$</span></h2>
  <h1>Upper bound</h1>
  <p>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 <span class="math-container">$|S_0|$</span> by an upper bound on the number of different possible histories <span class="math-container">$|\bar{H}|$</span>.
  <span class="math-container">$$ |SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |\bar{H}| $$</span></p>
  <p>The number of possible starting positions <span class="math-container">$|S_0|$</span> is the number of different ways to deal a 52 cards deck into 4 players
  <span class="math-container">$$|S_0| = \frac{52!}{13!^4} \approx 5.3\cdot10^{28}$$</span></p>
  <p>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
  <span class="math-container">$$ |\bar{S}| = \frac{39!}{13!^3} \approx 8.45 \cdot 10^{16} $$</span></p>
  <p>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
  <span class="math-container">$$|H| \leq {14!}^4 \approx 5.77 \cdot 10^{43}$$</span>
  This is an upper bound since some of those histories violates the rules of the game.</p>
  <p>Therefore, the number of legal positions in Spades is bounded by
  <span class="math-container">$$ |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} $$</span></p>
  <h1>Lower bound</h1>
  <p>In the paper: <a href="https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1876/1942" rel="nofollow noreferrer">Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search</a>, Sturtevant et al. describe a loose lower bound for the size of Skat:</p>
  <blockquote>
  <p>Skat is a 3-player card game with 32 cards, from which 10 are dealt
  to each player. There are <span class="math-container">$$ {32 \choose 10} = 364, 512, 240 $$</span>hands each
  player can have and
  <span class="math-container">$$ H := {22 \choose10} \cdot {12\choose10} = 42, 678, 636 $$</span>
  hands for the other players which is what constitutes an <strong>information set</strong> 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
  <span class="math-container">$$ 10!H \approx 1.54 · 10^{14}$$</span>
  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.</p>
  </blockquote>
  <p>Using the same logic to produce a loose lower bound on the size of Spades tree produce the following:</p>
  <p><span class="math-container">$$ H := {39 \choose 13} \cdot {26 \choose 13} = 8.45 \cdot 10^{16} $$</span></p>
  <p>At the start of the round (before bidding has been made) the number of information sets is lower bounded by
  <span class="math-container">$$ 14!H \approx  7.36 \cdot 10^{27}$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-26T12:59:14.990Z
Answers.LastActivityDate: 2021-02-14T07:23:52.163Z
Answers.LastEditDate: 2021-02-14T07:23:52.163Z
Answers.UserDisplayName: Cohensius
Body: <p>AI reached super-human level in many complex games, including imperfect information games such as <a href="https://science.sciencemag.org/content/365/6456/885.abstract" rel="nofollow noreferrer">six-player no-limit Texas hold’em poker</a>.  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 <a href="https://ai.stackexchange.com/questions/25439/why-multiplayer-imperfect-information-trick-taking-card-games-are-hard-for-ai">Why Trick-Taking games are a challenge for AI</a>.</p>
  <p>An important factor that makes those games a challenge for AI is their size, to be precise lets talk about the <em>State-space complexity</em> which is define as the number of legal game positions reachable from the initial position of the game  <a href="https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf" rel="nofollow noreferrer">[Victor Allis (section 6.2.4)]</a>.</p>
  <h2>What is the size of Spades?</h2>
  
Tags: <game-ai><game-theory><games-of-chance><state-space-complexity>
Title: What is the state-space complexity of Spades?
UserDisplayName: Cohensius
ThreadText: # What is the state-space complexity of Spades?
  
  (Asked by: username_0 on 2021-01-18)
  
  AI reached super-human level in many complex games, including imperfect information games such as [six-player no-limit Texas hold’em poker](https://science.sciencemag.org/content/365/6456/885.abstract). 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](https://ai.stackexchange.com/questions/25439/why-multiplayer-imperfect-information-trick-taking-card-games-are-hard-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)]](https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf).
  
  ## What is the size of Spades?
  
  **Tags:** game-ai, game-theory, games-of-chance, state-space-complexity
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-01-26. Score: 1 | Accepted answer
  
  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.
  
  ## $$ 7.36 \cdot 10^{27} \leq |SPADES| \leq 3.09 \cdot 10^{72} $$
  
  # 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](https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1876/1942), 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}$$
  
  
  ---
  
  