MORPION - IA ALGORITHMES MINMAX ET ALPHABETA POUR DÉBUTANTS
PCPT
Messages postés
13272
Date d'inscription
lundi 13 décembre 2004
Statut
Membre
Dernière intervention
3 février 2018
-
30 déc. 2007 à 21:24
mstarsup5 Messages postés 527 Date d'inscription lundi 15 octobre 2007 Statut Membre Dernière intervention 10 octobre 2013 - 6 janv. 2008 à 01:00
mstarsup5 Messages postés 527 Date d'inscription lundi 15 octobre 2007 Statut Membre Dernière intervention 10 octobre 2013 - 6 janv. 2008 à 01:00
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/45226-morpion-ia-algorithmes-minmax-et-alphabeta-pour-debutants
https://codes-sources.commentcamarche.net/source/45226-morpion-ia-algorithmes-minmax-et-alphabeta-pour-debutants
6 janv. 2008 à 01:00
En fait PCPT, je n'ai pas fait l'IA sous forme de classe pour 2 raisons.
La première, c'est que, comme je l'ai dit, j'ai fait cela un peu à la va vite dans le train pour partir en vacances, et j'ai posté cela tel quel, et la 2nde, c'est qu'en fait, il faut un minimum d'adaptation de l'algorithme pour chaque type de jeu.
Je m'explique: Il faut, pour chaque type de jeu, créer une fonction d'évaluation de la position sur le plateau qui lui est propre. Ensuite, utiliser une fonction qui dit quels coups sont possibles, et enfin créer deux fonctions: une simulant un coup, et une autre annulant le dernier coup joué.
Sinon, l'algorithme de recherche du meilleur coup est réutilisable si on intègre ces fonction, qui sont utilisées par l'algorithme.
Si j'ai le temps après mes exams qui viennent, je referai cela sous forme de classe, en mettant bien en avant le nom des fonctions utilisées, etc... pour qu'on puisse le reprendre tel quel.
Sinon, j'explique plus en détail les algorithmes, pour PRO MASTERCHIEF et d'autres, parce qu'il est vrai que je ne suis pas rentré vraiment dans les détails.
Pour l'algorithme MinMax, en fait, disons qu'il y a plusieurs étages. Quand c'est à l'ordinateur de jouer, et quand c'est à son adversaire.
Quand c'est à l'ordinateur de jouer, à un étage, il faut maximiser ses points, donc jouer le coup qui lui donne le plus de points.
Quand c'est à l'adversaire de l'ordinateur de jouer, ce dernier va essayer de maximiser ses points à lui, soit donc de minimiser ceux de l'ordinateur. Oa va donc, à un étage où c'est à l'adversaire de l'ordinateur de jouer le coup qui minimise le score pour l'ordinateur.
Ainsi, en répétant ce processus (min, max, min, max, ...) à chaque étage, l'ordinateur choisit le coup qui maximise à coup sur ses points, sa position.
Pour l'algorithme AlphaBeta, en fait c'est exactement le même principe, sauf qu'il permet de sauter des tests en retirant des branches de l'arbre de recherche dont il sait qu'elles seront inutiles. C'est en cela qu'il est beaucoup plus rapide que l'algorithme MinMax présenté précédemment.
(Vous pouvez essayer de lancer MinMax pour chercher le premier coup de l'ordinateur, et essayer la même chose avec AlphaBeta, vous verrez que la différence de temps de recherche est assez énorme. (et ce, même sur un jeu de morpion de 3 cases sur 3... imaginez avec un jeu d'échecs ou d'othello...))
Enfin bref, il élimine certaines branches qu'il voit comme inutiles.
Par exemple:
x
/ \
10 /\
9
Là, le x, c'est à l'ordinateur de jouer. Il va maximiser le score des branches qui sont juste en dessous.
Il regarde la première branche et trouve un score de 10.
Maintenant, il regarde la deuxième branche, qui elle même a deux feuilles.
A la 1ère feuille, il trouve 9. Sachant qu'à cet étage c'est à l'adversaire de jouer, il va minimiserle score des deux feuilles, donc l'évaluation de la deuxième branche sera quoi qu'il arrive inférieure à 9.
Mais à l'étage supérieur,on doit maximiser (c'est à l'IA de jouer), et comme 10>9, le coup qui sera choisi est celui menant à un score de 10.
Dans ce cas là, ce n'est même pas la peine de regarder la deuxième feuille de la deuxième branche, on sait qu'elle ne sera pas choisie.
C'est comme ça que l'algorithme réduit de façon assez impressionnante son temps de recherche :)
Je pense que j'expliquerai plus en détail cela aussi quand je mettrai le code sous forme de classe :)
J'espère que c'est compréhensible ce que j'ai dit, s'il y a des questions, n'hésitez pas!
En tout cas, merci pour vos commentaires :)
4 janv. 2008 à 22:49
L'autre alogorytme alpha beta semble plus difficile.
Continue comme ça je suis sûr que cette ia poura servir à plusieurs personnes.
Il serait peut être intéressant que tu explique le raisonnement de ton algorythme dans tes mots pour mieux comprendre le code.
a+
30 déc. 2007 à 21:24
je n'ai pas regardé le code...
d'après ta description, on peut utiliser ton "IA" pour tout type de jeu plateau.
pourquoi alors ne pas faire ton IA sous forme de classe afin de facilement l'intégrer et/ou la manipuler?
++ :p