How to minimize repeated pairs in an 8 player KO, which follows as second stage after 7 ~ 8 rounds of a prior stage tournament? Firstly I want to minimize repetitions preferably in both quarter and semi finals, secondly among all such pairings minimize for quarter finals. How is the greatest minimization achieved in general?

(Of course, this knowledge is needed for perfect EGC organization in future.)

I don't understand every detail of what you want.
But there are only 105 possible starting arrangements for single elimination tree with 8 players. A computer program can easily brute-force that and apply any evaluation function you want to that starting position.
Or do you want to optimize matchmaking during the prior 7-8 rounds too?
edit: miscalculated the number of arrangements. It's 8!/(2^4*4!)=105

_________________
Sanity is for the weak.

Is there such a program for KO?

For the previous stage, suitable programs already take care of the pairings.

For KO, I would prefer to do it manually. So 2500 would be too great a number. There should be more theoretical insight, I hope.

You need to state your assumptions and optimization goals more clearly.

As input we have a list of pairings that already occurred in earlier rounds. What do you assume about winning probabilities between the top 8 players? Since those affect the likelihood of repeated pairings in the semi-finals.

One could try to minimize:
1) Expectancy value of repeats in the semifinals+Expectancy value of repeats in the quarter-finals
2) If 1 is equal Expectancy value of repeats in the quarter-finals
Using the assumption that any match has even odds.

Is that what you want?

_________________
Sanity is for the weak.

Assumptions:

- We have 8 participants of the KO.
- We have a list of earlier pairs among those 8 players.
- The list is a subset of all possible pairs among those 8 players.
- Assume 50% winning likelihood for each possible game to be won by either player.
- For an arbitrary, specific KO pairing in the quarter finals and arbitrary, specific set of players winning in the quarter finals, and an arbitrary, specific KO pairing in the semi-finals, let Q be the number of repeated pairs in the quarter finals and S be the number of repeated pairs in the semi-finals.
- First priority aim: Minimize Q + S.
- Second priority aim: Among all pairings with minimal Q + S, minimize Q.

Can the pairing of the semi-final depend on the winners of the quarterfinal? Or is it fixed that the winner of QF1 plays the winner of QF2 and the winner of QF3 plays the winner of QF4?

_________________
Sanity is for the weak.

Will the semi-final pairing be independent of the quarter-final pairing ?

The other option would be

1-2 / 3-4 / 5-6 / 7-8 for the quarter-finals, strictly followed by

(1-2)-(3-4) / (5-6)-(7-8) for the semi-finals [(x-y) = winner of x-y]

_________________
The really most difficult Go problem ever: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

In the semi-final, pairings can be made independently of the quarter final's pairings! What matters is minimized repeated pairs - which index number plays which other index number does not matter at all!

An 8-player k.o. tournament can be written as a single tree:



Trees which just have exchanged subtrees at the same node are completely equivalent. For example, you could exchange P0 and P1 in the above without any effect on the pairings; the same holds for Q2 and Q3, or for S0 and S1.

In order to specify such a tree, it is sufficient to list the players in order. In order to get a list of non-equivalent trees, you need to specify a canonical representation, for example, such that among equivalent trees only the one with the players in more alphabetical order is used.

Then, a player's pairing "probability" against each other player is given by their relative positions. For example, P0 in the diagram above has a pairing probability of 1 against P1, of 1/4 against each of P2 and P3, and of 1/16 against all of P4 to P7. Note that for any two players, there is exactly one point in the tree where they can meet.

_________________
A good system naturally covers all corner cases without further effort.

Harleqin I think you misunderstood my(and Cassandra's) question. The question was if the pairing is fixed before the start like in Cassandra's example (i.e. the winner of A vs B will play the winner of C vs D), if the decision can be made after the 4 winners are known(which is of course equivalent to allowing more complex pairing rules like if A and C win they will play each other, but if B and D win they' won't play each other but instead play against E and F. And that wouldn't fit a simple tree.

_________________
Sanity is for the weak.

This is only true with a fixed pairing tree. Because in this type of tree pairing for round 2 is independent on the results of pairs in round 1.

As Robert explained, he would accept a pairing in round 2, which is "open" in such a sense, that the decisive parameter is (only) the fact, whether any two players have met before in the tournament. So you can optimize round 1 and round 2 on their own.

In my opinion, Robert's wish is eqivalent to have any two players, who played already against each other in the ("regular") tournament, meeting as late as possible in the knock-out tournament.

*****
As before, Li Kao had been faster

_________________
The really most difficult Go problem ever: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

ALA as the perfect minimum has not been described in general theory, Harleqin's description is at least a small helping tool for manual pairing.

Cassandra, my aim is not to postpone a particular repeated pair until the semi-final but just to minimize numbers of repeated pairs as described before. Only when the latter is solved would I also additionally care, if possible, for the former.

Robert, I have not written of a particular repeated pair to be avoided in the earlier rounds of the knock-out.

Of course, the effect I supposed has to be "proven", but I think it will be as described.

Also I think that pairing of round 1 of the knock-out cannot be done manually, if you want to fulfill your conditions. Perhaps round 2 can, because it seems possible to get a feeling for what is done for the (only) one game in round 3.

In round 1 you will have the 105 cases Li Kao mentioned as baseline and you will have to calculate all possible different results (16 each), thereafter calculating the resulting effect for optimizing round 2 (i.e. "can repeated pairings be avoided ?").

And this all depends on the table of pairs already encountered during the regular tournament.

Perhaps I could give an Excel-Makro a try, but developing will cost some days effort.

_________________
The really most difficult Go problem ever: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

It is all a bit dependend on how many players have allready been paired against eachother.

A bit of mathematics:

for the first round
There are 28 ways to pair 8 players
and for this round there are 4 games

so if you just pair this round I think in all except extreme situations it is not difficult to have a non -repeating pairing.

for the second round

There are 6 ways to pair 4 players
and for this round there are 2 games

so for this round it is more difficult but surely not often impossible

For the last round the game is prescribed. so the only option you have to swich colours if they allready have played eachother.

This presumes that the TD may decide the pairing after each round.
If you want an unchangable system it is more difficult.

if not many players have played other contestants. just put players in the different halves of the tree.
Butthe more players have played eachother the more difficult it becomes

If you for the first pairing put the players who have allready played eachother in different halves of the tournament
they will not play eachother till the final.

_________________
Promotor and Librarian of Sensei's Library

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.

_________________
A good system naturally covers all corner cases without further effort.

I think that you have an NP-complete problem.

There are weird linkages between S and Q. When pairing the Q-finals, it is presumably possible to have player Z who has played five of the other seven Q-finalists. It therefore makes sense to pair the other two ( call them X and Y ) so that someone is guaranteed to be available to play Z in the semis without duplication. But now there can be a player W who, for similar reasons, needs X to play against V. There is, IMHO, no way to be sure that one can reconcile this short of trying every set of pairings.

Some shortcuts may occur, but categorizing them is a bitch. In the classic NP-complete example, the traveling salesman, I recall that it can be proven that the optimal solution cannot include taking the three longest paths consecutively. The ordering of paths from longest to shortest in the traveling salesman problem is trivial. The ordering of possible pairs in Q-finals is not clearly so.

I think that you just have to brute-force this one.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

True. But more easily calulated by 7 * 5 * 3 = 105

EDIT: Or, to be complete: 7 * 5 * 3 * 1 = 105.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

This does not necessarily minimize.

Now this explains itself nicely without words, thanks!

I think it does, because the players' probability to reach a certain round is equal.

_________________
A good system naturally covers all corner cases without further effort.