[Session Report] Mathematical Optimization and Machine Learning for Multi-Player Imperfect Information Game AI #CEDEC2026

Introduction

This is a report on a session I attended at CEDEC2026. A researcher from CyberAgent, Inc. explained the theory behind how to build strong competitive AI for imperfect information games, where players cannot see their opponent's hand and similar hidden information.

The session overview is as follows.

• Title: Mathematical Optimization and Machine Learning for Multi-Player Imperfect Information Game AI
• Speaker: Takeyuki Abe (Research Scientist, Game AI Lab, CyberAgent, Inc.)
• Date and Time: July 24, 2026, 16:40–17:40
• Venue: Venue 10

What Does "Strength" Mean in Imperfect Information Games?

In perfect information games like chess or shogi, where the entire board is visible, tree search with look-ahead is effective. On the other hand, in imperfect information games like poker or mahjong, where you cannot see the opponent's hand or the draw pile, simple tree search cannot be used.

A strong competitive AI is useful not only as an opponent for players, but also as a foundation for game balance adjustments and automated testing. However, an AI built specifically to beat a particular opponent will see its win rate plummet the moment that opponent adapts their strategy. It is similar to rock-paper-scissors: if you tailor your strategy to beat an opponent who only throws one move, you lose the instant they change. In other words, being strong against a specific opponent is different from being strong against any opponent.

This is where the concept of Nash equilibrium comes in. This refers to a balanced set of strategies where no player can benefit by unilaterally changing their own strategy. In particular, in two-player zero-sum games where a winner and loser are determined between two players, the equilibrium strategy guarantees a certain level of performance even against the worst possible opponent. A simple example is the rock-paper-scissors strategy of throwing each move with a probability of one-third, which guarantees a 50% outcome against any opponent. Learning this robust strategy becomes the goal of building strong AI.

How to Learn Nash Equilibrium

Computing equilibria is generally extremely difficult, and it is known that in many cases it cannot be solved in practical time. However, two-player zero-sum games are an exception: they can be computed efficiently and formulated as mathematical optimization problems.

That said, real-world board games and card games are large in scale, making it difficult to solve them directly. Therefore, online learning is used, where strategies are gradually updated through repeated play to approach the equilibrium. Since each player can independently update based only on the results of play without knowing the opponent's strategy, this method is easy to scale to large games.

A representative method is Regret Matching, which makes it more likely to choose actions with a large past regret. Its extension to the tree structure of imperfect information games is CFR (Counterfactual Regret Minimization), which decomposes the overall game regret into smaller per-situation regrets and minimizes them. This CFR is a central component of AIs such as Libratus and Pluribus, which surpassed humans at poker.

Machine Learning for Scaling to Large Games

For even larger games, function approximation is used, where strategies for each situation are approximated with a neural network. However, this approach comes with several challenges. During training, strategies can cycle around the equilibrium and fail to converge. This is because when both sides keep updating toward moves that can beat the other, they loop back to where they started, just like in rock-paper-scissors.

As a countermeasure, a method was introduced that adds a regularization term to the payoff to prevent the strategy from straying too far from a reference strategy. This allows the strategy being updated to itself move toward the equilibrium. Furthermore, by gradually re-updating the reference strategy, it becomes possible to converge to the equilibrium of the original game. This idea is also used in DeepNash, which surpassed humans at Stratego, a game where the identities of the opponent's pieces remain hidden.

Impressions

Rather than flashy cutting-edge techniques, this was a presentation that explained step by step the foundational ideas underlying AI for multi-player imperfect information games. I felt that the perspective of mathematically reframing strength as Nash equilibrium — not just being strong against specific opponents, but possessing a robustness that holds up against any opponent — is a starting point for designing competitive AI.