Draw System for League Phases of European Cups 2024 onwards

including formats, draws, seedings, etc.
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

I apologize if it has already been mentioned , but do we have a full list of requirements for the League stage ?
Like teams from same country can’t face each other ( unless there are 5 or more and it is strictly needed )
Then I can think about teams not able to play more than 2 home or away matches in a row , teams from the same city need to play home and away on the same matchday , special restrictions for teams from selected countries etc . All in all do we have a full list of requirements ? Also curious to know if tv-pairings are still relevant somehow
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

elkjiaer is back wrote: Sun Jun 09, 2024 13:53 Just read against the Uefa regulations for the draw and they are quite “fluffy”
Some interesting points are the following :
16.02: The opponents of each team, as well as whether each match is played at home or away, are determined by means of a draw. In principle, teams from the same association cannot be drawn against each other and each team may play against a maximum of two opponents from any other one association
17.02 In principle, a club does not play more than two home or two away matches in a row and each club plays one home match and one away match across the first two matchdays and across the last two matchdays. The UEFA administration may derogate from these rules if necessary.
16.01 also says that the draw might be conducted digitally


Also curious to know if tv-pairings are still relevant somehow
greenbay
Senior Member
Posts: 7428
Joined: Tue Mar 13, 2012 17:01

Post by greenbay »

Imho it will be a "heuristic" draw. They'll draw one team from pot 1 to start with. They draw a home and an away opponent for said team from pot 1. Then home and away from pot 2, then from pot 3, then from pot 4. They'll continue with the next team drawn from pot 1. Once pot 1 is emptied, it goes down to pot 2, then to pot 3, finally to pot 4. And after each single "ball" drawn but before it's shown on the big screen, the computer will try many times by random drawn and for a given amout of time, if there is still at least one valid draw remaining. If not, the computer will simply choose another "ball" to show on the big screen that has at least one valid draw remaining.
"Put it in your signature to save you the trouble of writing it over and over again."
amirbachar
Senior Member
Posts: 1747
Joined: Thu Oct 18, 2007 02:22

Post by amirbachar »

greenbay wrote: Sun Jun 09, 2024 14:47 Imho it will be a "heuristic" draw. They'll draw one team from pot 1 to start with. They draw a home and an away opponent for said team from pot 1. Then home and away from pot 2, then from pot 3, then from pot 4. They'll continue with the next team drawn from pot 1. Once pot 1 is emptied, it goes down to pot 2, then to pot 3, finally to pot 4. And after each single "ball" drawn but before it's shown on the big screen, the computer will try many times by random drawn and for a given amout of time, if there is still at least one valid draw remaining. If not, the computer will simply choose another "ball" to show on the big screen that has at least one valid draw remaining.
That's my thought as well, once a team is drawn, the list of possible opponents will be calculated hueristically by the computer, and then the actual opponents will be drawn from that list.
greenbay
Senior Member
Posts: 7428
Joined: Tue Mar 13, 2012 17:01

Post by greenbay »

I'd say the problem could be solved without heuristics... random thoughts:

Make a "possible list" of all 36x36 possible match-ups.
I.e. Man City vs Man City isn't possible, but step 2 will do the trick.

Delete from that possible list all same country match-ups.
I.e. Arsenal vs Man City is history now, and so is Man City vs Man City.

<loop>

// say that loop was already performed 40 times. So there are already 40 valid match-ups drawn and stored in the "fixture list". So now we draw match-up #41

1. Select a random match-up from the possible list, delete it from the possible list and put it on the fixture list.
I.e. Barcelona (pot 1) vs Leverkusen (pot 2)

2. Delete the "return leg" from the possible list.
I.e. Delete Leverkusen vs Barcelona from the possibe list.

3. Delete all games from the possible list, that have the home team playing an away opponent from the same pot.
I.e. Delete Barcelona vs Atalanta (pot 2). Barcelona vs. Juventus (pot 2) etc. from the possible list

4. Delete all games from the possible list, that have the away team playing a home opponent from the same pot.
I.e. Delete Real (pot 1) vs Leverkusen. Man City (pot 1) vs Leverkusen. PSG (pot 1) vs Leverkusen etc. from the possible list.

5. Check fixture list if home team already had an opponent drawn from the same country before.
I.e. Barcelona vs Stuttgart is already on the fixture list, so they are at the maximum allowed two opponents from the same country. Delete all Barcelona matches against German opponents from the possible list.

6. Check fixture list if away team already had an opponent drawn from the same country before.
I.e. Leverkusen had no Spanish on the fixture list before. So no further action here.

7.
<for each team>
<for each pot>

a) check if team only has one possible home game opponent left in pot. Put that match-up on the fixture list. Deleted all same-pot match-ups featuring the same away team from the possible list.
I.e. with Bayern, Dortmund and Leipzig not possible anymore, Barcelona only have Man City left as possible home game from pot 1. So Barcelona vs Man City to the fixture list. All remaining Man City pot 1 away game are deleted from possible list.

b) check if team only has one possible away game opponent left in pot. Put that match-up on the fixture list. Deleted all same-pot match-ups featuring the same home team from the possible list.

</for each pot>
</for each team>

<loop until possible list is empty>
Last edited by greenbay on Mon Jun 10, 2024 07:57, edited 2 times in total.
"Put it in your signature to save you the trouble of writing it over and over again."
greenbay
Senior Member
Posts: 7428
Joined: Tue Mar 13, 2012 17:01

Post by greenbay »

And on second thought, it should even work the way UEFA will likely do the magic.

Say [FC Barcelona] was just drawn from the "manual draw pot" containing the 36 teams.

Instead of
1. Select a random match-up from the possible list, delete it from the possible list and put it on the fixture list.

Just have it
1. Select a random match-up featuring [FC Barcelona] either home or away from the possible list, delete it from the possible list and put it on the fixture list.

And instead of putting all this in a loop until the possible list is empty, those steps 1 to 7 are repeated in a loop until the possible list contains no [FC Barcelona] match-ups anymore.

Of course, all this goes into a "big loop" until the "manual draw pot" is empty.

EDIT: Another tweak necessary:
In step 7, the "forced" match-up is not put automatically on the fixture list, but remains there until it is properly drawn from the possible list in due course. While the other games are still to be deleted.
"Put it in your signature to save you the trouble of writing it over and over again."
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

All the above solutions are very interesting.
I didn't analyze all of them so I don't know if it has been already discussed.

My main general concerns is:
- exploring all the potential paths is very hard, quite impossible.
- using an "heuristic" method could not ensure to be deadlock-free: I mean that in general a draw may not cause immediately a deadlock, but all the alternative path might go to a deadlock in 2-5-10 steps ahead.
So my question is: how to identify in advance the deadlocks, and how to avoid the "path-to-deadlock" ?
Hope for more partecipants in the next Prediction Game
greenbay
Senior Member
Posts: 7428
Joined: Tue Mar 13, 2012 17:01

Post by greenbay »

That's a very tricky question. Not only you have to check for teams that have only one opponent left from a specific pot, therefore forcing match-ups. You also have to check for two (three, four...) teams having only the same two (three, four...) opponents left, forcing match-ups. At least that's what I came up when doing some code this afternoon based on my thoughts this morning. And even that got my code into a deadlock every now and then. As "max two opponents from each other country" might be in the way to force valid match-ups in case of two (three, four...) teams sharing the same set of valid opponents remaining.
"Put it in your signature to save you the trouble of writing it over and over again."
fabiomh
Senior Member
Posts: 1466
Joined: Thu Sep 24, 2020 20:00
Location: Milan, Italy

Post by fabiomh »

I tried to do some draw simuation by Excel-macro with same "driven" random draw (random with weight depending on the constraints and open choices).
It is not intended as a draw model, but at the moment it is able to generate some predetrmined table.
Furthermore at the moment it does not care about the MDs, home/away, and pairings.

The aborted generations due to deadlock is approx between 10% and 20%;
it was limited to 10%-20% only because country rules are not strict constraints, but only "nice to have"; a lot of times (30-50% ?) at least one team met three clubs from the same country. Otherwise the deadlock cases would be much higher.

I tried the simulation with the teams today included in the CL LS seeded list at https://kassiesa.net/uefa/seedcl2024.html

After approx 50+ iteration, unless there is something wrong in my poor generator, it looks like there are matches with higher probability:

for example (home/away not meaningful): Inter-Stuttgart, PSG-Leverkusen, PSG-Girona, Milan-Brugge, Milan-Shakhtar, Stuttgart-Celtic, Monaco/Brest-Girona, Bologna-Rangers, Bologna-Brugge, Bologna-Shakhtar, Arsenal-Atlético, Milan-Benfica. I am expecting 5-6 out of 13.

About Pot1 v Pot1 matches: each of the 6 (3x2) possible German vs English matches should have probability equal to 34%, so 2 matches are expected.
Hope for more partecipants in the next Prediction Game
amirbachar
Senior Member
Posts: 1747
Joined: Thu Oct 18, 2007 02:22

Post by amirbachar »

fabiomh wrote: Mon Jun 10, 2024 18:16 All the above solutions are very interesting.
I didn't analyze all of them so I don't know if it has been already discussed.

My main general concerns is:
- exploring all the potential paths is very hard, quite impossible.
- using an "heuristic" method could not ensure to be deadlock-free: I mean that in general a draw may not cause immediately a deadlock, but all the alternative path might go to a deadlock in 2-5-10 steps ahead.
So my question is: how to identify in advance the deadlocks, and how to avoid the "path-to-deadlock" ?
That's exactly the Hueristic... You try to simulate for each possible opponent the rest of the draw 1M times or something. If any of them is legal, great, if none of them then you remove this opponent from the possible opponents
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

So after reading the full very interesting thread here and trying it out myself , I came to the conclusion that the draw is more challenging than the previous years , not because of contrains , but mostly because we need not only to draw teams pairings but also ensure fixtures can be generated (home/away, no more than 2 opponents from same country , probably no more than 1 big match per matchday and so on )
There are possible methods to perform the draw by uefa :
1) just like the previous format : draw teams one by one and then draw their opponent taking into account home and away
The problem is , once you have generated the 144 fixtures , how do you compile the calendar ? It can lead to suspicion since it would probably the done offline and in the days following the draw ( and very complicated as well )
2) draw matches instead of pairs . Generate a list of all possible matchups taking into account country restriction , where each matchup is duplicated so Real-city and City-real are two different matchups. There are indeed not so many in the end . So you draw a fixture and you allocate it to matchday. 1 then You deleted matchups which aren’t valid anymore and you continue . This is the easiest to implement in a simulation but how do you randomly draw a matchup from a list ? I doubt Uefa will use this approach
3) pre-generate all fixtures beforehand . Use letters to indicate Pots and numbers for teams . Make sure all constrains are fulfilled . This is easy to do . Then draw one team at the time and assign it to a code , like Real=A1, PSG=A2 and so on . Every time you assign a team you must check how many valid positions ( A1 to A9, B2 to b9 etc ) a team has ensuring there are no deadlocks . Now it becomes similar to previous years where some groups were not possible for some teams . You don’t even need to perform 36 draws since after drawing a few teams then constrains will kick in and some allocations will be forced . This is what I indeed think is going to happen
greenbay
Senior Member
Posts: 7428
Joined: Tue Mar 13, 2012 17:01

Post by greenbay »

While playing around a little with your option 2, I'd say this is off the table. I'm just a hobby coder, not a software engineer, but I wonder if someone will really have an idea how to prevent deadlocks by fail safe code, not just but heuristic try and error.

Option 1 is basically just the same as option 2. You need to prevent deadlocks by code, not just by heuristic try and error.

Therefore option 3. And the longer I think about it, the more attractive this option looks to me. Why not publishing a fixture list before the draw? MD1: A1-A2, B1-C3, D4-A2 and so on. MD2: A2-D3, B2-B1 etc... UEFA can make one up to their liking. Making sure that i.e. C3 play away on MD1 and MD 7, while playing home on MD2 and MD8.

Then we could have an actual draw. Not some computer generated stuff leading to conspiracy theories by the dozen. Pick a ball from the 36 teams, say some time during the draw it's now Bayer Leverkusen's turn, from pot B, formerly known as pot 2. A quick computer check to which spots they can go, like before there was a computer check to which groups they can go, computer says it's B1, B2, B3, B5, B6 and B9. Then place the corresponding balls into a pot, and let an actual person do the draw, grabbing B1 from the pot, so we know that Bayer Leverkusen play C3 on MD1 at home, with C3 earlier been allocated to i.e. AC Milan. While playing B2, not allocated yet, away on MD2.

For sure this will not take 4 hours. It will definitely take far less than a minute per team to just grab some ball. So the whole draw can be done is half an hour or less.
"Put it in your signature to save you the trouble of writing it over and over again."
elkjiaer is back
Posts: 271
Joined: Fri Jul 28, 2017 09:08

Post by elkjiaer is back »

greenbay wrote: Tue Jun 11, 2024 08:51 While playing around a little with your option 2, I'd say this is off the table. I'm just a hobby coder, not a software engineer, but I wonder if someone will really have an idea how to prevent deadlocks by fail safe code, not just but heuristic try and error.

Option 1 is basically just the same as option 2. You need to prevent deadlocks by code, not just by heuristic try and error.

Therefore option 3. And the longer I think about it, the more attractive this option looks to me. Why not publishing a fixture list before the draw? MD1: A1-A2, B1-C3, D4-A2 and so on. MD2: A2-D3, B2-B1 etc... UEFA can make one up to their liking. Making sure that i.e. C3 play away on MD1 and MD 7, while playing home on MD2 and MD8.

Then we could have an actual draw. Not some computer generated stuff leading to conspiracy theories by the dozen. Pick a ball from the 36 teams, say some time during the draw it's now Bayer Leverkusen's turn, from pot B, formerly known as pot 2. A quick computer check to which spots they can go, like before there was a computer check to which groups they can go, computer says it's B1, B2, B3, B5, B6 and B9. Then place the corresponding balls into a pot, and let an actual person do the draw, grabbing B1 from the pot, so we know that Bayer Leverkusen play C3 on MD1 at home, with C3 earlier been allocated to i.e. AC Milan. While playing B2, not allocated yet, away on MD2.

For sure this will not take 4 hours. It will definitely take far less than a minute per team to just grab some ball. So the whole draw can be done is half an hour or less.
I am glad you like my idea and actually surprised havent´seen it mentioned anywhere so far. But this is the only realistic way to perform the draw, limiting the number of constrains to be checked and still keeping the excitment for the audience (i mean scenario 3 of course)
They could just show on a screen the 8 matchdays and every time a team is set to specific slot (A1, C3, D9 ETC) then it is highlited so it is easy to see all its opponents in the 8 matchdays
FEPG
Senior Member
Posts: 2409
Joined: Wed Jun 10, 2009 22:41
Location: England

Post by FEPG »

elkjiaer is back wrote: Tue Jun 11, 2024 08:341) ... The problem is , once you have generated the 144 fixtures , how do you compile the calendar ?
The calendar is just another constraint: a team can have no more than one game per matchday. Skip the team if it has already been drawn during the current matchday.
elkjiaer is back wrote: Tue Jun 11, 2024 08:342) ... This is the easiest to implement in a simulation but how do you randomly draw a matchup from a list ? I doubt Uefa will use this approach
Just pick 8 random matches (or fewer if some have already been drawn for the selected team) involving the selected team satisfying the constraints.
elkjiaer is back wrote: Tue Jun 11, 2024 08:343) pre-generate all fixtures beforehand . Use letters to indicate Pots and numbers for teams . Make sure all constrains are fulfilled . This is easy to do . Then draw one team at the time and assign it to a code , like Real=A1, PSG=A2 and so on . Every time you assign a team you must check how many valid positions ( A1 to A9, B2 to b9 etc ) a team has ensuring there are no deadlocks . Now it becomes similar to previous years where some groups were not possible for some teams . You don’t even need to perform 36 draws since after drawing a few teams then constrains will kick in and some allocations will be forced . This is what I indeed think is going to happen
This is simply reducing the branching factor of the search tree by removing some possible matchups & arbitrarily adjusting the probability matrix. If that's the best UEFA can do, then clearly it's not the engineers that are getting the corruption money.
Sagy
Posts: 882
Joined: Sun Dec 19, 2021 01:27
Location: Austin, TX, USA
Contact:

Post by Sagy »

My view all along, not saying it’s the best option, is that UEFA will use @elkjiaer is back option 3.
Post Reply