13 players, 13 rounds: $20 to the one who finds the perfect seeding


By jlm33

5 months ago


Stats

  • 33 posts
  • 16 Pinsiders participating
  • Latest reply 4 months ago by gorgar007
  • Topic is favorited by 2 Pinsiders

Find

Search this topic for posts matching certain words or written by a specific Pinsider. Or both!




Linked Games

No games have been linked to this topic.



    Topic Gallery

    There have been 2 images uploaded to this topic. (View topic image gallery).

    snip (resized).PNG
    Round1 (resized).png


    #1 5 months ago

    Long story short: we want to make a tournament with exactly 13 players, with 13 rounds.
    Let's assume we have 4 pins.

    Each of the players will play 12 of the 13 rounds (in other words, skip one round).
    During each round, four 3-player games are played, each on one of the four different pins.

    For that tournament to be as fair as possible, I would like to find the way to organize rounds 1-13 so that:
    - every participant plays against each of the 12 other players *exactly* twice (in total, you will face 12 x 2 players = 24 and you have 12 opponents)
    - every participant plays 4 times as the first player, 4 times as the last player, 4 times as player #2
    - every participant plays 3 games on Pin #1, 3 games on Pin #2, 3 games on Pin #3 and 3 games on Pin #4

    $20 PP gift and my eternal thanks to the one who finds the solution to this problem (it's NOT trivial)

    For example, round 1 may look like this (Player #13 does not play)... let me help filling the 12 remaining rounds!

    Round1 (resized).png

    #2 5 months ago

    My head hurts...

    #3 5 months ago

    Cant you just move everyone over one spot at a time. Then when they are in pin 1 third player they go to pin 2 first player? Everyone will play in the same spots once. Is that what you meant? Or did you actually want someone to fill out all 13 rounds for you?

    Edit: i just saw the part about everyplayer faceing each person twice.

    #4 5 months ago
    Quoted from Mfsrc791:

    Edit: i just saw the part about everyplayer faceing each person twice.

    That's the really difficult part (and the most important one: you do not want to face the best player more than your fair share...)

    #5 5 months ago

    If i could remember back to differetial equations in college there is probably a solution. Too bad i dropped out of that class

    #6 5 months ago

    You can do it with matchplay if you do four player groups. Not sure if you can force matchplay to give you three player groups if it can give you four player groups.

    #7 5 months ago

    Sorry, but this "problem" is worth more than $20 of time!!!

    #8 5 months ago
    Quoted from T7:

    Sorry, but this "problem" is worth more than $20 of time!!!

    True. I was hoping someone already found a solution to a similar question and implemented it in a tournament manager software / webpage. $20 for providing the link seems fair... $20 for finding the solution not so much!

    The interesting part is that with 12 players (which at first glance seems optimal) you cannot face each opponent the same number of times... You will play all 12 rounds, face 2x12 players... but you only have 11 opponents.

    #10 5 months ago

    A solution where each player plays against each other player exactly 2 times might not be possible. I can't neither prove or disprove this. I did find a solution so that each player plays against each other player at least 1 time but no more than 3 times. Shown below.

    13 players are numbered 0 - 12.

    round 1
    2 8 9
    3 11 12
    1 4 10
    5 6 7
    round 2
    4 9 11
    6 8 10
    2 3 7
    0 5 12
    round 3
    1 7 11
    3 6 8
    4 5 9
    0 10 12
    round 4
    0 4 6
    5 8 10
    7 11 12
    1 2 9
    round 5
    0 1 5
    2 6 11
    7 10 12
    3 8 9
    round 6
    1 10 11
    0 3 9
    4 8 12
    2 6 7
    round 7
    4 8 11
    7 9 10
    2 5 12
    0 1 3
    round 8
    1 5 8
    3 6 10
    0 9 11
    2 4 12
    round 9
    0 4 7
    1 9 12
    5 6 11
    2 3 10
    round 10
    2 4 10
    3 5 11
    1 6 12
    0 7 8
    round 11
    3 4 5
    6 7 9
    0 1 2
    8 11 12
    round 12
    7 10 12
    1 5 9
    3 6 8
    0 2 4
    round 13
    2 6 11
    1 4 10
    7 8 9
    0 3 5

    crosstable showing how many times the players play against each other.

    #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12
    #0. 0 3 2 3 3 3 1 2 1 2 1 1 2
    #1. 0 0 2 1 2 3 1 1 1 3 3 2 2
    #2. 0 0 0 2 3 1 3 2 1 2 2 2 2
    #3. 0 0 0 0 1 3 3 1 3 2 2 2 1
    #4. 0 0 0 0 0 2 1 1 2 2 3 2 2
    #5. 0 0 0 0 0 0 2 1 2 2 1 2 2
    #6. 0 0 0 0 0 0 0 3 3 1 2 3 1
    #7. 0 0 0 0 0 0 0 0 2 3 3 2 3
    #8. 0 0 0 0 0 0 0 0 0 3 2 2 2
    #9. 0 0 0 0 0 0 0 0 0 0 1 2 1
    #10. 0 0 0 0 0 0 0 0 0 0 0 1 3
    #11. 0 0 0 0 0 0 0 0 0 0 0 0 3
    #12. 0 0 0 0 0 0 0 0 0 0 0 0 0

    #11 5 months ago

    Looks good to me:)

    #12 5 months ago

    I think the answer is 42.

    #13 5 months ago

    This site is turning into a boho fiverr

    #14 5 months ago
    Quoted from Yoski:

    A solution where each player plays against each other player exactly 2 times might not be possible. I can't neither prove or disprove this. I did find a solution so that each player plays against each other player at least 1 time but no more than 3 times. Shown below.

    Thanks for the effort !
    Better than what I have achieved so far.
    If no else finds the perfect solution by Feb 24 (tournament is scheduled on Feb 25) you win the $20!

    #15 5 months ago

    I made some improvements to the algorithm, see if i can find a better solution.

    #16 5 months ago

    Here's one with only 2 pairs that are out of line. Chances are that's as good as it gets.
    Round 1
    3 10 12
    1 6 11
    5 7 8
    2 4 9
    Round 2
    0 4 12
    6 8 9
    2 7 10
    3 5 11
    Round 3
    0 3 7
    1 9 12
    5 6 10
    4 8 11
    Round 4
    1 8 10
    0 9 11
    4 6 7
    2 5 12
    Round 5
    2 3 9
    0 5 8
    6 10 11
    1 7 12
    Round 6
    2 8 11
    0 6 7
    1 3 4
    9 10 12
    Round 7
    0 1 10
    2 8 12
    3 4 5
    7 9 11
    Round 8
    2 4 6
    3 8 10
    1 5 9
    0 11 12
    Round 9
    3 6 12
    0 1 2
    4 9 10
    5 7 11
    Round 10
    0 3 8
    5 6 12
    1 4 7
    2 10 11
    Round 11
    2 3 7
    0 5 9
    1 6 8
    4 11 12
    Round 12
    1 2 5
    7 8 12
    3 6 9
    0 4 10
    Round 13
    1 3 11
    4 5 10
    0 2 6
    7 8 9

    0 1 2 3 4 5 6 7 8 9 10 11 12
    #0. 0 2 2 2 2 2 2 2 2 2 2 2 2
    #1. 0 0 2 2 2 2 2 2 2 2 2 2 2
    #2. 0 0 0 2 2 2 2 2 2 2 2 2 2
    #3. 0 0 0 0 2 2 2 2 2 2 2 2 2
    #4. 0 0 0 0 0 2 2 2 1 2 3 2 2
    #5. 0 0 0 0 0 0 2 2 2 2 2 2 2
    #6. 0 0 0 0 0 0 0 2 2 2 2 2 2
    #7. 0 0 0 0 0 0 0 0 3 2 1 2 2
    #8. 0 0 0 0 0 0 0 0 0 2 2 2 2
    #9. 0 0 0 0 0 0 0 0 0 0 2 2 2
    #10. 0 0 0 0 0 0 0 0 0 0 0 2 2
    #11. 0 0 0 0 0 0 0 0 0 0 0 0 2
    #12. 0 0 0 0 0 0 0 0 0 0 0 0 0

    #17 5 months ago

    Nice job - did you write a program to do it for you?

    #18 5 months ago
    Quoted from T7:

    Nice job - did you write a program to do it for you?

    Yeah, slow day at work I still wonder if there is a perfect solution to this. I leave it running over the weekend, maybe I luck into something.

    #19 5 months ago
    Quoted from Yoski:

    I still wonder if there is a perfect solution to this. I leave it running over the weekend, maybe I luck into something.

    Amazing!
    I am truly impressed!

    11
    #20 5 months ago

    Perfect solution to the problem. See below. I let the algorithm run over the long weekend and it came up with the solution shown below.

    Round 1
    1 6 8
    2 7 12
    3 9 11
    4 5 10
    Round 2
    0 10 11
    4 7 9
    2 3 6
    5 8 12
    Round 3
    4 11 12
    8 9 10
    1 3 5
    0 6 7
    Round 4
    6 10 12
    2 5 9
    0 1 4
    7 8 11
    Round 5
    0 3 9
    2 8 12
    5 6 11
    1 7 10
    Round 6
    1 2 11
    0 8 10
    3 4 7
    6 9 12
    Round 7
    0 9 12
    1 2 10
    5 7 11
    3 4 8
    Round 8
    3 10 12
    0 2 11
    1 8 9
    4 5 6
    Round 9
    0 5 7
    2 4 9
    1 11 12
    3 6 10
    Round 10
    0 1 6
    3 7 12
    2 5 8
    4 10 11
    Round 11
    1 7 9
    2 4 6
    3 8 11
    0 5 12
    Round 12
    0 2 3
    6 7 8
    1 4 12
    5 9 10
    Round 13
    1 3 5
    6 9 11
    2 7 10
    0 4 8

    0 1 2 3 4 5 6 7 8 9 10 11 12
    #0. 0 2 2 2 2 2 2 2 2 2 2 2 2
    #1. 0 0 2 2 2 2 2 2 2 2 2 2 2
    #2. 0 0 0 2 2 2 2 2 2 2 2 2 2
    #3. 0 0 0 0 2 2 2 2 2 2 2 2 2
    #4. 0 0 0 0 0 2 2 2 2 2 2 2 2
    #5. 0 0 0 0 0 0 2 2 2 2 2 2 2
    #6. 0 0 0 0 0 0 0 2 2 2 2 2 2
    #7. 0 0 0 0 0 0 0 0 2 2 2 2 2
    #8. 0 0 0 0 0 0 0 0 0 2 2 2 2
    #9. 0 0 0 0 0 0 0 0 0 0 2 2 2
    #10. 0 0 0 0 0 0 0 0 0 0 0 2 2
    #11. 0 0 0 0 0 0 0 0 0 0 0 0 2
    #12. 0 0 0 0 0 0 0 0 0 0 0 0 0

    #21 5 months ago

    Oh my head. Just use Brackelope and call it a day.

    #22 5 months ago
    Quoted from Yoski:

    Perfect solution to the problem. See below. I let the algorithm run over the long weekend and it came up with the solution shown below.
    Round 1
    1 6 8
    2 7 12
    3 9 11
    4 5 10
    Round 2
    0 10 11
    4 7 9
    2 3 6
    5 8 12
    Round 3
    4 11 12
    8 9 10
    1 3 5
    0 6 7
    Round 4
    6 10 12
    2 5 9
    0 1 4
    7 8 11
    Round 5
    0 3 9
    2 8 12
    5 6 11
    1 7 10
    Round 6
    1 2 11
    0 8 10
    3 4 7
    6 9 12
    Round 7
    0 9 12
    1 2 10
    5 7 11
    3 4 8
    Round 8
    3 10 12
    0 2 11
    1 8 9
    4 5 6
    Round 9
    0 5 7
    2 4 9
    1 11 12
    3 6 10
    Round 10
    0 1 6
    3 7 12
    2 5 8
    4 10 11
    Round 11
    1 7 9
    2 4 6
    3 8 11
    0 5 12
    Round 12
    0 2 3
    6 7 8
    1 4 12
    5 9 10
    Round 13
    1 3 5
    6 9 11
    2 7 10
    0 4 8
    0 1 2 3 4 5 6 7 8 9 10 11 12
    #0. 0 2 2 2 2 2 2 2 2 2 2 2 2
    #1. 0 0 2 2 2 2 2 2 2 2 2 2 2
    #2. 0 0 0 2 2 2 2 2 2 2 2 2 2
    #3. 0 0 0 0 2 2 2 2 2 2 2 2 2
    #4. 0 0 0 0 0 2 2 2 2 2 2 2 2
    #5. 0 0 0 0 0 0 2 2 2 2 2 2 2
    #6. 0 0 0 0 0 0 0 2 2 2 2 2 2
    #7. 0 0 0 0 0 0 0 0 2 2 2 2 2
    #8. 0 0 0 0 0 0 0 0 0 2 2 2 2
    #9. 0 0 0 0 0 0 0 0 0 0 2 2 2
    #10. 0 0 0 0 0 0 0 0 0 0 0 2 2
    #11. 0 0 0 0 0 0 0 0 0 0 0 0 2
    #12. 0 0 0 0 0 0 0 0 0 0 0 0 0

    There you go kids, maths at work. Stay in school!

    Nice work, Yoski!

    #23 5 months ago
    Quoted from Yoski:

    Perfect solution to the problem. See below. I let the algorithm run over the long weekend and it came up with the solution shown below.

    Outstanding! Thanks a million times...

    #24 5 months ago

    Will this also satisfy:

    Quoted from jlm33:

    - every participant plays 4 times as the first player, 4 times as the last player, 4 times as player #2
    - every participant plays 3 games on Pin #1, 3 games on Pin #2, 3 games on Pin #3 and 3 games on Pin #4

    Is this the only solution found, and was it done by brute force, with you running it all weekend?

    Great work either way

    #25 5 months ago
    Quoted from WJxxxx:

    Will this also satisfy:

    Is this the only solution found, and was it done by brute force, with you running it all weekend?
    Great work either way

    I found several (= 4) solutions (see listing below) to the problem of each player facing each other player exactly 2 times. Those solutions are rather challenging to find. If you throw in the additional constraint that each player has to play each machine exactly 3 times I am not sure if a solution still exists. Maybe, maybe not.
    I used:
    - a good random number generator
    - a permutation generator I wrote
    - the algorithm kept track how many times each player played against each other player in a cross table shown above. At the beginning of each new round it created a list of player pairs with the fewest matches against each other. From that list it tried to randomly select up to 4 match ups (or as many as possible) without a player getting a double assignment. Then the 3rd player was randomly selected from the remaining players. If the result produced a pair with 3 match ups it reset and tried again with a new random permutation. It tried multiple attempts at each round before it gives up and starts over from round one. It typically runs about 24 hours before it finds a solution, sometimes more, sometimes less, there's a certain luck factor. I wrote it in Perl. If you want to play around with it some more I can send you the code. It's ugly and poorly commented. OK, back to work, I got bigger fish to fry

    Solutions:
    #1 solution
    4 8 11
    5 6 12
    1 2 3
    7 9 10
    5 7 11
    0 6 8
    2 4 10
    3 9 12
    0 5 10
    7 8 12
    3 4 6
    1 9 11
    2 6 7
    0 1 4
    10 11 12
    5 8 9
    6 8 10
    1 7 12
    0 9 11
    2 3 5
    6 9 10
    0 2 7
    1 3 8
    4 11 12
    0 2 12
    1 5 8
    3 10 11
    4 7 9
    2 8 11
    0 3 12
    1 6 9
    4 5 10
    2 4 9
    0 6 11
    3 5 7
    1 10 12
    0 3 4
    1 7 11
    2 8 10
    5 6 12
    2 9 12
    3 6 11
    0 7 8
    1 4 5
    1 2 6
    4 8 12
    3 7 10
    0 5 9
    2 5 11
    4 6 7
    0 1 10
    3 8 9
    #2 solution
    4 6 12
    5 7 11
    2 3 9
    1 8 10
    7 8 9
    3 5 6
    2 4 10
    0 11 12
    9 10 12
    1 6 11
    0 5 8
    3 4 7
    0 6 10
    4 8 11
    2 7 12
    1 5 9
    5 10 11
    1 3 12
    2 6 8
    0 7 9
    0 1 2
    3 8 12
    4 7 10
    6 9 11
    0 3 10
    1 4 9
    2 7 11
    5 8 12
    3 8 11
    1 2 5
    0 4 9
    6 10 12
    0 4 5
    1 6 7
    9 11 12
    2 3 10
    7 8 10
    1 4 12
    2 5 6
    0 3 11
    0 1 8
    2 4 11
    3 6 9
    5 7 12
    4 6 8
    5 9 10
    1 3 7
    0 2 12
    1 10 11
    3 4 5
    2 8 9
    0 6 7
    #3 solution
    1 6 8
    2 7 12
    3 9 11
    4 5 10
    0 10 11
    4 7 9
    2 3 6
    5 8 12
    4 11 12
    8 9 10
    1 3 5
    0 6 7
    6 10 12
    2 5 9
    0 1 4
    7 8 11
    0 3 9
    2 8 12
    5 6 11
    1 7 10
    1 2 11
    0 8 10
    3 4 7
    6 9 12
    0 9 12
    1 2 10
    5 7 11
    3 4 8
    3 10 12
    0 2 11
    1 8 9
    4 5 6
    0 5 7
    2 4 9
    1 11 12
    3 6 10
    0 1 6
    3 7 12
    2 5 8
    4 10 11
    1 7 9
    2 4 6
    3 8 11
    0 5 12
    0 2 3
    6 7 8
    1 4 12
    5 9 10
    1 3 5
    6 9 11
    2 7 10
    0 4 8
    #4 solution
    4 5 10
    3 9 11
    2 6 8
    1 7 12
    3 6 10
    0 2 11
    4 8 12
    5 7 9
    9 10 12
    1 3 4
    0 5 6
    7 8 11
    0 8 9
    5 11 12
    1 2 10
    4 6 7
    0 3 8
    2 5 12
    7 10 11
    1 6 9
    2 3 4
    1 8 10
    0 7 9
    6 11 12
    4 9 12
    3 5 10
    0 1 11
    2 7 8
    0 10 12
    1 4 11
    2 6 9
    3 5 8
    3 7 12
    0 4 6
    1 2 5
    9 10 11
    2 7 10
    3 6 12
    4 8 11
    0 1 5
    2 4 9
    5 6 11
    1 8 12
    0 3 7
    1 3 9
    4 5 7
    6 8 10
    0 2 12
    0 4 10
    2 3 11
    1 6 7
    5 8 9

    #26 5 months ago

    Saving this thread to my favorites. Outstanding work by @yoski

    Marcus

    #27 5 months ago

    Put the code on github plz.

    #28 5 months ago

    @yoski

    care for another challenge?

    we run a WI cross league event each year. There are 24 total players (8 from each respective league which represent a team)

    We would like a format of 8 or 9 rounds of play; 3 player games. Each round a player from team 1 should play someone from team 2 and someone from team 3.

    Ideally each player will play every other player with no (or as few as possible repeats) and also no (or as few as possible) game repeats.

    #29 5 months ago

    I'll post the code. I hope to find some time to think about the 3 teams with 8 players problem. Right now I am busy, hopefully Friday or weekend.

    #30 5 months ago
    Quoted from Whysnow:

    yoski
    care for another challenge?
    we run a WI cross league event each year. There are 24 total players (8 from each respective league which represent a team)
    We would like a format of 8 or 9 rounds of play; 3 player games. Each round a player from team 1 should play someone from team 2 and someone from team 3.
    Ideally each player will play every other player with no (or as few as possible repeats) and also no (or as few as possible) game repeats.

    I am pretty sure that no perfect solution exists. 3 teams with players 1,2,...,8 each.
    So for example 111 would represent the match-up of all #1 players from the 3 teams. For none of those to ever meet again we can't have:
    11* = ( 111, 112, 113, ..., 118)
    1*1 = ( 111, 121, ..., 181)
    *11 = (111, 211, 311, ..., 811)
    So that's 3*8 = 24 minus the 2 duplicates of 111. This effectively eliminates 22 combinations just through a single match-up in the 1st round. Similarly for 222, 333, ..., 888 This makes for 8 first round matches times 22 eliminated combinations, for a total of 176 combinations gone after the 1st round. Similarly in the following rounds with some overlap of eliminated combinations between the rounds.
    In total we only have 8*8*8 = 512 combinations. With roughly a third gone after round one we run out of combinations long before the problem is solved in round 8. In the end you will have some players that have met twice and others that haven't met at all.

    #31 5 months ago

    thanks

    that was my thought also.

    i played around and got it so there were only a few repeats but was not able to get it all the way.

    Was hoping a smart math person could plot out mathematcially the 'best' way with fewest repeats

    #32 5 months ago

    Mathematically this is a mixed-integer programming problem and its complex because it's so overly constrained. Like Yoski mentioned the problem is with the players needing to play each other twice.

    A short run (100 seconds) produces a poor solution with many players playing against each other 3-4 times. I'll run it over the weekend to see how good it can get.

    here's the output and math model:
    https://drive.google.com/open?id=0B_RoyxcAZ9L8WkxrNjBMeEF5ZUU
    https://drive.google.com/open?id=0B_RoyxcAZ9L8cEl3TElteDVSU0k

    #33 4 months ago

    Had fun playing with the model. Ignore my last post because the model was technically incorrect - it was allowing multiple people to sit out each round.

    I'm just an amateur modeler, but I don't believe a solution exists given the constraints you described. There is an easy solution if you drop the player-vs-player requirement, and that solution is below.

    Model: https://drive.google.com/open?id=0B_RoyxcAZ9L8cEl3TElteDVSU0k
    Output: https://drive.google.com/open?id=0B_RoyxcAZ9L8WjBsRUJINFduSUU

    snip (resized).PNG

    Promoted items from the Pinside Marketplace
    From: $ 24.00
    Apparel - Unisex
    Double Danger Pinball
    $ 29.95
    Gameroom - Decorations
    ULEKstore
    $ 24.50
    Playfield - Protection
    ULEKstore
    From: $ 20.00
    Playfield - Toys/Add-ons
    Lermods
    $ 42.99
    Lighting - Interactive
    Lee's Parts
    € 24.95
    Playfield - Toys/Add-ons
    Multigame
    $ 48.00
    Cabinet - Other
    ModFather Pinball Mods
    $ 6.95
    Playfield - Toys/Add-ons
    ULEKstore
    € 29.95
    Playfield - Toys/Add-ons
    Multigame
    $ 9.95
    Playfield - Toys/Add-ons
    ULEKstore
    From: $ 349.95
    Boards
    PinSound
    $ 89.00
    Playfield - Toys/Add-ons
    PinballToys
    $ 160.00
    Lighting - Interactive
    Professor Pinball
    $ 66.95
    Cabinet - Shooter Rods
    Super Skill Shot Shop
    From: $ 45.00
    Playfield - Toys/Add-ons
    Pinbology
    $ 10.00
    Playfield - Toys/Add-ons
    ModFather Pinball Mods
    $ 29.00
    Lighting - Led
    PinballToys
    $ 48.00
    Cabinet - Other
    ModFather Pinball Mods
    $ 48.00
    Cabinet - Other
    ModFather Pinball Mods
    $ 45.00
    Apparel - Unisex
    Double Danger Pinball
    $ 14.00
    Cabinet - Decals
    ModFather Pinball Mods
    $ 35.99
    Lighting - Interactive
    Lee's Parts
    From: $ 25.00
    Cabinet Parts
    Flashinstinct

    Reply

    Wanna join the discussion? Sign up for a Pinside account, or log in if you already have an account.