3
$\begingroup$

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

$\endgroup$
4
  • $\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
    Jan 21 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
    Jan 21 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
    Jan 21 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
    Jan 21 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.