Comment by hangsi | Hacker News Reader

Comment by hangsi | Hacker News Reader

This is an interesting view of how random number based security is compromised for economic practicalities (though the meanings of "security" and "compromised" might be overstretched here).

For completeness, I wondered how many cards would be required to give the complete set of patterns.

If we number the positions in the 5x5 grid such that the top row has positions 1-5, the second row has 6-10 and so on, the grid positions can be converted to a sequence and we can use the permutation formula to find the number of arrangements. To account for rotations, we can divide the final value by 4 since every arrangement can be rotated and is therefore valid.

Of the 25 cards, there are 7 white, 8 red, 8 blue, 1 black and 1 double agent that can be red or blue, also deciding which team goes first. We can treat this final card as one of a kind, then double the formula output to account for cases where it is swapped to the other team.

Permutations of a multiset has a standard formula [0] that calculates a result from these values (rolling in the double agent factor of 2 and rotation division factor of 4):

25! / (7!8!8!1!1! * 2) = 946,551,177,000

(edit: as pointed out, this is 9 times too large as the double agent can indistinguishably replace each of the other 8 cards - a corrected value is 105,172,353,000)

This is (edit: still) more layout cards than have ever been printed across all production runs of Codenames, and would probably not fit into the current box size.

[0] https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_...

> To account for rotations, we can divide the final value by 4 since every arrangement can be rotated and is therefore valid.

Note that this is only approximately correct, since some layouts will have nontrivial symmetries. (Edit: Actually no they won't due to parity reasons! Oops. So that step is exact after all.)

Edit: Actually, this isn't correct either, and in a more serious way:

> Of the 25 cards, there are 7 white, 8 red, 8 blue, 1 black and 1 double agent that can be red or blue, also deciding which team goes first. We can treat this final card as one of a kind, then double the formula output to account for cases where it is swapped to the other team.

On the layout cards, nothing distinguishes the double agent -- the double agent is purely a matter of representation, it's not part of the actual layout. So doing things this way will give you a number that's too large by a factor of about 8 or 9.

What you want to do here (ignoring rotations) is take 25!/(9!8!7!) to get the count with 9 red and 8 blue, then double it to include the count with 8 red and 9 blue, then divide by 4 to account for rotation (contrary to what I said earlier no need to account for symmetries because the numbers mean that none of the layouts can be rotationally symmetric), so you get a total of

25!/(9!8!7!2) = 105,172,353,000

So yeah about 9 times smaller than what you wrote. For what it's worth, anyway. :P

Yes, I agree completely - I realised something was off in an espirit de l'escalier way not long after I posted.

This is great news for my proposed box redesign!

> Actually no they won't due to parity reasons!

Can you elaborate? I think I can construct some boards that effectively have complete rotational symmetry.

For the purposes of the game, black can be thought of as another white card (since you will never reveal it in the middle of a round), and the double agent can be placed in the center. Then, you just need to place the remaining categories with rotational symmetry (e.g. red on the two main diagonals, and blue on the squares directly clockwise from those). So, for instance:

  RBwwR
  wRBRB
  wBdBw
  BRBRw
  RwwBR

(w)hite and (d)ouble-agent are in lowercase; feel free to replace any single white square with blAck (Assassin).

Double agent isn't a color that appears on the card. A card has 7 white spaces, 1 black space, 9 spaces of one color, and 8 spaces of the other color. If you think that white and black are separate colors, you can't make a rotationally symmetric 5x5 board.

From the perspective of a player who is memorizing boards, it's beneficial to know which square is black, so as the memorizer's adversary it's probably best to put the black square in all 8 non-blue non-red squares for a given layout of blue and red squares.

The reason why I claim that black is uninteresting for the purposes of board memorization is that if you are explicitly stalling until there is enough information to uniquely identify the game board, then either the black square is never uncovered, or the opposing team uncovers the black square, in which case you win automatically.

It's not difficult to be adversarial against the proposed naive strategy (just generate boards with enough overlap such that you can't uniquely identify them from such a small number of revealed squares), but it's easiest to generate fully random boards (without any concerns for "weird" boards) and be done with it.

You could eliminate a board from consideration because a square was revealed to be white rather than black.

Reply on news.ycombinator.com