5
$\begingroup$

AI reached a super-human level in many complex games such as Chess, Go, Texas hold'em Poker, Dota2 and StarCraft2. 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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Jan 21, 2021 at 0:26
  • 1
    $\begingroup$ There been extensive research on trick-tacking games, especially Bridge. Research on Spades have been made mostly by Sturtevant at el. webdocs.cs.ualberta.ca/~nathanst/papers/mpuct_icga.pdf and AI factory core.ac.uk/download/pdf/157854537.pdf $\endgroup$
    – Cohensius
    Commented Jan 21, 2021 at 7:06
  • 1
    $\begingroup$ 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). $\endgroup$
    – nbro
    Commented Jan 21, 2021 at 16:49
  • $\begingroup$ Yes, they both tried MCTS / UCT. I have used MCTS and Supervised learning for the bidding phase at 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. $\endgroup$
    – Cohensius
    Commented Jan 21, 2021 at 20:27
  • 1
    $\begingroup$ @Cohensius I noticed you yourself have published a paper on this (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? $\endgroup$
    – Mobeus Zoom
    Commented Jan 20, 2022 at 22:51

1 Answer 1

Reset to default
0
$\begingroup$

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]. The reason is the following:

  1. Counterfactual Regret Minimization (CFR) is the leading framework for solving large imperfect information games.[BLGS19]

  2. CFR requires building strategies for all players and iterating over all information sets.[ZJBP07]

  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]

  • After improving my Spades-agent, 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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mobeus Zoom
    Commented Jan 23, 2022 at 0:45
  • $\begingroup$ @MobeusZoom, exactly. I was also interested about the size of poker, in ​ai.stackexchange.com/q/26637/4335 I state what I found, and what I did not. $\endgroup$
    – Cohensius
    Commented Jan 23, 2022 at 7:38
  • 1
    $\begingroup$ 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). $\endgroup$
    – Mobeus Zoom
    Commented Jan 23, 2022 at 19:07
  • $\begingroup$ 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. $\endgroup$
    – Cohensius
    Commented Jan 24, 2022 at 8:32
  • 1
    $\begingroup$ Thats awesome information! Thanks for sharing! $\endgroup$
    – FillipSmith
    Commented Feb 17, 2022 at 7:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .