Recommend
4 
 Thumb up
 Hide
12 Posts

Codenames» Forums » General

Subject: Number of possible unique games rss

Your Tags: Add tags
Popular Tags: [View All]
John Gallant
Canada
Dartmouth
Nova Scotia
flag msg tools
Avatar
mbmbmbmbmb
Since the game game out I've always wanted to figure out how many unique combinations of setups there are given 200 double sided cards, 40 key cards with 4 orientations. The double sided bit gave me a bit of trouble, but I figured it out using some smaller number cases and after seeing a similar treatment buried in the comments here addressing something else.

It ends up being a permutation problem without repetition of the form

n!/(n-r)! where n is 200 and r is 25 spots on the board. This gets you the number of ways to arrange the cards.

Each of the spots can have 2 configurations, side 1 or side 2 which gives another term of 2^25.

Multiply those two by 40 keys times 4 configurations gets you a total of
3.765464 x 10^66 which is about 4 billion times more games than there are atoms in the solar system.

Pretty neat!
8 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ben Kyo
Japan
Osaka
flag msg tools
Forward 1, Forward 2, Forward 3... siege attack 5?
badge
Why for this life there's no man smart enough, life's too short for learning every trick and bluff.
Avatar
mbmbmbmbmb
Clearly the game needs more cards =P
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Weiding Han
Singapore
flag msg tools
Avatar
mbmbmbmbmb
Cheeseburger wrote:
Since the game game out I've always wanted to figure out how many unique combinations of setups there are given 200 double sided cards, 40 key cards with 4 orientations. The double sided bit gave me a bit of trouble, but I figured it out using some smaller number cases and after seeing a similar treatment buried in the comments here addressing something else.

It ends up being a permutation problem without repetition of the form

n!/(n-r)! where n is 200 and r is 25 spots on the board. This gets you the number of ways to arrange the cards.

Each of the spots can have 2 configurations, side 1 or side 2 which gives another term of 2^25.

Multiply those two by 40 keys times 4 configurations gets you a total of
3.765464 x 10^66 which is about 4 billion times more games than there are atoms in the solar system.

Pretty neat!


Awesome calculations!

I was wondering though... the layout has a 4-fold rotational symmetry, as with the key cards. Wouldn't there be a reduction to the number of unique games? e.g. (Layout A in upright position with Key Card 1 in upright position) = (Layout A rotated 90 degrees clockwise with Key Card 1 rotated 90 degrees clockwise)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
John Gallant
Canada
Dartmouth
Nova Scotia
flag msg tools
Avatar
mbmbmbmbmb
I think it still counts as a unique setup for the game since the locations of the red and blue spies will change relative to the spymasters so it adds another layer of possibilities to the grid.

Edit: upon further thought you may be right. I'll think more about it tomorrow
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jorgen Peddersen
Australia
Sydney
New South Wales
flag msg tools
Avatar
mbmbmbmbmb
It's reduced even further if you consider rearranging a team's words or the innocent bystanders amongst each other.

For example, let's say that blue has to guess the words in the top-left and top-right corners (amongst others). It makes little difference if word A is on the left and word B is on the right or vice versa. Sure, the board looks different, but the layout is really irrelevant to the game.


Edit: I believe rotation will only reduce the number by a factor of 4. The rearrangement issue I mention here would reduce by 9!*8!*7! that would give you the number of combinations of words for each team (and the bystanders) rather than the permutations of the words for the teams.

Edit2: Hmm, there are even fewer combinations than I calculated too. Effectively, the same combination of words for each team with a different choice of key card is effectively the same game according to my logic above. This makes the key cards completely irrelevant to the number of real game states, they just add a random perturbation so you can't cheat by remembering where all the words are.
4 
 Thumb up
0.05
 tip
 Hide
  • [+] Dice rolls
Weiding Han
Singapore
flag msg tools
Avatar
mbmbmbmbmb
Clipper wrote:
It's reduced even further if you consider rearranging a team's words or the innocent bystanders amongst each other.

For example, let's say that blue has to guess the words in the top-left and top-right corners (amongst others). It makes little difference if word A is on the left and word B is on the right or vice versa. Sure, the board looks different, but the layout is really irrelevant to the game.


Edit: I believe rotation will only reduce the number by a factor of 4. The rearrangement issue I mention here would reduce by 9!*8!*7! that would give you the number of combinations of words for each team (and the bystanders) rather than the permutations of the words for the teams.

Edit2: Hmm, there are even fewer combinations than I calculated too. Effectively, the same combination of words for each team with a different choice of key card is effectively the same game according to my logic above. This makes the key cards completely irrelevant to the number of real game states, they just add a random perturbation so you can't cheat by remembering where all the words are.


Indeed! The number of unique scenarios would then be [# of combinations from choosing 25 cards from 200]*[# of combinations from 2 sides of a card]*[# of combinations from choosing 9 team 1 words, 8 team 2 words and 7 bystander words]= (C[200,25])*(2^25)*(C[25,9]*C[16,8]*C[8,7]) = 3.19E50.

But I'll never say no to more cards in the future! laugh
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lee Fisher
United States
Downingtown
PA
flag msg tools
badge
Avatar
mbmbmbmbmb
how many "key cards" can the app generate?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Curtis Reubens
United Kingdom
Harrow
Middlesex
flag msg tools
mb
Doesn't matter; by the above, more keycards don't actually make more game states
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Gallo
United States
New York
flag msg tools
Don't worry there will be more cards. I'm pretty sure when I watched the interview Jason Levine of the Dice Tower did with Vlada he said that they'd be releasing more word cards although at that time there was nothing to announce so it still looks like they're working on the word list.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
BoardGameCo
United States
Charlotte
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
I'm not a mathematician so correct me if I'm wrong; but isn't the order moot? Everything to do with teams, or code cards, or permuations within the grid is all a smoke screen. Meaning I think the real equation is from a deck of 200 cards, how many different ways are there to pick 1 card, then 9, then 8, then 7 for the 4 possible "types" a card can end up being. The order of cards within that 9, then 8, then 7 doesn't matter. Only which type a card ends up being.

Step 1:
Pull off one card, that's your X card. There are so far 200 different configurations possible.

So far that's 200 possible games.

Step 2:

The next step is really from 199 unique cards, how many different ways are there to get 9 unique cards, if the order of those 9 cards doesn't matter (for team A).
A bit of searching found this: http://mathforum.org/library/drmath/view/56212.html
Which seems to go into the math fairly well.

That leaves us with an equation...
199*198*197*...11*10
---------------------divided by
9*8*7*...2*1 (= 362880)

This is so large, most calculators call it infinity. That being said, I found one calculator that gives me the correct answer of 2.994556962e+361

Step 3:

The next step is really from 190 unique cards, how many different ways are there to get 8 unique cards, if the order of those 8 cards doesn't matter (for team B).

That leaves us with an equation...
190*189*188*...10*9
---------------------divided by
8*7*6*...2*1 (= 40320)

This one gives me 5.9545478159e+342

Step 4:

The next step is really from 182 unique cards, how many different ways are there to get 7 unique cards, if the order of those 7 cards doesn't matter (for neutral).

That leaves us with an equation...
182*181*180*...9*8
---------------------divided by
7*6*5*...2*1 (= 5040)

This one gives me 2.60531544e+326

Step 5:
Multiply all the above together =
200 * 2.994556962e+361 * 5.9545478159e+342 * 2.60531544e+326

which is 9.2911971e+1032, and that's before dealing with the double sided cards.

Is my math wrong? My numbers are clearly much higher than John's....but when I look at the logic it seems sound to me.

And for an idea of how large that number is, here's what a deck of cards looks like:
https://youtu.be/ObiqJzfyACM?t=860

And that's just 52 factorial. The above number of is so large that you have to multiply 52 factorial by itself 15 times to get to it.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Weiding Han
Singapore
flag msg tools
Avatar
mbmbmbmbmb
alexsr wrote:
I'm not a mathematician so correct me if I'm wrong; but isn't the order moot? Everything to do with teams, or code cards, or permuations within the grid is all a smoke screen. Meaning I think the real equation is from a deck of 200 cards, how many different ways are there to pick 1 card, then 9, then 8, then 7 for the 4 possible "types" a card can end up being. The order of cards within that 9, then 8, then 7 doesn't matter. Only which type a card ends up being.

Step 1:
Pull off one card, that's your X card. There are so far 200 different configurations possible.

So far that's 200 possible games.

Step 2:

The next step is really from 199 unique cards, how many different ways are there to get 9 unique cards, if the order of those 9 cards doesn't matter (for team A).
A bit of searching found this: http://mathforum.org/library/drmath/view/56212.html
Which seems to go into the math fairly well.

That leaves us with an equation...
199*198*197*...11*10
---------------------divided by
9*8*7*...2*1 (= 362880)

This is so large, most calculators call it infinity. That being said, I found one calculator that gives me the correct answer of 2.994556962e+361

Step 3:

The next step is really from 190 unique cards, how many different ways are there to get 8 unique cards, if the order of those 8 cards doesn't matter (for team B).

That leaves us with an equation...
190*189*188*...10*9
---------------------divided by
8*7*6*...2*1 (= 40320)

This one gives me 5.9545478159e+342

Step 4:

The next step is really from 182 unique cards, how many different ways are there to get 7 unique cards, if the order of those 7 cards doesn't matter (for neutral).

That leaves us with an equation...
182*181*180*...9*8
---------------------divided by
7*6*5*...2*1 (= 5040)

This one gives me 2.60531544e+326

Step 5:
Multiply all the above together =
200 * 2.994556962e+361 * 5.9545478159e+342 * 2.60531544e+326

which is 9.2911971e+1032, and that's before dealing with the double sided cards.

Is my math wrong? My numbers are clearly much higher than John's....but when I look at the logic it seems sound to me.

And for an idea of how large that number is, here's what a deck of cards looks like:
https://youtu.be/ObiqJzfyACM?t=860

And that's just 52 factorial. The above number of is so large that you have to multiply 52 factorial by itself 15 times to get to it.



Indeed the idea is right but the formulas used from step 2 onward are incorrect:

Picking 9 cards from 199 => C(199,9) is

(199*198*197...*191)
-------------------- divided by
(9*8...*1)

The website you've referenced is correct but unfortunately chose a confusing example (6*5*4 because its 3 terms, not because you stop right before 3)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
BoardGameCo
United States
Charlotte
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
Darn...so that means the actual answer is 8.472836335469458707784E+42; which is actually a little bit less than 52 factorial. Still pretty darn high though.

In fact, if you set a timer for that number in seconds; and then every billion years you spent 1 cent of Bill Gates net worth (79.2 billion), but that when you were done spending his fortune, you turned to the person next to you, and he/she spent 1 cent of Bill Gates net worth every billion years, and when he was done, the next person started, until all 7 billion people on planet earth had repeated that cycle of spending 79.2 billion dollars 1 penny at a time. Repeat that cycle 4846 more times and you'll finally have run down the timer.

Weiding, thanks for the correction!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.