5

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.

Ray
  • 344
  • 4
  • 12
Cohensius
  • 423
  • 3
  • 15

1 Answers1

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]. 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.

Cohensius
  • 423
  • 3
  • 15