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.
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.
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.
3. Heuristic Search
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