Draw System for League Phases of European Cups 2024 onwards

including formats, draws, seedings, etc.
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

Sagy wrote: Fri Jun 07, 2024 05:28
amirbachar wrote: Fri Jun 07, 2024 03:46
Sagy wrote: Fri Jun 07, 2024 03:16
There is little doubt in my mind that the general solution is an NP-complete problem. However, UEFA doesn’t need to come up with the best solution. At any point they just need a solution (pick) that ensures that there is at least one path with no deadlocks remains. That can be done in linear time or better.
That's the point, the question whether a soultion exists is NP-hard. It is possible there is no valid solution, and I don't think it can be proven in less than exponential time.
You can pre-create a list of valid matches for each team (both home and away). Yes, it will be a big list but nothing a modern computer will have a hard time with. Even if it takes a week to generate the needed combinations, it’s not an issue since it’s done before the draw. If needed, we can limit the number of combinations to be considered to no more than some arbitrary large number (let’s say 100M). At this point there are no checks just creating valid combination.

When we draw a team (A) the computer picks a valid team (X) for it to play against. At this point you go through all possible renaming combination and remove everything that doesn’t have that matchup (that can by done O(k) or better, k being the number of valid combinations available before the draw).

The computer now creates a list of all teams that have a valid path with a matchup vs team A. Worst case, the list of all teams eligible can be created in O(k) time. Now the computer select team Y from the list of valid teams (we know we will have at least 1 valid path after the selection) and remove all the combinations that don’t include that matchup (again, no worse than O(k) time).

When we remain with only 1 valid path, all matchups are determined and there is no need to continue with the draw, but there is nothing to stop the drawing on the remaining balls and showing the matchups for each of these teams.

If this process is followed, the draw itself is still in linear time. I think that worst case you have to traverse the list of valid matchups 72 times (might be wrong about 72).

Again, I fully agree that the general problem is NP-Complete, I’m just saying that for the purposes of the UEFA draw they don’t have to deal with the full complexity during the draw.
I think the same.
It is not so easy, but it is the only way: going forward looking if there still "feasible solutions".
I think also it is not so easy generating so many "feasible solutions", but I might be wrong.
Hope for more partecipants in the next Prediction Game
amirbachar
Senior Member
Posts: 1747
Joined: Thu Oct 18, 2007 02:22

Post by amirbachar »

Sagy wrote: Fri Jun 07, 2024 05:28
amirbachar wrote: Fri Jun 07, 2024 03:46
Sagy wrote: Fri Jun 07, 2024 03:16
There is little doubt in my mind that the general solution is an NP-complete problem. However, UEFA doesn’t need to come up with the best solution. At any point they just need a solution (pick) that ensures that there is at least one path with no deadlocks remains. That can be done in linear time or better.
That's the point, the question whether a soultion exists is NP-hard. It is possible there is no valid solution, and I don't think it can be proven in less than exponential time.
You can pre-create a list of valid matches for each team (both home and away). Yes, it will be a big list but nothing a modern computer will have a hard time with. Even if it takes a week to generate the needed combinations, it’s not an issue since it’s done before the draw. If needed, we can limit the number of combinations to be considered to no more than some arbitrary large number (let’s say 100M). At this point there are no checks just creating valid combination.

When we draw a team (A) the computer picks a valid team (X) for it to play against. At this point you go through all possible renaming combination and remove everything that doesn’t have that matchup (that can by done O(k) or better, k being the number of valid combinations available before the draw).

The computer now creates a list of all teams that have a valid path with a matchup vs team A. Worst case, the list of all teams eligible can be created in O(k) time. Now the computer select team Y from the list of valid teams (we know we will have at least 1 valid path after the selection) and remove all the combinations that don’t include that matchup (again, no worse than O(k) time).

When we remain with only 1 valid path, all matchups are determined and there is no need to continue with the draw, but there is nothing to stop the drawing on the remaining balls and showing the matchups for each of these teams.

If this process is followed, the draw itself is still in linear time. I think that worst case you have to traverse the list of valid matchups 72 times (might be wrong about 72).

Again, I fully agree that the general problem is NP-Complete, I’m just saying that for the purposes of the UEFA draw they don’t have to deal with the full complexity during the draw.
This number that you capped by (100M) is exactly the hueilristic I was mentioning and it may change the probabilities.
I agree it is an option to use this.
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

I have been working on a simulation tool to create League Phase fixtures taking into account all requirements and constrains.
Avoiding dead ends or deadlock situations is of course really important, but also very heavy from a computational point of view.
I finally solved the problem as followed (and this is what Uefa could be doing as well):
Generate a template for fixture list beforehand.
There are 9 matches in total between teams from the same Pot (so 4x9=36 in total) and 18 matches involving teams from different pots (for example 1 vs 2, for a total of 6x18=108)
All in all there are then 36+108=144 matches in the League Stage and 8 matchdays so 144/8=18 matches in each machday

Remember the number above? In each Matchday (MD) we are having an average of 1.125 matches from teams of the same Pot and 2.25 from teams of different pots.
Practical example: take the 9 matches involving POT1 teams and spread them out in the 8 matchdays, ensuring minimum 1 and maximum 2. Easy. Do the same also for pots 2, 3, and 4. Then add one match for 1vs2, 1 vs 3 1vs 4 2vs 3 2vs 4 and 3vs 4 and add what is missing.
I could easily do that in Excel

Ok so now we have a template for fixture list. We call Pots with letters A, B, C, D and teams with numbers 1, 2 and so on to 9.
so we have A1, A2...A9, B1, B2 to B9, C1 TO C9 and D1 TO D9.

The difficult part once you have all 144 fixtures is to balance them out in matchdays, and ensure that teams can not play home/away more than twice in a row. Again this is also easy to code even just using brute force.

Now you have a template. You Can start drawing one team at the time, and assign the team to a specific code in the fixture list for example Real Madrid = A1. Then every time you draw a team you must check if constrains are met. For example if a fixture is A1-A2 then FC Barcelona can not be assigned to A2. It sounds complicated but it is indeed easier than you think. Also, you do not need to draw 36 teams, cause lot of teams allocations will be "forced" by the computer . It is very simular to how the draw is conducted today but instead of assigning teams to groups you assign them to fixtures. Finally once you have a full fixture list, you can just see if you need to swap home/away team for other reasons
Sagy
Posts: 882
Joined: Sun Dec 19, 2021 01:27
Location: Austin, TX, USA
Contact:

Post by Sagy »

eye wrote: Fri Jun 07, 2024 13:27
Sagy wrote: Fri Jun 07, 2024 05:28 You can pre-create a list of valid matches for each team (both home and away). Yes, it will be a big list but nothing a modern computer will have a hard time with. Even if it takes a week to generate the needed combinations, it’s not an issue since it’s done before the draw. If needed, we can limit the number of combinations to be considered to no more than some arbitrary large number (let’s say 100M). At this point there are no checks just creating valid combination.
If it takes a week to generate the needed combinations it is surely huge problem since 7 spots are still unknown in the league phase and will be decided just a day before the draw. Although to generate all the valid combinations for each club it requires only few mins. For each club there are 28 possible pairs of opponents from the same pot and 36 possible pairs of opponents from each of the other 3 pots. Totally there are 1.3M different lists of opponents and you only need to check how many of these are valid. To do this for all clubs you need to check 36*1.3=47M possible combinations which requires less than 5 mins at an average computer. I might create such lists.

The major problem is when you are combining these lists and try to calculate which solutions will not lead you to a deadlock situation.
The “even if it takes a week” was not to be taken literally, it was a figurative way to say an unreasonable amount of time. I totally believe that modern computers can generate the full needed list in a small fraction of that time.

As to the seven unknown spots. Five of them (the champs) are not going to be an issue since the only restriction they can introduce is pots related and there are going to be less than a handful possible combinations using placeholders (they can only be in pots 3 & 4)). The other two will introduce a potential country conflict and might impact the pots. However, there are only 4 possible combinations to deal with. The lists associated with these limited number of combination can generated ahead of time as well (just in case there is an argument by someone that generating the list of valid paths will take a long time).

I might be wrong, I think that the number of paths to keep track of might be larger than the 47M since we also need to account for the fact that if Team A from pot X has a home game against a team from pot Y it can no longer be matched with team B from pot Y that has an away game. If we don’t keep track of this we might end up with a deadlock if we are left with a valid matchup of A vs B, but will not have a place to play it.

So we are clear. I’m not saying that this is what UEFA will use. I think that the template idea is much better. My point is that for UEFA’s purposes, a solution which will provide quick answers using manual drawing of 36 teams and a computer generated schedule is feasible.
eye
Posts: 467
Joined: Tue Jun 23, 2020 21:52

Post by eye »

The best way to perform the draw is to find in advanced all the possible combinations for 144 matches that we may have and after drawing pairs to remove the ones that are invalid. I don't think there are too many possible combinations that computer won't be able to check and eliminate the invalids in real time(a normal computer can do this in less than 5 mins if there are 1 billion combinations).

As @elkjiaer is back there are 36 matches involving clubs from same pots (9 for each pot) and 108 (6*18) involving clubs from different pots. For matches of same pot the calculation is quick enough since there are at worse case 36 possible matches (usually are less due to country protection) and we need to keep 9 of them so it is 94M totally combinations at worse case to test which of them are valid (each club should be twice). For the matches involving clubs of different pots the number is huge. There are maximum 81 possible matches between clubs of pot x and pot y and we need keep the combinations of 18 matches that are valid (each club to be at 2 combinations). There are something like 10^17 possible combinations to check and we need to do this calculation 6 times.

Even if we find a way to do all these calculations relative fast then we need to merge all these results to tables of 144 matches and check in order to eliminate the cases of a club being drawn against more than 2 clubs from same country. Again we will have a huge number of combinations.

So this solution is practically impossible. So the best solution to me is to have some predefined tables of 144 fixtures (fixtures in format Eng1 vs Fra1 or Eng4 vs Country1) and only draw clubs that won't affect the draw (eg at pot1 draw which of Liverpool and City will be Eng1 and which will be Eng 2, at pot4 which club will be country1 and which country2 for countries with just 1 club)
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

elkjiaer is back wrote: Fri Jun 07, 2024 15:29 I have been working on a simulation tool to create League Phase fixtures taking into account all requirements and constrains.
Avoiding dead ends or deadlock situations is of course really important, but also very heavy from a computational point of view.
I finally solved the problem as followed (and this is what Uefa could be doing as well):
Generate a template for fixture list beforehand.
There are 9 matches in total between teams from the same Pot (so 4x9=36 in total) and 18 matches involving teams from different pots (for example 1 vs 2, for a total of 6x18=108)
All in all there are then 36+108=144 matches in the League Stage and 8 matchdays so 144/8=18 matches in each machday

Remember the number above? In each Matchday (MD) we are having an average of 1.125 matches from teams of the same Pot and 2.25 from teams of different pots.
Practical example: take the 9 matches involving POT1 teams and spread them out in the 8 matchdays, ensuring minimum 1 and maximum 2. Easy. Do the same also for pots 2, 3, and 4. Then add one match for 1vs2, 1 vs 3 1vs 4 2vs 3 2vs 4 and 3vs 4 and add what is missing.
I could easily do that in Excel

Ok so now we have a template for fixture list. We call Pots with letters A, B, C, D and teams with numbers 1, 2 and so on to 9.
so we have A1, A2...A9, B1, B2 to B9, C1 TO C9 and D1 TO D9.

The difficult part once you have all 144 fixtures is to balance them out in matchdays, and ensure that teams can not play home/away more than twice in a row. Again this is also easy to code even just using brute force.

Now you have a template. You Can start drawing one team at the time, and assign the team to a specific code in the fixture list for example Real Madrid = A1. Then every time you draw a team you must check if constrains are met. For example if a fixture is A1-A2 then FC Barcelona can not be assigned to A2. It sounds complicated but it is indeed easier than you think. Also, you do not need to draw 36 teams, cause lot of teams allocations will be "forced" by the computer . It is very simular to how the draw is conducted today but instead of assigning teams to groups you assign them to fixtures. Finally once you have a full fixture list, you can just see if you need to swap home/away team for other reasons
I am trying to do some simulation using an Excel spreadsheet.
My feeling is that in order to reduce the huge complexity, the process should be built in separated steps, paying attention that choices in the prior step do not cause deadlock in the flowwing step.

IMHO a "possible" approach could be:
1) choosing the 144 matches (constraints: each team meet 2 teams per pot, if possible limiting the matches between teams of the same association)
2) associating the 144 matches to the 9 MDs
3) deciding the home/away for each match (constraints: each team meet 1 team per pot home, and 1 team per pot away, home/away for teams of the same city, pairings Tue/Wed due to TV rights)
4) in case changing the sort of MDs in order to avoid that teams play more than 2 match in a row home or away

My simulation is limited for the moment to step 1, and it is already really difficult to manage in order to avoid deadlocks;
of course I don't have a program exploring many feasible paths;
anyway my feeling is I think that some "derby" for teams of the same association could likely happen.
Hope for more partecipants in the next Prediction Game
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

Some time ago I wrote a python code to create fixtures for teams from the same pot . I used ChatGPT to be honest but the logic was simple and the code was fast
You just need to know team names and their country code . Then you create a duplicated list which is exactly the same as the first one .
Now you shuffle the order of teams from first list ( home teams ) to resemble a draw
Now you look at the other list ( away list ) and create a sub-list of possible opponents ( discarding a) teams from same country and b) looking at the fixture list already created discard opponents that give the same reversed fixture . For example if you had Real-Dortmund then Real is not a valid away opponent for Dortmund ) . Once you identify one possible opponent you need to create the same list for all remaining teams from home list again by applying criteria a) and b) and adding criteria c) which is deleting as possible opponent the one we have just selected . Then we count how many possibile opponents all teams have . Then to avoid deadlock we must check that every team has at least one possible valid opoonent ANd that this possible opponent is not the same . I know it sounds complicated but it took me a month to come up with this algorithm . And it worked super fine .
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

eye wrote: Fri Jun 07, 2024 17:32 ...
So this solution is practically impossible. So the best solution to me is to have some predefined tables of 144 fixtures (fixtures in format Eng1 vs Fra1 or Eng4 vs Country1) and only draw clubs that won't affect the draw (eg at pot1 draw which of Liverpool and City will be Eng1 and which will be Eng 2, at pot4 which club will be country1 and which country2 for countries with just 1 club)
Let me check if I understood correctly, since I have some concern.

Example: Let us assume that teams with the better coefficient will reach the LS.
So England will have the below teams:
Pot1: ManCity and Liverpool (Eng1 & Eng2)
Pot2: Arsenal
Pot4: Aston Villa

Arsenal and Aston Villa should avoid ManCity and Liverpool, so there are two options:
a) their draw is not free, and must be computer-assisted or
b) they need to be tagged as Arsenal=Eng3 or AV=Eng4, so in some way their matches can be identified by the predermined table.

In case the option is b) the same may happen for many teams as well:
Eng, Esp, Ita, Ger, Fra, Por, Ned, Sco will have overall 27 teams, and they should be tagged "as well";
11 out of 27 are the only one of their country in their pot:
PSG and Inter in pot1; Benfica, Arsenal and Rangers in pot2; Milan and Sporting in pot3; Aston Villa, Bologna, Girona and Stuttgart in pot4.

They would know in advance some of their opponents:
there will be likley matches between some of these teams (probably 10-12 matches) already predetermined before the "draw"
in other cases (if they meet some of the other 27-11=16 teams) they will know in advance at least the country of some their opponents for example in Pot1 or Pot2.

The draw would lose most of the appeal.
Hope for more partecipants in the next Prediction Game
eye
Posts: 467
Joined: Tue Jun 23, 2020 21:52

Post by eye »

fabiomh wrote: Fri Jun 07, 2024 22:09
eye wrote: Fri Jun 07, 2024 17:32 ...
So this solution is practically impossible. So the best solution to me is to have some predefined tables of 144 fixtures (fixtures in format Eng1 vs Fra1 or Eng4 vs Country1) and only draw clubs that won't affect the draw (eg at pot1 draw which of Liverpool and City will be Eng1 and which will be Eng 2, at pot4 which club will be country1 and which country2 for countries with just 1 club)
Let me check if I understood correctly, since I have some concern.

Example: Let us assume that teams with the better coefficient will reach the LS.
So England will have the below teams:
Pot1: ManCity and Liverpool (Eng1 & Eng2)
Pot2: Arsenal
Pot4: Aston Villa

Arsenal and Aston Villa should avoid ManCity and Liverpool, so there are two options:
a) their draw is not free, and must be computer-assisted or
b) they need to be tagged as Arsenal=Eng3 or AV=Eng4, so in some way their matches can be identified by the predermined table.

In case the option is b) the same may happen for many teams as well:
Eng, Esp, Ita, Ger, Fra, Por, Ned, Sco will have overall 27 teams, and they should be tagged "as well";
11 out of 27 are the only one of their country in their pot:
PSG and Inter in pot1; Benfica, Arsenal and Rangers in pot2; Milan and Sporting in pot3; Aston Villa, Bologna, Girona and Stuttgart in pot4.

They would know in advance some of their opponents:
there will be likley matches between some of these teams (probably 10-12 matches) already predetermined before the "draw"
in other cases (if they meet some of the other 27-11=16 teams) they will know in advance at least the country of some their opponents for example in Pot1 or Pot2.

The draw would lose most of the appeal.
My logic is to have several predetermine lists of 144 matches (10-20 or even more which will be published at UEFA site before the draw) and one of these preteremind lists will be drawn.

Let's name each spot as A1-A9, B1-B9, C1-C9 and D1-D9. At one predetermined list of 144 matches the English clubs may be A1, A4, B6 and D3 at other may be A2,A3, B5, D7 so their opponents are predetermind in a way but still will be drawn when we will draw which list will be used.
If we assume that the list of first example is drawn we can make a draw to determine which English club (City or Liverpool) will take A1 and which A4, for Arsenal and Aston Villa their spots will be B6 and D3. Then we will do the same for clubs from every country that has more than one club in a pot. If there are 2 or more countries that have just one club at competition and the clubs are at same pot eg at pot 3 there are clubs from Croatia, Greece, Serbia and Isreal (assuming the seeded clubs will qualify) and if at predetermind list that was drawn these spots spots C1,C5,C6,C8 we can make again a draw to determine which club will get each spot.

The logic of this procedure is that we have a draw since the matches at each list will be different, we have a draw at cases that will not affect the requirements of the draw and it will not take too much time. If we want more suspense we may perform first the draws of clubs from same country and the draws of clubs from countries with 1 club at same pot (eg Liverpool will get the first listed English spot A1 at first example A2 at second) and draw which predetermined list will be used at the end.

The idea is to avoid any deadlock situation and have a fast and simple enough process.
Sagy
Posts: 882
Joined: Sun Dec 19, 2021 01:27
Location: Austin, TX, USA
Contact:

Post by Sagy »

@eye, a variation of your approach with drawing the countries first is to still draw all teams from pot 1 first. To use your example, if Liverpool is drawn after City they are placed into A4 (even if they are 2nd or 3rd). If someone else is drawn 4th before Liverpool is drawn, they are placed into A5 "to avoid deadlock" (similar with what they used to do to split teams between Tuesday and Wednesday games) and A4 is "saved" until Liverpool is drawn.
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

eye wrote: Fri Jun 07, 2024 23:18
fabiomh wrote: Fri Jun 07, 2024 22:09
eye wrote: Fri Jun 07, 2024 17:32 ...
So this solution is practically impossible. So the best solution to me is to have some predefined tables of 144 fixtures (fixtures in format Eng1 vs Fra1 or Eng4 vs Country1) and only draw clubs that won't affect the draw (eg at pot1 draw which of Liverpool and City will be Eng1 and which will be Eng 2, at pot4 which club will be country1 and which country2 for countries with just 1 club)
Let me check if I understood correctly, since I have some concern.

Example: Let us assume that teams with the better coefficient will reach the LS.
So England will have the below teams:
Pot1: ManCity and Liverpool (Eng1 & Eng2)
Pot2: Arsenal
Pot4: Aston Villa

Arsenal and Aston Villa should avoid ManCity and Liverpool, so there are two options:
a) their draw is not free, and must be computer-assisted or
b) they need to be tagged as Arsenal=Eng3 or AV=Eng4, so in some way their matches can be identified by the predermined table.

In case the option is b) the same may happen for many teams as well:
Eng, Esp, Ita, Ger, Fra, Por, Ned, Sco will have overall 27 teams, and they should be tagged "as well";
11 out of 27 are the only one of their country in their pot:
PSG and Inter in pot1; Benfica, Arsenal and Rangers in pot2; Milan and Sporting in pot3; Aston Villa, Bologna, Girona and Stuttgart in pot4.

They would know in advance some of their opponents:
there will be likley matches between some of these teams (probably 10-12 matches) already predetermined before the "draw"
in other cases (if they meet some of the other 27-11=16 teams) they will know in advance at least the country of some their opponents for example in Pot1 or Pot2.

The draw would lose most of the appeal.
My logic is to have several predetermine lists of 144 matches (10-20 or even more which will be published at UEFA site before the draw) and one of these preteremind lists will be drawn.

Let's name each spot as A1-A9, B1-B9, C1-C9 and D1-D9. At one predetermined list of 144 matches the English clubs may be A1, A4, B6 and D3 at other may be A2,A3, B5, D7 so their opponents are predetermind in a way but still will be drawn when we will draw which list will be used.
If we assume that the list of first example is drawn we can make a draw to determine which English club (City or Liverpool) will take A1 and which A4, for Arsenal and Aston Villa their spots will be B6 and D3. Then we will do the same for clubs from every country that has more than one club in a pot. If there are 2 or more countries that have just one club at competition and the clubs are at same pot eg at pot 3 there are clubs from Croatia, Greece, Serbia and Isreal (assuming the seeded clubs will qualify) and if at predetermind list that was drawn these spots spots C1,C5,C6,C8 we can make again a draw to determine which club will get each spot.

The logic of this procedure is that we have a draw since the matches at each list will be different, we have a draw at cases that will not affect the requirements of the draw and it will not take too much time. If we want more suspense we may perform first the draws of clubs from same country and the draws of clubs from countries with 1 club at same pot (eg Liverpool will get the first listed English spot A1 at first example A2 at second) and draw which predetermined list will be used at the end.

The idea is to avoid any deadlock situation and have a fast and simple enough process.
Yes, I got it. Yes, it can work.
Probably it is not spectacular like the traditional manual draw, but...this way you are sure 100% it works.

I am afraid that most of the job need to be done by the computer in order to be 100% sure there is no deadlock.
The totally manual draw has been a TV show, with the "suspance" for each single draw and ball;
I don't know how UEFA will do to preserve this aspect, but sincererly I don't care.

In addition, the multiple-choice predetermined tables don't solve some of the remaining constraints, for example TV pairings, or avoiding two teams of the same city playing both home in the same MD.
So all the home/away can be solved only after the draw to choose the table.

---------------------------------------------------------------------------
Let me specule about the method UEFA will actually apply.
If I understood correctly they draw manually a team and then a computer will determine their opponent,
then they draw manually a second team and so on....

I suspect that, in order to be 100% sure, they might predetermine in advance one single fixture table which works,
and when they "draw" manually a team, the computer already "knows" which are their opponents, due to a pre-elaboration.
Why I think so?

My concern is that in order to be sure that will there be no deadlock, it is important to start the fixtures with the most critical teams:
in my opinion for example in 24/25 it is safer starting with the 3 German teams in Pot1: Bayern, Dortmund and Leipzig (if Leverkusen had won CL, they would have passed Barcelona in position 9 and Germany would have had 4 teams in Pot1)
Then you should complete the Pot1: the two English teams of Pot1, the two Spanish teams of Pot1, and finally Inter and PSG.
Then you pass to the two Italian teams of Pot2, and so on then you complete Pot2, starting from country with more teams.
Probably Pot4 should come before Pot3 because there are many teams from the Top5 countries with many other teams
Hope for more partecipants in the next Prediction Game
eye
Posts: 467
Joined: Tue Jun 23, 2020 21:52

Post by eye »

I tried to check if it was easy enough to find out all the valid sets of 144 matches (with the assumption that seeded clubs of qualifiers will be at LP) even if computer needed much time to find them. My plan was to do this at 3 steps.

The first step was easy enough since I only needed to remove the matches of clubs from same country. After removing them there are 31 valid matches between pot1 clubs, 35 valid matches between pot2 clubs,35 valid matches between pot3 clubs, 35 valid matches between pot4 clubs, 72 valid matches between pot1 and pot2 clubs, 80 valid matches between pot1 and pot3 clubs, 78 valid matches between pot1 and pot4 clubs, 71 valid matches between pot2 and pot3 clubs, 75 valid matches between pot2 and pot4 clubs and 80 valid matches between pot3 and pot4 clubs

The second step was to find out the sets of valid 9 between clubs of same pot for each pot and the sets of 18 valid matches between clubs from 2 different pots for all 6 pot combinations. So there are 6828 sets of valid matches between clubs of pot1 and 22512 valid sets of matches between clubs at each of the other 3 pots. This is where I stopped cause the third step would have been to combine all these to create sets of 144 matches to check if a club is drawn against more than 3 clubs from same country (this would have been the final step).

Combining just the 4 sets of 9 matches between clubs of same pots I get 7x10^16 combinations and obviously the sets of 18 matches between clubs from different pots will be many many more. So I stopped at this point.

Although there is a useful conclusion from this attempt. Even if a very small percentage (like 0.0001 %) of all possible 144 sets of matches is valid at step3 (the reverse country protection) there will still be billions of billions valid sets of 144 matches which means a deadlock in the draw is most likely impossible considering that I didn't even use the exception rule that we may have matches between clubs from same country (for countries with 4+clubs) in case of a deadlock situation.
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

eye wrote: Sat Jun 08, 2024 20:52 I tried to check if it was easy enough to find out all the valid sets of 144 matches (with the assumption that seeded clubs of qualifiers will be at LP) even if computer needed much time to find them. My plan was to do this at 3 steps.

The first step was easy enough since I only needed to remove the matches of clubs from same country. After removing them there are 31 valid matches between pot1 clubs, 35 valid matches between pot2 clubs,35 valid matches between pot3 clubs, 35 valid matches between pot4 clubs, 72 valid matches between pot1 and pot2 clubs, 80 valid matches between pot1 and pot3 clubs, 78 valid matches between pot1 and pot4 clubs, 71 valid matches between pot2 and pot3 clubs, 75 valid matches between pot2 and pot4 clubs and 80 valid matches between pot3 and pot4 clubs

The second step was to find out the sets of valid 9 between clubs of same pot for each pot and the sets of 18 valid matches between clubs from 2 different pots for all 6 pot combinations. So there are 6828 sets of valid matches between clubs of pot1 and 22512 valid sets of matches between clubs at each of the other 3 pots. This is where I stopped cause the third step would have been to combine all these to create sets of 144 matches to check if a club is drawn against more than 3 clubs from same country (this would have been the final step).

Combining just the 4 sets of 9 matches between clubs of same pots I get 7x10^16 combinations and obviously the sets of 18 matches between clubs from different pots will be many many more. So I stopped at this point.

Although there is a useful conclusion from this attempt. Even if a very small percentage (like 0.0001 %) of all possible 144 sets of matches is valid at step3 (the reverse country protection) there will still be billions of billions valid sets of 144 matches which means a deadlock in the draw is most likely impossible considering that I didn't even use the exception rule that we may have matches between clubs from same country (for countries with 4+clubs) in case of a deadlock situation.
Thanks for sharing . Some short comments :
1) all the numbers you posted might actually need to be doubled up . Cause City-Real is not the same as Real-City otherwise in your case you are fixing the home team beforehand
2) if you have 2x 31 =62 valid matches for teams of Pot1 facing each other then as soon as you draw the first one then the number of those will decrease drastically cause you would need to remove all other matches where the two teams involved in the first fixture are set as home and away team in the other matchups . So it gets much easier .
3) you would then have a problem of checking for dead ends as far as you keep drawing new fixtures . So every time you draw one you must ensure a valid solution exists
4) we still don’t know how those matches will be spread in the different match days . Either they have a set of compiled fixtures with all 144 using letters and numbers and then they allocate teams or as the draw fixtures they allocate them directly in the difffrent matchdays . This is is also drastically reducing the number of matchups . For example : if you draw City-real then you assign it to MD1 then City can’t play home on MD2 and Real can’t play away . Hope the logic is clear
eye
Posts: 467
Joined: Tue Jun 23, 2020 21:52

Post by eye »

elkjiaer is back wrote: Sun Jun 09, 2024 01:08
eye wrote: Sat Jun 08, 2024 20:52 I tried to check if it was easy enough to find out all the valid sets of 144 matches (with the assumption that seeded clubs of qualifiers will be at LP) even if computer needed much time to find them. My plan was to do this at 3 steps.

The first step was easy enough since I only needed to remove the matches of clubs from same country. After removing them there are 31 valid matches between pot1 clubs, 35 valid matches between pot2 clubs,35 valid matches between pot3 clubs, 35 valid matches between pot4 clubs, 72 valid matches between pot1 and pot2 clubs, 80 valid matches between pot1 and pot3 clubs, 78 valid matches between pot1 and pot4 clubs, 71 valid matches between pot2 and pot3 clubs, 75 valid matches between pot2 and pot4 clubs and 80 valid matches between pot3 and pot4 clubs

The second step was to find out the sets of valid 9 between clubs of same pot for each pot and the sets of 18 valid matches between clubs from 2 different pots for all 6 pot combinations. So there are 6828 sets of valid matches between clubs of pot1 and 22512 valid sets of matches between clubs at each of the other 3 pots. This is where I stopped cause the third step would have been to combine all these to create sets of 144 matches to check if a club is drawn against more than 3 clubs from same country (this would have been the final step).

Combining just the 4 sets of 9 matches between clubs of same pots I get 7x10^16 combinations and obviously the sets of 18 matches between clubs from different pots will be many many more. So I stopped at this point.

Although there is a useful conclusion from this attempt. Even if a very small percentage (like 0.0001 %) of all possible 144 sets of matches is valid at step3 (the reverse country protection) there will still be billions of billions valid sets of 144 matches which means a deadlock in the draw is most likely impossible considering that I didn't even use the exception rule that we may have matches between clubs from same country (for countries with 4+clubs) in case of a deadlock situation.
Thanks for sharing . Some short comments :
1) all the numbers you posted might actually need to be doubled up . Cause City-Real is not the same as Real-City otherwise in your case you are fixing the home team beforehand
2) if you have 2x 31 =62 valid matches for teams of Pot1 facing each other then as soon as you draw the first one then the number of those will decrease drastically cause you would need to remove all other matches where the two teams involved in the first fixture are set as home and away team in the other matchups . So it gets much easier .
3) you would then have a problem of checking for dead ends as far as you keep drawing new fixtures . So every time you draw one you must ensure a valid solution exists
4) we still don’t know how those matches will be spread in the different match days . Either they have a set of compiled fixtures with all 144 using letters and numbers and then they allocate teams or as the draw fixtures they allocate them directly in the difffrent matchdays . This is is also drastically reducing the number of matchups . For example : if you draw City-real then you assign it to MD1 then City can’t play home on MD2 and Real can’t play away . Hope the logic is clear
I think the home and away club of each pair and the matchdays will be decided after the draw from computer. There are clubs that can't play at home or away at same day due to city or TV restrictions. The whole system is so complicated already so there is no need to add more complexity which probably will be unnecessary.

From this experience I had I am pretty sure that a manual draw is not that hard to be done (leaving at the end which will be the home club of each pair and the schedule). The country protection issue is not that big and affects a small percentage of possible pairs). At matches between club from same pot at 3 pot only 1 out of the 36 pair is invalid and at the other pot 5 are invalid . At pair between clubs from different pots at worse case 10 out of 81 are invalid while at one combination there is only 1.

An easy way to perform manual draw is first to draw opponents for each each Italian and German club the for each English and Spanish club... leaving at the end the clubs from countries that have just 1 club at competition. This way you are controlling easier country protection at the beginning and you only need to focus at the reverse country protection at the end.

After my previous post I realized something very funny about the numbers I gave. If I let my computer run 24/7 to perform the combination of the 4 sets of 9 matches between clubs of same pots 3 years later it will have done something like 0.1% of the process 😀 (probably even much less cause I rounded up a lot the needed time)
diyx
Posts: 106
Joined: Mon Jul 02, 2018 18:17

Post by diyx »

eye wrote: Sun Jun 09, 2024 03:42 I think the home and away club of each pair and the matchdays will be decided after the draw from computer. There are clubs that can't play at home or away at same day due to city or TV restrictions. The whole system is so complicated already so there is no need to add more complexity which probably will be unnecessary.
I don't think the draw can be done without determining the home and away games right away. Otherwise I believe situations will occur where clubs cannot play one home and one away game against opponents from the same pot because some home or away games are forced to the clubs to meet the criteria.

Moreover, there are some soft constraits, such as that UEFA aims to spread matches of Pot 1 vs Pot 1 over as many matchdays as possible to increase TV audience.

All in all I cannot believe they will do something different than creating a predetermined schedule and then assigning clubs to spots (like A1, B5, C2, etc.).
Post Reply