How Does AI Conquer Imperfect Information Games? A Deep Dive into Tactico

Perfect vs. Imperfect Information: Where AI's Real Challenge Lies

In the field of artificial intelligence and gaming, Chess and Go have long been regarded as benchmarks for measuring the level of AI intelligence. DeepMind's AlphaGo and AlphaZero left the public deeply impressed by AI's mastery of board games. But one often-overlooked fact is this: Chess and Go are both essentially Perfect Information Games—both players can see the entire state of the board, with no hidden information whatsoever.

Game Theory Background: The concept of perfect information games originates from the seminal 1944 work Theory of Games and Economic Behavior by game theory founders John von Neumann and Oskar Morgenstern. In a perfect information game, all participants have complete knowledge of the rules, payoff structures, and current state of the game, so an optimal solution can theoretically be found through backward induction. From a mathematical structural standpoint, perfect information games can be precisely described using an extensive-form game tree, where each node corresponds to a unique historical information set. Zermelo's theorem (1913) proved that a finite two-player zero-sum perfect information game must have a pure strategy Nash equilibrium. Imperfect information games were later systematized by John Harsanyi in 1967, who introduced the concept of "type" to describe private information—work that earned him the 1994 Nobel Prize in Economics. The core mathematical structure of imperfect information games is the "information set"—which groups multiple game nodes indistinguishable to a player into a single set. A strategy must remain consistent across an entire information set, causing the strategy space to expand exponentially and fundamentally ruling out the direct application of backward induction.

This distinction is not merely academic classification; it determines the fundamentally different algorithmic paths AI needs to conquer each type of game. In perfect information games, the Minimax algorithm combined with alpha-beta pruning can directly traverse the game tree. In imperfect information games, however, because each player faces subjective uncertainty about the true current state of the world, the very definition of an "optimal solution" needs to be reconstructed—it must be robust in a probabilistic sense across all possible hidden states, raising the complexity of algorithm design by an entire dimension.

The number of legal board positions in Go even exceeds the number of atoms in the observable universe (Go has approximately 2.08×10^170 legal positions, while the universe has about 10^80 atoms). The core difficulty lies in "computational complexity" rather than "information uncertainty." When AlphaGo defeated world champion Lee Sedol in 2016, its core breakthrough was combining deep convolutional neural networks with Monte Carlo Tree Search (MCTS). The 2017 AlphaZero abandoned human game records entirely, surpassing all its predecessors within hours through self-play alone—but the premise of this methodology has always been that both sides have completely symmetric information and the board state is fully observable.

The truly thornier frontier for AI is precisely Imperfect Information Games—where you cannot see your opponent's cards and must reason and make decisions under uncertainty.

The most typical example is poker. In Texas Hold'em, players need to weigh what hands their opponents might hold, and also infer "what the opponent thinks you hold," then launch a bluff at the right moment. This kind of nested reasoning and psychological gaming is precisely the charm and difficulty of imperfect information games. The Tactico project recently shared by a Reddit developer is an intriguing exploration of this frontier.

Tactico: An Information War of Hidden Ranks

Tactico is a classic imperfect information strategy game, with rules highly similar to the classic board game Stratego. Since its inception in the 1940s, Stratego has been recognized as one of the benchmark imperfect information games in AI research. Compared to Texas Hold'em, Stratego's particular challenge lies in its extremely long game horizon (a single game can span hundreds of moves) and its extraordinarily massive information sets—there are more than 10^66 possible initial arrangements for 40 pieces, making direct enumeration of the game tree entirely infeasible.

The History of Stratego AI Research: Exploration in this field has been far more tortuous than the public realizes. As early as 2003, researchers attempted to optimize initial setups using genetic algorithms. After 2010, opponent-modeling methods based on Bayesian inference gradually became mainstream, attempting to infer the probability distribution of hidden ranks from piece movement patterns. A 2022 study on full-rule Stratego revealed a key challenge: in an extremely long game horizon, the maintenance and updating of the Belief State expands exponentially with the number of moves, making pure tree-search methods difficult to sustain in actual play. Approximate inference and strategy distillation techniques must be introduced. In 2020, DeepMind published a paper specifically studying systems that reach human expert level on full-rule Stratego, whose challenge lies in the need to simultaneously maintain spatial reasoning and probabilistic belief updates about hidden information.

Each player commands 40 pieces with hidden ranks, and the goal is to capture the opponent's flag before they capture yours.

You Can See Positions, But Not Identities

The most central mechanic of Tactico is this: you can see the positions of enemy pieces, but you cannot know their rank identities. Only when combat occurs do both pieces reveal their true ranks. This means every move is a combination of memory, reasoning, and bluffing:

• Memory: Track and record information about enemy pieces revealed in past engagements;
• Reasoning: Infer the possible identities of hidden pieces based on the opponent's positioning and historical behavior;
• Bluffing: Make a strong show with a weak piece, luring the opponent into misjudgment.

The Mathematical Mechanism of Belief Updates: In Tactico, whenever an opponent's piece moves or combat occurs, the AI must use this as new evidence to update the posterior probability distribution of each hidden piece's rank via Bayes' theorem. Theoretically, maintaining a precise Joint Belief Distribution requires tracking all possible arrangements of all piece identities—a computational load that is entirely infeasible. In practice, approximations are usually made using independence assumptions or the Particle Filter method—a particle filter maintains a set of representative "world state" samples and updates the probability weights at each step through importance resampling, approximating a complex belief distribution at a limited computational cost.

Particle filtering was systematized by del Moral and others in the 1990s and is one of the core tools of Bayesian nonparametric inference. In the Tactico scenario, a "particle" can be understood as a complete "hypothesis about the arrangement of enemy piece ranks." When a player observes the true rank revealed by an opponent's piece in combat, the weights of all particles contradicting that observation immediately drop to zero, and the remaining particles are renormalized. Resampling then eliminates low-weight hypotheses and reinforces high-weight ones, gradually narrowing the belief distribution to the world states that best match the observation history. This technique is also widely applied in robot localization and autonomous driving perception fusion, reflecting the cross-domain commonality of hidden information processing problems.

Because each piece's rank remains hidden, the number of possible enemy layouts reaches astronomical scales. It is precisely this immense information uncertainty that makes Tactico far harder for AI to conquer than Chess or Go.

Training Method: Imitation Learning + Self-Play Reinforcement Learning

To teach the AI to play Tactico, the project adopts the industry's mainstream two-stage training paradigm—an approach in line with the AlphaGo series, but with special adjustments for the imperfect information environment.

Stage One: Imitation Learning Lays the Foundation

The developer first uses tens of thousands of human game records for Imitation Learning. Through supervised learning, the neural network learns the decision-making patterns of human players in various situations, quickly establishing a basic understanding of the game.

Technical Principle: Imitation learning is an important branch of reinforcement learning. Its core idea is to have the agent learn behavioral strategies from expert demonstration data, rather than exploring from scratch through reward and penalty signals. The most basic form is Behavioral Cloning, which treats expert trajectories as a supervised learning dataset and directly fits the "state → action" mapping. However, behavioral cloning suffers from the "Distribution Shift" problem: in states never seen in the training data, the model may produce serious errors. To address this, improved algorithms like DAgger (Dataset Aggregation) expand the training data by having the learning agent continuously interact with the expert. In the special context of imperfect information games, imitation learning faces an additional challenge: human experts' decisions often rely on hard-to-quantify intuitive belief inferences rather than explicitly observable board states, requiring the neural network to implicitly encode probabilistic reasoning under information asymmetry while learning behavioral patterns. In Tactico, the value of imitation learning lies in quickly injecting human intuition about game rhythm and tactical priorities, providing a much better starting point than random initialization for subsequent reinforcement learning and greatly reducing exploration costs.

This step is equivalent to injecting "human experience" into the AI, avoiding the inefficient process of exploring from scratch.

Stage Two: Self-Play Converges to Nash Equilibrium

Once it has basic capabilities, the AI enters the Self-Play Reinforcement Learning stage, undergoing millions of games of self-play to continuously optimize its strategy, with the core goal of gradually converging its strategy toward Nash Equilibrium.

Nash equilibrium has special significance in imperfect information games—it represents an "unexploitable" strategic state. When the AI reaches Nash equilibrium, no matter what approach the opponent takes, they cannot systematically gain an advantage. This is highly consistent with the design philosophy of poker AIs (such as Libratus and Pluribus): in imperfect information games, the optimal strategy is often not "tailored to a specific opponent," but rather a set of one's own impregnable mixed strategies.

Algorithmic Core: Nash equilibrium was proposed by mathematician John Nash in 1950, describing a state in a game where no player can improve their payoff by unilaterally changing their own strategy while the other players' strategies remain fixed. In 2017, Carnegie Mellon University's Libratus defeated top professional players in no-limit Texas Hold'em, and its core algorithm, Counterfactual Regret Minimization (CFR), was designed specifically to approximate the Nash equilibrium of imperfect information games. CFR was proposed by Zinkevich and others at NIPS in 2007, and its theoretical foundation is the Regret Bound theory in online learning—by decomposing global regret into local regret at each information set, it can be proven that the average strategy converges to Nash equilibrium as the number of iterations approaches infinity. This decomposition is the key insight of CFR: instead of solving the global equilibrium of the entire game tree, one only needs to independently minimize local regret at each information set, and global convergence is still guaranteed. Since its introduction in 2007, CFR has spawned several important variants: CFR+ (2014) truncates negative regret to zero, improving the convergence speed by about an order of magnitude; Monte Carlo CFR (MCCFR) handles large-scale game trees through sampling, reducing the computational cost per iteration; and Deep CFR introduces neural networks for value function approximation, allowing the algorithm to scale to ultra-large scenarios like the six-player poker of Pluribus. In 2019, Pluribus defeated top human players in six-player no-limit Texas Hold'em, with its innovation lying in combining a Blueprint Strategy with Real-Time Subgame Solving—a framework of great reference value for long-horizon imperfect information games like Tactico, and a core idea borrowed by Tactico's AI training framework.

Why Nash Equilibrium Is Crucial Here

In perfect information games, an "optimal move" theoretically exists, and the AI only needs to calculate deeply enough to approximate it. But in imperfect information games, the situation is entirely different.

If the AI's strategy is deterministic and predictable, a clever opponent can identify the pattern and exploit it. Therefore, a powerful AI for games like Tactico must adopt a mixed strategy—making different choices with certain probabilities in similar situations, including well-timed bluffs and shows of false strength. Converging to Nash equilibrium means the AI has found the balance point of this probabilistic strategy, making it impossible for the opponent to beat it through any behavioral pattern.

Exploitability: The Essential Metric for Evaluating AI Strategy: In the AI evaluation system for imperfect information games, "Exploitability" is a more fundamental performance metric than win rate. Exploitability is defined as the maximum expected loss a strategy suffers when the opponent adopts the optimal counter-strategy against it. A strategy with zero exploitability is a Nash equilibrium strategy. It's worth noting that a Nash equilibrium strategy does not mean "best at beating weak opponents"—when facing lower-level human players, a targeted Exploitative Strategy may achieve a higher win rate, but at the cost of exposing one's own vulnerabilities. If Tactico's AI truly approximates Nash equilibrium, its strategy may seem "conservative," yet leaves no systematic openings against opponents of any level—this is the fundamental reason it's hard for humans to beat, rather than simply relying on an advantage in computational speed.

This also explains why the developer says "most people can't beat it." Human players often have identifiable behavioral habits and psychological tendencies, whereas an AI approaching Nash equilibrium leaves virtually no openings. Experimental economics research shows that humans in real-world games typically only engage in 1-2 levels of reasoning (i.e., "what I think the opponent will think," plus at most one more layer of "what the opponent thinks I will think"). A Nash equilibrium AI therefore gains a systematic advantage against boundedly rational humans—it doesn't need to guess the opponent's level of reasoning, because its strategy remains theoretically optimal against opponents at all levels.

Getting Started: Available on Both Browser and Android

The project currently offers two ways to experience it, with an extremely low barrier to entry:

• Browser version: Free, no registration required, playable immediately—ideal for a quick try;
• Android early beta version: The most fully featured, supporting offline and friend battles (it also runs in airplane mode). You need to join the tester group to become a Beta user to access it.

For players who want an intuitive feel for the difficulty of imperfect information games, personally sparring with this AI is far more convincing than reading any theoretical article. The developer half-jokingly throws down a challenge: "See how many moves you can last."

Conclusion: Conquering Hidden Information May Have More Real-World Significance Than Go

Although Tactico is a personal project, it reflects an extremely valuable direction in AI research. The vast majority of decision-making scenarios in the real world—business negotiations, financial trading, security confrontations, military games—are all imperfect information games. You can never grasp all the information; you must make the best possible decisions under uncertainty.

From this perspective, conquering hidden-information games like Stratego and poker may be closer to the real world's demands for intelligence than conquering Go. Breakthroughs in perfect information games are certainly exciting, but research in imperfect information games on Belief Update, strategy randomization, and Opponent Modeling truly touches the essence of intelligent decision-making—maintaining rationality in an environment where noise and deception coexist.

These three core capabilities are interdependent in real-world applications: belief updating requires the agent to continuously integrate incomplete and potentially distorted perceptual information; strategy randomization requires the agent to find a balance between optimal expected payoff and unpredictability; and opponent modeling requires the agent to infer others' intentions, capabilities, and even others' inferences about oneself—i.e., recursive "Theory of Mind."

Theory of Mind (ToM) was originally proposed by Premack and Woodruff in 1978 to describe an individual's ability to infer others' mental states (beliefs, intentions, desires). In the field of game AI, this concept corresponds to "k-level reasoning": a 0-level player only considers the current situation, a 1-level player considers what the opponent will think, a 2-level player considers "what the opponent thinks I will think," and so on recursively. Theoretically, a Nash equilibrium strategy corresponds to the fixed point of infinite-level reasoning—a strategy that remains optimal without relying on any assumptions about the opponent's level of reasoning. It is precisely this multi-layered, nested reasoning capability that constitutes the key bridge from game AI to general intelligence. Open-source practices like Tactico are an excellent entry point for helping more people intuitively understand this cutting-edge field.

Key Takeaways