[R] Encore MinMax

[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!

[TomAijerrie]

Je n'ai pas bien compris le principe de cette fonction.

Quels sont les arguments, que retourne cette fonction ?

[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!

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

[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!

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

[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!