---
title: "On the Complexity of Trick-Taking Card Games"
authors:
  - "Edouard Bonnet"
  - "Florian Jamain"
  - "Abdallah Saffidine"
doi: ""
url: "https://ijcai.org/proceedings/2013/79"
pdf: "https://ijcai.org/proceedings/2013/0079.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "482-487"
track: ""
keywords:
---

# On the Complexity of Trick-Taking Card Games

Edouard Bonnet, Florian Jamain, Abdallah Saffidine

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 482-487.

## Abstract

Determining the complexity of perfect information trick-taking card games is a long standing open problem. This question is worth addressing not only because of the popularity of these games among human players, e.g., Double Dummy Bridge, but also because of its practical importance as a building block in state-of-the-art playing engines for Contract Bridge, Skat, Hearts, and Spades. We define a general class of perfect information two-player trick-taking card games dealing with arbitrary numbers of hands, suits, and suit lengths. We investigate the complexity of determining the winner in various fragments of this game class. Our main result is a proof of PSPACE-completeness for a fragment with bounded number of hands, through a reduction from Generalized Geography. Combining our results with Wästlund's tractability results gives further insight in the complexity landscape of trick-taking card games.