A Genetic Algorithm to Generate the FIFA World Cup Group Draw

Content

• The FIFA World Cup 2026 Group Draw
  • Feasible Solution
  • Possible Combinations
  • Draw Constraints
• What is a Genetic Algorithm?
  • Basic Genetic Algorithm
• Initial Population
  • Individual Structure
• Fitness Function
• Genetic Algorithm Lifecycle
• Genetic Operators
  • Selection
  • Crossover
  • Mutation
  • Replacement
• Termination Criterion
• Results

The FIFA World Cup 2026 Group Draw

Fig: 1. Knockout round itinerary according to FIFA. This configuration enforces the restriction that Spain and Argentina, or France and England, cannot face each other before the final, affecting their group assignment in the draw.

Feasible Solution

Possible Combinations

Fig: 2. Order of teams in the pots. Host teams do not participate in the draw as their respective groups are pre-assigned.

• Pot 1: $9!$,
• Pots 2, 3, and 4: $12!$
• Total: $9! \times 12! \times 12! \times12! = 3.9881 \times 10^{31}$ possible combinations.

Just how big is this number? 39, 881, 724, 135, 495, 319, 399, 956, 480, 000, 000 possible ways to organize teams into groups. Ignoring constraints.

To get an idea of the magnitude: if we could evaluate every draw generated by a brute-force algorithm in 0.05 seconds, evaluating all possible solutions would take $6.3 \times 10^{22}$ years. If the algorithm had started at the Big Bang, it wouldn't have finished yet; in fact, it would only be 0.00000000002% of the way through.

Draw Constraints

• Hosts: Mexico will be assigned position A1, Canada position B1, and the United States position D1.
• Pot 1: The other nine teams in Pot 1 will be identified by nine balls of the same color and automatically assigned to position 1 of the group into which they are drawn.
• Uniform Distribution: Each group must have one team from each pot.
• Confederations per Group: No group can have more than one team from the same confederation, except for UEFA, which can have up to two teams in the same group.
• Top 4 Ranking: Finally, Spain and Argentina on one side, and France and England on the other, cannot face each other until the final, as they are the top four in the FIFA Men's Ranking at the time ^[2]. This restricts their placement into arbitrary groups.

Fig: 3. Distribution of brackets or team itineraries. Teams from one bracket that qualify for the next round will compete against teams from the other bracket. Spain vs Argentina and England vs France cannot meet until the World Cup final. This assumes each qualifies first in their respective groups.

What is a Genetic Algorithm?

Basic Genetic Algorithm

• Population Size: How many individuals (candidate solutions) will make up the population in each generation.
• Number of Generations: How many times the algorithm's lifecycle will repeat.
• Crossover Probability: Set at 80%, as this value is usually effective for exploring the search space.
• Mutation Probability: Set at 20%, as this value effectively maintains genetic diversity without altering existing solutions too much.

python
1POBLACION_TAM = 10 # Population size
2GENERACIONES = 1000 # Number of generations
3PROB_CROSSOVER = 0.8  # 80% crossover probability
4PROB_MUTACION = 0.2  # 20% mutation probability

Initial Population

We must find a way to represent it in the algorithm and create it (encoding).

python
1def crear_individuo(lista_equipos):
2    # Create an initial valid individual (draw)
3    bombos = {1: [], 2: [], 3: [], 4: []}
4    # Distribute teams by pot
5    for eq in lista_equipos:
6        bombos[eq.bombo].append(eq)
7    # Assign teams to groups
8    grupos = [[] for _ in range(12)]
9    for b in range(1, 5):
10        equipos = bombos[b]
11        # Shuffle for randomness
12        random.shuffle(equipos)
13        pendientes = []
14        for eq in equipos:
15            if eq.grupo_fijo:
16                # Assign to fixed group and skip (converts group letter to index)
17                idx = ord(eq.grupo_fijo) - 65
18                grupos[idx].append(eq)
19            else:
20                pendientes.append(eq)
21        idx_p = 0
22        # Assign remaining teams from this pot
23        for g_idx in range(12):
24            if len(grupos[g_idx]) < b:
25                grupos[g_idx].append(pendientes[idx_p])
26                idx_p += 1
27    return grupos

Individual Structure

Fig: 4. Representation of an individual as a complete draw of 12 groups and 48 teams. It can be seen that this individual does not meet some restrictions, for example, Group H has both Qatar and Jordan. These two teams belong to the same confederation and are not allowed to share a group.

python
1class Equipo:
2    def __init__():
3        self.nombre = nombre
4        self.confederacion = confederacion  # Simple String
5        self.bombo = bombo
6        self.grupo_fijo = grupo_fijo
7        self.ranking_top = ranking_top  # 1, 2, 3, 4 or None
8
9    def __repr__(self):
10        # Shows useful info when printing
11        r =  if self.ranking_top else ""
12        f =  if self.grupo_fijo else ""
13        return

python
1Equipo("Spain", ["UEFA"], bombo=1, ranking_top=1)
2Equipo("Argentina", ["CONMEBOL"], bombo=1, ranking_top=2)

python
1Equipo("Mexico", ["CONCACAF"], bombo=1, grupo_fijo="A")
2Equipo("Canada", ["CONCACAF"], bombo=1, grupo_fijo="B")

python
1Equipo("Germany", ["UEFA"], bombo=1)
2Equipo("Ecuador", ["CONMEBOL"], bombo=2)
3Equipo("Panama", ["CONCACAF"], bombo=3)
4# And so on until the rest are complete...

Fitness Function

Fig: 5. Evaluation of two individuals. Individual A has a fitness of 900 because it violates the confederation repetition rule in groups C, D, and E. Additionally, it fails to separate the itineraries of Spain and Argentina.

• Confederations: No group can have more than one team from the same confederation (except Europe, which allows two).

python
1for j in range(len(grupo)):
2            for k in range(j + 1, len(grupo)):
3                equipo_a = grupo[j]
4                equipo_b = grupo[k]
5
6                # Set intersection:
7                set_a = set(equipo_a.confederacion)
8                set_b = set(equipo_b.confederacion)
9                interseccion = set_a.intersection(set_b)
10
11                # If there is intersection and it is NOT UEFA (because UEFA allows 2), we penalize
12                conflicto_real = [c for c in interseccion if c != "UEFA"]
13
14                if conflicto_real:
15                    penalizacion += PENALTY_CONF_LIMIT

• Itineraries: The Top 4 seeded teams must be distributed in opposite brackets so they do not meet before the semifinals. If Top 1 and Top 2 land on the same side of the bracket, we apply a massive penalty (+500).

python
1# We create a dictionary to know where the Top 4 are
2  ubicacion_tops = {}
3    # For each group we get that location:
4    for equipo in grupo:
5            if equipo.ranking_top:
6                ubicacion_tops[equipo.ranking_top] = i
7
8    # Rule: Top 1 and Top 2 must go on opposite sides of the itinerary
9    if 1 in ubicacion_tops and 2 in ubicacion_tops:
10        it_1 = obtener_itinerario(ubicacion_tops[1])
11        it_2 = obtener_itinerario(ubicacion_tops[2])
12    # Penalize if they are on the same side of the bracket
13    if it_1 == it_2:
14        penalizacion += PENALTY_ITINERARY

python
1def calcular_fitness(sorteo):
2    """
3    Calculates total penalty of a draw (chromosome).
4    0 = Valid draw.
5    return: penalty
6    """
7    penalizacion = 0
8
9    # Penalty Constants (Weights)
10    PENALTY_CONF_LIMIT = 1000  # Confederation conflict (Severe)
11    PENALTY_UEFA_LIMIT = 500  # More than 2 Europeans
12    PENALTY_ITINERARY = 500  # Top seeds clashing before final
13
14    # Track where Top seeds landed {ranking: group_index}
15    ubicacion_tops = {}
16
17    # --- 1. Loop through Groups ---
18    for i, grupo in enumerate(sorteo):
19
20        # A. Check UEFA limit (Max 2)
21        # Count how many teams have 'UEFA' in their confederation list
22        uefa_count = sum(1 for equipo in grupo if ["UEFA"] in equipo.confederacion)
23
24        if uefa_count > 2:
25            # Penalize to correct it
26            penalizacion += PENALTY_UEFA_LIMIT * (uefa_count - 2)
27
28        # B. Check Confederation clashes (NON-UEFA)
29        # Use double for loop to compare everyone against everyone in the group
30        for j in range(len(grupo)):
31            for k in range(j + 1, len(grupo)):
32                equipo_a = grupo[j]
33                equipo_b = grupo[k]
34
35                # Set intersection:
36                # If Team A is ['CONMEBOL'] and Team B (Playoff) is ['CONMEBOL', 'AFC']
37                # The intersection is {'CONMEBOL'} -> Conflict!
38                set_a = set(equipo_a.confederacion)
39                set_b = set(equipo_b.confederacion)
40                interseccion = set_a.intersection(set_b)
41
42                # If there is intersection and it is NOT UEFA (because UEFA allows 2), we penalize
43                # Note: If both are UEFA, 'UEFA' will be in the intersection,
44                # but we already controlled that above with uefa_count.
45                conflicto_real = [c for c in interseccion if c != "UEFA"]
46
47                if conflicto_real:
48                    penalizacion += PENALTY_CONF_LIMIT
49
50        # C. Save location of Tops for phase 2
51        for equipo in grupo:
52            if equipo.ranking_top:
53                ubicacion_tops[equipo.ranking_top] = i
54
55    # --- 2. Itinerary Penalties (Bracket) ---
56
57    # Rule: Top 1 and Top 2 must go on opposite sides of the itinerary
58    if 1 in ubicacion_tops and 2 in ubicacion_tops:
59        it_1 = obtener_itinerario(ubicacion_tops[1])
60        it_2 = obtener_itinerario(ubicacion_tops[2])
61
62        if it_1 == it_2:
63            penalizacion += PENALTY_ITINERARY
64
65    # Rule: Top 3 and Top 4 must go on opposite sides of the itinerary
66    if 3 in ubicacion_tops and 4 in ubicacion_tops:
67        it_3 = obtener_itinerario(ubicacion_tops[3])
68        it_4 = obtener_itinerario(ubicacion_tops[4])
69
70        if it_3 == it_4:
71            penalizacion += PENALTY_ITINERARY
72
73    return penalizacion

Genetic Algorithm Lifecycle

python
1def ejecutar_ga_completo():
2    # --- CONFIGURATION ---
3    POBLACION_TAM = 10
4    GENERACIONES = 1000
5    PROB_CROSSOVER = 0.8  # 80% crossover probability
6    PROB_MUTACION = 0.2  # 20% mutation probability
7    K_TORNEO = 2  # Tournament size for selection
8
9    datos = generar_datos_usuario()
10    poblacion = [crear_individuo(datos) for _ in range(POBLACION_TAM)]
11
12    print()
13
14    for gen in range(GENERACIONES):
15        # Evaluate Fitness
16        # Save (score, individual)
17        evaluados = [(calcular_fitness(ind), ind) for ind in poblacion]
18        evaluados.sort(key=lambda x: x[0])
19
20        best_score = evaluados[0][0]
21        # Monitoring
22        if gen % 100 == 0 or best_score == 0:
23            print()
24
25        if best_score == 0:
26            print()
27            return evaluados[0][1]
28
29        # Selection (Simple Tournament)
30        nueva_poblacion = []
31
32        while len(nueva_poblacion) < POBLACION_TAM:
33            
34            # OPTION A: TOURNAMENT
35            # padre1 = seleccion_torneo(evaluados, k=K_TORNEO)
36            # padre2 = seleccion_torneo(evaluados, k=K_TORNEO)
37
38            # OPTION B: ROULETTE
39            padre1 = seleccion_ruleta(evaluados)
40            padre2 = seleccion_ruleta(evaluados)
41
42            # Crossover subject to probability (0.8)
43            if random.random() < PROB_CROSSOVER:
44                hijo1, hijo2 = cruzar(padre1, padre2)
45            else:
46                hijo1, hijo2 = copy.deepcopy(padre1), copy.deepcopy(padre2)
47            # Mutation subject to probability (0.2)
48            hijo1 = mutar(hijo1, PROB_MUTACION)
49            hijo2 = mutar(hijo2, PROB_MUTACION)
50
51            nueva_poblacion.append(hijo1)
52            if len(nueva_poblacion) < POBLACION_TAM:
53                nueva_poblacion.append(hijo2)
54        poblacion = nueva_poblacion
55
56    print("⚠️ Limit reached. Returning best approximation.")
57    return evaluados[0][1]

Genetic Operators

Selection

python
1def seleccion_ruleta(evaluados):
2    """
3    Input: List of tuples (fitness, individual)
4    Selection proportional to fitness (Roulette).
5    Since we seek to MINIMIZE cost, we invert the value.
6    Fitness 0 -> Very high weight. Fitness 500 -> Low weight.
7    """
8    individuos = [item[1] for item in evaluados]
9    costos = [item[0] for item in evaluados]
10
11    # We invert costs to obtain weights (Higher weight = Higher probability)
12    pesos = [1.0 / (1.0 + c) for c in costos]
13
14    # The choices function with 3 arguments (population, weights, quantity)
15    seleccionado = random.choices(population=individuos, weights=pesos, k=1)[0]
16
17    return seleccionado

Crossover

Fig: 6. Example of the crossover operator. In the image, we see that Parent A donates all teams belonging to pots 1 and 4 to Child A, and teams from pot 2 and 3 to Child B.

The crossover used here takes two parents and creates two children.

• Flip coin: from which parent to inherit this pot?
• Child1 inherits complete pot from selected parent
• Child2 inherits complete pot from other parent

python
1def cruzar(padre1, padre2):
2    """
3    Stratified Crossover Operator (Uniform Crossover by Pots).
4    The child inherits the entire configuration of a pot from one of the parents.
5    """
6    # Empty children
7    hijo1 = [[] for _ in range(12)]
8    hijo2 = [[] for _ in range(12)]
9    # We iterate through each Pot level (0 to 3)
10    for bombo_idx in range(4):
11        # Random decision: Who donates this pot?
12        if random.random() < 0.5:
13            # Case A: Child 1 inherits from Father 1, Child 2 inherits from Father 2
14            donante_1 = padre1
15            donante_2 = padre2
16        else:
17            # Case B: Crossed
18            donante_1 = padre2
19            donante_2 = padre1
20
21        # We copy the entire row of that pot to the children
22        for g_idx in range(12):
23            equipo_p1 = donante_1[g_idx][bombo_idx]
24            equipo_p2 = donante_2[g_idx][bombo_idx]
25
26            hijo1[g_idx].append(equipo_p1)
27            hijo2[g_idx].append(equipo_p2)
28    return hijo1, hijo2

Mutation

Fig: 7. Example of the mutation operator.

• Pick 2 random groups
• Pick a random pot (1, 2, 3, or 4)
• Swap the teams of that pot between the 2 groups
• Only if neither has a fixed group

python
1def mutar(individuo, prob_mutacion):
2    """
3    Attempts to mutate with probability 'prob_mutacion'.
4    """
5    if random.random() > prob_mutacion:
6        return individuo  # Does not mutate
7
8    # If it mutates, we perform the swap
9    nuevo = copy.deepcopy(individuo)
10    idx_g1, idx_g2 = random.sample(range(12), 2)
11    bombo_idx = random.randint(0, 3)
12
13    e1 = nuevo[idx_g1][bombo_idx]
14    e2 = nuevo[idx_g2][bombo_idx]
15
16    if not e1.grupo_fijo and not e2.grupo_fijo:
17        nuevo[idx_g1][bombo_idx], nuevo[idx_g2][bombo_idx] = (
18            nuevo[idx_g2][bombo_idx],
19            nuevo[idx_g1][bombo_idx],
20        )
21
22    return nuevo

Replacement

Termination Criterion

• If a draw with $\text{penalty} = 0 \Rightarrow \text{Success}$ is found.
• If it reaches generation $1000 \Rightarrow$ return the best one found.

Results