Application de l'algorithme MinMax

Bonjour tout le monde !

Je développe depuis plusieurs mois un jeu de type `jeu à damier` se jouant tour par tour à deux joueurs.

Voici le principe du jeu :
Sur un plateau de type matrice (8*8 cases) se situe des cases rouges appartenant à un joueur et des cases vertes appartenant à son adversaire , des cases impénétrables et des
cases pénétrables . Chacun leurs tours les joueurs ont la possibilité avec la case de leur couleur respective de leur choix de se dupliquer sur une case directement voisine (sur l'horizontale , la verticale et la diagonale) si celle-ci est
pénétrables ou se déplacer sur une case voisine à une case (la voisine de la voisine horizontal ou verticale mais pas diagonale) , si la case du joueur est alors voisine avec une case du joueur adverse la case du joueur adverse est 'contaminée'
et devient de la couleur du joueur . Le jeu se termine lorsque le plateau est rempli ou lorsqu'un joueur à aucune possibilité ou si un joueur n'a plus de cases (elles se sont toutes faites contaminées).
Ce n'est pas trés grave si vous n'avez pas tout saisi , je vous présente à présent le probléme !

C'est le parfait jeu pour appliquer l'algorithme MinMax de Van Neumann dans le butd'avoir une Intelligence Artificielle qui puisse jouer contre un joueur humain.
Voici à présent ma classe MinMax qui est sensé gérer l'IA . (Aprés instanciation j'appel la méthode DecisionMinMax() avec les paramétres demandés pour faire fonctionner la machine :p) :

EXEMPLE1:

Code:

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
99
100
101
102
103
104
105
106
107
108
109
110
class MinMax(object):
 
 
	'''Gestion de l'IA avec l'Algorithme minmax'''
	def __init__(self,plateau,joueur,adversaire):
		'''plateau : plateau de jeu sur lequel nous effectuons toutes nos simulations , il nous donne la situation actuel du jeu .
                MAX_H : seuil qui nous servira dans les fonctions de calcul
                joueur,adversaire :Nous sert de comparaison pour la méthode Adversaire
                '''
		self.plateau=plateau 
		self.MAX_H = 10000
		self.joueur=joueur 
		self.adversaire=adversaire
 
 
	###############################################
	#LES METHODES SUIVANTES FONCTIONNENT .#########
	def Adversaire(self,j):
		'''Retourne l'adversaire du joueur j'''
	def evaluation(self,joueur):
		'''Retourne la différence de score entre le joueur courant et l'adversaire - sert à evaluer la qualité d'un coup'''
	def AppliqueCoup(self,joueur,case)
		'''Propage un coup à la case case et retourne les cases modifiées par le coup'''
	def AnnuleCoup(self,joueur,case,casesModif)
		'''Annule un coup appliqué à la case case et annule les casesModif'''
	def CoupsPremierPossibles(self,joueur)
		'''Retourne un tableau donnant toutes les cases appartenant à joueur'''
	def CoupsSecondPossibles(self,coupPremier)
		'''Retourne toutes les cases qui seront jouables si l'on clique sur la case coupPremier'''
	###############################################
 
	def DecisionMinMax (self,joueur,p) :
		'''Décide du meilleur coup à jouer par le joueur j dans la situation 
                Début
                  Pour chaque coup de CoupJouables(e,j) faire
                        valeur[coup] = ValeurMinMax(Applique(coup,e),J,false)
                  Fin pour
                  retourner (coup tel que valeur[coup] est maximale)
                Fin'''
 
		coups=self.CoupsPremierPossibles(joueur)
		max=-64
		if not coups:
			meilleurCoup=[False,False]
		else:
			for case in coups :
				coupSecond=self.CoupsSecondPossibles(case)
				for c in coupSecond :
					val=self.AppliqueCoup(joueur,c) #On applique le coup
					if (self.ValeurMinMax(joueur,False,p)>max):
						meilleurCoup=[case,c]
					self.AnnuleCoup(joueur,c,val) #On annule le coup
		return meilleurCoup
 
 
 
 
 
	def ValeurMinMax (self,j,EstUnEtatMax,pmax) :
		'''{ Calcule la valeur de e pour le joueur J selon que e EstUnEtatMax ou pas
                  et pmax la profondeur maximale }
                Début
                  Si PartieGagnante(e,J) Alors retourner(+ValMax)
                  Sinon Si PartiePerdante(e,J) Alors retourner(-ValMax)
                                Sinon Si PartieNulle(e,J) Alors retourner(0)
                                          Sinon 
                                                 Si pmax=0 Alors retourner h(s,J)
                                 Sinon
                                                   vals = vide
                                                   Pour s parmi les successeurs de e faire
                                                          ajouter ValeurMinMax(s,J,not(EstUnEtatMax),pmax-1)) à vals
                                                   Fin pour
                                                   Si EstUnEtatMax
                                                   Alors retourner(maximum de vals)
                                                   Sinon retourner(minimum de vals)
                                                Fin si
                                          Fin si
                                Fin si
                  Fin si
                Fin
                '''
 
		#CAS 1 : FIN DE PARTIE
		if self.plateau.fini(self.Adversaire(j).getScore()): #Si la partie est finie
			if self.evaluation(j)>0: #Si le joueur a gagné
				r=+self.VAL_MAX
			elif self.evaluation(j)<0: #Si le joueur a perdu
				r=-self.VAL_MAX
			else: #égalité entre les deux joueurs
				r=0
		#CAS 2 : PROFONDEUR 0
		elif pmax==0: #Si la profondeur est de 0 : anticipation d'aucun coup - on joue le meilleur coup du moment
			return self.evaluation(j) #On retourn directement la différence de score entre l'Ordinateur et le joueur
		#CAS 3 : PROFONDEUR >0
		else :
			vals = []
			coups=self.CoupsPremierPossibles(j)
			for case in coups :
				coupSecond=self.CoupsSecondPossibles(case)
				for c in coupSecond :
					val=self.AppliqueCoup(j,c) #On applique le coup
					vals.append(self.ValeurMinMax(j,not(EstUnEtatMax),pmax-1))
					self.AnnuleCoup(j,c,val) #On annule le coup
			vals.sort() #Je tri la liste vals par valeur croissantt
			if (EstUnEtatMax):
				r=vals[len(vals)-1]
			else:
				r=vals[0]
 
		return r

J'ai maintenant modifié les méthodes DecisionMinmax() & ValeurMinMax de cette manière :

EXEMPLE2:

Code:

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 ValeurMinMax(self,j,profondeur,EstMax) :
		'''Evalue une situation de jeu pour le joueur j suivant l'algorithme MinMax
                EstMax= évaluation du maximum (meilleur coup de notre part ) et pas une évaluation du minimum (meilleur coup de l'adversaire) '''
 
 
 
		 #CAS 1 : FIN DE PARTIE
		if self.plateau.fini(self.Adversaire(j).getScore()): #Si la partie est finie
			if self.evaluation(j)>0: #Si le joueur a gagné
				return self.MAX_H-self.Adversaire(j).getScore()
 
			elif self.evaluation(j)<0: #Si le joueur a perdu
				return -self.MAX_H+j.getScore()
			else: #égalité entre l'ordinateur et l'adversaire
				return 0
 
 
 
 
		#CAS 2 : PROFONDEUR 0
		elif profondeur==0: #Si la profondeur est de 0 : anticipation d'aucun coup - on joue le meilleur coup du moment
			return self.evaluation(j) #On retourne directement la différence de score entre l'Ordinateur et le joueur
 
 
 
 
 
		#CAS 3 : CALCUL D'UN NOEUD MAX
		elif EstMax: #Si on est en mode max: je calcul le meilleur coup de ma part
			coups=self.CoupsPremierPossibles(j)
			if not(coups):
				return self.ValeurMinMax(j,profondeur-1,False)
			else:
				bscore = -(self.MAX_H+1)
				for case in coups:
 
					coupSecond=self.CoupsSecondPossibles(case)
					for c in coupSecond :
						app=self.AppliqueCoup(j,c)
						score = self.ValeurMinMax(j,profondeur-1,False);
						if score > bscore:
							bscore = score
						self.AnnuleCoup(j,c,app)
				return bscore
 
 
 
 
 
		#CAS 3 : CALCUL D'UN NOEUF MIN		
		else: 
			coups=self.CoupsPremierPossibles(self.Adversaire(j))
			if not(coups):
				return self.ValeurMinMax(j,profondeur-1,True)
			else:
				bscore = +(self.MAX_H+1)
				for case in coups:
					coupSecond=self.CoupsSecondPossibles(case)
 
					for c in coupSecond :
						app=self.AppliqueCoup(self.Adversaire(j),c)
						score = self.ValeurMinMax(j,profondeur-1,False);
						if score<bscore:
							bscore = score
						self.AnnuleCoup(self.Adversaire(j),c,app)
				return bscore
 
 
 
 
 
 
	def DecisionMinMax(self,profondeur,j) :
		'''Décider du coup à jouer en appliquant l'algorithme MinMax'''
		#La profondeur ne peut être inférieure à 1
		if (profondeur<1):
			profondeur=1
		S = -(self.MAX_H+1)
		coups=self.CoupsPremierPossibles(j)
		if not(coups):
			return self.ValeurMinMax(j,profondeur-1,True)
		else:
			meilleurCoup=[False,False]
			for case in coups:
				coupSecond=self.CoupsSecondPossibles(case)
				for c in coupSecond :
					app=self.AppliqueCoup(j,c)
					score = self.ValeurMinMax(j,profondeur-1,False)
					if (score > S) or ((score == S) and (random.randint(0,2)==1)):
						meilleurCoup=[case,c]
						S=score
 
					self.AnnuleCoup(j,c,app)
			return meilleurCoup #NOTRE SAINT GRAAL

Voici le constat :
EXEMPLE1 :
L'algorithme joue pas les coups attendues , ne fait aucune duplication uniquement un unique déplacement de case .

EXEMPLE2 :
Avec une profondeur de 1 l'algorithme marche bien , même trés bien .
Cependant , avec une profondeur supérieur le programme ne joue pas les coups attendues , en totale incohérence avec leniveau demandé .
Autrement dit le #CAS 2 de la méthode ValeurMinMax() de l'exemple 2 fonctionne mais le #CAS 3 et #CAS 4 fonctionnent mal. J'aimerais que vous m'éclairiez pour résoudre mon
problème .

Pour réaliser l'algorithme j'ai pris exemple sur le code de Fabien Torre dans l'exemple 1.
Dans l'exemple 2 j'ai utilisé un algorithme fait par ____ avec son programme Piotellino (qui marche) .

Merci beaucoup pour votre aide .

up :cry:

Bonsoir,
pour espérer une réponse, il faut penser à proposer un exemple simplifié qui cible le problème.

Je ne vois pas comment faire plus simple , ça traite d'un algorithme existant . Merci quand même :(

On a pas tous des compétences dans tous les domaines.

Si je trouve un peu de temps, j'essaierais de me pencher sur ton souci, à condition que tu proposes un ECM, ie un Exemple Complet Minimal, c'est à dire une code utilisable directement.

Ok , c'est vraiment gentil je vais essayer de préparer l'ECM dans le semaine !

Je ne suis pas un expert du MinMax (il m'attend pour dans quelques jours cela dit :P ), mais il y a beaucoup trop de code qui se répète dans vos exemples.

Vous y verrez sans doute plus clair en le simplifiant un peu.

Par exemple, les cas 3 et 4 sont si ressemblants que vous avez copié/collé (grave erreur, soit dit au passage).

À ce propos, votre erreur n'est-elle pas là ? Dans le calcul d'un nœud Min, vous avez oublié d'inverser le EstMax en True à l'appel. Bref...

Code:

score = self.ValeurMinMax(j,profondeur-1,False);

devrait peut-être être

Code:

score = self.ValeurMinMax(j,profondeur-1,True);

Eh oui, le copier/coller... ;)