Computational Intractability and Solvability for the Birds of a Feather Game

AAAI 2019 pp. 9648-9655

doi:10.1609/AAAI.V33I01.33019648 /aaai/2019/hoshino2019aaai-computational/

Abstract

In this paper, we analyze Birds of a Feather (BoaF), a perfectinformation one-player card game that is the subject of the 2019 EAAI Undergraduate Research Challenge. We prove that the generalized N × N BoaF game is NP-complete, and then explore the one million deals in the 4×4 BoaF testbed. We present several graph-theoretic algorithms to prove that 1880 of these million deals are unsolvable, and conclude the paper with two search algorithms that efficiently show that all of the remaining 998,120 deals are in fact solvable.

PDF AAAI Semantic Scholar

Cite

Text

Hoshino and Notarangelo. "Computational Intractability and Solvability for the Birds of a Feather Game." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33019648

Markdown

[Hoshino and Notarangelo. "Computational Intractability and Solvability for the Birds of a Feather Game." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/hoshino2019aaai-computational/) doi:10.1609/AAAI.V33I01.33019648

BibTeX

@inproceedings{hoshino2019aaai-computational,
  title     = {{Computational Intractability and Solvability for the Birds of a Feather Game}},
  author    = {Hoshino, Richard and Notarangelo, Max},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {9648-9655},
  doi       = {10.1609/AAAI.V33I01.33019648},
  url       = {https://mlanthology.org/aaai/2019/hoshino2019aaai-computational/}
}