Recommend
2 
 Thumb up
 Hide
14 Posts

Hanabi» Forums » Strategy

Subject: Near-optimal hanabi strategy (with extreme amount of convention) rss

Your Tags: Add tags
Popular Tags: [View All]
Jeff Wu
United States
California
flag msg tools
I came across this paper:

https://d0474d97-a-62cb3a1a-s-sites.googlegroups.com/site/rm...

which contains a very nice idea for Hanabi strategies. They're able to achieve an average score of 24.68 in 5 player games! I've not seen this mentioned elsewhere in these forums.

I've managed to reproduce their results at https://github.com/WuTheFWasThat/hanabi.rs, and even improve on them! So that contains the code for the highest scoring Hanabi strategy I know of

I'm curious whether anyone else is aware of strategies achieving such high scores.

Note: this strategy is highly impractical for humans to actually play with - however, it is theoretically sound (as the code proves) and is *not cheating*. also, this strategy works less well with 3 players, and quite poorly for 2.

Second note:
For those curious and want the quick explanation, the basic idea is this: imagine instead of a whole hand of cards, each person just had a 0 or 1. now when I'm hinting, I will hint a color if the sum of everyone's hand (besides mine) is even, and a value if the sum of everyone's hand is odd. Doesn't matter who I hint to. Now, *everyone* will learn the bit of their own hand. Why? They know the sum, and they know the value of everyone but their own.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sean McCarthy
United States
Seattle
Washington
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
That's pretty fascinating. Who is the author?

Quote:
I'm curious whether anyone else is aware of strategies achieving such high scores.

I've talked about this a lot with friends, albeit with the original ruleset (in Hanabi & Ikebana) that doesn't explicitly disallow null clues and was later clarified explicitly to allow them. Main credit for this strategy goes to Jonathan Anderson.
https://boardgamegeek.com/article/6812269#6812269
https://boardgamegeek.com/article/19494563#19494563

Edit: Ah, just noticed that it's for 5 players only. That's how they're able to get up to 8 distinct guaranteed clues despite not playing with null clues. I guess that's why I've been thinking that this type of strategy would be inferior to natural conventions once you remove the null clue ability - I think of 4 player as the canonical version of the game. Not that it's any less impressive!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Wu
United States
California
flag msg tools
Yes - it is very similar to the idea you mentioned there! With the null clue ability, this strategy indeed becomes even more powerful, I think probably substantially. I could try running that experiment later.

Re 5 players: it's quite good for 4 players too - currently a 24.76 average. and 23.357 for 3 players

Actually, I had to make the following improvement from the paper to give 3(n-1) possibilities instead of 2(n-1): hint either color of 1st card, value of 1st card, or a hint not involving the 1st card (guaranteed to exist if hand is at least size 4)

EDIT TO ADD: re author:
How to Make the Perfect Fireworks Display: Two Strategies for Hanabi
Cox, Christopher; de Silva, Jessica; Deorsey, Philip; Kenter, Franklin H. J.; Retter, Troy; Tobin, Josh
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Corrigan
United States
Portland
Oregon
flag msg tools
badge
[[img]https://boardgamegeek.com/jswidget.php?username=Krsnaji&numitems=5&header=1&text=title&images=medium&show=recentplays&imagesonly=1&imagepos=left&inline=1&addstyles=1&domains%5B%5D=boardgame&imagewidget=1[/img]
Avatar
mbmbmbmbmb
I too have perfected a method of cheating in which I inform my fellows just how our clues syntax and our hand management is to be used to communicate more than the legal standard clue information. Alternatively we have just found it a tad easier to not bother to seting up asome arcane cheating pre game language code but instead to simplify our cheating and just say any extra clue information we would have communicated via our syntax code info, why bother and pretend? Just use simple English. But I guess figuring how to cheat is also a form of a game too.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Nico Robbemont
Belgium
Hoogstraten
flag msg tools
Avatar
mbmbmbmbmb
Krsnaji wrote:
I too have perfected a method of cheating in which I inform my fellow's just how our clues syntax and our hand management is to be used to communicate more than the legal standard clue information. Alternatively we have just found it a tad easier to not bother to seting up asome arcane cheating pre game language code but instead to simplify the cheat and just say any extra clue information we would have communicated via our syntax code info, why bother and pretend? Just use simple English. But I guess figuring how to cheat is also a form of a game too.
From a mathematical perspective this is an interesting exercise.
But in my gaming book this is indeed serious cheating!
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Dylan Thurston
United States
Bloomington
Indiana
flag msg tools
Avatar
mbmbmbmbmb
Here's a version of the article giving the authors: http://www.ingentaconnect.com/contentone/maa/mm/2015/0000008...
You can get the code from one of the author's web pages:
https://github.com/rjtobin/HanSim

I think strategies like this are another way to play, and not cheating (although actually using a computer at the table would be cheating). But if you're going to do this, you should make the game harder.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Travis Cooper
United States
Salt Lake City
Utah
flag msg tools
badge
Avatar
mbmbmbmb
Playing the standard variant, our group will routinely get 25s. I haven't done an analysis on our average score, but we know each other so well that we find it pretty boring to play with just the standard 5 colors. My point here is that I don't think you need some elaborate, confusing system in order to get good scores. From a mathematical/computer science perspective I find this an intriguing idea though. Figuring out how to get computers to play this game at the highest possible level would be an interesting problem to try and solve, but I don't think I'd have fun playing the game that way.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Dylan Thurston
United States
Bloomington
Indiana
flag msg tools
Avatar
mbmbmbmbmb
monkeyboy157 wrote:
I haven't done an analysis on our average score, but we know each other so well that we find it pretty boring to play with just the standard 5 colors. My point here is that I don't think you need some elaborate, confusing system in order to get good scores.
Right. The standard 5-color game is ultimately too easy for this kind of analysis. I'm surprised that they only got to 75% success, and suspect that much of that comes from deck construction issues. I'd be interested to see how this kind of strategy would fare in a harder setup.
Quote:
From a mathematical/computer science perspective I find this an intriguing idea though. Figuring out how to get computers to play this game at the highest possible level would be an interesting problem to try and solve, but I don't think I'd have fun playing the game that way.
Well said!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sean McCarthy
United States
Seattle
Washington
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
WuTheFWasThat wrote:
Actually, I had to make the following improvement from the paper to give 3(n-1) possibilities instead of 2(n-1): hint either color of 1st card, value of 1st card, or a hint not involving the 1st card (guaranteed to exist if hand is at least size 4)

Yeah I was feeling like there had to be a way to get more options. Good thinking!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Wu
United States
California
flag msg tools
monkeyboy157 wrote:
From a mathematical/computer science perspective I find this an intriguing idea though. Figuring out how to get computers to play this game at the highest possible level would be an interesting problem to try and solve, but I don't think I'd have fun playing the game that way.
Yes - I agree with this sentiment as well

dthurston wrote:

The standard 5-color game is ultimately too easy for this kind of analysis. I'm surprised that they only got to 75% success, and suspect that much of that comes from deck construction issues. I'd be interested to see how this kind of strategy would fare in a harder setup.

What kind of variants do you have in mind? I think this strategy would do well on the rainbow variant, as the nature of the actual hint's reveal is mostly irrelevant. It does cause the 3(n-1) to become a 2(n-1) again, though. It should generalize pretty well to other variants too, I would imagine. Also, their 75% was with a somewhat rough pass. In the last two days, after getting a basic version implemented, I've improved it to 90%
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Aaron Goldsmith
msg tools
If you're going to do a hat game, why not do a hat game with 40 colors rather than just 8 (in 5 player game allowing null clues)? Then, you can communicate 40 different (quantifiable) scenarios to each of your 4 comrades with just one clue.

If you don't allow null clues, you could still get a good fraction of 40. Maybe it would be good to assume each player always has at least two colors and at least two numbers. Then you have at least 16 different scenarios with each clue. Plus, in the difficult rainbow version, you have all five colors in a hand with just one rainbow card.

I have to admit, though... I would really like a strategy that would make sense to all sufficiently experienced Hanabi players around the universe, without having to explain it beforehand.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Wu
United States
California
flag msg tools
Yes, with null clues you get a lot more clues.

But the other case is more subtle than you think. First - it's very dangerous to assume things that might be wrong, since *everyone* will receive a false clue. But the real problem is that even assuming 2 colors and 2 numbers isn't enough - they have to know what the hints mean. I.e. if I give player 3 a hint of green, how does player 3 know that green is color 2 and not color 1?

But you're right you could get more clues by working off public info, which I've put as a TODO for myself
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Rousselle
United States
Metairie
Louisiana
flag msg tools
I had devised a similar strategy for 5 player. I would like to think my conventions are easier to understand than those in the article. I'm a mathematician & I don't think the system outlined in the article is easy to understand.

I realize the article was written for a journal. My convention was written for players.

I'll try to clean it up & post it to the this site on a separate thread. The title will be something like "5 player strategy".
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Clive Jones

Cambridgeshire, UK
msg tools
mb
Iiinteresting! I'd considered various encodings but, despite being well aware of hat-guessing problems, somehow overlooked their applicability.


I think I can build something pretty simple and very good by combining that paper's thoughts with my own existing ones. I'll confine myself to:
• Four players
• Include multicoloured cards (treating them as being every colour)
• Null clues are permitted

Each person has 30 clues available to them (5 ranks and 5 colours to each of 3 other players). Label these so each is the composition of a rank clue modulo 5 and a colour clue modulo 6.

Every player's hand contains a mixture of identified and unidentified cards. Whenever a player gives a clue, they identify each other player's newest unidentified card (omitting players with no unidentified cards). Sum all the identified ranks modulo 5, sum all the identified colours modulo 6, give the corresponding clue.

Now just add some heuristics. Off the top of my head...

Define a card as "playable", or "dead" = a duplicate of something already played, "safe" = an unplayable duplicate of something not yet discarded, "unsafe" = an unplayable card that isn't safe.

Define a player as "blocked" if none of their identified cards is playable, dead or safe, and there are no cluestones available.

Define a player as "ill-informed" if no identified card is playable or dead, but at least one unidentified card is.

Define a player as "unblocking" if they know of at least one playable 5 or safe card.

Then do the first of these which is possible:
• If there is no unblocking player between you and a blocked one, unblock
• Play
• If any other player is ill-informed, clue
• Discard a dead card
• If any other player has unidentified cards, clue
• Discard a safe card
• Give a dummy clue
• Discard an unidentified card (risking an imperfect score)
• Discard the highest-ranked unsafe card (guaranteeing an imperfect score)

I should probably code this up and see how it fares.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls