Morpion - ia algorithmes minmax et alphabeta pour débutants

Soyez le premier à donner votre avis sur cette source.

Vue 15 221 fois - Téléchargée 1 123 fois

Description

Bonjour,
Cette source, comme son titre l'indique est un jeu de morpion, mettant en avant les algorithmes Minmax et AlphaBeta pour ceux qui voudraient utiliser une IA dans leurs programmes (morpion, échecs, dames, othello, puissance 4, et j'en passe...

J'ai fait en réalité cet algorithme dans un programme d'othello bien plus compliqué, cependant ma source n'est pas encore finie, donc je ne la mets pas sur le site, et j'ai vu que plusieurs personnes dont fdiedler2000 ont des problèmes à utiliser ces algorithmes pour faire une IA.
C'est pour cela que j'ai fait cette mini source sur un exemple basique (un morpion).

(Ps: je l'ai faite dans le train et à la va vite, donc le code en dehors de l'IA n'est peut être pas optimal :) )

Voila, en espérant que ça pourra être utile à des gens...

Christophe Fiter

Source / Exemple :


Voir zip.

Je n'ai commenté que les algorithmes de l'IA, le reste est je pense plus que compréhensible.

Conclusion :


J'espère que les algorithmes de l'IA dans la source aideront les gens à faire leur propre intelligence artificielle pour leurs jeux :)
Cette source intéressante pour l'IA, utilisable pour n'importe quel jeu de plateau, le jeu en lui même (un morpion) est selon moi sans intérêt et n'était là que pour servir d'exemple :p

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
1
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 :)
Messages postés
57
Date d'inscription
vendredi 4 novembre 2005
Statut
Membre
Dernière intervention
9 avril 2008

À première vue ton ia minmax semble marcher parfaitement je n'ai pas trouvé trop facile de battre l'ordinateur au morpion et même qu'il ma batu plus d'une fois :).

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+
Messages postés
13280
Date d'inscription
lundi 13 décembre 2004
Statut
Modérateur
Dernière intervention
3 février 2018
35
salut mstarsup5,
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

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.