Livre pour apprendre les algo MinMax et Alpha/beta

Question

Bonjour,

Je voudrais apprendre les bases des l'algorithmes Min/Max et Alpha/Beta avec un bon livre pour débutant ! 

Mon but et de comprendre comment réfléchie une IA pour en developper une dans le cadre d'un morpion ou puissance 4 dans un premier temps.

De plus, si vous connaissez des ressources sur le net qui explique vraiment pas à pas ces deux algos avec si possible un exemple en vb.net ca serait génial :)

Merci à tous

mstarsup5 · Answer

Salut,

Je suis entrain de développer un othello, perso, (à suivre par d'autres jeux) et il ne me manque plus que l'IA justement.
J'ai par ailleurs trouvé cette source: http://vbfrance.com/codes/ALPHA-BETA_24946.aspx 
Je vais essayer de la décortiquer un peu pour voir comment ça marche et en faire une moi même ;-)
C'est en vb6, pas en .net, mais bon ça doit être à peu près pareil pour comprendre je pense :)

fdiedler2000 · Answer

Oui mais pour l'algo alpha/beta, il faut d'abord comprendre l'algo Min/Max :)

Personne ne connait de livre ?

mstarsup5 · Answer

re salut
je viens donc de commencer à faire mes recherches (mon jeu est quasiment terminé, il ne me manque plus que l'IA), et j'ai trouvé ça.
J'ai pas encore lu pour l'algorithme alpha beta, par contre l'algo MinMax est plutôt simple à comprendre:
http://turing.cs.pub.ro/auf2/html/chapters/chapter3/chapter_3_4_2.html

mstarsup5 · Answer

Pour l'algo alpha beta, c'est assez simple aussi apparament, le seul truc difficile est de définir, pour le jeu en question, la loi qui te donne le nombre de points d'une position.(Pour des jeux avec une bonne profondeur de champ, on ne peut pas regarder jusqu'au bout de l'arbre, donc il faut faire cette loi par avance.

fdiedler2000 · Answer

Salut,

J'aais déjà toruvé ce site mais justement j'ai du mal à comprendre c'est pour ca que je cherche désespéremennt un livre dessus...

mstarsup5 · Answer

Re salut, 
En fait c'est assez intuitif comme principe:
Minmax sert à minimiser le pire qui puisse t'arriver (quand c'est à ton adversaire de jouer), et à maximiser tes gains (quand toi tu joues)
AlphaBeta sert à virer des branches de ton arbre dans le cas où tu sais que quoi qu'il arrive: soit ton minimum sera plus grand que celui déjà obtenu (dans ce cas on arrête la recherche dans cette branche), soit ton maximum sera inférieur au maximum déjà obtenu (pareil, dans ce cas là, on arrête la recherche dans cette branche)

si tu veux t'as un algorithme plutôt pratique et parlant:

int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}

et tu lances ton algo sur: Val=AlphaBeta (ProfondeurMax,Scoreminimum-1,Scoremaximum+1)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Yop, j'ai réussi à faire mon IA à plusieurs niveaux pour Othello, grâce à l'algorithme ci-dessus, ça marche impec.
T'as le même "en français" si tu préfères, si tu lances la recherche "alpha beta" sur wikipedia.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Ok je verrais ca ! Mais je recherche toujours un livre sur le thème c'est d'ailleurs l'objet de mon topic :)

mstarsup5 · Answer

Ben... l'algorithme, conceptuellement et physiquement tient en quelques lignes, c'est les liens, etc que je t'ai passé... Ca m'étonnerait franchement que t'aies un livre qui parle plus que 2 pages sur min max, et 2 pages sur alpha beta, alors un livre spécial pour ça...
J'ai cherché, t'as bien des livres contenant (en un chapitre parmis une 50aine) ces deux principes, mais sur ces deux principes précisément, t'apprendras rien de plus qu'avec ce que je t'ai passé dans ces liens, avec ces bouquins...

Enfin bref voila quoi, t'as le choix, soit tu prends ces liens, soit tu achètes un bouquin de 300 pages, avec un truc sur min max et alpha beta qui prend 4 pages sur les 300 du livre, et qui en plus ne t'en dira pas plus que ces liens... A toi de voir :-p

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Bon bah dès les vac de Noel je me plonge sur ces deux algo et on verras bien si je comprends :D

Merci

fdiedler2000 · Answer

Je cherche toujours un livre :(

mstarsup5 · Answer

Salut,

Toujours la même réponse de mon coté, tu peux chercher sur google si tu veux, pour avoir un livre qui parle pendant 3 pages de l'algo et qui contient 300 autres pages sur des trucs qui n'ont aucun rapport avec cet algo.
Fais une recherche sur google, tu trouveras plein de livres du genre.
Par contre, encore une fois, si tu n'as pas envie de dépenser 20? ou plus pour 3 pages, eh bien tu as les liens que je t'avais passé, ou alors continue tes recherches sur internet sur le sujet :D

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Salut,

Certes ;)

Mais comme tu as reussi de ton coté l'algo minimax, pourrais tu me donner ton code en vb.net ? ou dans le langage dans lequel tu programmes en espérant que c'est pas du C++ ou java :D

Ca m'aiderais pas mal car je suis en plein dedans et puis y'a certaines choses que je comprends pas du tout !

merci

mstarsup5 · Answer

Salut, je l'ai programmé en vb6, et le code est assez long, surtout que j'ai fait un truc plutôt compliqué en fait (parce que j'utilise pas mal de variables qui n'ont pas vraiment de rapport avec l'IA à l'intérieur).
Mais je peux te donner l'algorithme "en français" si tu veux :)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

>public function AlphaBeta (byval profondeur as integer, byval alpha as integer, byval beta as integer) as integer
- if profondeur = 0 then 'Si on est arrivé à la profondeur qu'on s'était fixé au début, on évalue la position sur le plateau
   alphabeta= EvaluationDuPlateau 'Il te faut créer ta fonction pour évaluer la position du plateau
   exit sub
endif
- GenereCoupsPossibles() 'La tu fais une fonction qui génère les coups possibles à partir de cette position du plateau (tu peux sauvegarder ces coups possibles dans une liste par exemple)
- Tant que tu n'as pas essayé tous les coups possibles générés par ta fonction ci dessus:
   - Joue un coup de la liste de coups possibles; (modifie le plateau en conséquence)
   - Val = -AlphaBeta(profondeur - 1, -beta, -alpha) 'C'est là l'intérêt de la fonction: tu appelles la fonction au coup suivant, et tu renfermes la valeur de l'évaluation du coup dans Val. Ps: là j'ai utilisé une amélioration de l'algorithme alpha beta qui s'appelle NegaMax: en interchangeant alpha, beta, en leur mettant un signe moins et en mettant un signe moins devant alphabeta, ça évite de faire des tests "si ... alors min.... sinon, max....."
   -AnnuleLeDernierCoupJoue 'il faut revenir à la position avant le test du dernier coup joué pour pouvoir tester les autres coups possibles à partie de la position originale


   -if (val >= beta) then 'Là, c'est dans le cas où une branche de l'arbre est inutile (amélioration apportés par l'algorithme alphabeta par rapport à minmax qui teste toutes les branches de l'arbre, même si on peut savoir dès le départ qu'elles sont inutiles



      AlphaBeta=beta
      exit sub
   Endif
   -if (val > alpha) then 'Ici, c'est si la branche testée est meilleure que eclles testées avant, on prend sa valeur
      alpha = val
      If Profondeur = ProfondeurDeRechercheSouhaitee Then
          MemoriseCoupJoue 'Il faut que tu mettes quelque part que ton programme mémorise le meilleur coup joué quand même ;-)
      End If
   Endif
WhileEnd
AlphaBeta=alpha 'On renvoie alpha (ie: la meilleure valeur testée)
end function

Pour appeler ta fonction alphabeta, fais comme suit:


Score = AlphaBeta(ProfondeurDeRechercheSouhaitee, scoreminimumpossible, scoremaximumpossible)








 Pour
apprendre
toujours
plus!

mstarsup5 · Answer

J'ai tout écrit à la main, je pense que c'est assez compréhensible et très facilement réutilisable pour ton programme. Cela dit, pour une meilleure compréhension de l'algo en lui même, je te reconseille les liens que je t'avais passé : D

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Merci mais c'est l'algo alpha/beta que tu m'a donnée et moi je comprends deja pas le minmax donc je suis pas prete de comprendre celui la. Je voulais le détail de l'algo MinMax et pas celui de l'alpha/beta...

Ca sert à rien de commancer compliqué si je comprends pas le plus simple !

mstarsup5 · Answer

Tu m'as demandé mon algo, j'ai utilisé l'alpha beta pour le mien, le min max n'étant pas performant du tout.

le min max, il y a deux concepts...
tout d'abord, si c'est à toi de jouer, tu vas choisir le coup qui te donne le plus de points parmis tes coups possibles... là tu maximises.
si c'est à ton adversaire de jouer, il faut que tu fasses comme si lui jouait le meilleur coup pour lui, celui qui te fait le plus mal (donc pour toi, celui ou tu as le moins de points), et là tu minimises.
En fin de compte:
imagine que c'est à toi de jouer, et que tu fais une recherche de profondeur 3.
(ie: on regarde: ton premier coup, son premier coup, et ton deuxième coup).
-Tu testes toutes les positions accessibles en 3 coups(1 coup toi, un coup lui, puis un coup toi).
De là tu te dis:
- ton deuxième coup doit être le meilleur coup possible.
donc là on maximise le score sur ce coup là.
- on remonte d'un cran dans l'arbre, là c'est à lui de jouer.
son meilleur coup te fait avoir un minimum de points (il joue bien et maximise ses points à lui).
On prend donc le minimum à cet étage.
-on remonte encore d'un cran: là c'est ton premier coup.
Tes coups possibles valent chacun un certain nombre de points: les minimums calculés avant.
Parmi ces minimum, il te faut prendre celui qui sera le plus bénéfique pour toi: celui au score maximum.
Il te faut donc prendre le maximum des minimums calculés précédemment.

Là c'est fini, tu as trouvé ton meilleur coup.
Simple :-)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah, la différence entre minmax et alphabeta, c'est que l'alpha beta enlève des tests inutiles:
Si tu dois prendre le maximum de plusieurs nombres, et que tu sais d'avance que l'un d'entre eux sera inférieur à au moins un autre de ces nombres, c'est pas besoin de faire tous les calculs pour connaître exactement sa valeur.
De même, si tu dois prendre le minimum de plusieurs nombres et que tu sais d'avance que l'un d'entre eux sera supérieur à au moins un autre de ces nombres, pas besoin de faire tous les calculs pour avoir sa valeur exacte.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Le pire c'est que j'ai compris le concept mais j'y arrive pas !

Voila mon code pour les procédures CalcMin et CalcMax :

Private Function calcMax(ByVal prof As Integer) As Integer
        Dim max As Integer = MINEVAL
        Dim tmp As Integer

        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMin(prof - 1)
                        If tmp > max Then
                            max = tmp
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next

            Return max
        End If
    End Function
    Private Function calcMin(ByVal prof As Integer) As Integer
        Dim min As Integer = MAXEVAL
        Dim tmp As Integer

        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMax(prof - 1)
                        If tmp < min Then
                            min = tmp
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next

            Return min
        End If
    End Function

Mais bon j'y arriverais pas de toute manière donc je crois que je vais abandonné. Il me faudrait un exemple en vb.net mais c'est introuvable.

mstarsup5 · Answer

Faut pas abandonner.
J'ai pas le temps de regarder ce soir, mais j'y jèterai un coup d'oeil plus tard si tu veux.

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Je reviens sur ce que j'ai dit, j'y ai jeté un coup d'oeil, ça m'a l'air bon comme ça (si tes fonction simulecoup, annulecoup et evalposition sont bonnes, si "If Grid1.Cell(i, j).BackColor = Color.White" ça veut bien dire qu'un coup est jouable, et si la syntaxe est bonne aussi (je programme pas en VB2005, donc je ne connais pas la syntaxe))

Te manque plus qu'à:
-Sauvegarder le meilleur coup à jouer pour ton IA là dedans (voir l'algo que je t'ai filé y'a quelques minutes, ça y est dedans et c'est exactement pareil)
-Lancer ton programme minmax avec les bons paramètres
-Faire que l'IA joue le coup sauvegardé

L'algo a l'air bon en tout cas, donc abandonner comme tu veux le faire, ça sert à rien :)

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Justement j'ai des gros problèmes avec la fonction eval...

Voila l'algo complet :
    Private Const MINEVAL As Integer = -1000
    Private Const MAXEVAL As Integer = 1000

    Private Sub calculIA(ByVal prof As Integer)
        Dim maxcourant As Integer = MINEVAL
        Dim tmp, max_i, max_j As Integer
        Dim coup As PictureBox = Nothing

        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()
        If Not prof 0 Or IsFinish() False Then
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMin(prof - 1)
                        If tmp > maxcourant Then
                            maxcourant = tmp
                            max_i = i
                            max_j = j
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next

            coup = convert1(max_i, max_j)
            PlacerPion(J2, coup)
            turn = 1
        End If
    End Sub
    Private Function calcMax(ByVal prof As Integer) As Integer
        Dim max As Integer = MINEVAL
        Dim tmp As Integer

        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMin(prof - 1)
                        If tmp > max Then
                            max = tmp
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next

            Return max
        End If
    End Function
    Private Function calcMin(ByVal prof As Integer) As Integer
        Dim min As Integer = MAXEVAL
        Dim tmp As Integer

        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMax(prof - 1)
                        If tmp < min Then
                            min = tmp
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next

            Return min
        End If
    End Function

Globalement, ca c'est bon je pense mais la fonction eval, je n'arrive pas à la faire ! Parce que je pense que mes fonctions "simulation" et "annuler" sont fausses.

Je ne sais pas à quel moment je dois simuler le joueur... enfin je comprends pas grand chose !

PS : Oui, si la couleur de la cellule est blanche alors c'est un coup possible, sinon la case est déjà occupé.

Merci pour tous en tout cas.

fdiedler2000 · Answer

En fait, je crois que je me prends la tete. On va essayer de la faire en francais avant de le programmer !

Donc,
1) Que dois je faire dans la simulation du coup ?
2) Que dois je faire dans l'annulation du coup ?
3) Que dois je faire dans la fonction d'évaluation appelée lorsque le jeu est fini ou que la profondeur est atteinte ?

Je sais qu'a un moment, je dois changer le joueur courant (une fois c'est un coup de l'IA qui est simmulé et une fois c'est le coup du joueur qui est simulé).

Par convention dans mon programme,

3 types de cases :
-  Rouge ===> c'est le joueur qui joue les "rond" (humain)
-  Verte ===> celui qui joue les Croix (IA)
-  Blanche ====> la case est libre

Voila, si tu as un peu de temps pour m'aider, je t'en remercie par avance :)

mstarsup5 · Answer

Ben
-Là apparamment tu veux faire ta fonction eval pour le morpion, c'est simple:
si l'ordi gagne à la position de ton évaluation, ça fait +1 point.
si son adversaire gagne, ça fait -1
sinon, 0.
-Fonction simulation du coup, il faut que tu "joues le coup simulé": que ton plateau (pas graphiquement, mais dans tes données), le coup soit joué.
-Fonction d'annulation du coup: exactement l'inverse, le coup qui a été joué doit être annulé pour que la position redevienne exactement ce qu'elle était avant que le coup soit joué

Exemple:
Position de départ:
_ _O
XX_
_ _O  
simulation d'un coup:
_ XO
XX
_ O_
annulation du coup:
_ _O
XX_
_ O_
(on est revenu à la position précédente)

Juste 3 trucs:
-le plateau du morpion a 9 cases, et peu de possibilités de coups, donc tu peux direct demander une profondeur de 9
-quand tu fais l'appel à l'IA, c'est toujours l'IA qui joue, donc tu commences toujours par une maximisation. 
Ton sub CalculIA ne sert donc à rien, il suffit d'appeler Score=calcmax(9)  'Je t'ai dit qu'une profondeur de 9 était nécessaire ici)
-Dernière chose: nulle part il y a dans calcmax ou calcmin un bout de code enregistrant le coup à jouer. (sachant que le premier coup est une maximisation, je t'aide, il faut placer ça dans calcmax, cf le code que je t'ai donné en début de soirée). Sans ça, y'a pas moyen de savoir quel coup est le bon: calcmax et calcmin te donneront à la fin le score du meilleur coup, mais pas le coup lui même.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Salut,

- La meilleur coup est normalement enregistré dans la fonction  calcIA qui est necessaire à mon sens... Les coordonnées sont :
    max_i = i
    max_j = j

- Pour le coup simulé et l'annulation j'ai compris mais je voulais savoir à quel moment dois je changer de joueur ? (après avoir simulé le coup ?) et lorsque j'annule le coup , est ce que je dois rechanger le joueur courant ou alors je touche à rien ?

-  Ta fonction eval est trop simple je pense, car c'est l'évaluation en fin de partie que tu m'a donnée. En effet, en milieu de partie, je faut évaluer la position avec le nombre de pions...

Je te donne le lien sur lequel je travaille :
http://fearyourself.developpez.com/tutoriel/sdl/morpion/part6/#L3

mstarsup5 · Answer

La meilleur coup est normalement enregistré dans la fonction  calcIA qui est necessaire à mon sens... Les coordonnées sont :
    max_i = i
    max_j = j

<---- Ca je suis d'accord, tu mets ce même bout de code dans calcmax, quand prof=profondeurRecherchee, tu fais un simple appel sur Score=calcmax(9) dans ton sub d'IA principal, et tu peux virer ton calculIA qui ne sert strictement à rien d'autre qu'à alourdir le code.
D'autant plus que tu as fait cette fonction:    Private Sub calculIA(ByVal prof As Integer)
D'où mes questions:
1 - Où est l'initialisation?
2 - A quoi sert de vouloir faire une fonction récursive sur un sub qui va appeler ta fonction min max?
3 - Si tu fais une fonction récursive, où initialises tu l'appel de ta fonction? (en d'autres termes: à quoi elle sert, vu que tu pourrais au lieu d'initialiser calculIA, initialiser calcmax directement.
Il te suffit de faire un sub (j'insiste) et d'y mettre Score=calcmax(9), sans oublier d'enregistrer le coup dans calcmax.

- Pour le coup simulé et l'annulation j'ai compris mais je voulais savoir à quel moment dois je changer de joueur ? (après avoir simulé le coup ?) et lorsque j'annule le coup , est ce que je dois rechanger le joueur courant ou alors je touche à rien ?
Forcément, si un coup est joué, c'est à l'autre joueur de jouer...

-  Ta fonction eval est trop simple je pense, car c'est l'évaluation en fin de partie que tu m'a donnée. En effet, en milieu de partie, je faut évaluer la position avec le nombre de pions...
Si on y réfléchit 2 minutes, je t'ai bien dit qu'une profondeur de 9 au départ arrivait quoi qu'il arrive à trouver tous les chemins possibles (Morpion: 9 cases, donc au bout de 9 coups, le plateau est remplis...).
Dans ce cas là, soit tu gagnes, soit ton adversaire gagne, soit personne gagne, c'est pas plus compliqué...
Cela dit, si tu veux t'enquiquiner à essayer de trouver une autre fonction d'évaluation (comment vas tu évaluer, sur quels critères??), libre à toi :-)

Sur ce, bonne continuation et joyeux noël !!!

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah, et juste un truc: sur ton lien (j'ai trouvé ça en 20 secondes hein) Pour résoudre ce problème, nous savons que nous devons utiliser la fonction d'évaluation. Comme évaluation basique nous allons définir:

évaluation(jeu) 1000 si l'IA a gagné

évaluation(jeu) -1000 si l'IA a perdu

évaluation(jeu) = 0 sinon

Dans son algorithme après, le seul truc qu'il a rajouté, c'est pour s'il a deux chemins pour gagner il prendra le plus court. Par contre, je remarque qu'il te donne la même chose pour calculIA, mais franchement, même s'il te donne ça, ça ne me fait pas changer d'avis sur le sujet: c'est inutile :) Pourapprendretoujoursplus!

mstarsup5 · Answer

Private sub IA()

'Là tu initialises toutes tes données, comme tu l'as fait dans ta fonction calculIA

dim Score as integer

Score=calcmax(9) 'Ou une profondeur que tu veux, peu importe...
'La tu fais jouer le coup à ton IA

End Sub


Public Function calcMax(ByVal prof As Integer) As Integer
        Dim max As Integer = MINEVAL
        Dim tmp As Integer
        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMin(prof - 1)
                        If tmp > max Then
                            max = tmp
                            If prof=profondeurdepart then
                              max_i = i
                              max_j = j
                            EndIf
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next
            Return max
        End If
    End Function

    Public Function calcMin(ByVal prof As Integer) As Integer
        Dim min As Integer = MAXEVAL
        Dim tmp As Integer
        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMax(prof - 1)
                        If tmp < min Then
                            min = tmp
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next
            Return min
        End If
    End Function

Une Fonction Eval

Une fonction Simule coup

Une fonction Annule coup

Et c'est gagné :D

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Je suis peut etre très bete mais je ne vois pas du tout comment supprimer la fonction CalcIA !

    Private Sub mz()
        'calculIA(9)
        Dim maxcourant As Integer = MINEVAL
        Dim tmp, max_i, max_j As Integer

        tmp = calcMin(9)
        If tmp > maxcourant Then
            maxcourant = tmp
        End If

        'et comment récupérer les coordonnées de la meilleur case ?
    End Sub

Je n'arrive pas à récupérer les bonnes coordonnées et puis il faut pas les sauvegarder dans la fonction MAX ou MIN d'où l'interet du sub CalcIA.

SInon effectivement, si on met une profondeur de 9 alors ta fonction eval est correcte mais si on met 7 (pour un computer niveau moyen ca ne marche plus !) Bref de toute manière on va deja essayer de le faire marcher avec une profondeur de 9 et donc voici ma fonction eval :

 If WhoWin() = "CROIX" Then ' IA a gagné
                Return 1000
            ElseIf WhoWin() = "ROND" Then 'joueur a gagné
                Return -1000
            Else 'partie nulle
                Return 0
            End If

Une autre question, dans ma fonction "simulation", je vérifie à l'aide d'un boolean si quelqu'un à gagné. Cependant, je ne sais pas quoi faire de ce résultat...

Voici la fonction SImulation :

Private Sub Grid1_CellClick(ByVal Row As Integer, ByVal Col As Integer, ByVal Header As LameGrid.HeaderInfo) Handles Grid1.CellClick
        If Grid1.Cell(Row, Col).BackColor = Color.White Then 'si le coup est possible
            Grid1.Cell(Row, Col).BackColor = couleur 'on le joue

            If IsWinner(couleur) = True Then 'vérifie si qq1 à gagné
                '  MsgBox(WhoWin)
            End If

            If couleur = Color.Red Then 'si c'est le joueur ROND alors c'est aux CROIX de jouer
                couleur = Color.Green
            ElseIf couleur = Color.Green Then 'et vice versa
                couleur = Color.Red
            End If
        Else
            MsgBox("impossible case non vide")
        End If
    End Sub

Voici la fonction "annuler"

    Private Sub annuler(ByVal row As Integer, ByVal col As Integer)
        Grid1.Cell(row, col).BackColor = Color.White 'on annule le coup

        If couleur = Color.Red Then 'et on change de nouveau dans l'autre sens le tour du joueur
            couleur = Color.Green
        ElseIf couleur = Color.Green Then
            couleur = Color.Red
        End If
    End Sub

Normalement avec tout ca, ca devrait marcher pourtant l'IA parfois joue bien ! et parfois joue mal !! J'ai l'impression qu'il préfère me contrer que de gagner directement. (je joue mal exprès).

fdiedler2000 · Answer

Si tu as Visual Studio Express (gratuit), je peux te donner mon projet en vb.net 2005 et puis je te commente toutes les lignes pour que tu comprennes le code, ca sera peut etre plus facile non ?

mstarsup5 · Answer

désolé, je n'ai pas visual studio express, et je n'ai jamais programmé en vb.net, donc je ne pense pas être plus utile qu'ici sur le forum malheureusement :/

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Re salut,

Je suis peut etre très bete mais je ne vois pas du tout comment supprimer la fonction CalcIA !
<--- Je t'ai donné la fonction dans mon précédent post: le sub IA.
Il te dit comment appeler la fonction (par un calcmax, et non pas un calcmin comme je le vois ici), et comment implémenter la récupération des données dans ton calcmax.
Si tu récupères les données dans le calcmax et lances tout d'abord un calcmin, ça pose problème, tu ne trouves pas?
De plus:
Private Sub mz()
        'calculIA(9)
        Dim maxcourant As Integer = MINEVAL
        Dim tmp, max_i, max_j As Integer

        tmp = calcMin(9)
        If tmp > maxcourant Then
            maxcourant = tmp
        End If

        'et comment récupérer les coordonnées de la meilleur case ?
    End Sub
<---- Tout ça je l'ai mis dans le sub IA, sauf la récupération de la meilleure case qui se fait au premier étage de la fonction calcmax.

SInon effectivement, si on met une profondeur de 9 alors ta fonction eval est correcte mais si on met 7 (pour un computer niveau moyen ca ne marche plus !) 
<--- Si si  :)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Si tu veux, je vais essayer de l'expliquer différemment, ton algo de calcul est bon. Si tes algorithmes pour simuler et annuler sont bons, et si la fonction qui vérifie si un coup est jouable ou non est bon (à toi de vérifier que ça marche en faisant par exemple des temps morts dans ta fonction), il te suffit de lancer cet algorithme.
Quand c'est à l'IA de jouer, il faut:
-initialiser les données (ça tu l'as fait)
-lancer l'algorithme (c'est à l'IA de jouer, donc il faut que tu maximises, et pas que tu minimises comme tu le proposes plus haut), soit faire un calcmax(ProfondeurSouhaitee)
les fonctions calcmax et calcmin te trouvent alors le meilleur chemin, et le premier calcmax lancé va te renvoyer le meilleur coup à jouer.
-Il ne te reste plus qu'à jouer ce coup, et c'est gagné.


(Et ta fonction Eval est bonne, (en supposant que Whowin te renvoie le bon résultat, bien sûr :) ))

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Bon, donc pour l'initialisation de l'IA :

Private Sub mz()
        Dim maxcourant As Integer = MINEVAL
        Dim tmp, max_i, max_j As Integer

        tmp = calcMax(9) 'lance l'algo avec profondeur 9
        If tmp > maxcourant Then
            maxcourant = tmp
        End If
    End Sub

Le soucis, c'est que CalcMAX et calcMIN sont des fonctions et retournent un Integer. Il est donc impossible de récupérer le meilleur coup sous forme de coordonnées (row et col)... De plus je récupère dans mon sub "mz", un integer MAXCOURANT mais il sert à rien ?

Mais pourquoi alors sur le lien :
http://fearyourself.developpez.com/tutoriel/sdl/morpion/part6/#L5.3.b

il lance d'abord un CalcMIN et puis il boucle sur tous les coups possibles alors que ta solution propose de lancer un CalcMAX sans lister les coups possibles...

J'y pert mon latin ! :(

Sinon les algos sont correctes, je les ai testé avec une partie humain VS humain. Cependant, dans ma fonction "SIMULER COUP" :

If Grid1.Cell(Row, Col).BackColor = Color.White Then 'si le coup est possible
            Grid1.Cell(Row, Col).BackColor = couleur 'on le joue

            If IsWinner(couleur) = True Then 'vérifie si qq1 à gagné
                MsgBox(WhoWin)
            End If

            If couleur = Color.Red Then 'si c'est le joueur ROND alors c'est aux CROIX de jouer
                couleur = Color.Green
            ElseIf couleur = Color.Green Then 'et vice versa
                couleur = Color.Red
            End If
        Else
            MsgBox("impossible case non vide")
        End If

Est ce que la partie en rouge, est nécessaire ? et qu'est ce que je dois en faire lors de la simulation de l'IA ?

Désolé mais je suis très débutant !

mstarsup5 · Answer

Bon...
On va (re)faire étape par étape...

Je t'ai écrit (copier coller):

Private sub IA()
'Là tu initialises toutes tes données, comme tu l'as fait dans ta fonction calculIA
dim Score as integer
Score=calcmax(9) 'Ou une profondeur que tu veux, peu importe...
'La tu fais jouer le coup à ton IA
End Sub

(ou encore écrit (copier coller)):

Quand c'est à l'IA de jouer, il faut:
-initialiser les données (ça tu l'as fait)
-lancer l'algorithme (c'est à l'IA de jouer, donc il faut que tu maximises, et pas que tu minimises comme tu le proposes plus haut), soit faire un calcmax(ProfondeurSouhaitee)
les fonctions calcmax et calcmin te trouvent alors le meilleur chemin, et le premier calcmax lancé va te renvoyer le meilleur coup à jouer.
-Il ne te reste plus qu'à jouer ce coup, et c'est gagné.

Toi tu me réponds:

Private Sub mz()
        Dim maxcourant As Integer = MINEVAL
        Dim tmp, max_i, max_j As Integer
        tmp = calcMax(9) 'lance l'algo avec profondeur 9
        If tmp > maxcourant Then
            maxcourant = tmp
        End If
    End Sub

Alors ce qu'il y a en rouge ne sert à rien: tu fais un appel sur calcmax et c'est tout, pas besoin de comparer quoi que ce soit. Et surtout, chose flagrante dans ton sub: tu ne joues pas de coup...
Ce qu'il y a en rose, mets le en variables globales, sinon tu vas avoir du mal à sauvegarder les coordonnées du meilleur coup.

Ensuite, tu me dis:

Le soucis, c'est que CalcMAX et calcMIN sont des fonctions et retournent un Integer. Il est donc impossible de récupérer le meilleur coup sous forme de coordonnées (row et col)... De plus je récupère dans mon sub "mz", un integer MAXCOURANT mais il sert à rien ?

Alors là, je te renvoie à un truc que je t'ai déjà dit et fait:
(Ancien post, page 3...):

Public Function calcMax(ByVal prof As Integer) As Integer
        Dim max As Integer = MINEVAL
        Dim tmp As Integer
        'joueur courant
        Dim joueur As joueur = getcurrentjoueur()        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For i As Integer = 0 To 2
                For j As Integer = 0 To 2
                    If Grid1.Cell(i, j).BackColor = Color.White Then
                        simuler(i, j, joueur.pion)
                        tmp = calcMin(prof - 1)
                        If tmp > max Then
                            max = tmp
                            If prof=profondeurdepart then
                              max_i = i
                              max_j = j
                            EndIf
                        End If
                        annuler(i, j, joueur.pion)
                    End If
                Next
            Next
            Return max
        End If
    End Function

(Remarque bien ce qu'il y a écrit en rouge... La récupération des coordonnées du coup se fait là, au premier étage de l'algorithme... profondeurdepart vaut ici 9 puisque tu le fais sur une profondeur de 9 au lancement..)


Pour ta dernière question:

Est ce que la partie en rouge, est nécessaire ? et qu'est ce que je dois en faire lors de la simulation de l'IA ?

Non, pas nécessaire pour cette partie de l'IA puisque ça serait quand même chiant que tu reçoives un message à chaque fois que l'IA a trouvé un chemin menant à la victoire de quelqu'un... (ce qui arrive assez souvent)

Et juste un dernier truc que j'ai remarqué:
tes MINEVAL et MAXEVAL doivent être strictement inférieur (respectivement supérieur) au min (resp. au max) de l'évaluation possible.
En réalité, il faudrait leur donner pour valeur -infini et +infini.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Donc au final :

    Private Sub mz()
        'calculIA(9)
        Dim maxcourant As Integer = MINEVAL
        calcMax(9) 'lance l'algo avec profondeur 9
        Grid1_CellClick(max_i, max_j, Nothing) 'joue le coup meilleur
    End Sub

    Private Function calcMax(ByVal prof As Integer) As Integer
        Dim max As Integer = MINEVAL
        Dim tmp As Integer
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For row As Integer = 0 To 2
                For col As Integer = 0 To 2
                    If Grid1.Cell(row, col).BackColor = Color.White Then
                        Simuler(row, col)
                        ' MsgBox("simulé calcMAX")
                        tmp = calcMin(prof - 1)
                        If tmp > max Then
                            max = tmp
                            If prof = 9 Then
                                max_i = row
                                max_j = col
                            End If
                        End If
                        annuler(row, col)
                        ' MsgBox("annulé calcMAX")
                    End If
                Next
            Next

            Return max
        End If
    End Function
    Private Function calcMin(ByVal prof As Integer) As Integer
        Dim min As Integer = MAXEVAL
        Dim tmp As Integer
        If prof 0 Or IsFinish() True Then
            Return eval()
        Else
            For row As Integer = 0 To 2
                For col As Integer = 0 To 2
                    If Grid1.Cell(row, col).BackColor = Color.White Then
                        Simuler(row, col)
                        ' MsgBox("simulé calcMIN")
                        tmp = calcMax(prof - 1)
                        If tmp < min Then
                            min = tmp
                        End If
                        annuler(row, col)
                        '  MsgBox("annulé calcMIN")
                    End If
                Next
            Next

            Return min
        End If
    End Function

Pourtant ca marche toujours pas... l'IA est assez bizarre...

Ya t-il un moyen de voir ou ca bloque ?

PS : Dans ma fonction "simuler", je me contente seulement de jouer le coup et je ne vérifie pas la position ce qui me parair bizarre :

Private Sub Simuler(ByVal row As Integer, ByVal col As Integer)
        If Grid1.Cell(row, col).BackColor = Color.White Then 'si le coup est possible
            Grid1.Cell(row, col).BackColor = couleur 'on le joue

            If couleur = Color.Red Then 'si c'est le joueur ROND alors c'est aux CROIX de jouer
                couleur = Color.Green
            ElseIf couleur = Color.Green Then 'et vice versa
                couleur = Color.Red
            End If
        Else
            MsgBox("impossible case non vide")
        End If
    End Sub 

Merci pour le temps passé sur mon problème !

mstarsup5 · Answer

Re,

Mets tes msgbox sans le " ' " pour voir déjà si l'ordi essaie toutes les possibilités.
(On va regarder pas à pas si tout va bien)

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Oui ca teste plein de truc mais impossible de savoir si c'est correcte ou pas. En mettant les MSGBOX seulement dans le MAX, j'obtient les schemas :

J'ai joué en (0,0) (la case rouge).

LE CPU à la couleur verte. Le reste est de la simulation.

Ensuite, il commance à annulé les coups puis à simuler... Aucun moyen de savoir. Je peux te compiler l'exe et la dll pour que tu vois si tu veux ?

mstarsup5 · Answer

Ok :)

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Donc dans le ZIP il y a 3 exe :

- Le premier avec des stops sur le MAX
- Le 2eme avec des stops sur le MAX et MIN
- Le dernier avec aucun stops

Voila le lien :
http://www.zonegeeks.com/temp/minmax.zip

fdiedler2000 · Answer

j'ai oublié de préciser :

Tu joue ton coup et ensuite tu cliques sur "IA" et ainsi de suite :)

mstarsup5 · Answer

Ps: dans la compilation, mets moi aussi le msgbox dans le min stp.
pour l'adresse email, demande moi en pv.
Ps: je pars chez mes parents demain vers 14h, et j'aurai plus le net pendant une dizaine de jours après (et encore après, j'ai des partiels) donc je risque de pas répondre pendant un temps..

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Cool, je regarde ça.

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah, moins cool de suite, j'ai un mesage d'erreur en lançant tes .exe...

(message d'erreur: L'application n'a pas réussi à s'initialiser correctement (0xc0000135). Cliquez sur OK pour arrêter l'application)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

(Et un truc bizarre: j'arrive pas à installer ta dll, c'est la première fois que ça me fait ça lol...)

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

la dll ne s'installe pas, il suffit de lancer l'exe mais la dll doit etre dans le meme répertoire que le .exe

Aussi il faut télécharger le framework 2.0 !
Dispo sur mon site :
http://www.zonegeeks.com/site/telechargements.php

fdiedler2000 · Answer

J'avais pas lu ton message d'erreur, ca veut dire que le Framework 2.0 n'est pas installé, prend le sur mon site et ensuite ca marchera. Ne t'occupe pas de la DLL, c'est pas comme en vb6 ou il faut l'enregistré ^^

mstarsup5 · Answer

Framework 2.0, ça sert à quoi?

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

C'est la packtage qui permet d'utiliser les classes en .net
C'est malheuresement indispensable pour lancer des appli créer en .net

Par exemple pour utiliser le classe System.IO ou System.Net, on a besoin du Framework et la version 2.0 correspond à la version 2005 de Visual Basic :)

mstarsup5 · Answer

Re,
Le moins qu'on puisse dire, c'est que le programme buggue un peu :-p
Je regarde

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Question: tu as mis MINEVALmaximum possible de l'évaluation?) (et pas >= ni <=?) J'essaie de voir pourquoi dans l'exe que tu m'as passé y'a un moment ou je tombe sur une boucle infinie, ça veut forcément dire qu'il y a un problème dans l'algo min max. Pourapprendretoujoursplus!

mstarsup5 · Answer

Quoi que... j'avais oublié que c'était du min max et pas du alpha beta... c'est pas une boucle infinie que j'obtiens, mais un truc qui prend très très longtemps...

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Eu mes constantes sont :
  Private Const MINEVAL As Integer = -1000
    Private Const MAXEVAL As Integer = 1000

Mais je peux mettre ca :
  Private Const MINEVAL As Integer = -100000
    Private Const MAXEVAL As Integer = 100000

Ca me change rien ...

mstarsup5 · Answer

Il vaut mieux.
j'y jette un oeil si j'ai le temps dans une heure, sinon, ben à dans 10 jours au moins ^^"

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

ok lol ;)

fdiedler2000 · Answer

Pourtant selon je lien que je t'ai donné :
Si la partie est terminée alors
    Si c'est une égalité, alors on retourne 0
    Sinon
        Si l'ordinateur a gagné, alors retourne 1000 (le maximum possible);
        Sinon l'ordinateur a perdu, alors retourne -1000 (le minimum possible);
        Fin Si
    Fin Si
Sinon 
    Soit la somme = 0
    Pour chaque ligne, chaque colonne, chaque diagonale,
       S'il y au moins un pion de chaque joueur, on ne fait rien
       Sinon
            S'il y a 2 pions de l'adversaire, on enlève 30 à somme
            sinon s'il y a 2 pions du joueur de l'IA, on ajoute 30 à somme
            sinon s'il y a 1 pion de l'adversaire, on enlève 10 à somme
            sinon s'il y a 1 pion de l'IA, on ajoute 10 à somme
            Fin Si 
       Fin Si
    Fin Pour

Il ont l'air de dire qu'il faut donner +1000 quand l'IA gagne et -1000 quand il pert et que c'est le max (resp. min) possible.
Donc, les constantes ne doivent etres pas etre égales ?
Fin Si

fdiedler2000 · Answer

Pourtant selon je lien que je t'ai donné :
Si la partie est terminée alors
    Si c'est une égalité, alors on retourne 0
    Sinon
        Si l'ordinateur a gagné, alors retourne 1000 (le maximum possible);
        Sinon l'ordinateur a perdu, alors retourne -1000 (le minimum possible);
        Fin Si
    Fin Si
Sinon 
    Soit la somme = 0
    Pour chaque ligne, chaque colonne, chaque diagonale,
       S'il y au moins un pion de chaque joueur, on ne fait rien
       Sinon
            S'il y a 2 pions de l'adversaire, on enlève 30 à somme
            sinon s'il y a 2 pions du joueur de l'IA, on ajoute 30 à somme
            sinon s'il y a 1 pion de l'adversaire, on enlève 10 à somme
            sinon s'il y a 1 pion de l'IA, on ajoute 10 à somme
            Fin Si 
       Fin Si
    Fin Pour

Il ont l'air de dire qu'il faut donner +1000 quand l'IA gagne et -1000 quand il pert et que c'est le max (resp. min) possible.
Donc, les constantes ne doivent etres pas etre égales ?
Fin Si

mstarsup5 · Answer

Dans ce qu'on a mis, on a mis un < et un >, donc si jamais on a égalité, le coup ne sera pas pris.

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Re

Dans tes fcts calcmax et calcmin remplace le Return eval() par
tmp=eval()
msgbox str(prof) & "," & str(eval)
return tmp

(pour voir ce qu'il se passe).
Merci

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Ah tu veux dire la :
  If tmp > max Then

C'est pour éviter le   If tmp = max Then qu'on change la valeur des const ?

fdiedler2000 · Answer

C'est fait :
http://www.zonegeeks.com/temp/minmax2.zip

mstarsup5 · Answer

Euh... c'est con ce que je t'ai dit...
Dans tes fcts calcmax et calcmin remplace le Return eval() par
tmp=eval()
msgbox "1" & "," & str(prof) & "," & str(eval)
return tmp
puis dans calcmax, avant le return max, mets msgbox "2" & "," & str(prof) & "," & str(max)
puis dans calcmin, avant le return min, mets msgbox "3" & "," & str(prof) & "," & str(min)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah tu veux dire la :
  If tmp > max Then

C'est pour éviter le   If tmp = max Then qu'on change la valeur des const ?


Ben en fait, si on trouve un coup équivalent, ça sert à rien de changer celui qu'on avait déjà trouvé, d'où le > au lieu de >=
Par contre, si tous les coups possibles valent -1000, on va se faire niquer sachant qu'à chaque fois on va avoir une égalité (et dans ce cas là, aucunes coordonnées de coup ne sera choisie, ce qui est embêtant ;-)  )

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

L'archive a été mise à jour le lien est le meme que avant

mstarsup5 · Answer

Salut,
Un problème flagrant: ton algo ne s'arrête pas s'il y a un gagnant: il continue à jouer des coups après...
Elle sert à quoi ta fonction IsFinish()?

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

IsFinish permet de savoir si le jeu est fini (toutes les cases sont remplies) mais ne vérifie pas qui est gagnant !

La fonction IsWinner avec comme argument une couleur permet de vérifier si les ROND (couleur rouge) ont gagné ou si les CROIX (couleur vert) ont gagné. Elle retourne un Boolean : True si la couleur en question a gagné sinon False.

Ai je fais une erreur ?

mstarsup5 · Answer

Il faut que isfinish, quand tu l'appelles dans calcmin ou calcmax te renvoie true si le plateau est rempli, ou si un joueur gagne, sinon, ça va faire n'importe quoi comme maintenant...
Renvoie moi le fichier quand ça ça sera changé déjà ^^"

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

C'est fait :
http://www.zonegeeks.com/temp/minmax2.zip

fdiedler2000 · Answer

Explication donc de la fonction IsFinish :

    Private Function IsFinish() As Boolean
        Dim res As Integer = 0

        For row As Integer = 0 To 2
            For col As Integer = 0 To 2
                If Grid1.Cell(row, col).BackColor = Color.White Then
                    res = -1 'le plateru n'est pas rempli
                    GoTo 10 'on va directement tester la 2eme condition
                End If
            Next
        Next

        res = 1 ' le plateau est rempli

10:
        Dim winner As Boolean = IsWinner(couleur)
        If winner True Or res 1 Then
            Return True 'dans ce cas, si y'a un gagnant ou si la plateau est rempli
        Else
            Return False 'pour tous les autres cas
        End If
    End Function

Normalement c'est bon ... (j'espère)

mstarsup5 · Answer

pas bon: ça fait pareil (teste: mets, sur la première diagonale: un rouge, un vert, un rouge, et regarde ce qui se passe.
Dans ta fonction, y'a des fois t'as deux gagnants...
Ca peut venir de deux choses:
Soit la fonction IsFinish n'est toujours pas correcte, soit quand tu fais "return qqch", la fonction continue d'exécuter ce qu'il y a après.
fais un test: mets un msgbox "hello" après un return qqch

 Pourapprendretoujoursplus!

mstarsup5 · Answer

(Ps: à mon avis, une fois que t'auras réglé ce problème, l'algo fonctionnera, mais là, tant qu'il s'arrête pas quand il trouve un gagnant, ça pourra pas fonctionner (pour deux raisons:
La première, c'est bête de continuer à voir ce qui se passe après qu'un gagnant a déjà été trouvé, si tu comprends pas ça, tu n'as rien compris de l'algo.
Deuxième raison: imagine tu trouves un gagnant, il continue de tester et trouve un deuxième gagnant (ce qui arrive des fois dans ton algo d'ailleurs).
Comment attribuer des points dans ce cas? A qui, et pourquoi? C'est débile ^^

Enfin bon voilà, il faut corriger ça quoi :)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ps: si il y a une erreur dans ta fonction IsFinish, elle est là:
Dim winner As Boolean = IsWinner(couleur)
(mais j'en sais rien perso s'il y a une erreur, je peux pas la tester ni rien ^^") => A toi de vérifier

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

pas bon: ça fait pareil (teste: mets, sur la première diagonale: un
rouge, un vert, un rouge, et regarde ce qui se passe.
Dans ta fonction, y'a des fois t'as deux gagnants...
Ca peut venir de deux choses:
Soit
la fonction IsFinish n'est toujours pas correcte, soit quand tu fais
"return qqch", la fonction continue d'exécuter ce qu'il y a après.
fais un test: mets un msgbox "hello" après un return qqch

Pas compris, pourtant en jouant sans IA ca marche très bien... comment peut-il y avoir deux gagants ?

mstarsup5 · Answer

Bah écoute, fais ce que je t'ai dit, tu prends le programme que tu m'as passé, tu joue rouge en haut à gauche, vert au milieu, rouge en bas à droite, tu lances l'IA et tu regardes ce qui se passe... A un moment t'as deux gagnants, c'est clairement pas bon lol

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

J'ai l'impression que ca marche !
J'ai mis à jour l'archive qu'en penses tu ?

En fait, il faut pas vérifier si le joueur courant à gagné mais si l'un des deux joueurs à gagné (donc il faut testé les deux !)

mstarsup5 · Answer

Bien sûr qu'il faut tester les deux, c'est ce que je t'avais marqué.
"Ca a l'air de marcher", mais je vais pas faire 2000 tests non plus pour voir si c'est fini complètement ^^"
Par contre l'IA est hyper lente...
Et ça pour deux raisons:
1 l'algo minmax pas du tout optimisé (utilise alpha beta qui est bien mieux, beaucoup plus rapide)
2 changer les couleurs des cases à chaque fois, ça prend beaucoup plus de temps que de mettre dans une variable la valeur de la case (0 pour vide, 1 pour rouge, 2 pour vert par exemple)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

(Ps: j'ai fait deux autres test, et non ça ne marche pas, y'a encore qqch qui merde ^^")

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Biensur maintenant que ca marche, je vais optimiser tout ca et puis je vais me lancer dans l'algo Alpha/Beta maintenant que j'ai compris le Min/Max.

Merci encore pour ta grande aide et tout le temps passé sur ce topic pour m'aider :) Je vais te laisser tranquille et puis je me donne 10 jours pour comprendre le nouvel algo et puis je te tiens au courant sur ce thread :)

fdiedler2000 · Answer

Mince !!! Quel test as tu fait ?

mstarsup5 · Answer

Bon par contre, j'ai pas le temps de tchatter, je veux pas louper mon train, donc ben bonnes vacances, à dans 10 jours, et si j'ai le temps un après midi, je ferai un morpion avec IA sur vb6 (avec min max et alpha beta au choix) et je le posterai si tu veux pour que tu voies comment il marche.
Bonnes vacances, et à la prochaine.
(Ps: ça m'en a pris du temps ce problème dis donc, faut que je me mette à réviser moi x_x)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Rouge haut gauche, vert milieu droit, rouge bas gauche, puis IA.

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah remarque je suis con, de toute façon le vert a perdu, attends j'en avais un autre, je regarde si il est bon ou pas.

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah non, l'autre c'est pareil, je suis trop con lol :p
Enfin bon pas grave, j'essaierai de faire les deux quand même, tu verras le gain de temps, j'optimiserai les deux de toute façon.
(Ps: tu vois que mon algo était bon, le problème venait de tes fonctions :-p)

 Pourapprendretoujoursplus!

mstarsup5 · Answer

Ah ce coup ci j'ai vraiment trouvé un truc qui n'allait pas:
Rouge milieu, Vert bas droite, IA, vert milieu gauche, IA  (le dernier IA n'est pas bon du tout ^^")
Te fais ça pendant les vacs, à plouche

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Donc au final l'algo marche enfin ou pas ?
Effectivement c'était mes fonctions qui plantaient !

mstarsup5 · Answer

Salut, j'ai pu me connecter 2 minutes chez mon parrain, je te poste la source que j'ai faite dans le train, avec comme promis les deux algorithmes minmax et alphabeta.
Tout marche, je te laisse regarder.
(je te file le lien quand même:  http://www.vbfrance.com/codes/MORPION-IA-ALGORITHMES-MINMAX-ALPHABETA-DEBUTANTS_45226.aspx )
Bon sur ce, à plus et bonnes vacances.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

A mon sens, il y a une erreur :
Place un rouge en haut à gauche, un vert au milieu à droite et un rouge en bas à gauche puis tu fais IA minmax et il va se planter....

mstarsup5 · Answer

Non: vert sait qu'il a perdu, et comme je l'ai mis dans le code en commentaire, quand il sait qu'il gagne (ou qu'il perd, comme ici), il va tout faire pour finir la partie au plus vite.
Dans le cas que tu donne, vert perd quoi qu'il arrive, et le programme marche comme je lui ai dit de marcher :)

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Exact j'avais vu ce point dans le code :)
Donc je vais me pencher un peu plus près...
Bonne année ! et merci

fdiedler2000 · Answer

Re,
Je crois que j'ai trouvé le bug !

ScoreTemp = ScoreTemp + Profondeur 'Permet à l'ordinateur de toujours prendre le chemin le plus court pour gagner (ps: ça veut aussi dire que lorsqu'il sait qu'il a perdu, il va tout faire pour que la partie soit finie le plus rapidement possible, ne vous étonnez donc pas s'il a l'air de jouer n'importe quoi...)

La seule différence avec mon programme et le tien c'était cette subtilité qui me parraissait pas un soucis. J'ai essayé de rajouter le "+ Profondeur" pour voir comment se comporte l'IA et j'ai découvert qu'elle joue correctement comme la tienne !! (testé après moultes essais).

Ensuite, j'ai décidé de virer le "+ profondeur" dans ton programme pour voir si l'IA déconnait comme dans mon programme. ===> Resultat : OUI ^^ Donc j'en conclut que cette ligne est essentielle dans l'algo mais pourquoi ??

Je compile le programme et je te le met à disposition pour que tu puisses tester si tu as un peu de temps :)

Merci

fdiedler2000 · Answer

Voila la programme :
http://www.zonegeeks.com/temp/morpion.zip

Thanks et bonne vac :)

mstarsup5 · Answer

Salut, injouable ton prog, j'ai lancé l'IA, j'ai dû arrêter le programme, au bout de 3 minutes de réflexion, il était encore entrain de réfléchir pour jouer le premier coup lol...
Soit y'a un bug, soit c'est pas optimisé du tout.
(Mon programme, même avec l'algo minmax, et pas alphabeta me donne le premier coup en 4 secondes...) Là, ton prog était parti pour me donner un résultat en (au moins!) 30 minutes (il était encore entrain de tester le premier coup possible pour l'IA: en haut à gauche, et les variations qui en découlent... Il n'avait pas encore même testé d'autre coup pour l'IA!)
Enfin bref, y'a un truc qui ne marche pas sur la version que tu m'as passé.

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Bizarre chez moi elle mets 10 secondes pour jouer le premier coup...
C'est normal c'est pas optimisé... QU'as tu fais exactement ? Tu as coché directement IA ? Et si tu joues en premier ?

mstarsup5 · Answer

Si je joue en premier, ça me fait pareil, ça prend pas mal de temps (pas testé jusqu'au bout, ça prend trop de temps :/ )
mon pc est assez vieux, mais quand même... j'ai un P4 à 2.8GHz, il devrait me faire ça assez rapidement normalement.
OS: XP

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

c dingue... meme avec un P4 2,8 Ghz ca devrait passer !!
Idem XP. Donc, je vais optimiser l'algo en ne montrant pas le détail c'est ca qui prend du temp et je te redonne la source.

fdiedler2000 · Answer

Voila c'est optimisé ! 10 sec pour le premier coup en debug et moins en release...
http://www.zonegeeks.com/temp/morpion.zip

J'espère que cette fois c'est bon :)

mstarsup5 · Answer

Oui, c'est beaucoup moins long, mais encore trop long pour mon piti pc qui date...
(c'est 10 fois plus long que mon algo...)
Cela dit, je peux voir que ça marche au moins ce coup ci : )

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Pour l'optilisation, j'ai opté pour un tableau bi dimensionnel et puis je mets en string des couleurs (rouge ou vert) donc c'est pas la meilleur solution mais ca marche ^^
Cependant, je trouve ca bizarre que ca lag sur un P4... meme si je suis en core 2 duo...

Donc effectivement ca marche mais il fallait rajouter le

ScoreTemp = ScoreTemp + Profondeur
'Permet à l'ordinateur de toujours prendre le chemin le plus court pour
gagner (ps: ça veut aussi dire que lorsqu'il sait qu'il a perdu, il va
tout faire pour que la partie soit finie le plus rapidement possible,
ne vous étonnez donc pas s'il a l'air de jouer n'importe quoi...)

Donc c'est obligé apparemment !

Merci pour tous, maintenant je vais décortiquer l'algo ALPHA/BETA pour voir un peu mais ca devrait pas trop etre diff quand on a compris le MINMAX :)

Thanks for all !

mstarsup5 · Answer

Moi aussi je trouve ça bizarre, surtout que bon...
Mon programme: moins de 4 secondes de réflexion
Ton programme: de 35 secondes à 1 minute si il est déjà essoufflé par une première réflexion...
(Et je pense que ça aurait pris plus de 30 minutes avant ta dernière version !)
Mais bon ça marche, te reste plus qu'à regarder le alpha beta maintenant.
J'ai intégré le NegaMax dedans, ça complique un peu, mais ça prend moins de lignes de code.
sur ce, bonne continuation, à+

 Pourapprendretoujoursplus!

fdiedler2000 · Answer

Merci j'ouvrirais un autre topic en cas de soucis :)
Je vais encore optimiser le code car c'est loin d'etre fait !

Livre pour apprendre les algo MinMax et Alpha/beta

101 réponses

Votre réponse

Discussions similaires