Live data from Hacker News

Building AI that can master complex cooperative games with hidden information

ai.facebook.com

11–20 of 29 posts

Re: Building AI that can master complex cooperative games with hidden information

#11
post #5

Earlier quoted context omitted.

Hey Noam, this is some great work; I'll need to sit down and give the paper a deeper read. Also, the visualizations on this blog post are incredible. I saw a talk on the Libratus agent a while back, and one of the most interesting takeaways was that the behavior of the bot had already started to impact the professional players, who now spontaneously bet large amounts to force other players out of a hand. Were there a…

In terms of Hanabi, this bot arrived at conventions that are pretty different from how humans play the game. We invited an advanced Hanabi player to play with the bot and he pointed out a few things in particular that he'd like to start using. For example, humans usually have a rule that if your teammate hints multiple cards of the same color/number, you should play the newest one. The bot uses a more complicated rul…

> For example, humans usually have a rule that if your teammate hints multiple cards of the same color/number, you should play the newest one. The bot uses a more complicated rule: if the card you just picked up was hinted then play that card, otherwise play the oldest hinted card. That gives you way more flexibility to hint playable cards that would otherwise be tough to get played.

I've definitely seen advanced Hanabi players use a more subtle version of that rule: "If your hint looks like it's telling me to play my leftmost hinted card, how long has that card been playable? If it could have been hinted for play a long time ago, and it's just being hinted now, it must not be playable. So what else must you mean...?"

That version of the rule allows for more subtle cases. Suppose you hint that a player's second-from-the-left and fourth-from-the-left cards are both red. If there hasn't been an opportunity to hint the second-from-the-left since it became playable, go ahead and play the second-from-the-left. If there have been opportunities to hint second-from-the-left, play fourth-from-the-left.

That rule requires human players to model whether the other players' actions in the interim have been "urgent" things that needed taking care of before hinting them, or whether those other players would have hinted them sooner if their card was playable.

Re: Building AI that can master complex cooperative games with hidden information

#12
post #2

they (basically) applied the ideas from a bot that plays poker to another game. it's interesting work, though perhaps not groundbreaking. This idea of selfplay + counterfactual regret minimization does seem to be the superior way to solve game theoretic problems. Identifying valuable game theoretic problems remains a challenge...

Hanabi definitely has traits involving theory of mind that I've not seen present in other games. For example, I've played Hanabi with 3+ players where the person before me deliberately gave a misleading hint to the person after me. For example, "this is your only blue card" indicating a blue 5 even though only blue 1-3 have been played. They were counting on me to anticipate that the mislead person was now very likel…

> For example, I've played Hanabi with 3+ players where the person before me deliberately gave a misleading hint to the person after me. For example, "this is your only blue card" indicating a blue 5 even though only blue 1-3 have been played. They were counting on me to anticipate that the mislead person was now very likely to waste that valuable card & realize that I could only reasonably avert that misplay by playing a blue 4, which is how I came to realize that I must be holding a blue 4.

(In Hanabi convention, that kind of hint is typically called a "finesse".)

Hanabi has a huge amount of depth in modeling other players. (To the point that the most common failure mode in Hanabi is assuming too much about the reasoning another player will do, or overthinking things in "iocaine powder" style, "but you know that, but I know you know that, but ...".) In general, you can often assume your partners can make use of most the information available to them, especially when playing electronically with an interface that makes all that information readily visible, such as "what hints have everyone received and which cards did those hints identify". (As a notable exception, it's relatively uncommon to use "negative information" if it isn't being tracked for you, such as "this card isn't red or blue because you've gotten red and blue hints that didn't point to it".)

One thing this article doesn't talk about in detail is how well the bot manages to make plays that humans can understand when playing alongside it. (The article mentions things that improve play with humans, but doesn't mention how well human players can understand and cooperate with the bot using common conventions. The comments here do talk about that, though!) The article focuses on the bot playing itself.

I would expect that when playing itself the bot can learn to give hints that will result in multiple successful plays; that'll be especially true when expanding to 3+ players. Effectively, the bot can learn to communicate with itself using hints as a channel to provide information. The question then becomes, are those hints trained for maximum information efficiency at the expense of human understanding, or are those hints something that relies on logical reasoning humans can cooperate with?

A group of human players who know they'll only be playing with each other could absolutely develop a set of conventions more efficient and effective than those commonly used for playing with unknown players. Those conventions will then be completely baffling to anyone outside that group, and will result in serious losses when playing with anyone else.

In the end this can become an information-theory issue: how many bits of information does each player need to know what to play, and how efficiently can you communicate that information to all players in time for them to play, using the limited information channels of hints and discards and plays and even intentional misfires. And you might be able to squeeze even more information through that channel if you can Huffman-code it based on the likelihood of possible game states in other player's minds. If you know the other players are copies of you or very similar to you, and are doing similar modeling and assuming others are doing similar modeling, then you can encode the information very densely.

But maximizing the information-theoretic bandwidth of that communication channel doesn't necessarily result in hints that support logical reasoning. That requires modeling other players who aren't necessarily copies of you, and figuring out how they'll understand your hint or play.

High-level Hanabi play absolutely results in complex multi-level models of other players. You don't just need to model the other players, you also need to model how the other players will model others, including you.

Some examples of the kinds of logical reasoning common in a 3+ player Hanabi game, including such multi-level models (assume you're player 1 and the players after you are 2, 3, 4, and so on):

- Finesse: Player 1 hints player 3 or later, with a hint that they could interpret as "play", which would otherwise misfire, so an earlier player knows to play a card in their hand that will work. Also note that with 4+ players, you could give a hint to player 4 or later, and the players in-between have to figure out which of them has the card to make the finesse work. Player 2 will see if any other players have a card that will work, and if so, they'll skip playing (doing something else like hinting instead) and a subsequent player will know they need to play.

- Multiple finesse: Player 1 hints player 4 or later, and multiple players in-between need to play for that hint to work.

- Bluff: Player 1 hints player 3 or later, with a hint that looks like a finesse, knowing that player 2 will think it's a finesse. Player 2 plays their card, only to find that it isn't the card that would make the hinted player not bomb, but it is a different playable card. The hinted player then needs to realize that the bluff happened, and not play the card they were hinted, but remember what card it must be to have looked like a finesse. (For instance, red 1-3 and blue 1 have been played, player 1 hints red to player 3's 5R, player 2 plays their leftmost card thinking it's the playable 4R, but it's actually the playable 2B. Player 3 now knows they have the 5R, and later in the game, once the 4R is played, player 3 plays the 5R without needing further hints.)

- Reverse finesse: Player 1 hints player 2, which might otherwise look like telling player 2 to play. But player 2 sees that player 3 or later has a playable card that it seems like you've hinted player 2 as having. For instance, red 1-3 have been played, you hint player 2's 5R as red, and player 3 has the 4R either as the newest card or as the newest card that's hinted either red or 4. Player 2 realizes that they shouldn't play their R (which they now know to be the 5R) because you are reversing player 3's 4R. Player 3 then realizes that because player 2 knew not to play the 5R, they must have the 4R so they should play it. And on the next time around, player 2 needs to remember that they have the 5R and play it without any further hint from anyone.

Re: Building AI that can master complex cooperative games with hidden information

#13
post #10

If you're wondering why this is interesting, games that AIs excel at like chess/checkers/go are all two-player, zero-sum, perfect-information (everyone knows everything), deterministic games, so you can exactly predict your opponents behavior by simulating "what would I do if I were them, and trying to make me lose". The only real hard problem in this space is extreme branching factors. Everything gets vastly more co…

In particular, communication is in some ways a complex multiplayer game requiring multi-level modeling of other participants. In the ideal case, it can be modeled as a cooperative game. In suboptimal cases that sadly occur often in the real world, it's a game where you're fractionally cooperating and fractionally competing with every other player, and the degree to which you're cooperating or competing with any given player depends on your model of them, which you update over time based on your observations of how they "play". And it's a helpful shortcut in modeling if you can group expectations of other "players" into common conventions.

Hanabi's multi-level "what is my model of each other player, and what is my model for their model of other players including me" is remarkably deeper than it looks on the surface. Play it for long enough, and you start to handle situations for which preconceived "conventions" don't help: "OK, of the four players at the table, three of them understand certain common conventions, one of them doesn't seem to understand at least one convention based on the misfire they just had/caused (which is also consistent with their low player rating), I can probably assume they don't understand any other conventions commonly considered more challenging than the one they just failed at, so if I give this hint, how will the more advanced players understand it, can I do so without the less advanced player misunderstanding it in a harmful way, and what will happen? And also, for future games, I should remember that this player doesn't know these conventions (yet) until I see evidence that they've improved. I might also consider helping them learn more common conventions. Or, if they don't know enough conventions and don't improve, I might not want to play with them in the future at all."

Re: Building AI that can master complex cooperative games with hidden information

#14
post #10

If you're wondering why this is interesting, games that AIs excel at like chess/checkers/go are all two-player, zero-sum, perfect-information (everyone knows everything), deterministic games, so you can exactly predict your opponents behavior by simulating "what would I do if I were them, and trying to make me lose". The only real hard problem in this space is extreme branching factors. Everything gets vastly more co…

>randomness is equivalent to an extra player that makes irrational unpredictable moves.

Irrational and unpredictable moves are also present in two-player perfect information games.

Re: Building AI that can master complex cooperative games with hidden information

#15
post #10

If you're wondering why this is interesting, games that AIs excel at like chess/checkers/go are all two-player, zero-sum, perfect-information (everyone knows everything), deterministic games, so you can exactly predict your opponents behavior by simulating "what would I do if I were them, and trying to make me lose". The only real hard problem in this space is extreme branching factors. Everything gets vastly more co…

> randomness is equivalent to an extra player that makes irrational unpredictable moves. Irrational and unpredictable moves are also present in two-player perfect information games.

The difference is that in something like chess, you see it happen and adjust. It probably isn't the strongest move and thus probably does more harm than good.

In something like starcraft there can be a lot of moves that can seem irrational because they are only strong if they are undiscovered for too long.

Re: Building AI that can master complex cooperative games with hidden information

#17

Hi! I'm one of the authors on the paper. We'd be happy to answer any questions. Ask us anything!

What's FB going to do with this?

Open source it, learn from it, and build upon it to continue to push forward the frontier of AI.

Re: Building AI that can master complex cooperative games with hidden information

#18

Hi! I'm one of the authors on the paper. We'd be happy to answer any questions. Ask us anything!

Isn't this not the same thing as AI that can beat humans at things like Bridge where the bidding game matters quite a lot? IIRC in Hanabi the fact that there is imperfect information does not really matter that much for strategy, where as in things like League of Legends or Bridge or many of those types of games it really does matter quite a lot.

Re: Building AI that can master complex cooperative games with hidden information

#20

Hi! I'm one of the authors on the paper. We'd be happy to answer any questions. Ask us anything!

Damn, I haven’t gotten around to fully reading Pluribus yet, and now there’s more? Congrats on the results! What’s next?
Post reply on HN