Introduction
Birds of a Feather is a perfect-information solitaire game played on a 4x4 grid. The objective is to stack cards based on matching suits, ranks, or adjacent ranks until only a single stack remains. While the rules are straightforward, the state space is vast, making it a significant challenge for AI researchers focused on "solvability"—the ability to quickly determine if a given deal is solvable or to prove its impossibility.
Standard search algorithms, such as Depth-First Search (DFS), often struggle with "dead ends"—states that appear promising but are mathematically impossible to complete. This research introduces a highly efficient solver that achieves a 99.56% reduction in search time compared to standard DFS by combining graph-theoretic pruning with a novel search algorithm.
Methods
Graph-Theoretic Pruning
The authors utilize a "flockability graph" where nodes represent cards and edges represent potential moves. This representation enables two powerful pruning rules that act as early-warning systems for unsolvable states:
- Odd Bird: If a card has zero potential moves (degree 0), the state is immediately identified as unsolvable.
- Separated Flock: If the flockability graph contains multiple disjoint components, the cards can never be merged into a single stack, allowing for early termination of the search path.
Best-$n$ Depth-First Search
The primary algorithmic contribution is Best-$n$ Depth-First Search. This approach modifies standard DFS by managing the forward search in small "cohorts" of size $n$.
As shown in Algorithm 1, nodes within a cohort are sorted by a heuristic and explored. This allows for localized "best-first" behavior, guiding the search toward promising areas while maintaining the memory efficiency and depth-oriented nature of DFS. Empirical testing found $n=4$ to be the optimal "sweet spot" for balancing guidance and overhead.
Solvability Prediction
To further guide the search, the team employed logistic regression to analyze game features. They generated a dataset of over 1.2 million non-terminal game states labeled by solvability. Features such as "mobility per card" and "suit dominance" were evaluated for their predictive power, achieving a prediction accuracy of 75.45%.
Experimental Results
The combination of pruning and Best-$n$ DFS yielded significant performance gains over 100,000 random puzzle seeds:
- Search Speed: Average solve time per puzzle seed dropped from 1,212 ms (basic DFS) to just 5.32 ms.
- Pruning Impact: Graph-theoretic checks alone reduced basic DFS solve time by over 95%.
- Heuristic Insights: Interestingly, the feature best at predicting solvability (mobility) differed from the one best for node ordering (state flockability), which prioritizes states with more potential future connections.
Conclusion
While the optimized solver provides a massive speedup, "outlier" puzzles still exist that require millions of nodes to resolve. These difficult cases suggest subtle dependencies not yet captured by current heuristics. Future directions include developing subgoal-directed search algorithms, running parallel ensembles of different strategies, and applying deep learning to capture more nuanced game features.
Summary updated