Taking the random out of racking
April 4, 2012 4:24 PM Subscribe
After tens of thousands of games of pool, every time I rack the balls I seem to switch about half of them around. I know I'm wasting time. So, I want to know exactly how many balls I should normally expect to swap (the median), and what is the most I should ever have to swap. For those of you who aren't pool nerds like me, I've explained the 8-ball racking process inside.
A "proper" rack should look something like this.
There are 15 balls. 7 "stripes", 7 "solids", and one black ball.
You dump them into the triangle at random, then swap them around until you have the "correct" pattern. There are two different recognised patterns (European and American), but we'll pretend there's just one.
You can either start that pattern with stripes at the front, or solids. You can also reverse the pattern in terms of symmetry. As such, I think there are four ways of racking the balls correctly.
However, once the balls are in, you can spin the triangle into three positions, giving you 12 total possibilities.
There is a complication: the black is the only ball that has to sit on one of the inside three spots.
So, if the balls happen to land in the worst possible way, what are the most number of ball swaps that you'll ever have to make? I'm talking about straight swaps — no moving three at a time.
A second, perhaps more-important question: what's the median starting position, in terms of how many ball swaps I'll have to make?
A "proper" rack should look something like this.
There are 15 balls. 7 "stripes", 7 "solids", and one black ball.
You dump them into the triangle at random, then swap them around until you have the "correct" pattern. There are two different recognised patterns (European and American), but we'll pretend there's just one.
You can either start that pattern with stripes at the front, or solids. You can also reverse the pattern in terms of symmetry. As such, I think there are four ways of racking the balls correctly.
However, once the balls are in, you can spin the triangle into three positions, giving you 12 total possibilities.
There is a complication: the black is the only ball that has to sit on one of the inside three spots.
So, if the balls happen to land in the worst possible way, what are the most number of ball swaps that you'll ever have to make? I'm talking about straight swaps — no moving three at a time.
A second, perhaps more-important question: what's the median starting position, in terms of how many ball swaps I'll have to make?
This is a somewhat interesting math problem as framed, even if the details of the rules don't agree with the problem as it's laid out. So, assuming nonetheless that there is only one "correct" layout of the balls, here are some things to consider:
1) It's valid to swap stripes for solids and vice versa, so long as their relative pattern is correct (i.e., in the linked diagram, red can be taken to be either stripes or solids, so long as the correct configuration is reached at the end).
2) The 8 ball always has to end up in a certain spot, so basically we can reduce the complexity by ignoring it completely (i.e., its inclusion adds at most 1 swap to the number of swaps we perform to get to the correct pattern).
3) OK, between 1 and 2 above, it implies that no more than half the 14 non-8-ball balls can be in the wrong place to start (if they are, we just "flip" so that red means the opposite of whatever it was before). This means that:
4) There are at most 7 balls in the wrong places. Of those, 4 must be of one type (stripes, say) and 3 must be of the other type. But this asymmetry means, in fact, that the one of the stripes MUST be in the correct position. So really, there is at most 3 stripes and 3 solids out of place. Thus you should be able to get a correct configuration by performing 3 swaps.
Example:
I'll encode the 14 positions in the picture from top to boot and left to right with X (red) and O (yellow). The correct pattern is:
XOXXOOXOXXOXOO
A worse case arrangement is (out-of-place balls are bold):
XOXXOOXXOOXOXO
I perform 3 swaps to get them to the correct arrangement:
1) XOXXOOXOXOXOXO
2) XOXXOOXOXXOOXO
3) XOXXOOXOXXOXOO
So adding the 8-ball back in, the worse case is 4 swaps. If you're allowed to rotate without that counting, it becomes 3 (I rotate to get the 8 ball to where it needs to go, and I'm left with at worse 3 swaps).
posted by axiom at 5:05 PM on April 4, 2012 [1 favorite]
1) It's valid to swap stripes for solids and vice versa, so long as their relative pattern is correct (i.e., in the linked diagram, red can be taken to be either stripes or solids, so long as the correct configuration is reached at the end).
2) The 8 ball always has to end up in a certain spot, so basically we can reduce the complexity by ignoring it completely (i.e., its inclusion adds at most 1 swap to the number of swaps we perform to get to the correct pattern).
3) OK, between 1 and 2 above, it implies that no more than half the 14 non-8-ball balls can be in the wrong place to start (if they are, we just "flip" so that red means the opposite of whatever it was before). This means that:
4) There are at most 7 balls in the wrong places. Of those, 4 must be of one type (stripes, say) and 3 must be of the other type. But this asymmetry means, in fact, that the one of the stripes MUST be in the correct position. So really, there is at most 3 stripes and 3 solids out of place. Thus you should be able to get a correct configuration by performing 3 swaps.
Example:
I'll encode the 14 positions in the picture from top to boot and left to right with X (red) and O (yellow). The correct pattern is:
XOXXOOXOXXOXOO
A worse case arrangement is (out-of-place balls are bold):
XOXXOOXXOOXOXO
I perform 3 swaps to get them to the correct arrangement:
1) XOXXOOXOXOXOXO
2) XOXXOOXOXXOOXO
3) XOXXOOXOXXOXOO
So adding the 8-ball back in, the worse case is 4 swaps. If you're allowed to rotate without that counting, it becomes 3 (I rotate to get the 8 ball to where it needs to go, and I'm left with at worse 3 swaps).
posted by axiom at 5:05 PM on April 4, 2012 [1 favorite]
All of that is assuming, of course, that you don't make wasteful swaps. If you factor in wasteful swaps, the worse case number becomes infinite.
posted by axiom at 5:07 PM on April 4, 2012
posted by axiom at 5:07 PM on April 4, 2012
Sigh. BOTTOM not BOOT, and WORST not WORSE (where appropriate).
posted by axiom at 5:14 PM on April 4, 2012
posted by axiom at 5:14 PM on April 4, 2012
Response by poster: I love that answer. When I was doing it experimentally (trying to put all the balls as out of order as I could) I was getting four swaps tops. But in a way, this was an easy experiment to run.
However, what's most important is that I'd like to know is what the median number of swaps is. If four is the most I'll ever have to swap, what should I normally expect?
If it makes it a lot easier, you can pretend that the black ball always starts in one of the three center spots. It's the only thing I can generally ensure as I'm "randomly" putting the balls in the triangle.
Is this the kind of thing you can only answer by running every possible way through a computer? Is there a program that could help me do this?
posted by omnigut at 5:25 PM on April 4, 2012
However, what's most important is that I'd like to know is what the median number of swaps is. If four is the most I'll ever have to swap, what should I normally expect?
If it makes it a lot easier, you can pretend that the black ball always starts in one of the three center spots. It's the only thing I can generally ensure as I'm "randomly" putting the balls in the triangle.
Is this the kind of thing you can only answer by running every possible way through a computer? Is there a program that could help me do this?
posted by omnigut at 5:25 PM on April 4, 2012
Although this does not answer the question, you should know: Under APA league rules, the only requirements for an 8-ball rack are that 1) the eight ball is in the center, and 2) the two back corners are one striped ball and one solid ball. Additionally, most people like to have the #1 ball in the front corner. This is how I rack.
posted by teatime at 5:25 PM on April 4, 2012 [1 favorite]
posted by teatime at 5:25 PM on April 4, 2012 [1 favorite]
It's 4.43333 swaps in expectation, with a few simplifying assumptions:
* There is exactly one acceptable final position.
* Ignoring triangle rotation
* Treating stripes and solids as distinct and not interchangeable [i.e., if your random arrangement is completely backwards, it's incorrect]
0. Assume we swap the 8-ball as our first move, if necessary.
1. Encode positions as 14-bit binary strings (like axiom did), and arbitrarily say that the final position is 11111110000000.
2. Observe that for every incorrect stripe, there must be an incorrect solid. Thus, if we have swapped the high-order 7 bits to be correct, the low-order bits must also be correct.
3. Therefore, we can ignore the low order seven bits. The final correct solution we want is 1111111.
4. If we start with 00000000000000 and place seven 1's randomly, how many zeroes will be in the first seven bits in expectation? This tells us how many swaps we must perform, because swapping a zero for a one brings us one step closer to the correct solution. If we were to iterate over all the numbers between 0000000 and 1111111, summing number of zeroes, and then average them, we get 3.5. These represent an expected value of 3.5 pairs of out-of-place balls, after the 8-ball is in the correct position.
5. If we factor in a 14 out of 15 chance of needing to swap the 8-ball, then we get 4.4333 expected swaps.
posted by qxntpqbbbqxl at 5:25 PM on April 4, 2012 [3 favorites]
* There is exactly one acceptable final position.
* Ignoring triangle rotation
* Treating stripes and solids as distinct and not interchangeable [i.e., if your random arrangement is completely backwards, it's incorrect]
0. Assume we swap the 8-ball as our first move, if necessary.
1. Encode positions as 14-bit binary strings (like axiom did), and arbitrarily say that the final position is 11111110000000.
2. Observe that for every incorrect stripe, there must be an incorrect solid. Thus, if we have swapped the high-order 7 bits to be correct, the low-order bits must also be correct.
3. Therefore, we can ignore the low order seven bits. The final correct solution we want is 1111111.
4. If we start with 00000000000000 and place seven 1's randomly, how many zeroes will be in the first seven bits in expectation? This tells us how many swaps we must perform, because swapping a zero for a one brings us one step closer to the correct solution. If we were to iterate over all the numbers between 0000000 and 1111111, summing number of zeroes, and then average them, we get 3.5. These represent an expected value of 3.5 pairs of out-of-place balls, after the 8-ball is in the correct position.
5. If we factor in a 14 out of 15 chance of needing to swap the 8-ball, then we get 4.4333 expected swaps.
posted by qxntpqbbbqxl at 5:25 PM on April 4, 2012 [3 favorites]
Response by poster: Thanks teatime, but as I said in the question description, there are other official methods for racking pool balls outside of America.
posted by omnigut at 5:30 PM on April 4, 2012 [1 favorite]
posted by omnigut at 5:30 PM on April 4, 2012 [1 favorite]
Note that in qxntpqbbbqxl's formulation, NOT-ing (0->1, 1->0) is a "free" operation once you treat stripes and solids interchangeably.
From here, we can determine the non-rotational maximum number of swaps:
#1: The black ball is out of place
Assume the spot for the black ball is taken by a 0.
Now we have 7 balls of interest; if 4 or more are wrong, use the free NOT operation to change the right ones to wrong.
Now you just have 3 swaps to perform.
The maximum is then 4, consistent with your findings.
We can also recalculate the expected value: all numbers above 3 become their complement of 7 instead.
posted by 0xFCAF at 5:37 PM on April 4, 2012 [1 favorite]
From here, we can determine the non-rotational maximum number of swaps:
#1: The black ball is out of place
Assume the spot for the black ball is taken by a 0.
Now we have 7 balls of interest; if 4 or more are wrong, use the free NOT operation to change the right ones to wrong.
Now you just have 3 swaps to perform.
The maximum is then 4, consistent with your findings.
We can also recalculate the expected value: all numbers above 3 become their complement of 7 instead.
posted by 0xFCAF at 5:37 PM on April 4, 2012 [1 favorite]
0xFCAF is right, if we treat not as free then the expected number of swaps is ~3.32, including the 8-ball swap.
Although visually it might be difficult to look at a random triangle and decide quickly (i.e., faster than one swap) if you need to ¬ it, but I suppose you'd get good at it with practice.
posted by qxntpqbbbqxl at 6:00 PM on April 4, 2012
Although visually it might be difficult to look at a random triangle and decide quickly (i.e., faster than one swap) if you need to ¬ it, but I suppose you'd get good at it with practice.
posted by qxntpqbbbqxl at 6:00 PM on April 4, 2012
Kind of besides the point, but was there a regulation change in the past couple of decades? My understanding of the actual rules are that even the most nerdy interpretation says only that the rear corners should be opposite balls (one stripe, one solid). There are always people who think the balls should alternate like you posit here, but I've never come across an official requirement or anything more than an informal preference.
posted by rhizome at 6:27 PM on April 4, 2012 [1 favorite]
posted by rhizome at 6:27 PM on April 4, 2012 [1 favorite]
Response by poster: Great, so we're clear that 4 is the maximum number of swaps we'd need to do (we can't do parts of swaps, you either swap or you don't). And I think this would be regardless of whether or not you allow for the rotation of the triangle once the balls are in it.
However, the median number of swaps would definitely be changed if you allowed for the rotation of the rack (and considered it not to count as a move). I made this diagram just to make sure we're clear on what I mean:
Image
I'd love to know what the median number of swaps I'd need to do to get one of these twelve outcomes. I think that framing the question like this takes out the mental complication of the rack rotations — all you're trying to do is achieve one of these twelve.
What's my next step? Contact MIT? Invent a program to calculate it? Give up?
posted by omnigut at 6:38 PM on April 4, 2012
However, the median number of swaps would definitely be changed if you allowed for the rotation of the rack (and considered it not to count as a move). I made this diagram just to make sure we're clear on what I mean:
Image
I'd love to know what the median number of swaps I'd need to do to get one of these twelve outcomes. I think that framing the question like this takes out the mental complication of the rack rotations — all you're trying to do is achieve one of these twelve.
What's my next step? Contact MIT? Invent a program to calculate it? Give up?
posted by omnigut at 6:38 PM on April 4, 2012
Response by poster: Am I right in thinking that to work out the median I'd have to work out the number of swaps needed from all possible starting positions to make each one of those twelve possibilities, and then just add them all up at the end?
How do I work out what all the starting positions could possibly be?
posted by omnigut at 6:45 PM on April 4, 2012
How do I work out what all the starting positions could possibly be?
posted by omnigut at 6:45 PM on April 4, 2012
This is easy to brute force for you. I showed above that if the 8-ball is assumed to be in the right place (equivalent to allowing a free rotation), there are always (at least) 8 balls in the correct place (under the "red can be either stripes or solids" rule). Of the other 6, let's just arbitrarily assign the correct pattern to be 111000 (because we can number spots in any order, this is OK to do). So, of the other 6 balls NOT NECESSARILY in the right place, how can they (3 of each type) be arranged?
It's just counting up to 111000 in binary to show the possibilities. There are 2^6 = 64 numbers with 6 binary digits, of which only 20 have exactly three 1s and three 0s. They are (in ascending order):
000111 (3 swaps)
001011 (2 swaps)
001101 (2 swaps)
001110 (2 swaps)
010011 (2 swaps)
010101 (2 swaps)
010110 (2 swaps)
100011 (2 swaps)
100101 (2 swaps)
100110 (2 swaps)
011001 (1 swap)
011010 (1 swap)
011100 (1 swap)
101001 (1 swap)
101010 (1 swap)
101100 (1 swap)
110001 (1 swap)
110010 (1 swap)
110100 (1 swap)
111000 (0 swaps)
Adding them up and dividing, we get 30 total swaps divided over 20 outcomes, for an average of 3/2 or 1.5 swaps.
posted by axiom at 7:00 PM on April 4, 2012
It's just counting up to 111000 in binary to show the possibilities. There are 2^6 = 64 numbers with 6 binary digits, of which only 20 have exactly three 1s and three 0s. They are (in ascending order):
000111 (3 swaps)
001011 (2 swaps)
001101 (2 swaps)
001110 (2 swaps)
010011 (2 swaps)
010101 (2 swaps)
010110 (2 swaps)
100011 (2 swaps)
100101 (2 swaps)
100110 (2 swaps)
011001 (1 swap)
011010 (1 swap)
011100 (1 swap)
101001 (1 swap)
101010 (1 swap)
101100 (1 swap)
110001 (1 swap)
110010 (1 swap)
110100 (1 swap)
111000 (0 swaps)
Adding them up and dividing, we get 30 total swaps divided over 20 outcomes, for an average of 3/2 or 1.5 swaps.
posted by axiom at 7:00 PM on April 4, 2012
Incidentally, the median is also 1.5, as should be evident from the enumeration above.
posted by axiom at 7:22 PM on April 4, 2012
posted by axiom at 7:22 PM on April 4, 2012
Adding rotation makes it a much harder problem because the minimum number of swaps in one orientation is not independent of the minimum number of swaps for other rotations. This is because of the asymmetrical pattern. So you can't just treat each rotation as a separate random variable. That's the cue to abandon statistical reasoning and just write a little program to brute force it.
posted by qxntpqbbbqxl at 9:07 PM on April 4, 2012
posted by qxntpqbbbqxl at 9:07 PM on April 4, 2012
Actually there is rotational symmetry: two right rotations is the same as one left and three rotations is the same as none. Therefore if rotations don't "cost" anything, and since the order of operations commutes, I think the above analysis still applies. It would change if rotations started to count the same as swaps.
posted by axiom at 11:16 PM on April 4, 2012
posted by axiom at 11:16 PM on April 4, 2012
Surely you don't mean to say that there are three valid positions in the rack for the #8 ball, and not just one, do you?
posted by teatime at 4:06 AM on April 5, 2012
posted by teatime at 4:06 AM on April 5, 2012
Best answer: Wrote a program to brute force it. (source).
posted by qxntpqbbbqxl at 9:19 AM on April 5, 2012 [2 favorites]
Minimum Swaps Percentage of Cases 0 0.023 % 1 1.4 % 2 20 % 3 63 % 4 16 % Average (mean) minimum swaps: 2.927That includes all twelve of the goal states (rotation, not, flip operations are free).
posted by qxntpqbbbqxl at 9:19 AM on April 5, 2012 [2 favorites]
This thread is closed to new comments.
a partial answer: i think the maximum number of swaps would be seven. that is, if it's possible for the balls to be arranged in a way that won't lead to a "correct" pattern before seven swaps have been reached, which i haven't verified.
there is no reason to swap two balls of the same class, and it's stupid to swap two balls if you're just going to swap it with the 8-ball later. so, either the 8-ball is in the right place and you swap each stripe for a solid, or the 8-ball is in the wrong place, and you swap all but the one in the center.
posted by cupcake1337 at 4:43 PM on April 4, 2012