Introduction
Birds of a Feather (BoF) is a single-player, perfect-information card game where the objective is to stack all cards into a single pile based on suit or rank adjacency. Despite its simple rules, the search space for a solution grows exponentially with board size, making it a complex puzzle for both human players and automated solvers. Researchers have recently developed a deep learning framework to address the solvability prediction problem: determining if a solution path exists for a given board configuration without exhaustive search.
Feature Engineering: The Board as an Image
The core innovation of this approach is treating the game board not as a list of cards, but as a spatial tensor or multi-channel image. This allows the model to leverage spatial relationships between cards.
Four primary image-based features were designed:
- Rank: The numerical value of the card.
- Suit: The card's suit.
- Movability: A categorical value indicating if a card can move horizontally, vertically, both, or neither.
- Odd Bird (OB): A specific condition where a card is trapped and cannot move regardless of other moves, a strong indicator of unsolvability.
Model Architecture
The authors proposed a two-part neural network designed to capture both immediate spatial context and the long-term sequence of moves required for a solution.
- Representation Encoding Layer: A 3x3 Convolutional Layer (CNN) captures structural patterns, such as how cards relate to their immediate neighbors. The inclusion of this layer boosted performance from 68.5% to over 90% accuracy on initial states.
- Step Encoding Layers: A stack of 15 Fully Connected (FC) layers that gradually decrease in size. The authors hypothesize that these layers simulate the sequence of moves necessary to reach a goal state.
Datasets and Training
The study utilized two datasets: the BOAF dataset from the EAAI-19 challenge and a new InitSet containing 1 million unique initial board states. A significant discovery was the extreme class imbalance in random boards; only about 0.18% of random seeds are unsolvable. To train effectively, the researchers created a balanced subset for the model to learn the nuances of unsolvable configurations.
Key Results and Insights
- High Accuracy on Initial States: On the balanced
InitSet, the CNN-based model achieved 90.6% accuracy. - Interim State Challenges: Performance dropped to 76.7% on mid-game states (interim states). This suggests that "game-in-progress" states, characterized by empty grid cells, have different structural properties than full starting boards.
- Spatial Context is Crucial: The success of the CNN layer proves that solvability depends heavily on the relative positioning of cards rather than just the card values present on the board.
- Heuristic vs. Learning: While the "Odd Bird" heuristic is a powerful manual indicator of unsolvability, the neural network outperformed simple rule-based logic, indicating it learned complex patterns beyond basic card entrapment.
Limitations and Future Work
While the model is highly effective for 4x4 boards, the extreme rarity of unsolvable boards in the wild remains a challenge for real-world application. Future research will focus on scaling this approach to larger grids (e.g., 7x7) and investigating whether these learned solvability patterns can be used to guide search-based solvers to find actual solution paths more efficiently.
Summary updated