On the Complexity of Trick-Taking Card Games
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.
@inproceedings{ijcai2013p79,
title = {On the Complexity of Trick-Taking Card Games},
author = {Bonnet, Edouard and Jamain, Florian and Saffidine, Abdallah},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {482--487},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/79},
}
TY - CPAPER TI - On the Complexity of Trick-Taking Card Games AU - Bonnet, Edouard AU - Jamain, Florian AU - Saffidine, Abdallah T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 482 EP - 487 UR - https://ijcai.org/proceedings/2013/79 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
