Page 1 sur 1
[R] Encore MinMax
Posté : lun. 18 mai 2015 07:27
par sozary
Bonjour! Alors voilà, j avais il y a un certain temps commencé un algorithme MinMax. Faute de temps et d investigation dans le projet, j avais fini par laisser tomber, malgré l aide que vous m aviez fourni...
M y étant remis depuis peu, je bloque sur un élément: Plusieurs sites me conseils de faire une fonction et une fonction max séparées, alors que moi je voudrais créer une seule fonction minmax (et d autre aussi bien sur). Pour cela, j aimerais donc utiliser la récursivité (que je ne maitrise pas encore très bien). J ai déjà créer ma fonction d évaluation et une fonction qui dit tous les coups possible. Le jeu est Tic Tac Toe.
Ma question est donc: Pourriez vous soit m aider a créer cette fonction, j ai du mal a bien structurer mon programme... Ou alors pour ceux qui le peuvent et le veulent, créer la fonction minmax. Apprendre comment faire une telle fonction et programme serais très enrichissant pour moi!
Merci d avance!
Re: [..] Encore MinMax
Posté : lun. 18 mai 2015 12:14
par TomAijerrie
Je n'ai pas bien compris le principe de cette fonction.
Quels sont les arguments, que retourne cette fonction ?
Re: [..] Encore MinMax
Posté : lun. 18 mai 2015 13:41
par sozary
En fait cette fonction est récursive et renvoi soit le score minimum ou maximum(sur mon ancient poste nommé 'minmax', mikell avait donné un lien très utile!
Re: [..] Encore MinMax
Posté : mar. 19 mai 2015 00:58
par Tlem
Ce que TomAijerrie a essayé de vous dire, c'est que sans le cheminement exact de votre fonction, il va être difficile de vous aider.
Essayez de décrire comment vous voulez utiliser la fonction. Quel est le nombre d'argument envoyé à celle-ci et quel type de retour attendez-vous.
Idéalement montrez nous comment vous envisagez les fonctions Min et Max séparées. Si vous n'avez même pas le début d'un code, essayez de nous faire un schéma ou un organigramme pour nous expliquer le fonctionnement de la fonction que vous voulez créer.
Re: [..] Encore MinMax
Posté : mar. 19 mai 2015 08:19
par sozary
► Afficher le texte
Code : Tout sélectionner
fonction jouer : void
max_val <- -infini
Pour tous les coups possibles
simuler(coup_actuel)
val <- Min(etat_du_jeu, profondeur)
si val > max_val alors
max_val <- val
meilleur_coup <- coup_actuel
fin si
annuler_coup(coup_actuel)
fin pour
jouer(meilleur_coup)
fin fonction
fonction Min : entier
si profondeur = 0 OU fin du jeu alors
renvoyer eval(etat_du_jeu)
min_val <- infini
Pour tous les coups possibles
simuler(coup_actuel)
val <- Max(etat_du_jeu, profondeur-1)
si val < min_val alors
min_val <- val
fin si
annuler_coup(coup_actuel)
fin pour
renvoyer min_val
fin fonction
fonction Max : entier
si profondeur = 0 OU fin du jeu alors
renvoyer eval(etat_du_jeu)
max_val <- -infini
Pour tous les coups possibles
simuler(coup_actuel)
val <- Min(etat_du_jeu, profondeur-1)
si val > max_val alors
max_val <- val
fin si
annuler_coup(coup_actuel)
fin pour
renvoyer max_val
fin fonction
fonction eval : entier
si le partie est finie alors
si joueur a gagné alors
renvoyer 1000-nombre_de_coups
sinon si adversaire a gagné alors
renvoyer -1000+nombre_de_coups
sinon
renvoyer 0
fin si
fin si
renvoyer nb_de_series_de_2_joueur - nb_de_series_de_2_adversaire
fin fonction
Alors voila, ça c est le pseudo code fonctionnel pour réaliser un ia pour le jeu tic tac toe (avec la fction d eval relativement simple). Ce code viens
de open classroom. Donc voila l exemple avec deux fonctions séparées, je ne pourrais pas en revanche vous fournir le code pour la fonction que je voudrais coder tout de suite (étant au lycée pour la journée), je la mettrais donc ce soir sur le forum en revenant!
Re: [..] Encore MinMax
Posté : mar. 19 mai 2015 14:58
par Capablanca
Bonjour,
L'Alpha-Bêta est mieux que le minimax car cela permet d'élaguer l'arbre de manière substantielle.
Tu pourras trouver des explications sur Internet
Le TicTacToe n'est pas un jeu bien compliqué mais en fonction de la profondeur de calcul, tu apprécieras nettement l'Alpha-Bêta.
Cela est d'ailleurs utilisé dans tous les jeux intelligents comme les Echecs, les Dames, Othello, le Go, etc.
Re: [..] Encore MinMax
Posté : mar. 19 mai 2015 22:31
par sozary
► Afficher le texte
Code : Tout sélectionner
#include <array.au3>
Global $TicTacToe[3][3]
$TicTacToe[0][0]="O"
$TicTacToe[1][0]="O"
_ArrayDisplay($TicTacToe)
MsgBox(0,"","Joue en "&_ProchainCoup($TicTacToe,"X",3)&"!")
Func _ProchainCoup($Jeu,$Joueur,$prof)
Local $coups=_ListeDesCoups($Jeu)
Local $LesScore[0]
For $i=0 to UBound($coups)-1
_ArrayAdd($LesScore,_MinMax($Jeu,$coups[$i][0],$coups[$i][1],$Joueur,$prof))
Next
_ArrayDisplay($LesScore)
Return $coups[_ArrayMaxIndex($LesScore)][0]&","& $coups[_ArrayMaxIndex($LesScore)][1]
EndFunc
Func _MinMax($Jeu,$EndroitDuCoup1,$EndroitDuCoup2,$Joueur,$profondeur)
If $profondeur>0 Then
Switch $Joueur
Case "X"
$Jeu[$EndroitDuCoup1][$EndroitDuCoup2]="X"
Local $eval=_EvaluationDuJeu($Jeu)
;_ArrayDisplay($Jeu)
If $eval[0]=0 Then
Dim $eval[0]
Local $coups=_ListeDesCoups($Jeu)
For $i=0 to UBound($coups)-1
_ArrayAdd($eval,_MinMax($Jeu,$coups[$i][0],$coups[$i][1],"O",$profondeur-1))
Next
$point=_ArrayMax($hehe)
MsgBox(0,"",$point)
Return $point
Else
Return _ArrayMax($eval)
EndIf
Case "O"
$Jeu[$EndroitDuCoup1][$EndroitDuCoup2]="O"
Local $eval=_EvaluationDuJeu($Jeu)
;_ArrayDisplay($Jeu)
If $eval[1]=0 Then
Local $point
Local $hehe[0]
Local $coups=_ListeDesCoups($Jeu)
For $i=0 to UBound($coups)-1
_ArrayAdd($hehe,_MinMax($Jeu,$coups[$i][0],$coups[$i][1],"X",$profondeur-1))
Next
$point=_ArrayMin($hehe)
MsgBox(0,"",$point)
Return $point
Else
Return _ArrayMin($eval)
EndIf
EndSwitch
EndIf
EndFunc
Func _EvaluationDuJeu($Jeu)
Local $Score=[0,0] ;Score[0]=Point de X, l autre point de O
#Region X
If $Jeu[0][1]="X" And $Jeu[1][1]="X" and $Jeu[2][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[0][2]="X" And $Jeu[1][2]="X" and $Jeu[2][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[0][0]="X" And $Jeu[0][1]="X" and $Jeu[0][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[0][0]="X" And $Jeu[1][1]="X" and $Jeu[2][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[0][0]="X" And $Jeu[1][0]="X" and $Jeu[2][0]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[1][0]="X" And $Jeu[1][1]="X" and $Jeu[1][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[2][0]="X" And $Jeu[2][1]="X" and $Jeu[2][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
If $Jeu[2][0]="X" And $Jeu[1][1]="X" and $Jeu[0][2]="X" Then
$Score[0]=10
$Score[1]=-10
EndIf
#EndRegion
#Region O
If $Jeu[0][1]="O" And $Jeu[1][1]="O" and $Jeu[2][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[0][2]="O" And $Jeu[1][2]="O" and $Jeu[2][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[0][0]="O" And $Jeu[0][1]="O" and $Jeu[0][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[0][0]="O" And $Jeu[1][1]="O" and $Jeu[2][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[0][0]="O" And $Jeu[1][0]="O" and $Jeu[2][0]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[1][0]="O" And $Jeu[1][1]="O" and $Jeu[1][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[2][0]="O" And $Jeu[2][1]="O" and $Jeu[2][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
If $Jeu[2][0]="O" And $Jeu[1][1]="O" and $Jeu[0][2]="O" Then
$Score[1]=10
$Score[0]=-10
EndIf
#EndRegion
Return $Score
EndFunc
Func _ListeDesCoups($Jeu) ;ça c est ok.
Local $PositionCoup[0][2]
For $i=0 to UBound($Jeu)-1
For $j=0 to UBound($Jeu,2)-1
If $Jeu[$i][$j]="" Then _ArrayAdd($PositionCoup,$i&"|"&$j)
Next
Next
Return $PositionCoup
EndFunc
Ma fonction. J'ai vu l'élagage aussi durant mes recherches, mais j'aimerais beaucoup réussir minmax avant!
Mon problème est de faire remonter les valeurs en fin de parties de la fonction minmax
comme ici!