A Monte Carlo Tree Search Player for Birds of a Feather Solitaire

Christian Roberson, Katarina SperdutoAAAI 2019 · DOI

Introduction

"Birds of a Feather" (BoF) is a solitaire variant designed specifically as a benchmark for artificial intelligence. Played on a 4x4 grid with 16 cards, the objective is to consolidate all cards into a single stack. Despite its simple rules and perfect information—where all cards are visible from the start—the game presents a massive search space and numerous "traps" that lead to unsolvable states. This paper presents an AI agent that combines Monte Carlo Tree Search (MCTS) with a specialized solvability checker to achieve near-perfect performance.

The Birds of a Feather Challenge

In BoF, a card or stack can be moved onto another card or stack in the same row or column if they share the same suit, the same rank, or have adjacent ranks.

Figure 5: Illustration of legal moves in Birds of a Feather. A card (like the Jack of Spades) can move to cards in its row or column that match its suit or rank.

The primary difficulty lies in the risk of isolating cards. A single move might seem beneficial by creating a larger stack but can inadvertently "strand" a card by removing all potential partners in its row and column.

Methodology: Enhanced MCTS and Pruning

The researchers implemented a multi-layered strategy to navigate the game's complexity:

1. Solvability Checker

The core innovation is a "death state" detector. By identifying configurations that are mathematically guaranteed to be unwinnable, the agent can prune these branches from its search tree early. Three primary death states were defined:

  • Stranded States: A card has no remaining legal moves in its row or column.
  • Separated Flocks: Groups of cards that can only interact with each other, becoming isolated from the rest of the grid.
  • Lynchpin Cards: Critical cards that act as the only bridge for others; moving them prematurely results in stranded cards.

2. Monte Carlo Tree Search (MCTS)

The agent utilizes MCTS to simulate potential game paths. The standard MCTS cycle—Selection, Expansion, Simulation, and Backpropagation—is enhanced by the solvability checker.

Figure 2: The four stages of the Monte Carlo Tree Search process used by the agent to explore potential move sequences.

During the Simulation phase, if the agent encounters a state identified as unsolvable by the checker, the branch is immediately pruned. Furthermore, instead of purely random moves, the simulation is guided by a tuned heuristic.

The heuristic function $h(s)$ balances the current score (the sum of squares of stack sizes) against "mobility" (the number of available legal moves). The authors found that prioritizing mobility—specifically weighting it 2.5 times more than the raw score—prevented the agent from creating large, isolated stacks too early in the game.

Results and Discussion

The agent was tested against a benchmark of 10,000 game seeds. The results demonstrate the power of combining heuristic search with automated pruning:

  • Efficiency: The tuned agent found solutions by expanding an average of only 103 nodes, a significant improvement over standard Depth-First Search, which required over 5,000 nodes.
  • Win Rate: With 8,000 iterations per move, the MCTS player achieved a win rate of 99.88% on solvable deals.
  • Pruning Impact: The solvability checker successfully identified approximately 38% of all unsolvable states, drastically reducing the computational overhead of the search.

Conclusion

By formalizing the reasons why a game becomes unwinnable, the researchers created an agent that avoids the common pitfalls of Birds of a Feather. Future work will focus on identifying more complex unsolvable patterns and exploring characteristics of guaranteed winning states to further refine the search process.

Summary updated

BibTeX
@inproceedings{roberson2019monte,
  author = {Christian Roberson and Katarina Sperduto},
  title = {{A Monte Carlo Tree Search Player for Birds of a Feather Solitaire}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019700},
}
Figure