Livre pour apprendre les algo MinMax et Alpha/beta

Signaler
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008
-
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008
-
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

101 réponses

Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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 :)
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

Oui mais pour l'algo alpha/beta, il faut d'abord comprendre l'algo Min/Max :)

Personne ne connait de livre ?
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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.
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

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...
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

Ok je verrais ca ! Mais je recherche toujours un livre sur le thème c'est d'ailleurs l'objet de mon topic :)
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

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

Merci
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

Je cherche toujours un livre :(
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

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
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
>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!
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

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 !
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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!
Messages postés
383
Date d'inscription
samedi 29 janvier 2005
Statut
Membre
Dernière intervention
1 décembre 2008

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.