Notes

Donkeyspace

My talk from GDC 2011 has been made free in the GDC vault, you can see it here. One of the frequent comments I’ve heard is that people are confused by my discussion of what I call “Donkeyspace” so I thought I should try to clarify.

The things about Poker that make it a more interesting AI problem than something like Chess or Go are the aspects of hidden information and psychology. Really, these are the same thing, because the important information that’s hidden from you is your opponent’s psychology, her state of mind, her tendencies and plans, her strategy. Of course, the cards in your opponent’s hand are hidden from you, as are the order of cards in the deck, but this kind of uncertainty doesn’t really add that much interest to the game’s AI problem, since it just adds some simple probability calculations (simple for a computer). What makes Poker so much weirder and cooler is the way in which players infer from their opponent’s actions what’s going on in their opponent’s minds and then adjust their own strategies accordingly.

You can look at every game as a problem to be solved. We say a game is solved when we can describe how to play perfectly play from any position. Tic Tac Toe is solved. Connect Four is solved. Checkers is solved. It’s easy to imagine what it would mean for Chess or Go to be solved in this way. Once you have instructions you can follow to achieve the best outcome from any position there’s really nothing left.

But what does it mean to solve Rock Paper Scissors? It’s easy to articulate a strategy which will guarantee that you can’t be beaten, just pick randomly. When I say you “can’t be beaten” I don’t mean you’re guaranteed to win, I mean no-one can have any better strategy, there is no way of playing that will do better against you. But if you enter a RPS tournament and want to win, you should be able to do better than that. You should recognize when you’re up against a drunk dude who only throws Rock and adjust your strategy to take advantage of him. Then, when you’re up against someone throwing pure random you adjust back to random yourself to guarantee at least an even chance of winning.

This is the situation that Poker is in. It’s easy to imagine a “solved” version of simple forms of poker. And using this perfect strategy you could gurantee that no-one in the world can have an edge on you, no-one can outplay you. But that’s not the actual goal of Poker. The goal of Poker is to get that money. If you play “pefectly” against a drunk tourist, a fish, a donkey, you are throwing money away. So the real AI problem of poker is this inference problem of recognizing what type of player you are up against and adjusting your play to maximize your edge against their strategy.

Imagine all the possible strategies you could be up against plotted in a multidimensional space, over here is the “perfect” strategy, unexploitable, there’s nothing you can do against it but play it yourself. But all around it are the vast, diverse spectrum of sub-optimal strategies that people actually use. This is Donkeyspace, and your goal is to place your opponent as accurately as possible at a point in this space, and then maneuver yourself to the point that takes maximal advantage of him.

But guess what? Your opponent is doing to the same thing to you. As you maneuver through D-Space to lock onto your target, your target is simultaneously maneuvering around to get the drop on you. At the highest levels, poker is all about this dance. When Viktor Blom and Tom Dwan play, not only are they struggling like Chess players to discover perfect play, they are also moving through chaotic orbits around this undiscovered point, adjusting to their perceptions of each other’s flawed models, and then adjusting to the adjustments. This simultaneous, second-order problem solving is the big, juicy problem of Poker AI. It touches on deep, underlying dynamics of social interaction, the way we constantly interpret and adapt to the behavior of the people around us. It is, as computer scientists like to say, “non-trivial”. I think we can also call it beautiful.