资源论文On the Complexity of Trick-Taking Card Games

On the Complexity of Trick-Taking Card Games

2019-11-11 | |  81 |   44 |   0
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 CON TRACT BRIDGE , SKAT , HEARTS , and SPADES . We define a general class of perfect information twoplayer 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 Wa?stlund’s tractability results gives further insight in the complexity landscape of trick-taking card games.

上一篇:Constraint Acquisition via Partial Queries

下一篇:Comprehensive Score: Towards Efficient Local Search for SAT with Long Clauses

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...