Self-Play AI Tackles Dominoes: The Abstraction Dilemma of MCTS and CFR

Introduction: From Board Games to Imperfect Information Games

In recent years, AI breakthroughs in game-playing have extended from Go (AlphaGo) to Texas Hold'em (Libratus/Pluribus), with core methodologies evolving from pure search to a fusion of search and game-theoretic solving. AlphaGo's victory over Lee Sedol in 2016 established AI's dominance in perfect information games, relying on the combination of deep neural networks and MCTS. However, perfect information games represent only the tip of the iceberg in real-world decision-making—the vast majority of real-world decision scenarios involve information asymmetry. In 2017, Carnegie Mellon University's Libratus defeated professional players in heads-up no-limit Texas Hold'em, and in 2019 Pluribus extended this achievement to 6-player tables, marking AI breakthroughs in multiplayer imperfect information games. The core shift in this technological evolution is: from "computing optimal moves given a complete game state" to "constructing robust strategies under uncertainty."

A developer recently shared a challenging project on Reddit: building a self-play AI for Pernambuco Dominoes (a popular 4-player team domino variant from the Pernambuco region of Brazil), with a tech stack combining Monte Carlo Tree Search (MCTS) and Counterfactual Regret Minimization (CFR). The project is currently stuck on a critical bottleneck—search abstraction.

Although this case stems from a niche game, it reflects the core challenges of modern imperfect information game AI, making it worthy of deep analysis.

Why Dominoes Is a Tough Nut to Crack

The Nature of Imperfect Information

Unlike perfect information games such as chess and Go, dominoes is an imperfect information game—players cannot see their opponents' tiles, nor do they know the exact distribution of remaining tiles. This information asymmetry renders traditional Minimax search ineffective, as you cannot compute a precise value for a deterministic game state.

From a formal game-theoretic perspective, imperfect information is characterized through Information Sets. An information set refers to the collection of all possible game states that the current player cannot distinguish at a given decision point. For example, in dominoes, you know your own 7 tiles and the tiles already played, but you cannot distinguish between the many possible distributions of opponent hands—all these possibilities constitute your current information set. Game theory requires that strategies within the same information set must be identical (since the player cannot distinguish these states), which means that although the underlying state space is enormous, effective strategy representation must be organized by information sets rather than specific states.

The Complexity of Team Cooperation

The Pernambuco variant is typically a 2v2 team competition, which further increases difficulty. The AI must not only reason about opponents' hidden information but also engage in implicit cooperation with teammates—conveying signals through tile-playing choices without direct communication. This is similar to bridge's play and signaling systems, and is an extremely difficult aspect to model in game theory.

Bridge and Pernambuco dominoes share many similarities: 4 players in 2 teams, imperfect information, and implicit teammate cooperation. However, bridge has a formalized bidding convention system that provides explicit encoding standards for signal transmission between teammates. Dominoes lacks such formalized conventions, making signal transmission between teammates much more subtle—for instance, deliberately playing a certain suit to hint at having many tiles of that suit, or choosing to pass when other options are available to convey information. How to enable AI to learn such implicit communication protocols is a problem with both theoretical depth and practical difficulty.

State Space Explosion

Even with standard double-six dominoes (28 tiles), the distribution combinations among 4 players are enormous. When we need to maintain strategies for every information set, the state space quickly expands to an intractable scale. This is precisely the problem that abstraction techniques aim to solve.

Specifically, Pernambuco dominoes uses standard double-six dominoes (28 tiles, from 0-0 to 6-6). Four players are divided into two teams sitting across from each other, each dealt 7 tiles with no remaining draw pile. Players take turns playing tiles that must match the pip count on either end of the table chain; if unable to play, they must pass. When a round ends, the team with the fewest remaining pip points scores, or if a player plays all their tiles (domino), that team wins outright. Passing reveals hand information—opponents can deduce which suits you lack, making information inference a core skill in high-level play. The number of initial combinations for distributing 28 tiles among 4 players is C(28,7)×C(21,7)×C(14,7) ≈ 4.86×10^12, and considering the dynamic information during gameplay, the enormity of the state space becomes evident.

MCTS + CFR: Combining Two Paradigms

The Role of MCTS

Monte Carlo Tree Search evaluates action values through random simulations, avoiding complete expansion of the entire game tree. In imperfect information scenarios, Information Set MCTS (IS-MCTS) is typically employed, which samples hidden information (determinization) at each simulation, temporarily converting the imperfect information problem into a series of perfect information subproblems for solving.

The core idea of the Determinization method (also known as Perfect Information Monte Carlo, PIMC) is: at each simulation, randomly sample a specific distribution of opponent hands from the current information set, then treat the problem as a perfect information game to solve. The final decision is guided by averaging results across multiple samples. This method is simple and effective, but suffers from a fundamental flaw known as "strategy fusion"—it assumes future decisions can exploit currently invisible information. For example, a certain action might be optimal when the opponent holds A and also optimal when they hold B, but they require different follow-up strategies, while in reality the player may still be unable to distinguish A from B in the future. IS-MCTS partially mitigates this issue by maintaining statistics at the information set level rather than at specific state levels.

The Role of CFR

Counterfactual Regret Minimization is the mainstream algorithm for solving Nash Equilibria in imperfect information games. Through repeated self-play, it accumulates "regret values" for each action at every information set, iteratively optimizing strategies based on these values, eventually converging to a near-equilibrium solution. The core of top poker AIs like Libratus and Pluribus is precisely various CFR variants (such as MCCFR, Deep CFR).

The core idea of CFR can be intuitively understood as "regret minimization": in each iteration, the algorithm calculates "how much expected payoff would improve if a different action were taken at a certain information set"—this is the positive regret for that action. Strategies are updated in proportion to cumulative positive regret values, meaning actions with higher regret receive more selection probability in the future. Zinkevich et al. proved in 2007 that after T iterations, the average strategy produced by CFR converges to Nash equilibrium at a rate of O(1/√T). This convergence guarantee is unconditional—regardless of how opponents act, regret growth is sublinear in the long run. MCCFR (Monte Carlo CFR) reduces per-iteration cost by sampling only partial game paths in each iteration, enabling CFR to scale to larger games.

Motivation for Fusion

The rationale for combining both approaches is: use CFR to guarantee game-theoretic soundness of strategies (avoiding exploitation by opponents), and use MCTS/search during real-time play for local deep solving. This aligns with Pluribus's "blueprint strategy + real-time search" architecture.

Pluriubs's architecture has two phases: the offline phase runs MCCFR on a highly abstracted game tree to generate a "blueprint strategy"—a base strategy with global coverage but limited precision; the online phase, during actual gameplay when it's the AI's turn to decide, uses the blueprint strategy as a starting point and performs depth-first search on a finer representation of the current subgame. This search is called "depth-limited solving," which only expands a few future actions and uses blueprint strategy values as leaf node estimates. The key innovation is that the search optimizes not only its own strategy but also considers opponents' possible best responses, ensuring the search results don't introduce exploitable weaknesses. This "coarse-grained global + fine-grained local" paradigm is a typical embodiment of MCTS and CFR fusion.

The Core Bottleneck: Search Abstraction

What Is Abstraction

The search abstraction bottleneck encountered by the developer is the most typical and thorny challenge in such projects. Abstraction refers to clustering and merging massive raw game states into a manageable number of abstract states, enabling CFR/search to converge within finite computational resources.

Abstraction is typically divided into two categories:

• Information Abstraction: Grouping strategically similar hands/situations into one class. For example, in poker, merging hands with similar point values and comparable win rates.
• Action Abstraction: Reducing the number of actions considered, such as retaining only a few typical bet sizes in betting games.

In the history of Texas Hold'em AI development, information abstraction techniques have undergone multiple generations of evolution. Early Tartanian series used k-means clustering based on Expected Hand Strength (EHS), compressing millions of possible post-flop hand combinations into a few thousand abstract buckets. Later methods introduced "potential-aware" clustering—considering not only current hand strength but also the distribution of hand strength after future community cards are revealed (i.e., drawing potential). More advanced methods like Baby Tartanian8, a winner in ACPC competitions, used a "blueprint-to-refined" progressive abstraction scheme, employing coarse abstraction in early actions and dynamically switching to finer abstraction at critical decision points. These experiences have direct reference value for abstraction design in dominoes.

The Abstraction Dilemma

The essence of the bottleneck lies in a fundamental trade-off:

Too coarse an abstraction causes the AI to lose critical strategic discrimination ability, degrading strategy quality; too fine an abstraction prevents state space compression, making CFR unable to converge in reasonable time.

For dominoes, how to design an abstraction scheme that captures key features like "which tiles have been played, which suits are blocked, what might teammates hold" while dramatically compressing the state count is the key to project success or failure.

Possible Breakthrough Directions

Domain Knowledge-Driven Feature Abstraction

A pragmatic direction is incorporating domain expert knowledge to manually design compact state features: such as remaining counts per suit, suit-absence information exposed by each player's passes, current scores, etc. Clustering based on these features is often more efficient than purely data-driven abstraction.

From Manual to Learned Abstraction

The industry trend is replacing manual abstraction with neural networks—the Deep CFR approach—using function approximators to directly learn the mapping from information sets to strategies/regret values, letting the network "implicitly" complete the abstraction. This avoids information loss from manual clustering but requires more training data and hyperparameter tuning experience.

Deep CFR, proposed by Brown et al. in 2019, uses two neural networks to approximate the cumulative regret value function and the average strategy function respectively, thereby bypassing the need to explicitly enumerate all information sets. During training, CFR traversal trajectories are stored as experience samples, and networks fit these samples through supervised learning. Its core advantage lies in generalization ability—for unseen information sets, the network can provide reasonable estimates based on similar features, which is equivalent to implicitly completing abstraction. However, in practice Deep CFR faces significant challenges: low sample efficiency (requiring extensive traversals to generate sufficient training data), function approximation errors that may break convergence guarantees, and high hyperparameter sensitivity. For individual developers with limited computational resources, combining domain knowledge to design network input features may be necessary to reduce learning difficulty.

Borrowing from Signaling Game Modeling

For the team cooperation challenge, one can reference bridge AI approaches (such as WBridge5, NooK) in modeling teammate signals, explicitly modeling tile-playing sequences as communication channels, enabling AI to learn to "speak through plays."

Traditional strong bridge AIs like WBridge5 primarily rely on the combination of Determinization + Double Dummy Solver, sampling opponent hands then using a perfect information solver to compute optimal play. In 2022, NukkAI's NooK introduced deep learning, using neural networks to predict optimal plays and demonstrating teammate intent reasoning capabilities surpassing traditional methods. For dominoes AI, a feasible approach is to explicitly encode "signals conveyed by teammate's play history" in the information set representation—observations like "teammate had other options in round 3 but still played a 6-pip suit"—enabling the AI to learn to leverage these implicit communications for more precise inference of teammate hand distributions.

Conclusion: The Universal Value of Niche Projects

Although this dominoes AI project is small in scale, it fully encapsulates the core proposition of imperfect information game AI: how to construct strategies that are both robust and computationally tractable under the triple pressure of information asymmetry, state explosion, and implicit cooperation. The abstraction bottleneck the developer encountered is precisely the same challenge that milestone works from Libratus to Pluribus all had to confront head-on.

For algorithm enthusiasts in the community, such practical projects provide excellent learning samples—reminding us that progress in game AI depends not only on computational power but more on deep understanding and clever abstraction of the problem structure itself. From a broader perspective, solving techniques for imperfect information games are permeating into more real-world scenarios: attack-defense games in cybersecurity, multi-vehicle interaction in autonomous driving, and strategy optimization in business negotiations—all these domains share the core challenge of "making robust decisions under uncertainty," and "toy problems" like dominoes serve as ideal proving grounds for honing methodologies.

Key Takeaways