7
\$\begingroup\$

I was hoping some one could point me in the right direction about what type of AI you would use for a Spades game? For instance, would you create a behavioral tree or would you implement some other type of AI concept. I'm fairly new to AI which is why I'm hoping to get some AI vets to chime in.

\$\endgroup\$
1
  • \$\begingroup\$ This is a really broad question... the AI you'd use depends heavily on the type of game, and the problem that needs to be solved. Without more details, it's not really suited for the Q&A format. It might be better to ask this in the chat. \$\endgroup\$
    – thedaian
    Sep 29 '11 at 20:36
7
\$\begingroup\$

I once programmed AI for Tarneeb, a card game very similar to Spades. The person I was working with wanted to do a pattern recognition thing involving lots of stored games and stats on the outcome based on what moves were done in different situations. In essence, the AI would become better over time the more games it played. However, from playing many hands and analyzing my own thought process, I determined that there were just a small number of "algorithms" I would employ to figure out what card I would play.

Thus the approach I took was to have the computer use a different algorithm depending on the situations, In each case it was pretty straightforward to go from the computer's current hand to deciding what play to make.

The situations were:

Bidding:

  1. making the first bid,
  2. making a bid after the first

Playing:

  1. playing a new trick with Spades in hand,
  2. playing a new trick without Spades,
  3. playing into an already started trick with Spades,
  4. playing into an already started trick without any Spades.
\$\endgroup\$
2
\$\begingroup\$

The current state of the art AI for trick-taking games such as Spades is a search algorithm like MCTS/UCT combined with Supervised Learning [1].


My implementation of a Spade agent uses several heuristics, Monte-Carlo sampling and Supervised learning. My agent is stronger than recreational humans, but weaker than professional players. I describe it in my paper: https://ecai2020.eu/papers/235_paper.pdf

Another source is AI-factory, they describe their Spades agents in a series of (5) papers, I would start from: Intergrating MCTS with knowladge based methods to create engaging play in commercial mobile game - AAAI13. See also their Article List on their site.

Note that an agent is a coupling of two completely separate algorithms: bidding and playing. From my experience, an agent that uses just heuristics can get to a level of an intermediate human. If you go in that path then you need to write a heuristic for each situation (there are quite a few), some of the parameters that need to be considered:

  • In the bid phase: your hand, bids by other players, nil bids, scores.
  • In the playing phase: first trick, leading/2/3/4th in the trick, number of played cards from that suit, can we take this trick, can we set a nil opponent, did we/opponents already made our/thier contract.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ lol I love that you put more technical language (eg. "heuristics" is a better term than my quote "algorithms") to my hand-wavy answer from years ago. \$\endgroup\$
    – jhocking
    Nov 9 '21 at 17:30
0
\$\begingroup\$

As thedaian said, this is indeed too broad of a question. But, for starters, you can have a look at what most board/cards games use: Minimax.

The trick is to have a state of the game and being able to properly evaluate how good in a position a given player is. Once you have solved this step, then you simply emulate X steps ahead to choose the best path the player should go.

\$\endgroup\$
3
  • 6
    \$\begingroup\$ Minimax, or minimax alone, is not a very common strategy in games with uncertainty or asymmetric information. The search space diverges far too drastically and standard pruning (e.g. alpha-beta) is no help in reducing it. I do not think the question has scope issues (although it did have a typo); I do think you have tried to answer a far more general question than was being asked, and given a bad answer as a result. \$\endgroup\$
    – user744
    Sep 29 '11 at 23:31
  • \$\begingroup\$ No disagreement there. \$\endgroup\$
    – pek
    Sep 29 '11 at 23:38
  • \$\begingroup\$ Minimax is mostly good in 2-player games. The current state of the art for Trick-taking-games like spades is Monte Carlo Tree Search (MCTS) with Supervised learning. \$\endgroup\$
    – Cohensius
    Nov 10 '21 at 8:33
-2
\$\begingroup\$

Use expectimax (Russell and norvig Artificial intelligence 3rd edition). Alpha beta is possible with bounded evaluation function values)

\$\endgroup\$

You must log in to answer this question.

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