Very briefly, when a game of Uno starts, all players hold 7 cards in their hand and one starting card is face-up on the table. The players take turn to discard from their own hand onto the face-up card on the table, as long as they hold a matching card in their hand. If they cannot, they have to draw a new card. The first player to have an empty hand wins. There are some special cards that have effects such as reversing the turn order, forcing an opponent to draw extra cards, or blocking the next opponent from playing one turn.

Normally, Uno is played with hidden cards. My son (at age 4) plays with open cards, so I figured I’d make my program treat Uno as a perfect information game.2² Note that while the game has perfect information, it also has uncertainty: the outcome of drawing new cards is non-deterministic. This was fortunate because it’s much easier to write an ai for such a game, but it also became the downfall for the solver because apparently, once the ai is decent, it becomes really good at denying its opponent a win when playing with open cards.

It knows exactly which cards to play to block the opponent from playing3³ And in some situations it even moves further from winning itself, because it can do so while increasing the overall uncertainty of who the winner is going to be. Essentially, once it’s fairly sure it will lose, it focuses on just introducing chaos to the game to even out everyone’s chances – because that also increases its own chances., and this means a large fraction of the games it plays, it runs into a stalemate. (The cards in the deck run out and nobody can play anything.)

This makes it more time consuming to evaluate ai against each other. If 80 % of games are stalemates, then one needs to simulate 5× as many games to get the same quality data on wins and losses. Since I wrote the engine with the goal of modularity rather than performance, a simulated game could take a few seconds even on good hardware.

The first baseline ai was one which enumerated all possible actions it could perform, then for as long as it had time left in its budget, went through each action, simulated the outcome of it, and played that outcome out until the end using uniformly random moves. Then when its time budget was out, it picked the action that had the greatest win rate among its random playouts.

The Uno branching factor is fairly low. There’s often only one or two legal actions a player can perform. So the baseline ai spent a lot of time re-treading its steps through the first few nodes of the game tree. I figured maybe that could be avoided by distributing \(n\) playouts evenly across the valid actions, and then subdividing them into the valid children of each action, and so on. This worked, but I couldn’t get the allocation logic tight enough to actually save any time over the baseline ai, which meant the baseline ai could run more playouts within its time budget, and thus was stronger anyway.

Then I read up on the basics of Monte Carlo tree search (mcts), which is a little like the allocating ai just described, excpt mcts dynamically allocates more playouts to the more promising actions (instead of uniformly across all branches). Again the same problem: the bookkeeping logic for constructing the game tree cost more than it was worth. Using that part of the time budget to cram in more playouts instead (which is what the baseline ai does) comes out on top.

Rather unsatisfying!

I learned a little about playing Uno, but not all that much. I suspect if I want to go further, I will need to make the ai capable of handling imperfect information, i.e. they need to play with hidden cards.4⁴ I have started skimming what I think is a PhD thesis from a Daniel Whitehouse which covers this topic in some detail. Depending on how fun it sounds, I might tackle it some day. That’s the way the game is supposed to be played anyway, and it might reduce the incidence of those annoying stalemates.

Also now that I know the rules and I have proved to myself I can write a modular engine for Uno, I can probably also spend some time rewriting it with a fixed feature set, but running more quickly.