A Neural Network Approach for Birds of a Feather Solvability Prediction

Benjamin Sang, Sejong YoonAAAI 2019 · DOI

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.

Figure 4: Decomposition of a board state into multi-channel features including Rank, Suit, Movability, and the Odd Bird condition.

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.

Figure 2: Detailed architecture of the network, featuring a Representation Encoding Layer (CNN) followed by 15 Step Encoding Layers (FC).
  1. 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.
  2. 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

BibTeX
@inproceedings{sang2019neural,
  author = {Benjamin Sang and Sejong Yoon},
  title = {{A Neural Network Approach for Birds of a Feather Solvability Prediction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019706},
}
Figure