Discussion :

[Wyxau]

Bonjour a tous
Pour les cours d'info de prépa moi et deux amis avont un projet a faire sur Python, et il nous a été proposé de programmer un jeu de société appeler le jeu du Neutron, c'est un jeu de plateau de type échec mais en moins complexe, voici les règles : https://fr.m.wikipedia.org/wiki/Neutron_(jeu)
Pour l'instant avec mon groupe on a réussi a coder le jeu (on a même mis un pack de skin pokémon) sauf qu'on aimerait faire mieux parce que pour l'instant on joue en tapant des trucs dans la console et pas en cliquant sur la fenêtre graphique. Mais surtout on aimerait faire un bot pour jouer contre et c'est pour ça que je demande de l'aide : comment faire un bot pas spécialement invincible mais un bot qui du moins qui ne joue pas que de manière random ?

Je peux montrer notre code si nécessaire mais il est relativement long

Merci de votre aide ^^

[wiztricks]

Salut,

Mais surtout on aimerait faire un bot pour jouer contre et c'est pour ça que je demande de l'aide : comment faire un bot pas spécialement invincible mais un bot qui du moins qui ne joue pas que de manière random ?

Déjà il faut un algo. qui utilisera des techniques d'intelligences artificielles qui vont de l'élagage alpha beta aux réseaux de neurones avec auto-apprentissage... (la rubrique Algorithme est l'endroit ou se trouvent de telles compétences) puis il faudra le coder éventuellement avec Python (et c'est à partir de là qu'on pourra vous aider ici).

- W

[Wyxau]

Suite à votre réponse j'ai fait des ptites recherches sur l'algorithme min max et je l'ai codé pour mon jeu avec une profondeur d'un seul tour, ça marchait mais comme prévu le bot était relativement nul, du moins qqn de sencé ne pouvait perdre contre lui.
Du coup j'ai prolongé le programme pour que le bot regarde un autre tour en avance, sauf que la le nombre de combinaisons devient immense et le temps d'éxecution infini, je suspecte la fonction copy.deepcopy d'en etre le principale responsable puisque pour faire tourner l'algo je dois effectuer un nombre immense de fois cette fonction.
Je sollicite donc votre aide pour l’accélérer, mon code est le suivant

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
89
90
91
92
93
94
95
96
97
98
P=[["b","b","b","b","b","b","b"],["b",1,2,3,4,5,"b"],["b",0,0,0,0,0,"b"],["b",0,0,"n",0,0,"b"],["b",0,0,0,0,0,"b"],["b",6,7,8,9,10,"b"],["b","b","b","b","b","b","b"]] #P est la matrice position du plateau au début d'une partie, les "b" délimitant les bordures du plateau, le "n" représente le neutron et 1,2,3,4,5 les pions du joeur1 et 6,7,8,9,10 les pions du joueur 2 en l'occurence du bot
A=[["NO",-1,-1],["N",-1,0],["NE",-1,1],["O",0,-1],["E",0,1],["SO",1,-1],["S",1,0],["SE",1,1]]
import copy
import random
def Liste(P): #associe à la matrice de position P la liste des déplacements possible pour chaque pion ainsi que leur coordonnées
    A=[["NO",-1,-1],["N",-1,0],["NE",-1,1],["O",0,-1],["E",0,1],["SO",1,-1],["S",1,0],["SE",1,1]]
    L=[] #on reinitialise L à chaque boucle
    for i in [1,2,3,4,5,6,7,8,9,10,"n"]: #pour chaque pion
        U=[] #liste de mémoire vive
        for k in range(7): #trouver les coordonnées du pion
            for l in range(7):
                if P[k][l]==i:
                    a,b=k,l #on affecte à (a,b) les coordonnées du pion
        for j in A:
            if P[a+j[1]][b+j[2]]==0:
                U+=[j[0]]
        L+=[[U,[a,b]]]
    return(L)
 
def calcNeutron(P): #calcule toute les possiiblités de jeu suite au déplacement du neutron
    L=Liste(P)
    LISTE=[]
    for j in range(len(L[10][0])): #effectue la boucle le nombre de fois que le neutron a de possibilités de déplacement
        a=L[10][1][0]
        b=L[10][1][1]
        dc=L[10][0][j]
        K=copy.deepcopy(P)   #travaille sur une copy de P pour ne pas modifier le='état du plateau de jeu
        for i in A :
            if dc==i[0] :
                while K[a+i[1]][b+i[2]]==0:
                    K[a+i[1]][b+i[2]]="n"
                    K[a][b]=0
                    a+=i[1]
                    b+=i[2]
                break
            a=L[10][1][0]
            b=L[10][1][1]
        LISTE+=[K]
    return(LISTE)
def calcPion(P,joueur): #calcule toute les possiiblités de jeu suite aux déplacements des différents pions d'un joueur
    L=Liste(P)
    PION=[]
    for pion in range(5*joueur,5*(joueur+1)): #selectionne les pions 1 à 5 ou 6 à 10 en fonction du joueur
        for j in range(len(L[pion][0])):
            K=copy.deepcopy(P)
            y=L[pion][1][0]
            x=L[pion][1][1]
            dc=L[pion][0][j]
            for i in A :
                if dc==i[0] :
                    while K[y+i[1]][x+i[2]]==0:
                        K[y+i[1]][x+i[2]]=pion+1
                        K[y][x]=0
                        y+=i[1]
                        x+=i[2]
                    break
                a=L[10][1][0]
                b=L[10][1][1]
            PION+=[K]
    return(PION)
def Arbre(P):
    score=0
    LISTE=calcNeutron(P)
    TOUR1=[]   #Liste des situations possibles du plateau après que le bot ai joué son neutron et ses pions
    TOUR2=[]    #Liste des situations possibles du plateau après que l'adversaire ai joué son neutron et ses pions
    TOUR3=[]   #Liste des situations possibles du plateau après que le bot ai a nouveau joué son neutron et ses pions
    TOUR4=[]    #Liste des situations possibles du plateau après que l'adversaire ai a nouveau joué son neutron et ses pions
    scoreTOUR3=[] #Liste des scores attribués à chaque possibilités à la fin du Second tour de l'adversaire
    for Matrice in LISTE:
        TOUR1+=calcPion(Matrice,1)
    scoreTOUR1=[]
    for k in TOUR1:
        TOUR2=[]
        LISTE2=calcNeutron(k)
        for Matrice1 in LISTE2:
            TOUR2+=calcPion(Matrice1,0)
        for Matrice2 in TOUR2:
            LISTE3=calcNeutron(Matrice2)
            for Matrice3 in LISTE3:
                TOUR3+=calcPion(Matrice3,1)
            for Matrice4 in TOUR3:
                LISTE4=calcNeutron(Matrice4)
                for Matrice5 in LISTE4:
                    TOUR4+=calcPion(Matrice5,0)
                score=10000
                for j in TOUR4 :
                    if calcscore(j)<=score:
                        score=calcscore(j)
                scoreTOUR3+=[score]
            scoremaxtour3=max([k for k in scoreTOUR3])
        scoremaxtour2=min([k for k in scoremaxtour3])
    scoremax=max([k for k in scoremaxtour2])
    Choixpossibles=[]
    for k in range(len(TOUR1)):
        if scoremaxtour2[k]==scoremax:
            Choixpossibles+=[k]
    choix=random.choice(Choixpossibles)
    return(TOUR1[choix])

Les règles du jeu sont trouvables sur wikipedia, merci beaucoup de votre aide

[wiztricks]

Salut,

Du coup j'ai prolongé le programme pour que le bot regarde un autre tour en avance, sauf que la le nombre de combinaisons devient immense et le temps d'éxecution infini

Soit vous êtes trop pressé (i.e. çà se termine mais pas assez vite pour vous), soit il y a un bug dans votre code. J'ai du mal a y retrouver un algo. de minmax qui par essence est récursif.
Enfin vous vous plaignez de .deepcopy mais rien ne vous empêche de remettre les choses en place pour l'étape suivante.

Ceci dit, prenez déjà début de votre code:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
P=[["b","b","b","b","b","b","b"],["b",1,2,3,4,5,"b"],["b",0,0,0,0,0,"b"],["b",0,0,"n",0,0,"b"],["b",0,0,0,0,0,"b"],["b",6,7,8,9,10,"b"],["b","b","b","b","b","b","b"]] #P est la matrice position du plateau au début d'une partie, les "b" délimitant les bordures du plateau, le "n" représente le neutron et 1,2,3,4,5 les pions du joeur1 et 6,7,8,9,10 les pions du joueur 2 en l'occurence du bot
A=[["NO",-1,-1],["N",-1,0],["NE",-1,1],["O",0,-1],["E",0,1],["SO",1,-1],["S",1,0],["SE",1,1]]
import copy
import random
def Liste(P): #associe à la matrice de position P la liste des déplacements possible pour chaque pion ainsi que leur coordonnées
    A=[["NO",-1,-1],["N",-1,0],["NE",-1,1],["O",0,-1],["E",0,1],["SO",1,-1],["S",1,0],["SE",1,1]]
    L=[] #on reinitialise L à chaque boucle
    for i in [1,2,3,4,5,6,7,8,9,10,"n"]: #pour chaque pion
        U=[] #liste de mémoire vive
        for k in range(7): #trouver les coordonnées du pion
            for l in range(7):
                if P[k][l]==i:
                    print('k, l', k, l)
                    a,b=k,l #on affecte à (a,b) les coordonnées du pion

Vous partez d'un P qui représente ce que vous voyez à l'écran... et cette représentation vous condamne à effectuer une double boucle 7x7 pour trouver la dedans les (a, b) qui contiennent un pion. Si déjà vous représentiez cela avec un dictionnaire où les clefs seraient les (a, b) qui contiennent un pion (les autres on s'en fout), çà ferait bien moins d'itération (et çà changerait drastiquement la structure de votre code).

Donc vous voyez il y a du boulot: comprendre le jeu, fabriquer une représentation interne qui soit optimale (sinon un peu meilleure) pour lui appliquer un algo. de minmax et un élagage alpha beta,... A moins que quelqu'un ait déjà une solution toute fait (cherchez sur Internet) pas grand monde aura le temps de faire quoi que ce soit pour vous.

- W