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.
Partager