Arbre de tournoi, combinaison/rotation de chiffre

**Hindioumax** · 10/03/2010, 13h05

Bonjour à tous,
C'est bien la 1ère fois que je poste sur le forum mathématique/algo mais j'avoue que là vous êtes ma dernière chance.

Introduction :
J'organise à mes heures perdues des tournois de jeux vidéo online/LAN et à chaque tournoi il y a une phase de poule (avec X nombre de joueurs répartis dans Y nombre de poules) suivi d'un arbre final.
Au départ, chaque poule contient des favoris qui, si toute logique sportive est respectée, doivent normalement se qualifier pour l'arbre final.
Une fois les matches de poules terminés, on fait un classement du 1er au moins bon pour chaque poule et ainsi qualifier Z nombre de joueurs.

Constantes :
- Le nombre de poule et le nombre de joueurs qualifiés sont toujours pairs et de puissance de 2. (2, 4, 8, 16, 32, 64 etc)

Problème et contraintes :
Mon problème se situe au niveau de l'affectation des joueurs qualifiés dans l'arbre final. Je dois faire absolument respecter les 2 consignes suivantes :

1) dans l'arbre final, et en partant du principe que les meilleurs gagnent toujours, les meilleurs issus des poules jouent toujours contre les moins bons qualifiés d'une autre poule.

Exemple pour 4 poules de 4 joueurs :
En 1/8ème de finale, le 1er d'une poule joue toujours contre un 4ème d'une autre poule, suivi d'un 2ème qui joue contre un 3ème d'une autre poule,
En 1/4 de finale il faut toujours un 1er contre un 2ème de chaque côté de l'arbre,
Ce principe doit être respecté pour chaque tour de l'arbre.

2) Faire jouer des joueurs issus d'une même poule le plus tard possible.

Le but de tout cela est, vous l'avez compris, de faire en sorte que les favoris se retrouvent le plus loin possible dans l'arbre et qu'il y ai le moins d'accidents sportifs (entendez par là que des favoris ne s'éliminent pas entre eux trop tôt). Et aussi de faire rencontrer des joueurs issus d'une même poule le plus tard dans l'arbre.

Alors évidemment, des combinaisons qui fonctionnent, j'en ai trouvé plein, mais j'ai dû les faire à la main, en testant "un peu bêtement" des rotations de chiffres jusqu'à ce que ça marche. Quand on a 8 ou 16 joueurs c'est faisable, mais quand on a 32, 64, 128, 256 joueurs ou plus, ca devient pour ma part un vrai casse tête chinois.

Si vous pouviez m'aider à trouver le moyen de remplir les arbres "facilement" en suivant une logique mathématique, un algorithme (voire même, pourquoi pas, un moyen mémo-technique) bref une méthode que je pourrais ensuite concrétiser sous forme de programme, ça serait absolument génial.

Pour vous donner une idée, voici l'exemple d'algorithme/technique qui permet de générer tous les matches d'un championnat sans doublons "Round Robin Tournament Scheluling" : http://www.devenezia.com/downloads/r...bin/index.html

C'est un peu ce genre de chose que je recherche mais il se peux que pour mon cas je fasse complètement fausse route (d'où mon post).

Voilà, le besoin est réel, d'autant plus que ce problème est fréquemment connu dans les tournois. Face aux joueurs, les organisateurs sont parfois dans de très mauvaises positions en cas d'arbre final mal rempli.

Je vous ai joint un fichier excel, reprenant un exemple concret ainsi qu'une image pour ceux qui n'auraient pas excel.
Ps : dans mon exemple, les 1ères lettres des prénoms des joueurs correspondent à leur poule (Alain est dans la poule A, Christophe dans la poule C etc...)

J'espère avoir été assez clair dans mes explications (sinon n'hésitez pas à me poser vos questions), et si vous pouvez m'aider et m'aiguiller sur les bonnes pistes, j'en serais enchanté.

Merci à vous.

**Nemerle** · 10/03/2010, 13h13

Question supplémentaire: si tu as N=2^p qualifiés, combien de poules as-tu (ou, équivalent, combien de joueurs qualifiés par poule)? Est-ce un paramètre libre dans ton souhait de modélisation?

**Hindioumax** · 10/03/2010, 13h31

En fait pour le moment je suis parti d'un postulat simple qui est que le nombre de poule est égal au nombre de joueurs qualifiés (4 poules = 4 joueurs qualifiés, 8 = 8 etc) mais effectivement dans son second temps, j'aimerais bien arriver au même résultat avec le maximum de possibilités comme 8 poules de 4 joueurs (très fréquent dans les tournois), 16 poules de 8, 8 poules de 2, 16 poules de 4 etc.

Edit : attention, dans mon exemple, les matches de poules sont terminés et j'affiche le classement des joueurs qui sont qualifiés. Ce qui veux dire qu'au tout début du tournoi il y a eu par exemple 4 poules de 8 joueurs, on en a gardé que les 4 premiers (selon mon souhait, mon propre paramètre).

**Hindioumax** · 12/03/2010, 13h14

petit up

**Nemerle** · 12/03/2010, 14h03

Modélisons le problème:

- tu as 2^n qualifiés
- tu as 2^p poules où dans chaque il y a 2^q qualifiés (et donc p+q=n)

Posons X=2^p et Y=2^q. Ta matrice X*Y des joueurs est alors

J(1,1) J(2,1) ... J(2^p,1)
J(1,2) J(2,2) ... J(2^p,2)
... ... ... ...
J(1,2^q) J(2,2^q) ... J(2^p,2^q)

où chaque colonne représente les Y qualifiés d'une poule. Pour tout J(i,j) et J'(i',j'), posons d(J,J')=|i-i'|+|j-j'|.

1ière étape: en itérant i puis j, chaque joueur J(i,j) joue contre J'(i',j') tel que d(J,J') soit maximal. Ainsi J(1,1) joue contre J(X,Y), J(2,1) contre J(X-1,Y),etc. A chaque fois que tu as apparié 2 joueurs, tu les "tue" dans la matrice.

Etapes suivantes: tu "tues" les vaincus de ta matrice, et tu réitères... attention, à partir de maintenant, le J' tel que d(J,J') soit maximal n'est plus forcément unique: tu privilégies dans ce cas celui qui maximise |i-i'| (poule différente).

En implémentation, ta matrice sera booléenne (1=en vie, 0=tué).

**Hindioumax** · 19/03/2010, 21h19

Merci pour la réponse mais n'étant pas matheux d'origine j'ai un peu de mal à comprendre les syntaxes et du coup à les interprêter.
Cela dit, je comprend tout à fait la manière de procéder, reste qu'en terme de programmation, je ne sais pas manier les matrices et à l'heure actuelle je n'ai pas les connaissances nécessaires pour faire l'étude de tous les appariements possibles, vérifier qu'ils sont valides et les tuer au fur et à mesure.

Voilà l'idéal absolu que je voudrais obtenir, et ainsi avoir le choix de toutes les solutions possibles (où le X correspond à une combinaison d'arbre qui marche).

Une solution qui marche en 4 poules de 4 joueurs
X O O O O O O X O X O O O O X O
O O X O O X O O O O O X X O O O
O X O O O O X O X O O O O O O X
O O O X X O O O O O X O O X O O

Une autre solution qui marche en 4x4
X O O O O X O O O O X O O O O X
O O O X O O X O O X O O X O O O
O O X O O O O X X O O O O X O O
O X O O X O O O O O O X O O X O
etc etc

Nemerle, tu pourrais me faire un petit exemple en vba ou en vb ? J'aimerais vraiment saisir ta réponse précédente.

Malgré tout j'ai trouvé une méthode mémotechnique (merci Blaarg ^^) pour avoir une solution mais je ne sais pas comment trouver les autres et je sais qu'il y a moyen de faire beaucoup mieux que le code vba excel qui suit. D'ailleurs il fonctionne avec nbPoule = nbQualif et nbPoule > nbQualif, mais ne fonctionne pas avec nbPoule < nbQualif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
Sub methode_blaarg(nbPoule As Long, nbQualif As Long)
'Cette procédure permet de générer les 1ers matchs d'un arbre en indiquant :
'- le nombre de poule
'- le nombre de qualifiés par poule
'-----------------------------------------------------------------------------------
'Les matchs ainsi générés dans l'ordre permettent de garantir :
'- qu'au 1er tour : un 1er jouera toujours contre un dernier qualifié d'une autre poule, un 2ème contre un avant-dernier etc
'- que des joueurs issus d'une même poule joueront le plus tard possible dans l'arbre
'------------------------------------------------------------------------------------
'Le nombre de poule et le nombre de qualifiés doivent être pairs et de puissance de 2
 
'Déclarations des variables
    Dim i As Integer, j As Integer, c As Integer, nbMatch As Integer
    Dim chaine As String, numQualif As String, numPoule As String, separateur As String
    Dim rngP As Range, rngQ As Range, rngM As Range
    Dim cell As Object
 
'Paramètres
    Set rngP = Range("E2") 'Destination du résultat des poules
    Set rngQ = Range("F2") 'Destination du résultat des qualifiés
    Set rngM = Range("G1") 'Destination du résultat du nombre de matches
    separateur = "|"
 
'Vérification si les 2 chiffres sont pairs et puissances de 2
    If EstPuissanceDe(nbPoule, 2) = False Or EstPuissanceDe(nbQualif, 2) = False _
    Or Not isPair(nbPoule) Or Not isPair(nbQualif) Then
        MsgBox "Certains chiffres ne sont pas puissance de 2 ou ne sont pas pairs, arrêt du programme.", vbCritical
        Exit Sub
    End If
 
'Création de la chaine avec les n° de qualifiés dans l'ordre
'le 1er avec le dernier, le 2ème avec l'avant dernier, etc etc
'on répète le processus autant de fois qu'il y a un nombre de paires (nbQualif/2) par poules (nbPoule)
    For i = 1 To nbPoule
        c = 0
        For j = 1 To nbQualif / 2
            chaine = chaine & j & separateur & nbQualif - c & separateur
            c = c + 1
        Next j
    Next i
 
   'Stockage du résultat dans une nouvelle variable (numQualif)
    numQualif = Mid(chaine, 1, Len(chaine) - 1) 'Suppression du dernier séparateur
    Debug.Print "valeur de numQualif :" & numQualif
 
 
    chaine = "" 'Reset de la chaine précédente
    c = 0       'Reset du compteur précédent
 
 
'Création de la chaine avec les n° des poules
'rotation des chiffres de 1 à chaque tour dans le sens horlogique
'on répète le processus autant de fois qu'il y a de joueurs qualifiés (nbQualif)
'c détermine le n° de départ
    For i = 1 To nbQualif
        c = i
        For j = 1 To nbPoule
            chaine = chaine & c & separateur
            c = c + 1
            If c > nbPoule Then c = 1
        Next j
    Next i
 
   'Stockage du résultat dans une nouvelle variable (numPoule)
    numPoule = Mid(chaine, 1, Len(chaine) - 1) 'Suppression du dernier séparateur
    Debug.Print "valeur de numPoule :" & numPoule
 
   'conversion des chiffres de poules en lettres   
   'affichage
   'etc etc...
 
end sub

Explication du code ci-dessus :
On sait qu'un 1er jouera toujours un dernier et un 2ème avec un avant dernier etc.
Pour 4 joueurs par exemple, on aura toujours 1-4 suivi de 2-3. Cette suite de chiffre (1-4-2-3) on la rèpète autant de fois que l'on a de poules. ce qui donne pour 4 poules :
1-4-2-3-1-4-2-3-1-4-2-3-1-4-2-3

Ensuite, concernant les poules, on a cette suite (pour 4 poules) : A-B-C-D
A chaque n+1 qualifiés, on fait une rotation horlogique, ce qui donne pour le tour suivant : B-C-D-A
Au final pour 4 joueurs on obtient :
A-B-C-D-B-C-D-A-C-D-A-B-D-A-B-C

On concatène les 2 suites :
A-B-C-D-B-C-D-A-C-D-A-B-D-A-B-C
1-4-2-3-1-4-2-3- 1-4-2-3- 1-4-2-3

Et on obtient une solution qui marche. Mais ce n'est pas LA solution, il y en a pleins et j'espère que vous aller m'aider à trouver l'algo ultime qui commence à prendre pour moi une dimension obsessionnelle.

Je cherche encore le moyen d'avoir cette suite qui est le modèle parfait d'affectation des joueurs que je recherche pour du 4x4 :
A-D-C-B-C-B-A-D-C-B-A-D-A-D-C-B
1-4-3-2-2-3-4-1-1-4-3-2-2-3-4-1

Petit bémol cependant, même s'il est possible de trouver l'algorithme de cette suite, cela ne marchera pas pour un arbre à 8x8

**Nemerle** · 22/03/2010, 10h30

Ci-dessous le code "vite codé" qui solutionne ton problème. Pour 256 poules de 32 joueurs, ça prend qq secondes.

A chaque étape des "ko", j'ai tiré aléatoirement les vainqueurs

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
p0 = Worksheets("Sheet1").Cells(2, 2) 
    q0 = Worksheets("Sheet1").Cells(3, 2) 
 
    p = 2 ^ p0 '=== Nb de poules
    q = 2 ^ q0 '=== Nb de players
    n = p * q
 
    For i = 1 To p
        For j = 1 To q
            b(i, j) = True
        Next j
    Next i
 
    no = 1
 
    While no < p0 + q0  '======== no: No du tour
        i = 0
        j = 1
        count = 0
        While count < n / (2 ^ no)
            i = i + 1
            If i > p Then
                i = 1
                j = j + 1
            End If
            While b(i, j) = False
                i = i + 1
                If i > p Then
                    i = 1
                    j = j + 1
                End If
            Wend
            v = cand((i), (j), b, (p), (q))
            count = count + 1
            match(count, 1) = i
            match(count, 2) = j
            match(count, 3) = v(1)
            match(count, 4) = v(2)
            b(i, j) = False
            b(v(1), v(2)) = False
        Wend
        Worksheets("Sheet1").Cells(1, 4 + no) = "Tour No " & no & ":"
        For i = 1 To count
            Worksheets("Sheet1").Cells(1 + i, 4 + no) = "(" & match(i, 1) & "." & match(i, 2) & "," & match(i, 3) & "." & match(i, 4) & ")"
        Next i
        '============= tirage aléatoire des victorieux
        For i = 1 To p
            For j = 1 To q
                b(i, j) = True
            Next j
        Next i
        Worksheets("Sheet1").Cells(3 + count, 4 + no) = "Victorieux:"
        For i = 1 To count
            If Rnd < 0.5 Then
                Worksheets("Sheet1").Cells(4 + count + i, 4 + no) = "'(" & match(i, 1) & "." & match(i, 2) & ")"
                b(match(i, 1), match(i, 2)) = False
            Else
                Worksheets("Sheet1").Cells(4 + count + i, 4 + no) = "'(" & match(i, 3) & "." & match(i, 4) & ")"
                b(match(i, 3), match(i, 4)) = False
            End If
        Next i
        no = no + 1
    Wend
 
End Sub
 
Function cand(i As Integer, j As Integer, b() As Boolean, p As Integer, q As Integer) As Variant
 
    Dim ecart As Integer, val As Integer, v As Integer, w As Integer
    Dim sol(2) As Variant
 
    ecart = 0
    sol(1) = 0
    For k = 1 To p
        For l = 1 To q
            If b(k, l) = True Then
                v = Abs(i - k)
                w = v + Abs(j - l)
                If w > ecart Or (w = ecart And v > Abs(i - sol(1))) Then
                    ecart = w
                    sol(1) = k
                    sol(2) = l
                End If
            End If
        Next l
    Next k
    cand = sol
End Function

Ca donne ça par exemple, pour q0=q0=2:

Tour No 1: Tour No 2: Tour No 3:
(1.1,4.4) (1.1,3.4) (1.1,4.4)
(2.1,4.3) (2.1,1.4) (2.1,4.3)
(3.1,1.4) (3.2,1.3)
(4.1,1.3) (4.2,2.3)
(1.2,3.4)
(2.2,4.2)
(3.2,2.4)
(2.3,3.3)

Victorieux: Victorieux: Victorieux:

(4.4) (3.4) (1.1)
(4.3) (1.4) (2.1)
(3.1) (3.2)
(4.1) (2.3)
(1.2)
(2.2)
(2.4)
(3.3)

Tu peux simplement modifier la fonction cand qui te donne le meilleur adversaire pour un joueur (i,j) donné, afin d'obtenir d'autres constructions...

[EDIT] en fait, c'est pas les victorieux, c'est les perdants qui sont affichés (codé trop vite !), mais ça ne change rien... [/EDIT]