Answers.Body: <p>Since no answers to my question were made, I will try to answer it myself, however while I do write AI agents, am not an expert.</p>
  <p>Trick-taking games are too large to be solved with current search algorithms and computation capabilities <a href="https://arxiv.org/abs/1905.10911" rel="nofollow noreferrer">[RSBS19]</a>.
  The reason is the following:</p>
  <ol>
  <li><p>Counterfactual Regret Minimization (CFR) is the leading framework for solving large imperfect information games.<a href="https://proceedings.mlr.press/v97/brown19b.html" rel="nofollow noreferrer">[BLGS19]</a></p>
  </li>
  <li><p>CFR requires building strategies for all players and iterating over all information sets.<a href="https://proceedings.neurips.cc/paper/2007/file/08d98638c6fcd194a4b1e6992063e944-Paper.pdf" rel="nofollow noreferrer">[ZJBP07]</a></p>
  </li>
  <li><p>CFR reached super-human level in poker, but does not work well in Spades and other trick-taking games because:</p>
  <p>(a) Large number of information sets. My estimation for Spades is <code>10^58</code>.</p>
  <p>(b) No good abstractions (found yet). While for comparison, in Poker abstractions significantly reduce the size of the game trees.<a href="https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewPaper/1876" rel="nofollow noreferrer">[LSBF10]</a></p>
  </li>
  </ol>
  <hr />
  <ul>
  <li><p>After improving <a href="https://ecai2020.eu/papers/235_paper.pdf" rel="nofollow noreferrer">my Spades-agent</a>, it wins more than 60% of her
  games Vs recreational players. Unfortunately, I never tested
  her Vs experts.</p>
  </li>
  <li><p>If DeepMind or someone in their caliber will try to make a super-human trick-taking agent, I guess that they will succeed.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-23T00:45:11.993Z
Answers.Text: Very interesting and the point about abstractions seems very pertinent :) Regarding number of information sets - I guess it's probably accurate to say that most trick-taking games like Spades/Hearts/Whist will have more information sets than Poker, because of the larger number of cards in players' hands?
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-23T07:38:45.727Z
Answers.Text: @MobeusZoom, exactly.  I was also interested about the size of poker, in  ​https://ai.stackexchange.com/q/26637/4335 I state what I found, and what I did not.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-23T19:07:04.870Z
Answers.Text: Made a couple of comments there. It's worth noting that even if Poker with a large stack-size could have more game states than a game like a Spades, I'd guess Poker decisions which differ only slightly in the continuous space of bids yield very similar effects (so we can get very close to equilibrium playstrength without a full solution).
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T08:32:01.137Z
Answers.Text: You are right, they discretized the bets into several buckets. For example: 1/3 pot, 1/2 pot 2/3 pot, pot, 2pots, 4pots+.  A bet of 100\$ and a bet of 101\$ are treated the same.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T07:46:29.397Z
Answers.Text: Thats awesome information! Thanks for sharing!
Answers.UserDisplayName: FillipSmith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T19:43:00.617Z
Answers.LastActivityDate: 2022-01-23T14:37:08.407Z
Answers.LastEditDate: 2022-01-23T14:37:08.407Z
Answers.UserDisplayName: Cohensius
Body: <p>AI reached a super-human level in many complex games such as <a href="https://www.sciencedirect.com/science/article/pii/S0004370201001291" rel="nofollow noreferrer">Chess</a>, <a href="https://www.nature.com/articles/nature24270" rel="nofollow noreferrer">Go</a>, <a href="https://science.sciencemag.org/content/365/6456/885.abstract?casa_token=nyS4YED061UAAAAA:-YZnlUJVkOPOC7UOVxgUyaT_4XK_QqXMlJMovMSWyCxoAyCCzSB1xTSndhlu2IGPU1fXj1HDdvLunIc" rel="nofollow noreferrer">Texas hold'em Poker</a>, <a href="https://openai.com/projects/five/" rel="nofollow noreferrer">Dota2</a> and <a href="https://www.nature.com/articles/s41586-019-1724-z" rel="nofollow noreferrer">StarCraft2</a>. However it still did not reach this level in trick-taking card games.</p>
  <p>Why there is no <strong>super-human</strong> AI playing imperfect-information, multi-player, trick-taking card games such as Spades, Whist, Hearts, Euchre and Bridge?</p>
  <p>In particular, what <strong>are the obstacles</strong> for making a super-human AI in those games?</p>
  <hr />
  <p>I think those are the reasons that makes Spades hard for AI to master:</p>
  <ol>
  <li><p><strong>Imperfect information</strong> games pose two distinct problems: move selection and inference.</p>
  </li>
  <li><p>The size of the game tree isn't small, however larger games have been mastered.</p>
  <p>I. <strong>History size</strong>: <span class="math-container">$14!^4 = 5.7\cdot10^{43}$</span></p>
  <p>II. There are <span class="math-container">$\frac{52!}{13!^4}= 5.4\cdot10^{28}$</span> possible initial states.</p>
  <p>III. Each initial information set can be completed into a full state in <span class="math-container">$\frac{39!}{13!^3}=8.45\cdot10^{16} $</span> ways</p>
  </li>
  <li><p><strong>Evaluation only at terminal states</strong>.</p>
  </li>
  <li><p><strong>Multiplayer</strong> games:</p>
  <p>I. harder to prune - search algorithms are less effective</p>
  <p>II. opponent modeling is hard</p>
  <p>III. Goal choosing - several goals are available, need to change goals during rounds according to the reveled information.</p>
  </li>
  <li><p>Agent need to coordinate with a partner: <strong>conventions</strong>, <strong>signals</strong>.</p>
  </li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T00:26:25.947Z
Comments.Text: Isn't poker an imperfect information and multi-player game? I think so. Therefore, I guess that you're only interested in knowing why games like spades (that are apparently called "trick-taking") have not yet been "solved" by an AI. Isn't a game like poker more difficult than spaces? I don't know because I don't think I'm familiar with spades, but I'm certainly familiar with 1 version of poker. If yes, then maybe there isn't yet some AI that solves spaces simply because nobody got interested in the game. This is really just a guess.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T07:06:00.663Z
Comments.Text: There been extensive research on trick-tacking games, especially Bridge. 
  Research on Spades have been made mostly by Sturtevant at el. https://webdocs.cs.ualberta.ca/~nathanst/papers/mpuct_icga.pdf
  and AI factory https://core.ac.uk/download/pdf/157854537.pdf
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T16:49:30.053Z
Comments.Text: The first paper has more than 10 years, while the second is more recent. Just to have an idea, because now I don't have the time to read them, have they (in the second example, at least) tried to use recent techniques that have also been used in the case of say poker or AlphaGo, or are they using maybe some more traditional approaches? To be honest, I'm not familiar with the _all_ details not even of AlphaGo, but, as far as I recall, it uses MCTS and RL. Most of the others that you mention that achieved superhuman performance probably use these techniques too (at least, RL).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T20:27:24.287Z
Comments.Text: Yes, they both tried MCTS / UCT.  I have used MCTS and Supervised learning for the bidding phase at https://ecai2020.eu/papers/235_paper.pdf   however on my implementation, UCT is helpful in the playing phase only close to the round's end (~5 last tricks) partly because of a strict time/computation limit.
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-20T22:51:05.747Z
Comments.Text: @Cohensius I noticed you yourself have published a paper on this (https://arxiv.org/abs/1912.11323) so perhaps we should be asking you this question! I'm very curious if you have an idea why Poker has been solvable for AI to superhuman standards (DeepStack, Libratus, Pluribus) but trick-taking cardgames like Spades, Hearts, etc cannot be addressed by the same approaches?
Comments.UserDisplayName: Mobeus Zoom
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-22T18:40:39.777Z
Comments.Text: @MobeusZoom, I will add my thoughts, but I am not an AI-expert (yet) so I might be way wrong.
Comments.UserDisplayName: Cohensius
Tags: <gaming><state-of-the-art><computational-complexity><imperfect-information><games-of-chance>
Title: Why multiplayer, imperfect information, trick-taking card games are hard for AI?
UserDisplayName: Cohensius
ThreadText: # Why multiplayer, imperfect information, trick-taking card games are hard for AI?
  
  (Asked by: username_0 on 2020-12-29)
  
  AI reached a super-human level in many complex games such as [Chess](https://www.sciencedirect.com/science/article/pii/S0004370201001291), [Go](https://www.nature.com/articles/nature24270), [Texas hold'em Poker](https://science.sciencemag.org/content/365/6456/885.abstract?casa_token=nyS4YED061UAAAAA:-YZnlUJVkOPOC7UOVxgUyaT_4XK_QqXMlJMovMSWyCxoAyCCzSB1xTSndhlu2IGPU1fXj1HDdvLunIc), [Dota2](https://openai.com/projects/five/) and [StarCraft2](https://www.nature.com/articles/s41586-019-1724-z). However it still did not reach this level in trick-taking card games.
  
  Why there is no **super-human** AI playing imperfect-information, multi-player, trick-taking card games such as Spades, Whist, Hearts, Euchre and Bridge?
  
  In particular, what **are the obstacles** for making a super-human AI in those games?
  
  ---
  
  I think those are the reasons that makes Spades hard for AI to master:
  
  1. **Imperfect information** games pose two distinct problems: move selection and inference.
  2. The size of the game tree isn't small, however larger games have been mastered.
  
     I. **History size**: $14!^4 = 5.7\cdot10^{43}$
  
     II. There are $\frac{52!}{13!^4}= 5.4\cdot10^{28}$ possible initial states.
  
     III. Each initial information set can be completed into a full state in $\frac{39!}{13!^3}=8.45\cdot10^{16} $ ways
  3. **Evaluation only at terminal states**.
  4. **Multiplayer** games:
  
     I. harder to prune - search algorithms are less effective
  
     II. opponent modeling is hard
  
     III. Goal choosing - several goals are available, need to change goals during rounds according to the reveled information.
  5. Agent need to coordinate with a partner: **conventions**, **signals**.
  
  **Tags:** gaming, state-of-the-art, computational-complexity, imperfect-information, games-of-chance
  
  > **Comments:**
  > **username_1**: Isn't poker an imperfect information and multi-player game? I think so. Therefore, I guess that you're only interested in knowing why games like spades (that are apparently called "trick-taking") have not yet been "solved" by an AI. Isn't a game like poker more difficult than spaces? I don't know because I don't think I'm familiar with spades, but I'm certainly familiar with 1 version of poker. If yes, then maybe there isn't yet some AI that solves spaces simply because nobody got interested in the game. This is really just a guess.  
  > **username_0**: There been extensive research on trick-tacking games, especially Bridge.  Research on Spades have been made mostly by Sturtevant at el. https://webdocs.cs.ualberta.ca/~nathanst/papers/mpuct_icga.pdf and AI factory https://core.ac.uk/download/pdf/157854537.pdf  
  > **username_1**: The first paper has more than 10 years, while the second is more recent. Just to have an idea, because now I don't have the time to read them, have they (in the second example, at least) tried to use recent techniques that have also been used in the case of say poker or AlphaGo, or are they using maybe some more traditional approaches? To be honest, I'm not familiar with the _all_ details not even of AlphaGo, but, as far as I recall, it uses MCTS and RL. Most of the others that you mention that achieved superhuman performance probably use these techniques too (at least, RL).  
  > **username_0**: Yes, they both tried MCTS / UCT.  I have used MCTS and Supervised learning for the bidding phase at https://ecai2020.eu/papers/235_paper.pdf   however on my implementation, UCT is helpful in the playing phase only close to the round's end (~5 last tricks) partly because of a strict time/computation limit.  
  > **username_2**: @username_0 I noticed you yourself have published a paper on this (https://arxiv.org/abs/1912.11323) so perhaps we should be asking you this question! I'm very curious if you have an idea why Poker has been solvable for AI to superhuman standards (DeepStack, Libratus, Pluribus) but trick-taking cardgames like Spades, Hearts, etc cannot be addressed by the same approaches?  
  > **username_0**: @username_2, I will add my thoughts, but I am not an AI-expert (yet) so I might be way wrong.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2022-01-22. Score: 0
  
  Since no answers to my question were made, I will try to answer it myself, however while I do write AI agents, am not an expert.
  
  Trick-taking games are too large to be solved with current search algorithms and computation capabilities [[RSBS19]](https://arxiv.org/abs/1905.10911).
  The reason is the following:
  
  1. Counterfactual Regret Minimization (CFR) is the leading framework for solving large imperfect information games.[[BLGS19]](https://proceedings.mlr.press/v97/brown19b.html)
  2. CFR requires building strategies for all players and iterating over all information sets.[[ZJBP07]](https://proceedings.neurips.cc/paper/2007/file/08d98638c6fcd194a4b1e6992063e944-Paper.pdf)
  3. CFR reached super-human level in poker, but does not work well in Spades and other trick-taking games because:
  
     (a) Large number of information sets. My estimation for Spades is `10^58`.
  
     (b) No good abstractions (found yet). While for comparison, in Poker abstractions significantly reduce the size of the game trees.[[LSBF10]](https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewPaper/1876)
  
  ---
  
  * After improving [my Spades-agent](https://ecai2020.eu/papers/235_paper.pdf), it wins more than 60% of her
    games Vs recreational players. Unfortunately, I never tested
    her Vs experts.
  * If DeepMind or someone in their caliber will try to make a super-human trick-taking agent, I guess that they will succeed.
  
  > **Comments:**
  > **username_2**: Very interesting and the point about abstractions seems very pertinent :) Regarding number of information sets - I guess it's probably accurate to say that most trick-taking games like Spades/Hearts/Whist will have more information sets than Poker, because of the larger number of cards in players' hands?  
  > **username_0**: @username_2, exactly.  I was also interested about the size of poker, in  ​https://ai.stackexchange.com/q/26637/4335 I state what I found, and what I did not.  
  > **username_2**: Made a couple of comments there. It's worth noting that even if Poker with a large stack-size could have more game states than a game like a Spades, I'd guess Poker decisions which differ only slightly in the continuous space of bids yield very similar effects (so we can get very close to equilibrium playstrength without a full solution).  
  > **username_0**: You are right, they discretized the bets into several buckets. For example: 1/3 pot, 1/2 pot 2/3 pot, pot, 2pots, 4pots+.  A bet of 100\$ and a bet of 101\$ are treated the same.  
  > **username_3**: Thats awesome information! Thanks for sharing!  
  
  ---
  
  