AlphaCats: Counterfactual Regret in a Hidden-Information Game
Over the holidays I played Exploding Kittens with my family for the first time. The player who draws the exploding cat loses unless they can defuse it; cards can skip turns, draw from the bottom of the deck, reveal the next few cards, shuffle the deck, or force a card to change hands. It is a pleasantly compact ruleset and can be played with almost any number of players. I lost, and in typical fashion, set out to solve the game. I call it AlphaCats.
I wrote it to explore algorithms for imperfect-information games, alongside go-cfr, a Go framework for counterfactual-regret minimization (CFR), sampled CFR variants, and information-set Monte Carlo tree search. The name is an obvious nod to AlphaGo, but the important difference is in the information available to a player. Go has a fully visible board. AlphaCats has hidden hands, a shuffled draw pile, and private knowledge produced by cards such as See the Future.
Imperfect information and infosets
A player knows their own hand, the sequence of actions that have occurred, and perhaps a few cards on top of the deck (if they played the See the Future card). What a player knows defines an information set. It collects all of the indistinguishable game states that look identical to one player (For example, there are many different permutations of cards in the deck that the player cannot distinguish between). A valid strategy must choose a distribution over legal actions for each infoset.
This is what makes AlphaCats harder than AlphaGo. In AlphaGo, the search and neural networks can work from the complete board position. In AlphaCats, a search must operate from a point of view: public history plus private observations and a belief about the hidden cards.
The AlphaCats state model makes that separation explicit. It keeps the remaining draw-pile multiset and the fixed positions needed to generate chance correctly, but represents each player’s view separately: known cards in their own hand, known and unknown cards in the other hand, and any known positions in the draw pile. When an exploding cat is put back into the deck, prior knowledge is temporarily disrupted until the player has enough evidence to reconstruct it. Those fussy bookkeeping rules are not peripheral to the game; they are the game-theoretic model.
Counterfactual Regret Minimization
The most successful approach for this kind of game is Counterfactual Regret Minimization (CFR), and it was used to solve Heads-up No-limit Hold Em’. The algorithm is to repeatedly traverse an extensive-form game and ask, at each information set: how much would this player have gained by taking each other action, counterfactually, while holding the rest of the trajectory fixed?
Those counterfactual advantages accumulate as regrets. Regret matching says that you should choose your actions based on the accumulated regret. (My girlfriend says this is how I live my life!) For a two-player, zero-sum game, the time-averaged strategies converge toward a Nash equilibrium as regret falls.
The original version visits the whole tree every iteration. But that can be prohibitively expensive for a game with a large game tree. The Monte Carlo CFR family reduces the cost of a pass by sampling part of the tree and reweighting for the sampling probability.
go-cfr is a laboratory for these algorithms. It has full-tree CFR and sampled variants including chance, external, outcome, robust, average-strategy, and generalized sampling. It also supports CFR+, linear weighting, and discounted regret schemes.
Making the hot loop cheap in Go
For these algorithms, the inner loop is not a few expensive decisions. It is a vast number of small ones: iterate over possible actions, create the next game state, sample chance, find a policy, update a short vector, and discard the successor. Minimizing allocations is essential to keep this fast.
AlphaCats therefore uses deliberately compact, value-oriented representations. The counts of up to ten card types fit in a single 64-bit cards.Set; an ordered draw-pile stack packs card identities into another 64-bit value. The public history has room for 48 bit-packed actions inside the game state, while details that are private—such as the exact position of a card in the draw pile—stay out of that public representation. Applying an action copies and updates a small value state instead of assembling a heap-shaped object graph.
The game tree is too big to materialize, so we create game states lazily. A node builds children only when a traversal needs them, then returns its child and cumulative-probability slices to small local pools when it is cleared.
Putting a Python model beside a Go rollout loop
Eventually I realized that all approaches involving a “tabular” representation of the policy were going to be intractable. For larger games, the policy needs to be represented by a neural network, as in Neural Fictitious Self-Play or Deep CFR.
Go is great for implementing a performant game tree, but to train a neural network we have to use Python.
To do this, we first draw samples of gameplay in Go and write them to an .npz file. Then, we shell out to a python script to train a network built with Keras, which produces a TensorFlow SavedModel. Go then loads that model using the TensorFlow Go bindings to run inference for the next round of samples. We use an LSTM neural network that operates over the sequence of actions observed in an infoset.
It did not work
Exploding Kittens is a much larger game than typically studied in the literature. Each turn, a player has a large number of actions to choose from, and there are a large number of rounds in the game compared to something like poker. The game tree and number of infosets is huge (and the game play is irregular enough that it is hard to estimate).
All that is to say, AlphaCats never solved Exploding Kittens. But while trying you learn to see the shape of the problem, what really makes it difficult, and why various papers still fail despite initially seeming to hold promise.
External sampling is the well-behaved MC-CFR variant — low variance, reliable convergence — but it is not tractable here, because a single iteration has to walk an enormous fraction of a very deep tree.
Most of the engineering that followed was an attempt to buy my way out of that. Sampled actions, regrets, and reservoir buffers moved onto disk (RocksDB). Infosets were abstracted down to the last few actions plus the discard pile and known cards, and serialized so that public history formed a path prefix and a strategy could shard across the filesystem as directories. I bit-packed cards, pooled slices, and wrote assembly for the regret updates.
None of it changed the verdict, because the binding constraint was statistical rather than computational. The cheaper sampling schemes — outcome sampling and its relatives — bring the cost of an iteration down to something affordable and pay for it in variance. The advantage estimates were noisy enough that the network never settled; I could run many more iterations and still not converge. Later work went after that directly, with variance-reduced Deep CFR (aka DREAM) a baseline network, and eventually a switch to MCTS with policy-space response oracles and fictitious play. The game outlasted all of them.
But overall I learned a lot! Working on this project I learned a lot about imperfect information games, and I’ve enjoyed following some of the recent work in this field. I also learned a lot about how to write high-performance Go–something I’ve found useful in my day job working on a monitoring system.
Further reading
- Zinkevich, Johanson, Bowling, and Piccione, “Regret Minimization in Games with Incomplete Information”, 2007.
- Lanctot, Waugh, Zinkevich, and Bowling, “Monte Carlo Sampling for Regret Minimization in Extensive Games”, 2009.
- Brown, Lerer, Gross, and Sandholm, “Deep Counterfactual Regret Minimization”, 2019.
- Cowling, Powley, and Whitehouse, “Information Set Monte Carlo Tree Search”, 2012.
