Recommend
 
 Thumb up
 Hide
24 Posts

LYNGK» Forums » General

Subject: How many possible starting positions? rss

Your Tags: Add tags
Popular Tags: [View All]
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
I have some math skills, but they're not mad enough to figure this out. I do know this much, however:

- Each of the colors are functionally the same. Red pieces on one particular whole-board arrangement will be the same as Blue, etc.
- Seems like there are many possibilities for rotations and/or reflections, which also are functionally the same.

So, anyone else also interested in knowing this and care to take a stab at it? You know, just because.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
Here's my stab. This can't be exact, but hopefully it's a decent estimate?

[C(43,8) + C(35,8) + C(27,8) + C(19,8) + C(11,8)] / 6 ~=

28,473,359
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tim K
United States
Palatine
Illinois
flag msg tools
Avatar
mbmbmbmbmb
You've got the right idea. Apply probability theory. Not clear to me if you use combinations or permutations in this case. Interesting enough to follow up, but I'd need to do it later.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
Let me take a stab at it.

There are 43 spots on the board. Let's start by forgetting about the shape. There are 43! ways of placing 43 chips. Once we identify all chips of the same color, then we realize we are overcounting. There are eight chips in each of the five main colors and three wild chips, so we need to divide by (8!)^5(3!). Furthermore, if we don't distinguish between two configurations where the main colors are permuted, then we can divide by another 5! worth of options. So, if we ignore the shape, then there are 43!/[(5!)(8!)^5(3!)] different starting positions.

Now, what kind of shape symmetries do we have? The board is essentially a hexagon (with sharp points sticking out of the side) and so has twelve symmetries (six rotations and six rotations followed by a reflection). Thus, there are 43!/[(5!)(8!)^5(3!)(12)] ~ 6x10^25 total starting positions when we account for permutations of the chips within a color, the colors, and symmetries of the board.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
France
flag msg tools
mbmbmb
repnA wrote:
Now, what kind of shape symmetries do we have? The board is essentially a hexagon (with sharp points sticking out of the side) and so has twelve symmetries (six rotations and six rotations followed by a reflection). Thus, there are 43!/[(5!)(8!)^5(3!)(12)] ~ 6x10^25 total starting positions when we account for permutations of the chips within a color, the colors, and symmetries of the board.

That may be a good approximation, but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions, so that dividing by 12 yields slightly too low a value.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
France
flag msg tools
mbmbmb
qswanger wrote:
Here's my stab. This can't be exact, but hopefully it's a decent estimate?

[C(43,8) + C(35,8) + C(27,8) + C(19,8) + C(11,8)] / 6 ~=

28,473,359

You should multiply rather than add, and then divide by 12 rather than 6 (perhaps you forgot the axial symmetry?). Would yield the same result as repnA.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
eobllor wrote:
repnA wrote:
Now, what kind of shape symmetries do we have? The board is essentially a hexagon (with sharp points sticking out of the side) and so has twelve symmetries (six rotations and six rotations followed by a reflection). Thus, there are 43!/[(5!)(8!)^5(3!)(12)] ~ 6x10^25 total starting positions when we account for permutations of the chips within a color, the colors, and symmetries of the board.

That may be a good approximation, but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions, so that dividing by 12 yields slightly too low a value.


I'm not really sure what you mean by, "but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions". Perhaps you can clarify.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
repnA wrote:
I'm not really sure what you mean by, "but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions". Perhaps you can clarify.

I.e. in some positions, the 12 rotations & rotations+reflections are not distinct.

Simple example of putting 2 As and 5 Bs on a tiny hexhex:

This has 6 distinct rotations/reflections:
A A B A B B
B B B B B A B B A
B B B B B A

B B B B A B
B B B A B B A B B
A A A B B B



but this has only 3 distinct rotations/reflections:
A B B A B B
B B B B B B A B A
B A A B B B
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
eobllor wrote:
qswanger wrote:
Here's my stab. This can't be exact, but hopefully it's a decent estimate?

[C(43,8) + C(35,8) + C(27,8) + C(19,8) + C(11,8)] / 6 ~=

28,473,359

You should multiply rather than add, and then divide by 12 rather than 6 (perhaps you forgot the axial symmetry?). Would yield the same result as repnA.


Yeah, after I posted this I thought 12 rather than 6 was probably the more accurate number to divide by. However, regarding the multiplication rather than addition ...
I can see how that would make sense if interchanging the colors mattered, but in LYNGK it doesn't. For example, if the whole board pattern/distribution of pieces was such that Red=pattern1, Blue=pattern2, etc. that would not make a lick of difference if it was Blue=pattern1, Red=pattern2, etc. So, this cuts down significantly on the number of unique board positions. That's why I think addition here makes more sense than multiplication.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
qswanger wrote:
However, regarding the multiplication rather than addition ...
I can see how that would make sense if interchanging the colors mattered, but in LYNGK it doesn't. For example, if the whole board pattern/distribution of pieces was such that Red=pattern1, Blue=pattern2, etc. that would not make a lick of difference if it was Blue=pattern1, Red=pattern2, etc. So, this cuts down significantly on the number of unique board positions. That's why I think addition here makes more sense than multiplication.

Hmm? Addition makes no sense for this kind of probability calculation. You multiply because for each way to place the first color's disks, you consider all possible ways to put the remaining disks. That kind of "for each way of doing this, we do all the remaining stuff" type problem is a a classic multiplicative probability calculation.

E.g. consider a simpler problem: how many ways to arrange 2 red and 2 blue in a row of 4? By your reasoning, that would be C(4,2) + C(2,2) = 6 + 1 = 7, right? But the correct answer is 6 (= C(4,2)*C(2,2)).
RRBB RBRB RBBR BRRB BRBR BBRR

If you want to consider that RRBB and BBRR are equivalent because colors don't matter in LYNGK, then that's a separate independent additional step (divide by 2 (=2! since 2 = number of colors in this simple example) to get 3 possible ways to arrange the row of 4).
xxyy xyxy xyyx
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tim K
United States
Palatine
Illinois
flag msg tools
Avatar
mbmbmbmbmb
qswanger wrote:
Yeah, after I posted this I thought 12 rather than 6 was probably the more accurate number to divide by. However, regarding the multiplication rather than addition ...
I can see how that would make sense if interchanging the colors mattered, but in LYNGK it doesn't. For example, if the whole board pattern/distribution of pieces was such that Red=pattern1, Blue=pattern2, etc. that would not make a lick of difference if it was Blue=pattern1, Red=pattern2, etc. So, this cuts down significantly on the number of unique board positions. That's why I think addition here makes more sense than multiplication.


I am a graduate-level educated and very experienced electrical engineer from one of the best schools in the country, but I must say nothing burns my brain more than probability theory. I always need to dig out my college textbook and walk through things carefully to be certain I'm applying the theory correctly. If any of you guys are doing this stuff off the top of your head props to you.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
France
flag msg tools
mbmbmb
qswanger wrote:
I can see how that would make sense if interchanging the colors mattered, but in LYNGK it doesn't. For example, if the whole board pattern/distribution of pieces was such that Red=pattern1, Blue=pattern2, etc. that would not make a lick of difference if it was Blue=pattern1, Red=pattern2, etc. So, this cuts down significantly on the number of unique board positions. That's why I think addition here makes more sense than multiplication.

Right, I forgot to mention you also had to divide by 5! to get repnA's result, otherwise the product represents the number of positions when the colours are not equivalent.
Addition still makes no sense to me, though.

Edit: sorry, I hadn't seen Russ's answer!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
France
flag msg tools
mbmbmb
russ wrote:
repnA wrote:
I'm not really sure what you mean by, "but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions". Perhaps you can clarify.

I.e. in some positions, the 12 rotations & rotations+reflections are not distinct.

Simple example of putting 2 As and 5 Bs on a tiny hexhex:

This has 6 distinct rotations/reflections:
A A B A B B
B B B B B A B B A
B B B B B A

B B B B A B
B B B A B B A B B
A A A B B B



but this has only 3 distinct rotations/reflections:
A B B A B B
B B B B B B A B A
B A A B B B

Thanks to clarify my point

Thus, to compute the precise number of relevant positions, we should count, for each number 0 < x < 12 (actually 2, 3, 4 and 6 only), the number y of positions having exactly x images by rotations/reflections, and then add (y/x - y/12) to repnA's value.

I said 'we should' for lack of a less tedious idea...
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
Summoning this math prof in the hopes that he has an interest in this problem and can set us straight:

David Molnar
United States
Ridgewood
New Jersey
flag msg tools
Avatar
mbmbmbmbmb

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
eobllor wrote:
russ wrote:
repnA wrote:
I'm not really sure what you mean by, "but some positions have symmetries themselves (amongst the 12 agreeing with the empty board), therefore representing less than 12 equivalent positions". Perhaps you can clarify.

I.e. in some positions, the 12 rotations & rotations+reflections are not distinct.

Simple example of putting 2 As and 5 Bs on a tiny hexhex:

This has 6 distinct rotations/reflections:
A A B A B B
B B B B B A B B A
B B B B B A

B B B B A B
B B B A B B A B B
A A A B B B



but this has only 3 distinct rotations/reflections:
A B B A B B
B B B B B B A B A
B A A B B B

Thanks to clarify my point

Thus, to compute the precise number of relevant positions, we should count, for each number 0 < x < 12 (actually 2, 3, 4 and 6 only), the number y of positions having exactly x images by rotations/reflections, and then add (y/x - y/12) to repnA's value.

I said 'we should' for lack of a less tedious idea...


I see your point now, eobllor (thanks for the assist, Russ). As to computing the correction factor, yikes. It is not obvious to me how to do that quickly.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
eobllor wrote:

Addition still makes no sense to me, though.


Okay, so that's multiple (pun intended) opinions against addition.
Like I said, my math skills are not mad skillz but for some reason I'm still thinking some addition here makes sense in the context that all of the 5 distinct patterns are interchangeable (the 3 joker pieces are always what's left over after all 5x8 colored sets have been placed). If this can be solved in an iterative manner, it seems clear to me that the 1st set of pieces provides for C(43,8) possibilities (not considering rotations and reflections at this point). After they are on the board we will have 35 spots left for the next set of 8 pieces, the color of which does not matter, hence the "...+ C(35,8)". If this was "...* C(35,8)" that would imply that each of the same colored 8 pieces was somehow different/distinct/independent.

I concede I could be totally wrong, but that what's in my head so far.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
qswanger wrote:
eobllor wrote:

Addition still makes no sense to me, though.


Okay, so that's multiple (pun intended) opinions against addition.
Like I said, my math skills are not mad skillz but for some reason I'm still thinking some addition here makes sense in the context that all of the 5 distinct patterns are interchangeable (the 3 joker pieces are always what's left over after all 5x8 colored sets have been placed). If this can be solved in an iterative manner, it seems clear to me that the 1st set of pieces provides for C(43,8) possibilities (not considering rotations and reflections at this point). After they are on the board we will have 35 spots left for the next set of 8 pieces, the color of which does not matter, hence the "...+ C(35,8)". If this was "...* C(35,8)" that would imply that each of the same colored 8 pieces was somehow different/distinct/independent.

I concede I could be totally wrong, but that what's in my head so far.


Hi, Quinn. Try an easier situation where you have four spaces and four colors. You will have C(4,1) = 4 spots for the first color. There are now three spots remaining for the second color. By your logic, that would give you C(3,1) choices and adding gives you 7 total. Continuing, you would have two choices for the next color and then 1 for the last. Adding these up gives 10 choices. However, there are actually 24 (4*3*2*1) choices here.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
I think this actually helps support my point:

In your simplified example with only 4 spaces:
R B G W is functionally the same in LYNGK as
G B W R, etc.

EDIT: The number of possibilities here is only 1!

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
qswanger wrote:
I think this actually helps support my point:

In your simplified example with only 4 spaces:
R B G W is functionally the same in LYNGK as
G B W R, etc.



Only once you start taking into account color symmetries. In that case, every one of the arrangements is functionally the same. Your argument, though, is being done pre-symmetry.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Swanger
United States
Holly Springs
North Carolina
flag msg tools
badge
Avatar
mbmbmbmbmb
Sorry, I edited my reply before you quoted me. The number of possibilities in your example is actually only 1.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adam Glesser

Placentia
California
msg tools
mbmbmbmbmb
qswanger wrote:
Sorry, I edited my reply before you quoted me. The number of possibilities in your example is actually only 1.


Right, but only if you use the additional color symmetry, which is not what you are doing in your first argument.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
France
flag msg tools
mbmbmb
qswanger wrote:
If this can be solved in an iterative manner, it seems clear to me that the 1st set of pieces provides for C(43,8) possibilities (not considering rotations and reflections at this point). After they are on the board we will have 35 spots left for the next set of 8 pieces, the color of which does not matter, hence the "...+ C(35,8)". If this was "...* C(35,8)" that would imply that each of the same colored 8 pieces was somehow different/distinct/independent.

If the 8 pieces were considered distinct from one another, you would have far more choices, you would have A(43, 8)*A(35, 8)*... instead of C(43, 8)*C(35, 8)*..., that is, 8!^5 as many choices. In both cases you use multiplications, anyway.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Yper Cube
Greece
Athens
flag msg tools
mb
I got similar numbers.

More accurately, I got lower and upper limits as 6.56 and 7.04 * 10^25 respectively.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matthias Neumann-Brosig
msg tools
mb
Concerning the correct counting, as in factoring out the symmetries, this is an instance of Burnside's lemma, as you are basically counting orbits of a finite group acting on a finite set - maybe that helps?
 
 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.