Empathy in Hanabi

This is a bit of a detour from my last post. In my free time, I develop a rules-based bot that plays Hanabi. I was recently improving the algorithm below and thought to document it, since it's a pivotal part of the game and convention-agnostic.

In Hanabi, empathy is the term used to describe what other people know about their cards. For example, in a No Variant game¹, if a card was clued with 4 and not clued with red, then its empathy would be [y4,g4,b4,p4]. The fixed multiplicity of card identities in Hanabi leads to more information being available to everyone than just from clues. For example, if Alice holds a fully-clued g5, it is common knowledge that everyone else's cards cannot be g5, since there is only 1 such card in the deck.

In its simplest form, empathy depends on common knowledge: everyone knows (that everyone knows that everyone knows...) such information about a card. Things get more complicated when you start looking at asymmetric information, especially when you consider that a subset of players may share knowledge that the rest of the players do not. This post will only discuss common knowledge empathy. Some conventions sets also have the notion of good touch which can provide even more information, but that won't be covered in this post either.

In my bot, computing empathy is composed of two algorithms²:

• basic elim, when the total multiplicity of an identity is guaranteed across a set of cards
• cross elim, when the total multiplicity of multiple identities are guaranteed across a set of cards

Setup

Initially, buckets are created where a copy of every card is placed into a bucket for each possible identity it has. For example, a card that can be [y5,b5,p5] will be in the y5, b5 and p5 buckets. However, if a card has only one identity, it is not placed into any bucket. If the card is known³, the known count of that identity is increased by 1. If the known count for an identity becomes equal to the total multiplicity (e.g. two r3s), this identity is highlighted for later. The highlighted identities are then sent to basic elim.

This step just organizes the cards by their possible identities, making it easier to access all cards that could be particular identity.

Basic elim

Every card in a highlighted identity's bucket has that identity removed, unless it is already known to match. If a card is reduced to only one possible identity as a result, then it is removed from its remaining bucket and the known count of that identity is increased by 1. That may cause the known count of that identity to equal the total multiplicity, so again that identity is saved for another round of basic elim. This process is repeated until no new identities are highlighted.

This initial process is only a part of basic elim: in particular, this uses only "complete" information, such as two r2s being visible. However, basic elim can also be triggered from information such as two cards that can only be [r5,g5], which is discovered using cross elim.

Cross elim

This is similar to a sudoku technique known as the naked group (like naked single, naked double). For example, since there exists only 1 copy of r5 and 1 copy of g5, if there are two cards that have possibilities [r5, g5], then both r5 and g5 must be within those two cards and no other cards can be those identities.

A naked group is a set of cards where the size of the set is equal to the total multiplicity of the union of the cards' possible identities. For example, five cards with [r4,r5], [r4,r5], [r3,r4, r5], [r3,r5] and [r3,r4] form a naked 5-tuple. However, since the number of subsets of a set is 2^n where n is the size of the set, doing this for every possible subset would take extremely long, even if we already exclude known cards. Therefore, only unknown cards that are either clued or that have 5 or less possible identities are considered.

Even with this restriction, the search space is very large. The algorithm is recursive and attempts to add (or not add) each card to a running subset, and checks whether the required multiplicity is equal to the number of cards in the set. If so, a naked group has been found. If a card was added and the required multiplicity is greater than the number of contained cards and remaining cards combined, then it's impossible for any subset containing the current cards to ever form a naked group. The entire search branch with sets that include these cards can thus be pruned here.

Once a naked group is found, the contained cards are first attempted to be identified symmetrically. Consider again the case where two cards are [r5,g5]. If these cards are held by different players, who holds which card is in fact common knowledge! This is because the player holding one card knows that the other player can see their card and thus infer their card is the other one, and vice versa. More generally, within a naked group, if the count of visible cards of an identity is equal to the total multiplicity of that identity, the other cards in the group can eliminate that identity as long as the player holding them isn't also holding one of the visible cards.

If no symmetric information is gained, basic elim can instead be performed on the involved identities. The other cards in the relevant buckets have that identity removed, potentially causing further basic elim. Once that is completed, subsets that were previously considered in cross elim may need to be considered again, so the process is restarted from the beginning, with any newly known cards removed. Once no new naked groups are found, the empathy operation is completed.

Examples

Here's a few examples of cross elim, since the wording can be confusing.

Suppose Alice has [r5,g5] (actually r5) and Bob has [r5,g5] (actually g5) and we are Alice. This is a naked pair. To check for symmetric information, we look at the visible counts of r5 and g5. We don't see any r5s, which is less than the total multiplicity of 1, so we can't eliminate it. But we see exactly one g5, so g5 can be eliminated from our card since we aren't holding a g5. Basic elim is then performed on r5, which causes Bob's card to become exactly [g5]. Result: Everyone knows Alice has [r5], Bob has [g5].

Suppose now Alice has [r4,r5] (actually r4) and Bob has two [r4,r5] cards (actually r4, then r5) and we are Alice. This is a naked triple. We can only see one r4 when there are a total of 2 of them, but we can see one r5, so we can eliminate r5 from our card. Bob cannot eliminate r5 from his r4 card because he holds a copy of the visible r5. Basic elim is then performed on r4, but nothing occurs. Result: Everyone knows Alice has [r4], Bob has [r4,r5] [r4,r5].

Suppose Alice has [r5,y5,g5] [r5,y5,g5] (actually r5, y5) and Bob has [r5,y5,g5] (actually g5). and we are Alice. This is a naked triple. We can symmetrically eliminate g5 from our cards, making them [r5,y5] and [r5,y5], but Bob can't do any elimination (basic elim on g5 also does nothing). Our 2 cards then form a naked double, but since we can't see any r5s or y5s, no symmetric info is gained. However, r5 and y5 are both removed from Bob's card during the subsequent basic elim, since everyone knows r5 and y5 must be in our hand, just not the order. Result: Everyone knows Alice has [r5,y5], Bob has [g5].

Closing Thoughts

This is a surprising amount of work for something that relies on no conventions! Of course, it is very possible that your teammates' model of common knowledge is not as extensive as it could be due to mental limitations. However, when playing between bots or when playing online where empathy is pre-computed for human players, being able to maximize the amount of common knowledge is very important. Anecdotally, it's easy in real life to apply cross elim to 5s and other cards where only 1 identity is left (e.g. if a copy of it was discarded), but very difficult when other ranks are included. Basic elim is easily and subconsciously performed by human players.

From rough profiling, about 25% of my bot's runtime is spent computing empathy⁴. As such, I've spent a significant amount of effort improving the algorithm to its current state. I haven't seen any articles about empathy or other approaches to its implementation (though hanab.live surely has one), but I'm hoping this reveals a bit about how intricate and complex Hanabi can be. The beauty is that you might not even notice all the work your brain is doing when you play it.