Discussion :

[GemRire]

Bonjour ,

Dans le cadre d'un projet universitaire, je dois programmer des IA sur deux jeux qui sont Reversi et l'Awale.
Les algorithmes de bases comme MinMax et AlphaBêta sont installés et semblent bien marché. Mon problème vient de la fonction d'évaluation surtout au niveau de l'Awale ( j'ai essayé d'y jouer un peu et je n'arrive même pas à battre un IA de niveau facile ... ). J'ai aussi un autre problème, mon professeur dispose d'un site qui permet de déposer nos programmes et de les tester contre les IA des autres étudiants du projet. Cependant ce site dispose d'un time-out qui refuse notre programme si il prend un certain temps à s'exécuter, et ce time-out est plutôt court pour Reversi et très court pour l'Awale ( je ne fais pas mieux que l'horizon 2 pour le Reversi et 4 pour l'Awale ). Je viens donc vous solliciter pour améliorer mes fonctions d'évaluations et peut-être mes codes pour ceux qui ont le temps de les lires.

Langage de programmation : Python

1 ) Problème sur Reversi :

Je m'en sors plutôt bien pour le Reversi, mes fonctions d'évaluations semblent marcher. Mais j'ai un problème au niveau d'une fonction d'évaluation très importante que je n'ai pas réussi à programmer. Cela concerne le fait de savoir si un pion est définitif ou non. Pour ceux les non-connaisseurs , un pion définitif est un pion qui ne pourra jamais changer de couleur. J'ai essayé plusieurs façon de le faire mais ça reste assez brouillon, j'ai réussi pour l'instant à identifier que ceux qui sont présents sur les bords :

Code Python :

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
#structure de jeu imposé Jeu = [ plateau , tour, coupdispo, coupjoues, Score] avec tour = 1 ou 2 , coupdispo = coupdisponible sur le moment, coupJoue l'ensemble des coups joués.
 
def scan_verticale(jeu,coup) :
""" jeu * coup -> bool
Hypothèse : ce coup n'est pas un coin
Retourne vrai si le coup permet de poser un pion définitif"""
 
i = coup[0] - 1
j = coup[1]
while i >= 0 :
if jeu[0][i][j] == jeu[0][coup[0]][coup[1]] :
if i==0 :
return True
i -= 1
else :
break
 
i = coup[0] + 1
while i <= 7 :
 
if jeu[0][i][j] == jeu[0][coup[0]][coup[1]] :
if i == 7 :
return True
i += 1
else :
break
 
return False
 
def pion_def(jeu,pos):
"""jeu * coup -> bool
Retourne True si le pion à pos est définitif"""
i = pos[0]
j = pos[1]
if est_coin(pos) :
return True
if est_bord(pos) :
if i == 0 or i == 7 :
if scan_horizontale(jeu,pos) :
return True
elif j == 0 or j == 7 :
if scan_verticale(jeu,pos):
return True
return False
else :
return False
# et la fonction qui pose problème
def scan_diagonale(jeu,coup) :
""" jeu * coup -> bool
Hypothèse: coup[0] == coup[1]
Retourne vrai si le coup permet de poser un pion qui ne peut pas être changé sur la diagonale """
 
i = coup[0] + 1
j = coup[1] -1
b=0
while i < 8 and j >= 0 :
 
if jeu[0][i][j] == jeu[0][coup[0]][coup[1]] and scan_horizontale(jeu,(i,j)) :
if i == 7 or j == 0 :
b += 1
break
i += 1
j -= 1
else :
break
 
 
if b == 1 :
i = coup[0] -1
j = coup[1] + 1
while i >= 0 and j < 8 :
if jeu[0][i][j] == jeu[0][coup[0]][coup[1]] and scan_horizontale(jeu,(i,j)) :
if i == 0 or j == 7 :
b+=1
break
i -= 1
j += 1
else :
break
if b == 2 :
return True
return False

La fonction scan_horizontale marche de la même façon que le scan verticale. J'avais pensé à faire un scan_diagonale, qui regarde si le pion est bien entouré de pion définitif mais cela semble trop long et trop complexe et ne marche pas à tous les coups. Auriez-vous une solution plus simple à me proposer ?

Voici comment j'évalue mes cases :

Code Python :

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
def eval_score(jeu,moi) :
 
L_moi = [0,0,0,0,0]
L_adv = [0,0,0,0,0]
adv = moi % 2 + 1
for i in range (0,8) :
for j in range (0,8) :
if jeu[0][i][j] == moi :
if est_coin((i,j)):
L_moi[0] += 1
if pion_def(jeu,(i,j)) :
L_moi[1] += 1
if est_bord_coin(jeu,(i,j),moi) :
L_moi[2] += 1
elif est_bord((i,j)):
L_moi[5]+=1
if adj_coin_vide(jeu,(i,j)) :
L_moi[3] += 1
else :
L_moi[4] += 1
 
elif jeu[0][i][j] == adv :
if est_coin((i,j)):
L_adv[0] += 1
if pion_def(jeu,(i,j)) :
L_adv[1] += 1
if est_bord_coin(jeu,(i,j),adv) :
L_adv[2] += 1
elif est_bord((i,j)):
L_adv[5]+=1
if adj_coin_vide(jeu,(i,j)) :
L_adv[3] += 1
else :
L_adv[4] += 1
return (L_moi,L_adv)
#p est une liste correspondant à différent poids pour donner de l'importance à certaines cases.
def eval(jeu,moi) :
L,L2 = eval_score(jeu,moi)
if tour_jeu(jeu) < 14 :
return (p[0] * (L[0]-L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + 2*p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) + p[6] * (L[6]-L2[6]) )
else :
return (p[0] * (L[0]-L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) + p[6] * (L[6]-L2[6]) )

Tout retour sur celui-ci est le bienvenue !


2 ) Awale :

Ici j'ai un gros problème sur la compréhension des stratégies en Awale, tout d'abord , il faut savoir qu'on a été limité à 100 tours et qu'a la fin des 100 tours on prend les graines qui sont dans notre camp. J'ai pensé à plusieurs fonctions d'évaluations :

Code Python :

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
def nb_pos_mangeable(jeu,i) :
""" jeu -> int
Retourne le nombre de position mangeable de notre côté """
cpt =0
for j in range(0,6) :
if mangeable(i,j,jeu) :
cpt += 1
return cpt
 
def suite_pierre_mangeable(jeu,i) :
"""Retourne le max de suite mangeable"""
max=1
cpt=0
for j in range (0,6) :
if mangeable(i,j,jeu) :
cpt += 1
else :
if cpt > max :
max = cpt
cpt = 0
return max
 
def sup_3(jeu,i,j) :
""" jeu * int * int -> bool
Si la case >= 3 alors on retourne True"""
if jeu[0][i][j] > 3 :
return True
return False
 
def sup_12(jeu,i,j) :
""" jeu * int * int -> bool
Si la case >= 12 alors on retourne True"""
if jeu[0][i][j] >= 12 :
return True
return False
 
def nb_graine_dispo(jeu,i):
""" Retourne le nombre de graine disponible dans notre camp"""
cpt = 0
for j in range(0,6) :
cpt += jeu[0][i][j]
return cpt
 
# Partie Evaluation
 
#poids actuels basé sur l'apprentissage automatique entre deux de mes IA.
p=[-0.1921608482234869, 0.007018486323293982, 0.005610612295873526, -0.14026026594929142, -0.7864595029841923, 0.7811131059857571, 0.8019527799343023]
 
 
def eval_score(jeu,moi) :
 
L = [0,0,0,0,0,0,0]
L_adv = [0,0,0,0,0,0,0]
adv = moi % 2
 
for j in range (0,6) :
if sup_12(jeu,moi-1,j) == True :
L[0] += 1
elif sup_3(jeu,moi-1,j) :
L[1] += 1
if sup_12(jeu,adv,j) == True :
L_adv[0] += 1
elif sup_3(jeu,adv,j) :
L_adv[1] += 1
 
if moi-1 == 0 :
L[2] += (6-j) * (5*jeu[0][moi-1][j])
L_adv[2] += (j+1) * (5 * jeu[0][adv][j])
 
else :
L[2] += (j+1) * (5 * jeu[0][moi-1][j])
L_adv[2] += (6-j) * (5*jeu[0][adv][j])
 
L[3] -= nb_pos_mangeable(jeu,moi-1)
L_adv[3] -= nb_pos_mangeable(jeu,adv)
L[4] -= suite_pierre_mangeable(jeu,moi-1)
L_adv[4] -= suite_pierre_mangeable(jeu,adv)
L[5] += jeu[4][moi-1]
L_adv[5] += jeu[4][adv]
L[6] = nb_graine_dispo(jeu,moi-1)
L_adv[6] = nb_graine_dispo(jeu,adv)
 
return (L,L_adv)
 
cpt_eval = 0
 
def eval(jeu,moi) :
global tour
L,L2 = eval_score(jeu,moi)
if tour <= 30 :
return (p[0] * (L[0]-L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) )
else :
return ((-5) *p[0] * (L[0]-L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) + p[6] * (L[6]-L2[6]) )
 
#Avec L[5] le score actuel , L[2] la valeur de la somme des graines de notre côté qui sont selon le côté plus important à droite ou à gauche.

Ma façon de penser était d'essayer d'avoir le moins de suite de cases mangeables et de positions mangeables tout en essayant en début de partie de manger le plus chez l'adversaire. En fin de partie on profite du fait qu'on soit limité à 100 tours pour stacker les graines de notre côté et de les prendre à la fin pour booster le score.
Malheureusement je n'arrive qu'a 76% de victoires ( booster par le fait qu'il a beaucoup d'étudiants qui ont mis des IA aléatoires ). Avec le top2 qui sont à 90% je sollicite donc vos connaissances pour savoir comment je peux améliorer mes programmes tout en étant bien niveau temps !


3 ) Trier les listes.

Pour finir , j'ai une idée claire de comment trier mes listes de coup en Reversi pour améliorer l'efficacité d'alpha-bêta , cependant je n'arrive pas à voir comment trier celle de l'Awale car il faut tester avant de connaître l'efficacité du coup contrairement au reversi ou les coups correspondant à un coin du plateau seront naturellement les premiers à passer. Auriez-vous une solution pour ça ?

Merci d'avoir pris le temps de lire !
Bonne journée à tous.

[GemRire]

Finalement , j'ai trouvé la réponse pour l'Awale , j'avais plus ou moins déjà les bonnes fonctions d'évaluations, il suffisait ensuite de rajouter dans mon cas une autre fonction sup24 car comme on est limité à 100 tours si au 100 ème tours on a 24 graines ou plus ça permet de prendre au moins une égalité assuré. Le poids des différentes fonctions sup3 sup12 sup24 doivent être positive pour monter progressivement.
Voici donc ma fonction d'évaluation actuel :

Code Python :

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
def eval_score(jeu,moi) :
 
    L = [0,0,0,0,0,0,0]
    L_adv = [0,0,0,0,0,0,0]
    adv = moi % 2
 
    for j in range (0,6) :
            if sup_12(jeu,moi-1,j) == True :
                L[0] += 1
            elif sup_3(jeu,moi-1,j) :
                L[1] += 1
            if sup_12(jeu,adv,j) == True :
                L_adv[0] += 1
            elif sup_3(jeu,adv,j) :
                L_adv[1] += 1
            if sup_24(jeu,moi-1,j) == True :
                L[6] += 1
            elif sup_24(jeu,adv,j) == True :
                L_adv[6] += 1
 
            if moi-1 == 0 :
                L[2] += (j+1) * (5*jeu[0][moi-1][j])
                L_adv[2] += (6-j) * (5 * jeu[0][adv][j])
 
            else :
                L[2] += (6-j) * (5 * jeu[0][moi-1][j])
                L_adv[2] += (j+1) * (5*jeu[0][adv][j])
 
    L[3] -= nb_pos_mangeable(jeu,moi-1) 
    L_adv[3] -= nb_pos_mangeable(jeu,adv) 
    L[4] -= suite_pierre_mangeable(jeu,moi-1)
    L_adv[4] -= suite_pierre_mangeable(jeu,adv)
    L[5] += jeu[4][moi-1]
    L_adv[5] += jeu[4][adv]
 
    return (L,L_adv)
 
cpt_eval = 0 
 
def eval(jeu,moi) :
    global tour
    L,L2 = eval_score(jeu,moi)
    if tour <= 30 :
        return (p[0] * (L[0]-L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) + p[6]*(L[6]-L2[6]))
    else :
         return (2 *p[0] * (L[0]-2*L2[0]) + p[1] * (L[1]-L2[1]) + p[2] * (L[2]-L2[2]) + p[3] * (L[3]-L2[3]) + p[4] * (L[4]-L2[4]) + p[5] * (L[5]-L2[5]) + p[6] * (L[6]-L2[6]) )

Pour l'Othello, trouvé les pions définitifs en dehors de ceux des bords semble trop couteux en terme de temps et peut être pas si utile que ça.