About two months ago, I was invited to join a Mahjong party that involved three square game tables and twelve players (four players per table). After each (of the six) round(s) the seating assignment changes: the goal being to maximize the diversity of players at each table per round.
During the party, one of the participants shared with me a yet-to-be resolved quandary faced by the group ever since the inception these parties: What pattern(s) of seating rotation are necessary so that all twelve players are able to play with the other eleven players by the end of the sixth round? In this post, I discuss in some detail the problem and my attempt at the solution.
On the day I was posed this problem, I (naïvely) thought I could solve this problem overnight or at least in short order. Before trying to solve the problem, I elicited some ideas, summarized below:
- Keep one player at each of the three tables stationary and rotate the other three players out
- Conveyor belt rotation (“triple figure-eight”)
- Random assignment
One colleague was strongly convinced that the stationary-player idea was the best solution, “Within three, maybe four rounds, everybody would have seen each other. The simplest solution is the best one.” Unfortunately, based on my investigation, I’m afraid that Ockam’s Razor isn’t powerful enough to solve this problem.
Towards a Solution
Naturally, on my first attempts at deriving a rotation pattern I used the traditional tools of paper-and-pencil to sketch out (1) the movement pattern, (2) seating assignment table and (3) frequency table displaying the number of times each player sees another unique player (each player is assigned a letter A through L):
(1) Movement pattern
(2) Seating Assignment
(3) Frequency Table, with Arithmetic Mean
Based on the frequency table, my pattern isn’t at all optimal:
- Lots of zeroes (many players don’t see certain other players at all)
- Some sixes (some players see another player all the time)
- In general, the distribution doesn’t seem even at all
The manual counting required to populate the frequency table was at least slightly laborious. It was irritating to imagine spending more time formulating another creative rotation pattern, then constructing the two tables to finally yield similar non-optimal results. Human error would have also manifested itself when accompanied with tedium. Dump the paper-and-pencil method!
So, in order to check my frequency table, I wrote a simple module (program) using Python and got basically the same table.
With this module, I could enter other rotation patterns and produce a frequency table letting the computer do all the counting.
After spending some time thinking about another rotation pattern, I concluded that there must be a better way than guessing-and-checking. Manually entering different patterns, checking them and repeating the process would take ages. If I could generate patterns using an algorithm, that would be way better than creating patterns by hand. Randomization time!
Initially, when my partner suggested that I could try random assignment, I sneered at him. It turns out that randomization yielded better results. So, I added some more code to my little module to make it into a randomizing simulator. Along with the corresponding frequency table I also added some code for the arithmetic mean and tabulated the number of 0s, 1s, 2s, etc., i.e. how many pairs see each other 0-times, 1-time, 2-times, etc. Sample results (representing the better patterns plus one no-so-good pattern):
Some Observations (after running the randomizer module 100s of times)
- No instances of 0s < 3
(There will be at least three pairs of persons that never see/play each other)
- Average number of times a person plays with another person is around 1.5
(not 2 as a colleague conjectured).
- Most pairs see each other 2 or 3 times.
- No instances of 6s > 0
(no pairs of persons ever see each other for every game)
- Different patterns with same mean values
(e.g. patterns with mean = 1.5417, hmmmmm….)
Although none of the generated rotation patterns yielded results where everybody got to play with each other, by far, the patterns were still better than the one I had created using paper and pencil. From the data, I’m not sure we can conclude that 0s = 0 is possible.
- Check the “triple-figure-eight” conveyor-belt pattern.
- Write another module starting with a frequency table
(“backward-engineered” version of the randomizing simulator)
- Develop the current randomizing simulator for n number of tables and 4n number of players, and then compare the frequency tables for different values of n.
- Determine why 0s = 0 is so hard to get: Can everybody really play with everybody else given three tables and six rotations? What if there were more than six rotations?
- Write in code for σ sample standard deviation (just for fun).