Sorteio dos 1/4, 1/2 e Final da Liga dos Campeões (Inter - Milan/Napoli)

[Hungry Alien]

Como estava com algum tempo livre, pus-me a fazer um script em python para simular o serteio dos oitavos de final da Champions, levando em atenção todas as condicionantes. Depois usei esse script para fazer 5 milhões de simulações.

Esta tabela indica a frequência absoluta com que cada confronto surgiu na simulação:



e esta tabela mostra a mesma infomação mas em percentagem:



O resultado mais frequente, mas com apenas 1615 ocorrências em 5 milhões, foi:

Bayern - Brugges
Benfica - Leipzig
Chelsea - Inter
FCP - Liverpool
Man City - Frankfurt
Napoli - Paris SG
Real Madrid - Dortmund
Tottenham - Milan

Em spoiler estão histogramas com a as frequências relativas para cada uma das 16 equipas.

Spoiler

[fechar]

Exercicio giro de se fazer. E confirma as tabelas de probabilidades que já tinha visto por aí

Diria que isto se pode calcular recorrendo a arranjos e/ou combinações para calcular o total de possibilidades, e o número de eventos em que pode ocorrer cada um dos encontros, calculando depois a probabilidade. Mas já lá vão mais de 15 anos desde que dei isso...

é mesmo isso. foi assim que essa tabela em cima foi calculada.

Assim por alto, consegue dizer-me como chegar a esses valores? Só um... Obrigado.

Confesso que é um conceito confuso.

Digamos assim, imagina que sai a bola do porto primeiro. Nessa situação podem calhar 7 clubes aos gajos e as probabilidades de calhar qualquer um desses são 1/7.

Contudo pode não ser o porto a calhar primeiro no sorteio. Pode ser segundo, ou terceiro, etc. E cada clube que calhar antes deles, com as suas próprias condicionantes, altera a probabilidade de certo adversário ainda lá estar quando sair o porto.

Estas probabilidades contam com isso tudo junto. Mas certamente há aqui alguém mais esperto que possa explicar melhor.

E se quiseres ver o código que gera estas probabilidades até podes ir a esta pagina que lá em baixo tem um link para o código no Git.

https://eminga.github.io/cldraw/

Já agora que estamos a partilhar código, podem dar uma vista de olhos no meu se quiserem.

import random
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
from tqdm import tqdm

n_iter = 5*10**6

class Team():
    def __init__(self, name, country, group, position, choices):
        self.name = name
        self.country = country
        self.group = group
        self.position = position
        self.choices = choices

    def __str__(self) -> str:
        return f"{self.name}({self.country})"

Napoli = Team('Napoli', 'Italy', 'A', 1, [])
Liverpool = Team('Liverpool', 'England', 'A', 2, [])
Porto = Team('FCP', 'Portugal', 'B', 1, [])
Brugges = Team('Brugges', 'Belgium', 'B', 2, [])
Bayern = Team('Bayern', 'Germany', 'C', 1, [])
Inter = Team('Inter', 'Italy', 'C', 2, [])
Tottenham = Team('Tottenham', 'England', 'D', 1, [])
Frankfurt = Team('Frankfurt', 'Germany', 'D', 2, [])
Chelsea = Team('Chelsea', 'England', 'E', 1, [])
Milan = Team('Milan', 'Italy', 'E', 2, [])
Real_Madrid = Team('Real Madrid', 'Spain', 'F', 1, [])
Leipzig = Team('Leipzig', 'Germany', 'F', 2, [])
Man_City = Team('Man City', 'England', 'G', 1, [])
Dortmund = Team('Dortmund', 'Germany', 'G', 2, [])
Benfica = Team('Benfica', 'Portugal', 'H', 1, [])
Paris_SG = Team('Paris SG', 'France', 'H', 2, [])

Teams = [Napoli, Liverpool, Porto, Brugges, Bayern, Inter, Tottenham,
        Frankfurt, Chelsea, Milan, Real_Madrid, Leipzig, Man_City,
        Dortmund, Benfica, Paris_SG]

def get_choices(Teams):
    for team in Teams:
        team.choices = [other for other in Teams if
                        other.country != team.country
                        and other.group != team.group
                        and other.position != team.position]

order = [1, 2]
index = [team.name for team in Teams if team.position == order[0]]
columns = [team.name for team in Teams if team.position == order[1]]
frequencies = pd.DataFrame(0, index=index, columns=columns, dtype=int)
percentage = pd.DataFrame(0, index=index, columns=columns, dtype=float)
Draws = {}

def simulate_draw():
    Teams = [Napoli, Liverpool, Porto, Brugges, Bayern, Inter, Tottenham,
            Frankfurt, Chelsea, Milan, Real_Madrid, Leipzig, Man_City,
            Dortmund, Benfica, Paris_SG]

    Pot1 = [team for team in Teams if team.position == order[0]]
    Pot2 = [team for team in Teams if team.position == order[1]]
    draw = []

    for n in range(7):
        get_choices(Teams)
        single_choice = [team for team in Teams if len(team.choices) == 1]

        while len(single_choice) > 0:
            for team in Pot1:
                if len(team.choices) == 1:
                    frequencies[team.choices[0].name][team.name] += 1
                    draw.append(f"{team.name} - {team.choices[0].name}")
                    Teams.remove(team)
                    Teams.remove(team.choices[0])
                    Pot1.remove(team)
                    Pot2.remove(team.choices[0])
                    get_choices(Teams)
                    single_choice = [team for team in Teams if len(team.choices) == 1]

            for team in Pot2:
                if len(team.choices) == 1:
                    frequencies[team.name][team.choices[0].name] += 1
                    draw.append(f"{team.choices[0].name} - {team.name}")
                    Teams.remove(team)
                    Teams.remove(team.choices[0])
                    Pot1.remove(team.choices[0])
                    Pot2.remove(team)
                    get_choices(Teams)
                    single_choice = [team for team in Teams if len(team.choices) == 1]
   
        if len(Pot1) > 0:
            equal_choice = []
            for team1 in Teams:
                for team2 in Teams:
                    if team1 != team2 and team1.choices == team2.choices and len(team1.choices) == 2:
                        equal_choice.append([team1, team2])
           
            if len(equal_choice) > 0:
                ball_1 = random.choice(random.choice(equal_choice))
            else:
                ball_1 = random.choice(Pot1)           
            ball_2 = random.choice(ball_1.choices)
            if ball_1.position == order[1]:
                ball_1, ball_2 = ball_2, ball_1

            Teams.remove(ball_1)
            Teams.remove(ball_2)
            Pot1.remove(ball_1)
            Pot2.remove(ball_2)
            frequencies[ball_2.name][ball_1.name] += 1
            draw.append(f"{ball_1.name} - {ball_2.name}")

    if len(Pot1) > 0:
        frequencies[Pot2[0].name][Pot1[0].name] += 1
        draw.append(f"{Pot1[0].name} - {Pot2[0].name}")

    if tuple(sorted(draw)) in Draws:
        Draws[tuple(sorted(draw))] += 1
    else:
        Draws[tuple(sorted(draw))] = 1

def monte_carlo(iterations):
    for n in tqdm(range(iterations)):
        simulate_draw()
    print(frequencies)
 
def make_plots():
    Teams = [Napoli, Liverpool, Porto, Brugges, Bayern, Inter, Tottenham,
            Frankfurt, Chelsea, Milan, Real_Madrid, Leipzig, Man_City,
            Dortmund, Benfica, Paris_SG]
    Pot1 = [team for team in Teams if team.position == order[0]]
    Pot2 = [team for team in Teams if team.position == order[1]]
    get_choices(Teams)

    for Team in Pot1:
        X = [team.name for team in Team.choices]
        Y = [percentage.loc[Team.name][team.name] for team in Team.choices]
        fig = plt.figure(figsize=(8,6))
        plt.bar(X, Y, width=0.8, edgecolor="white", linewidth=0.7, color=np.random.rand(3,))
        plt.title(Team.name)
        plt.savefig(f"{Team.name}.png")
        plt.show()

    for Team in Pot2:
        X = [team.name for team in Team.choices]
        Y = [percentage[Team.name][team.name] for team in Team.choices]
        fig = plt.figure(figsize=(8,6))
        plt.bar(X, Y, width=0.8, edgecolor="white", linewidth=0.7, color=np.random.rand(3,))
        plt.title(Team.name)
        plt.savefig(f"{Team.name}.png")
        plt.show()

monte_carlo(n_iter)

percentage = frequencies.mul(100/n_iter).round(2)
most_common_draw = max(Draws, key=Draws.get)
least_common_draw = min(Draws, key=Draws.get)

print(f"Most common Draw is {most_common_draw} with frequency {Draws[most_common_draw]}")
print(f"Least common Draw is {least_common_draw} with frequency {Draws[least_common_draw]}")
print(f"Total number of distinct draws is {len(Draws)}")

make_plots()
# frequencies.to_excel('UCL draw.xls')
# percentage.to_excel('UCL draw percentage.xls')

[Dr. Captainous]

Mas por que raios é que este sorteio não é na 6a Feira como o habitual?!

Não vou poder ver!

[Dr. Captainous]

seria um grande balde de água fria levar com o Liverpool...

de resto venha qualquer equipa.

Sim, seria um grande balde de água fria para o Liverpool.

[lPhoenix]

Neste momento estão todos a não querer apanhar o Benfica . O Benfica nesta época é das melhores equipas da europa ...

Eu nesta fase também não queria apanhar nenhum desses. O ideal seria chegar às meias com equipas perfeitamente ao alcance, para ir mantendo o hype até à final, a UEFA ir delirando com as audiências e com as chapadas de luva branca na Superliga, os árbitros em sentido sem "medo" de tomar decisões impopulares, todos a seguir a equipa sensação e na final apanhar o Real Madrid, fazendo ver a Florentino que o Benfica talvez não fosse o adversário mais fácil para apanhar num sorteio...........................

Ahhh não custa sonhar.

[Crente]

Como estava com algum tempo livre, pus-me a fazer um script em python para simular o serteio dos oitavos de final da Champions, levando em atenção todas as condicionantes. Depois usei esse script para fazer 5 milhões de simulações.

Esta tabela indica a frequência absoluta com que cada confronto surgiu na simulação:



e esta tabela mostra a mesma infomação mas em percentagem:



O resultado mais frequente, mas com apenas 1615 ocorrências em 5 milhões, foi:

Bayern - Brugges
Benfica - Leipzig
Chelsea - Inter
FCP - Liverpool
Man City - Frankfurt
Napoli - Paris SG
Real Madrid - Dortmund
Tottenham - Milan

Em spoiler estão histogramas com a as frequências relativas para cada uma das 16 equipas.

Spoiler

[fechar]

Exercicio giro de se fazer. E confirma as tabelas de probabilidades que já tinha visto por aí

Diria que isto se pode calcular recorrendo a arranjos e/ou combinações para calcular o total de possibilidades, e o número de eventos em que pode ocorrer cada um dos encontros, calculando depois a probabilidade. Mas já lá vão mais de 15 anos desde que dei isso...

é mesmo isso. foi assim que essa tabela em cima foi calculada.

Assim por alto, consegue dizer-me como chegar a esses valores? Só um... Obrigado.

Confesso que é um conceito confuso.

Digamos assim, imagina que sai a bola do porto primeiro. Nessa situação podem calhar 7 clubes aos gajos e as probabilidades de calhar qualquer um desses são 1/7.

Contudo pode não ser o porto a calhar primeiro no sorteio. Pode ser segundo, ou terceiro, etc. E cada clube que calhar antes deles, com as suas próprias condicionantes, altera a probabilidade de certo adversário ainda lá estar quando sair o porto.

Estas probabilidades contam com isso tudo junto. Mas certamente há aqui alguém mais esperto que possa explicar melhor.

E se quiseres ver o código que gera estas probabilidades até podes ir a esta pagina que lá em baixo tem um link para o código no Git.

https://eminga.github.io/cldraw/

Obrigado. Também já tinha percebido essa primeira parte. Agora, a matemática parece-me ser mais complexa. Li algo sobre polinómios de torre (de xadrez), que são usados em problemas de tabuleiro de xadrez.
No entanto, apesar da minha formação em Matemática, nunca estudei este tema em particular e embora me pareça interessante, acho que vou ficar pela ignorância... 😁
A parte da programação também me parece interessante.

[Notguilty]

Quem vier morre 

[mm_slb]

 

Como estava com algum tempo livre, pus-me a fazer um script em python para simular o serteio dos oitavos de final da Champions, levando em atenção todas as condicionantes. Depois usei esse script para fazer 5 milhões de simulações.

Esta tabela indica a frequência absoluta com que cada confronto surgiu na simulação:



e esta tabela mostra a mesma infomação mas em percentagem:



O resultado mais frequente, mas com apenas 1615 ocorrências em 5 milhões, foi:

Bayern - Brugges
Benfica - Leipzig
Chelsea - Inter
FCP - Liverpool
Man City - Frankfurt
Napoli - Paris SG
Real Madrid - Dortmund
Tottenham - Milan

Em spoiler estão histogramas com a as frequências relativas para cada uma das 16 equipas.

Spoiler

[fechar]

Por curiosidade que metodo usas para gerar os dados aleatorios?
Isto porque a distribuição para o Benfica nao e linear, o Liverpool aparece com 20% vs 13% do resto. (a nao ser que existe ai algum factor extra)

O que sucede é que o Liverpool apenas pode jogar com uma de quatro equipas: Benfica, Bayern, Real e Porcos. É essa a razão de o Liverpool ter uma maior probabilidade de calhar com o Benfica. Mas como o Bayern por seu lado também apenas pode jogar com Liverpool, Brugge, Milan ou PSG, a probabilidade de termos um Bayern - Liverpool dispara para cerca de 37%.

O método usado para gerar os dados aleatórios é simplesmente a função random.choice(), que aplica uma distribuiçáo uniforme a uma lista, mas existem muitas linhas de código para garantir que a lista contêm apenas as equipas corretas dadas as condicionantes do sorteio.

É isto mesmo. Costumamos pensar que de entre as equipas que podem jogar contra nós, a probabilidade de apanhar qualquer uma delas seria igual, mas as condicionantes mudam tudo. Azar terem ficado tantas equipas inglesas em 1o e apenas o Liverpool em 2o.

[gizmo]

Como estava com algum tempo livre, pus-me a fazer um script em python para simular o serteio dos oitavos de final da Champions, levando em atenção todas as condicionantes. Depois usei esse script para fazer 5 milhões de simulações.

Esta tabela indica a frequência absoluta com que cada confronto surgiu na simulação:



e esta tabela mostra a mesma infomação mas em percentagem:



O resultado mais frequente, mas com apenas 1615 ocorrências em 5 milhões, foi:

Bayern - Brugges
Benfica - Leipzig
Chelsea - Inter
FCP - Liverpool
Man City - Frankfurt
Napoli - Paris SG
Real Madrid - Dortmund
Tottenham - Milan

Em spoiler estão histogramas com a as frequências relativas para cada uma das 16 equipas.

Spoiler

[fechar]

Caro Hungry Alien, bom trabalho. Mas não há cá scripts nem nada que se aproxime do que a história e realidade nos diz. É que vai calhar a mais fdda ao Benfica e a mais merdosa ao fóculporto. É sempre assim. Só não calha o Bruges novamente aos porcos, porque não podem.

[nfgl]

os primeiros do grupo jogam o segundo jogo em casa

Muito bom.

É as equipas portuguesas ficarem em primeiro outra vez e estas regrinhas mudam todas

Por acaso há vantagem em ter o segundo jogo em casa

[Petrov_Carmovich]

Mas por que raios é que este sorteio não é na 6a Feira como o habitual?!

Não vou poder ver!

Bolas quentes, bolas frias. E evitar a cagada em dois actos da época passada.

[Petrov_Carmovich]

Neste momento estão todos a não querer apanhar o Benfica . O Benfica nesta época é das melhores equipas da europa ...

Eu nesta fase também não queria apanhar nenhum desses. O ideal seria chegar às meias com equipas perfeitamente ao alcance, para ir mantendo o hype até à final, a UEFA ir delirando com as audiências e com as chapadas de luva branca na Superliga, os árbitros em sentido sem "medo" de tomar decisões impopulares, todos a seguir a equipa sensação e na final apanhar o Real Madrid, fazendo ver a Florentino que o Benfica talvez não fosse o adversário mais fácil para apanhar num sorteio...........................

Ahhh não custa sonhar.

Tive um ex-supervisor meu no meu antigo emprego que me disse uma vez há coisa de 6 anos atrás.

"Se o Benfica voltar a ganhar uma Champions vai ser outra vez numa final contra o Real ou o Barça."

Vou ser sincero, não sei se alguma vez verei o Benfica vencedor da Champions League(sem ser por imagens de arquivo), e se vai ser este ano...mas acho que quando acontecer vai ser como nos anos 1960. Um vendaval de bom futebol. Se for contra uma equipa grande espanhola melhor.

[EagleVision]

Depois de lançado o desafio pelo Hungry Alien, deixo aqui também as probabilidades para a solução exacta, juntamente com o código (talvez não tão elegante, mas corre em menos de um segundo ). Espero não me ter escapado nada!

import numpy as np
import pandas as pd
pd.options.display.float_format = "{:,.2f}".format

seeded = {0: "Bayern", 1: "Benfica", 2: "Chelsea", 3: "FCP", 4: "ManCity", 5: "Napoli", 6: "RealMadrid", 7: "Tottenham"}
unseeded = {0: "Brugge", 1: "Dortmund", 2: "Frankfurt", 3: "Inter", 4: "Leipzig", 5: "Liverpool", 6: "Milan", 7: "Paris"}

l = [[0,5,6,7], # Bayern
     [0,1,2,3,4,5,6], # Benfica
     [0,1,2,3,4,7], # Chelsea
     [1,2,3,4,5,6,7], # FCP
     [0,2,3,4,6,7], # ManCity
     [0,1,2,4,7], # Napoli
     [0,1,2,3,5,6,7], # RealMadrid
     [0,1,3,4,6,7]] # Tottenham

total = 0
keys = np.empty((8,0), dtype=np.int8)
for k0 in l[0]:
    for k1 in l[1]:
        for k2 in l[2]:
            for k3 in l[3]:
                for k4 in l[4]:
                    for k5 in l[5]:
                        for k6 in l[6]:
                            for k7 in l[7]:
                                key = [k0, k1, k2, k3, k4, k5, k6, k7]
                                if(len(key) == len(set(key))):
                                    # Only keys where all elements are different
                                    total += 1
                                    keys = np.append(keys, [[k0],[k1],[k2],[k3],[k4],[k5],[k6],[k7]], axis=1)
print(total)

probs = np.zeros([8,8], dtype=np.float32)
for i in range(8):
    team_keys = np.unique(keys[:][i])
    for j in team_keys:
        # Count the number of occurences of each key and convert to percentage
        probs[i][j] = np.sum(keys[:][i] == j) / total * 100

df = pd.DataFrame(probs)
display(df.rename(index=seeded, columns=unseeded))

** NOTA (EDIT) **: Jogo mais provável no sorteio será mesmo um Bayern x Liverpool (P~40%), enquanto que os possíveis adversários do Benfica são, muito grosseiramente falando, equiprováveis (P=[11,20]%).

[Hungry Alien]

Depois de lançado o desafio pelo Hungry Alien, deixo aqui também as probabilidades para a solução exacta, juntamente com o código (talvez não tão elegante, mas corre em menos de um segundo ). Espero não me ter escapado nada!

import numpy as np
import pandas as pd
pd.options.display.float_format = "{:,.2f}".format

seeded = {0: "Bayern", 1: "Benfica", 2: "Chelsea", 3: "FCP", 4: "ManCity", 5: "Napoli", 6: "RealMadrid", 7: "Tottenham"}
unseeded = {0: "Brugge", 1: "Dortmund", 2: "Frankfurt", 3: "Inter", 4: "Leipzig", 5: "Liverpool", 6: "Milan", 7: "Paris"}

l = [[0,5,6,7], # Bayern
     [0,1,2,3,4,5,6], # Benfica
     [0,1,2,3,4,7], # Chelsea
     [1,2,3,4,5,6,7], # FCP
     [0,2,3,4,6,7], # ManCity
     [0,1,2,4,7], # Napoli
     [0,1,2,3,5,6,7], # RealMadrid
     [0,1,3,4,6,7]] # Tottenham

total = 0
keys = np.empty((8,0), dtype=np.int8)
for k0 in l[0]:
    for k1 in l[1]:
        for k2 in l[2]:
            for k3 in l[3]:
                for k4 in l[4]:
                    for k5 in l[5]:
                        for k6 in l[6]:
                            for k7 in l[7]:
                                key = [k0, k1, k2, k3, k4, k5, k6, k7]
                                if(len(key) == len(set(key))):
                                    # Only keys where all elements are different
                                    total += 1
                                    keys = np.append(keys, [[k0],[k1],[k2],[k3],[k4],[k5],[k6],[k7]], axis=1)
print(total)

probs = np.zeros([8,8], dtype=np.float32)
for i in range(8):
    team_keys = np.unique(keys[:][i])
    for j in team_keys:
        # Count the number of occurences of each key and convert to percentage
        probs[i][j] = np.sum(keys[:][i] == j) / total * 100

df = pd.DataFrame(probs)
display(df.rename(index=seeded, columns=unseeded))

** NOTA (EDIT) **: Jogo mais provável no sorteio será mesmo um Bayern x Liverpool (P~40%), enquanto que os possíveis adversários do Benfica são, muito grosseiramente falando, equiprováveis (P=[11,20]%).

Interessante. Uma boa forma de obter rapidamente uma boa aproximação das probabilidades, mas se reparares não são iguais às que alguem partilhou atrás,

https://github.com/eminga/cldraw

Esses valores são muito mais próximos dos meus que os teus. Por exemplo, para um Liverpool - Bayern tu tens 39,86%, eu tenho 36,95% e eles têm 37,12%.

E o código deles tem uma performance que depende muito das especificidades do sorteio, tanto pode demorar 1 décimo de segundo com pode demorar quase hora e meia, e usar mais de 5 GB de RAM. O meu método usa apenas cerca de 115 MB de RAM, e penso que não variará muito com as especificidadades de cada sorteio.

The memoization technique described above works better the more similar the teams are (e.g. the algorithm is faster if there are 2 runners-up and 2 winners from country A and 2 runners-up and 2 winners from country B, compared to 1 runner-up and 3 winners from country A and 2 runners-up and 1 winner from country B).

Tests with a Pentium G4600 using Node.js 10.13.0 yield computation times of 110ms for the CL draw 2017/18 and 2:02 minutes (310MB RAM usage) for the EL draw 2017/18. However, there are cases where the computation is much more expensive, like EL season 2014/15 where it takes 88 minutes and 5.3GB of RAM.

To bypass the long computation times, precomputed probabilities can be used in EL mode. With a gzipped filesize of 5MB all possible combinations of the first 4 or 6 draw steps can be stored. The probabilities for the remaining 26/28 teams are then computed locally which usually takes a couple of seconds / up to 1 minute.

Repara também que o meu código não está optimizado, foi feito entre ontem e hoje, e a minha única preocupação era que funcionasse. Pode talvez ser modificado para usar todos os cores do processador em vez de apenas 1.

[sbremoved_42475]

Agora todo o mundo programa em Python?

[B_B]

Agora todo o mundo programa em Python?

Não é assim tao mau como o Python