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” card 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. There are expansion decks with additional cards and unique mechanics. It is a fun game and can be played with almost any number of players. I lost, and in typical fashion, set out to solve it. The result is 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. Exploding Kittens 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: the set of game states that look identical from where they sit (for example, the many permutations of the draw pile that are all consistent with what they have seen). A valid strategy must choose a distribution over legal actions for each infoset.
This is the core difficulty, and it is not one AlphaGo had to deal with. In Go, the search and neural networks can work from the complete board position. Here, 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. That bookkeeping is fussy, and it is also where the infosets come from, so it has to be exactly right.
How big is it?
Parts of this are straightforward to count exactly.
The two-player deck in the iOS app has 19 action cards, plus two Defuses and one Exploding Kitten. Each player is dealt four cards and a Defuse, leaving thirteen cards in the draw pile. That gives 165 distinct opening hands, 1.13 × 1012 initial deals, 3.26 × 1011 distinguishable ordered draw piles, and 2.23 × 1015 reachable card configurations. The retail 56-card box is far worse: 1.54 × 1041 deals and 3.01 × 1045 configurations.
Counting infosets is harder. There is no closed form, and while enumerating them is conceptually simple — walk the tree and collect the distinct ones — the tree is far too large to walk. So I estimated instead: sample playouts, apply a species-richness estimator to the infosets seen at each depth, and calibrate that estimator against exhaustive enumeration of a cut-down six-card deck where the exact answer is computable. Coverage collapses past about depth six, which leaves most of the total resting on an extrapolation across another fifteen levels — hence a wide range. I estimate 1016 to 1021 information sets, with a best guess around 1018 to 1019.
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 limit Texas hold’em. (No-limit hold’em has never been solved; Libratus and DeepStack play it better than the best humans, which is not the same thing.) 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 to choose actions in proportion to positive 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, which is prohibitively expensive here. 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 58 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. This was empirically much faster.
The game tree is too big to materialize, so states are created 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
A “tabular” representation of the policy was never going to fit this game — I will come back to the arithmetic below. For larger games the policy has 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 training a neural network means Python.
So I draw samples of gameplay in Go and write them to an .npz file, shell out to a Python script that trains a network in Keras, and get back a TensorFlow SavedModel. Go loads that model using the TensorFlow Go bindings to run inference for the next round of samples. The network is an LSTM over the sequence of actions observed in an infoset.
It did not work
AlphaCats never solved Exploding Kittens. What I got instead was a much clearer picture of why it is hard, and of why several approaches that looked promising did not help here.
Start with where the game sits relative to the ones people usually study:
| Game | Information sets | Status |
|---|---|---|
| Kuhn poker | 12 | solved analytically |
| Leduc hold’em | 288 | solved exactly |
| Goofspiel (5 cards) | ~2 × 104 | solved |
| Heads-up limit hold’em | 3.2 × 1014 | solved in 2015 — the largest game ever solved |
| Goofspiel (13 cards) | ~8 × 1015 | unsolved |
| Exploding Kittens | ~1018–1019 | unsolved |
| Heads-up no-limit hold’em | ~10161 | superhuman play, unsolved |
Exploding Kittens is roughly four orders of magnitude past the largest game anyone has ever solved. That alone would be enough to explain the failure — but it is not the interesting part, because no-limit hold’em is 10142 times larger still, and computers have been beating professionals at it since 2017. The size of a game turns out to be a poor predictor of whether it can be beaten; what matters is whether it has structure you can exploit.
Three pieces of structure make no-limit hold’em tractable in practice, and Exploding Kittens has none of them.
The first is a good abstraction. Poker hands can be bucketed by equity distribution, and suits can be permuted losslessly, which collapses an absurd game into a merely enormous one while bounding how much you give up. Exploding Kittens cards are not interchangeable in any comparable way — Skip, See the Future, and Shuffle do unrelated things — so the abstractions I tried were lossy with no bound on the damage.
The second is shallow, regular episodes. Poker is four betting rounds. This game is twenty-two decisions with no round structure to decompose along.
The third, and I think the fatal one, is a small public belief state. The technique that actually cracked no-limit hold’em is continual re-solving: you re-solve a subgame from a compact summary of what everyone publicly believes. That works because a poker player’s private information is a single hole-card combination, one of 1326, fixed at the deal and never added to. The belief is a 1326-vector per player and it stays that size all game.
Exploding Kittens has no such summary, because private information here accumulates by observation rather than being dealt once. Every card you draw is yours alone to see. See the Future gives you a private view of a pile both players are reasoning about. And when you defuse a kitten, you choose where to put it back without revealing the position. A player’s private state is their entire observation history, and the space of those grows with the length of the game rather than staying fixed at 1326.
Sampling is not a panacea
The same distinction sharpens what goes wrong with sampling. External sampling is the well-behaved MC-CFR variant — low variance, reliable convergence — and the natural worry is that a single iteration is simply too expensive on a tree this deep. It isn’t. go-cfr samples chance nodes rather than enumerating them, so an iteration branches only at the traversing player’s own decisions, about ten of them at 3.5 actions each: something like 107 node visits, well under a second.
The problem is coverage, not cost. Each iteration touches on the order of 105 to 106 information sets. Against 1018 of them, you need something like 1012 iterations before the average infoset has been visited once. The iterations are cheap and there are far too many of them. That is also the arithmetic behind the tabular policy: Cepheus solved heads-up limit hold’em tabularly, and even after suit isomorphism collapses it to about 1013 infosets, this game is five orders of magnitude beyond that.
What I tried anyway
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. If you need 1012 iterations, the obvious move is to make each one much cheaper, and the cheaper sampling schemes — outcome sampling and its relatives — walk a single trajectory instead of a subtree. You buy several orders of magnitude of iterations and pay for them 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) and a baseline network, and eventually a switch to MCTS with policy-space response oracles and fictitious play. The game outlasted all of them.
Still, I got a lot out of it. I understand imperfect-information games far better than when I started, and I’ve enjoyed following some of the recent work in this field. I also picked up a good deal about writing high-performance Go — something that has been useful in my day job 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.
- Bowling, Burch, Johanson, and Tammelin, “Heads-up Limit Hold’em Poker is Solved”, 2015.
- Brown, Lerer, Gross, and Sandholm, “Deep Counterfactual Regret Minimization”, 2019.
- Steinberger, Lerer, and Brown, “DREAM: Deep Regret Minimization with Advantage Baselines and Model-free Learning”, 2020.
- Cowling, Powley, and Whitehouse, “Information Set Monte Carlo Tree Search”, 2012.
