MORPION - IA ALGORITHMES MINMAX ET ALPHABETA POUR DÉBUTANTS

Commentaire de mstarsup5 le 06/01/2008 01:00:50

Salut PCPT, PRO MASTERCHIEF, je suis désolé de répondre si tard à vos posts, j'étais chez ma mère pour ces vacances et je n'avais pas internet pendant un petit bout de temps.

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 :)