actually, if i assume fixed pairing tree from the first round to the finals, then i think there are 315 (= 3 * 105) possible pairings. 105, as was many times repeated, and 3 because after making four pairs, you have three different ways how to put them into the tree. correct me if i am wrong
then, from the 315 starting positions, 6 games are played to determine finalists (4 in quarterfinals and 2 in semifinals), so it makes 2^6 = 64 ways of possible tournament progress. 315 * 64 = 20 160 ways to be evaluated. again, correct me if i am wrong
third, i am not sure what were Robert Jasiek's preferences for avoiding repetitions, but i think it is natural to weigh repetition in quarterfinals (1st round) with 1 and in semifinals with 1/4 (repetition in finals is unavoidable), because for latter rounds the players causing repetition have to first win their games in former rounds (with 0.5 likelihood each). then we can simply take weighted sum of the repetitions in worst case scenario for each starting position and choose the tree with smallest value
fourth, it is not difficult to write one-purpose program that can search through all initial pairings and for each search through all possible scenarios and then choose the pairing (pairings) with lowest score. (i believe that even if i made some mistake with number 20 160)
fifth, as i checked last year EGC results, it was pretty easy to evaluate the situation even only with paper and pencil. i didn't save it, but if i recall correctly, taking situation after 7 rounds of main tournament, the best solution was 1 possible repetition in semifinal pairing. with 8 rounds it became slightly more complicated but still pretty manageable. i admit i should check also results few years back to see if it is usually easier of more difficult.
last, i don't fully understand why it is so important to avoid repeated pairings. in swiss and MM tournaments it is clear, because repeated pairing provides less information about the players performance than a not-repeated one. but in this case you use macmahon tournament only as qualification for the otherwise independent knock-out. repetitions are surely less fun for both players and fans (ok, this argument should be important enough), but in my opinion doesn't hurt this tournament system. actually, games of the main tournament seems to be even less important because the standings of 8 qualified players are not even mentioned as a seeding criterion for pairing of the knock-out. or, if they are considered as such, they are of less importance than avoiding repetitions.
sorry if i messed up terms quarterfinals and semifinals somewhere, i got confused several times during writing. otherwise i hope my long post is meaningful and will help the discussion
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 12:21 pm
by RobertJasiek
Players prefer not to have repeated opponents. From an abstract POV, giving a player a second chance to win against the same opponent is undesirable (but this argument has counter-arguments).
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 2:01 pm
by Joaz Banbeck
Cassandra wrote:
Joaz Banbeck wrote:There are 105 possible first round pairings. They generate 70 possible quartets for for the semi-finals, leading to 28 possible finals pairs. Thus the upper bound for the total number of possibilities is 205800. That is well within brute-force range.
The room to work with is not that big. ...
True, but really not relevant. Once we have established an upper bound, and we conclude that this means that Jasiek should just solve it by brute force, then refining the upper bound doesn't add anything to the conclusion.
Laman wrote:actually, if i assume fixed pairing tree from the first round to the finals, then i think there are 315 (= 3 * 105) possible pairings. 105, as was many times repeated, and 3 because after making four pairs, you have three different ways how to put them into the tree. correct me if i am wrong
then, from the 315 starting positions, 6 games are played to determine finalists (4 in quarterfinals and 2 in semifinals), so it makes 2^6 = 64 ways of possible tournament progress. 315 * 64 = 20 160 ways to be evaluated. again, correct me if i am wrong
third, i am not sure what were Robert Jasiek's preferences for avoiding repetitions, but i think it is natural to weigh repetition in quarterfinals (1st round) with 1 and in semifinals with 1/4 (repetition in finals is unavoidable), because for latter rounds the players causing repetition have to first win their games in former rounds (with 0.5 likelihood each). then we can simply take weighted sum of the repetitions in worst case scenario for each starting position and choose the tree with smallest value
fourth, it is not difficult to write one-purpose program that can search through all initial pairings and for each search through all possible scenarios and then choose the pairing (pairings) with lowest score. (i believe that even if i made some mistake with number 20 160) ...
Most of the comments above have assumed that elements on the tree can be be swapped around. But it can be solved with a fixed tree too, and your final answer is correct.
@Jasiek: Again, just brute force it.
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 2:13 pm
by RobertJasiek
Cassandra appears to have written an Excel file for brute force minimization. Any1 to do it for OpenOfficeCalc?
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 2:39 pm
by Laman
RobertJasiek wrote:Players prefer not to have repeated opponents. From an abstract POV, giving a player a second chance to win against the same opponent is undesirable (but this argument has counter-arguments).
ok, i can agree with that. i was only under impression that repetitions are thought to affect results in a negative way (and i couldn't understand that)
brute force is always a solution
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 7:17 pm
by Joaz Banbeck
Laman wrote:...
brute force is always a solution
All too true. Unfortunately, it is not always a good solution.
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Wed Nov 24, 2010 11:35 pm
by Cassandra
Joaz Banbeck wrote:
Laman wrote:... brute force is always a solution
All too true. Unfortunately, it is not always a good solution.
Fortunately, there will be more than 1 solution in many cases.
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Thu Nov 25, 2010 8:32 am
by emeraldemon
Here's a script to calculate the best by brute force, the website won't let me attach the file. The hard part is enumerating the combinations in a way with no redundancies. I wrote it so it should in theory work with any size, but for s=16 it takes too long to finish. s=8 finishes basically instantly. just change the list that says "previous" to include whatever pairs have already played each other, it will return all possible combos sorted by score.
#how many ways are there to partition a set into 2 equal subsets? n choose (n/2). #then we just continually push into smaller & smaller sub-partitions # At the top level, we break into a number of lists, i.e. lists of pairs [(brkt1, brkt2)] # then for each sub bracket we do the same, i.e. [([(sub1, sub2)], [(sub3, sub4)]] # finally at each pairing we need to do the cartesian product, i.e. for each comb. of sub1 & sub2, create a bracket. def subpairs(parts): if len(parts) == 1: return [parts] l = [] t = list(combinations(parts, len(parts)//2)) for j in range(0, len(t)//2): for a in subpairs(t[j]): for b in subpairs(t[len(t) - 1 -j]): l.append(a + b) return l
for perm in subpairs(players): rematch = 0.0 s = map(lambda x : [x], perm)
while len(s) > 2: t = [] for i in range(0,len(s),2): for j in s[i]: for k in s[i+1]: if (j,k) in previous or (k,j) in previous: rematch += 1.0/(len(s[i])**2) t.append(s[i] + s[i+1]) s = t
permutation_score.append((rematch, perm))
permutation_score.sort(reverse = True) for out in permutation_score: print out
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Thu Nov 25, 2010 3:39 pm
by Cassandra
RobertJasiek wrote:Cassandra appears to have written an Excel file for brute force minimization. Any1 to do it for OpenOfficeCalc?
I suppose that it would be sufficient to let someone with OpenOffice convert the Excel file I have sent you.
May be that it would even work to just open the Excel file with OpenOffice. Because it is said that OpenOffice is compatible to Microsoft Office, so that one can at least open Microsoft Office files.
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Sat Dec 11, 2010 9:59 pm
by HermanHiddema
I decided to also give it a shot.
The code at the bottom (hidden) is Python 3. Save it as e.g. "egcknockout.py"to use it. (BTW: Can an admin please relax the restrictions on attachments? I couldn't even attach it as txt).
The program takes as input a wall list as produced by common pairing programs (in a format compatible with the EGD), e.g. the top 8 Europeans from the EGC 2010 after round 7 (courtesy Asparagus):
Note: I have listed Antti Tormanen here, but with the current rules it could also be Catalin Taranu, depending on the result of a play-off
As output, it returns all possible pairings, ranked by desirability. Desirability is determined by three factors:
1. Minimize the number of repeat pairings in the Quarter Final 2. Minimize the average number of repeat pairings in the Semi Final 3. Try to stay as close as possible to a fold pairing.
Running the above list through the program returns (first 25 lines):
Where the first number is repeat pairings in the QF, the second is the average number of repeats in the SF, and the third is closeness to fold pairing (sum of squares). For each of them, lower is better.
The above means there are three pairings without repetitions that minimize SF repetitions to 12.5% (2 out of 16 possible results have a forced repeat pairing). The best has a fold quality of 12. It is possible to improve the fold quality to 4 (closer to fold), but at the cost of increasing the chance of a repetition in the SF to 18.75% (3/16).
The 20th to 23rd listed pairings reduce the chance of a repetition in the SF to zero, but at the cost of containing a repetition in the QF.
For determining the closeness to a fold pairing, the order of listing is used, not the order of placement as given in the data. That means you can swap lines around if you feel that the resulting listing gives a better ordering to the player, without having to renumber anything. (For example, in case of equal MMS/SOS, you might want order players according to Prior Rating, while the pairing program orders them by SOSOS)
To test the program, you can call it from the commandline and it will run on the top 8 from the EGC 2010 as listed above. The code also contains a version with Catalin instead of Antti. Choose the preset "egc2010b" for that (default is "egc2010a").
At the bottom is data from the EGC 2009 after 7 rounds, from which other test sets can be made.
To test under windows, you can also run IDLE (python GUI) and (if the file is save as egcknockout.py in python's Lib/site-packages directory) do:
Specify a file to read, a block of text to parse, or a list of lines to parse.
Each line should be white space separated, with the following fields: <id> <firstname> <lastname> <other fields>
This format is compatible with the one used by wall lists for the EGD
The first three fields will be parsed as such, and are mandatory. The id is parsed as a number, any additional characters will be discarded.
Make sure there are no spaces in names (replace by underscores if needed). First/last name can be in any order, the order will be retained
The other fields will be parsed for pairings. A pairing should be a number (referring to an opponent) followed by a +, = or - (win, draw or loss). It can optionally be followed by more characters, such as color and handicap info, which will simply be discarded.
Each player will be assigned an order, which is used to determine the quality of the pairing. The order is assigned according to the order of the players in the input, not according to the player's id. """
def parseplayers(filepath=None, text=None, lines=None): if filepath: try: with open(filepath) as f: text = f.read() except IOError: print("Unable to open file {0}".format(filepath)) return False elif text: lines = text.splitlines() elif not lines: print("No argument given, please specify one of filepath, text or lines") return False players = {} order = 0 pairing = re.compile(r"^(\d+)[+=-]") for line in lines: fields = line.split() if len(fields) > 3: p = { "id":fields[0], "name":"{0} {1}".format(fields[1], fields[2]), "order":order, "opponents":[] } for field in fields[3:]: match = pairing.match(field) if match: p["opponents"].append(match.group(1)) order += 1 players[p['id']] = p return players
"""Creates a matrix of prior pairings"""
def priormatrix(plist): np = len(plist) #number of players priors = [[0]*np for i in range(np)] # create matrix for id, player in plist.items(): for opp_id in player["opponents"]: if opp_id in plist: # this opponent is also in the group opponent = plist[opp_id] priors[player['order']][opponent['order']] = 1 #the reverse matrix entry is not set, it will be set by the reverse entry return priors
"""Generator function, which yields all possible pairings within the given list of players. Number of players must be even. """
def allpairings(plist): length = len(plist) if (length % 2) != 0 or length < 2: return # odd number of players or empty list if length == 2: yield [(plist[0], plist[1])] else: for i in range(1,length): head = (plist[0], plist[i]) for tail in allpairings(plist[1:i] + plist[i+1:length]): yield [head] + tail
"""Determines pairing quality as a triple of numbers. The first of these indicates the number of repeats in this pairing, the second indicates the average number of repeats in the next round, the third indicates how close to a fold pairing this pairing is.
The arguments are a pairing and the prior pairings matrix.
How close to a fold pairing the pairing is is calculated as a sum of the squares of the distances of each pairing from perfect.
E.g. with 8 players, 1-8 is a perfect pairing, as are 2-7, 3-6 and 4-5. If the sum of the order of players is 9, it is perfect, and any such pairings have distance zero. If the sum is not 9, the difference with 9 is the distance, and this is squared to calculate quality (e.g. the pairing 1-7 is close to perfect, distance 1, squared to 1, the pairing 1-2 is far from perfect, distance 6, squared to 36. """
def pairingquality(pairing, priors): repeats = 0 # number of repeat pairings in this pairing avgreps = 0 # average number of repeat pairings in next round pairings quality = 0 # Pairing quality (sum of squares distance from fold pairing) np = len(pairing) optimal = 2 * np - 1 # with fold pairing, this is the optimal sum of positions (where first position is zero) for pair in pairing: repeats += priors[pair[0]['order']][pair[1]['order']] quality += (pair[0]['order'] + pair[1]['order'] - optimal) ** 2 result = 0 minimums = [] while result < 2**np: # consider all possible results (encoded in bits) winners = [] for i in range(np): if result & 2**i > 0: winners.append(pairing[i][1]) else: winners.append(pairing[i][0]) minreps = len(winners) for wpairing in allpairings(winners): reps = 0 for wpair in wpairing: reps += priors[wpair[0]['order']][wpair[1]['order']] if reps < minreps: minreps = reps minimums.append(minreps) result += 1 avgreps = sum(minimums)/len(minimums) return (repeats, avgreps, quality)
"""Evaluates all possible pairings within the given list of players, and returns a sorted list of pairings. Each list items is a tuple of four items. The first three are those returned by the pairingquality function, the last is a textual representation of the pairing, using player names. The list is first sorted by the first entry in the tuple, then the second, then the third. """
def evaluatepairings(plist, priors): pairings = [] for pairing in allpairings(plist): pairstr = "" for pair in pairing: pairstr = pairstr + "{0} - {1}, ".format(pair[0]['name'], pair[1]['name']) pairstr = pairstr.rstrip(", ") quality = pairingquality(pairing, priors) pairings.append(quality + (pairstr,)) return sorted(pairings)
Harleqin wrote:If you do not have a fixed tree, but instead re-pair each round after the previous has been completed, the proceeding is very simple: just do not repeat a pairing. The rounds are independent then, so you only have to look at the players in the round at hand.
This does not necessarily minimize.
Every time you pair players for the first time the number of first-time pairings increases by 1 for each player. So no it doesn't necessarily minimize, actually it doesn't ever minimize, nor maximize. All you can do is arrange players to maximize first-time pairings in the current round.
For that I suggest a computer program to run combinations, or for small tournaments just keep a league table and use it for the next tournament as well, blocking out pairs which have already been done and then limiting yourself to choosing pairs from what is available.
In theory there's no way to get around the fact that each time you pair someone the number of previous pairings increases by one; no matter how you try to arrange the players, eventually there will exist players who have a previous number of first time pairings equal to the number of players in the tournament, and then there's just nothing you can do. Well there's one thing. If you seed players with a large number of pairings against players with a low number of previous pairings in the first round, that makes it more likely the players who have a large number of previous pairings will get knocked out. That's about all you can do I'd guess, once you start running into large numbers of players with more than 7 previous pairings.
-
Re: Minimize Repeated Pairs in 8 Player KO
Posted: Sun Dec 12, 2010 2:44 am
by HermanHiddema
usagi wrote:
RobertJasiek wrote:
Harleqin wrote:If you do not have a fixed tree, but instead re-pair each round after the previous has been completed, the proceeding is very simple: just do not repeat a pairing. The rounds are independent then, so you only have to look at the players in the round at hand.
This does not necessarily minimize.
Every time you pair players for the first time the number of first-time pairings increases by 1 for each player. So no it doesn't necessarily minimize, actually it doesn't ever minimize, nor maximize. All you can do is arrange players to maximize first-time pairings in the current round.
Since the pairing in question is knock-out, any pairings that are added during the knock-out are irrelevant, since that pairing can never happen again anyway, as one of the players has been knocked out. That means that only the prior pairings from the McMahon phase (rounds 1-7) are relevant.
As Joaz has shown theoretically, and several programs have since shown experimentally, it is possible to minimize the chance of repeat pairings in the next round by optimizing the pairing for the current round.
For that I suggest a computer program to run combinations, or for small tournaments just keep a league table and use it for the next tournament as well, blocking out pairs which have already been done and then limiting yourself to choosing pairs from what is available.
For general pairing, there are plenty program. This thread is very specifically about an 8 player knock-out after 7 rounds McMahon at the European Go Congress.
In theory there's no way to get around the fact that each time you pair someone the number of previous pairings increases by one; no matter how you try to arrange the players, eventually there will exist players who have a previous number of first time pairings equal to the number of players in the tournament, and then there's just nothing you can do. Well there's one thing. If you seed players with a large number of pairings against players with a low number of previous pairings in the first round, that makes it more likely the players who have a large number of previous pairings will get knocked out. That's about all you can do I'd guess, once you start running into large numbers of players with more than 7 previous pairings.
-
The pairing does not involve the whole tournament, only the top 8 Europeans, who have played part of their previous pairings against players outside the top 8 (or against non-European players).
