Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

MORPION - IA ALGORITHMES MINMAX ET ALPHABETA POUR DÉBUTANTS


Information sur la source

Catégorie :Jeux Classé sous : morpion, minmax, alphabeta, IA, alpha Niveau : Débutant Date de création : 30/12/2007 Date de mise à jour : 30/12/2007 17:00:10 Vu / téléchargé: 7 309 / 434

Note :
10 / 10 - par 1 personne
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

Commentaire sur cette source (3)
Ajouter un commentaire et/ou une note

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

  • Voir zip.
  • Je n'ai commenté que les algorithmes de l'IA, le reste est je pense plus que compréhensible.
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
 

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

30 décembre 2007 17:00:11 :
-

Commentaires et avis

signaler à un administrateur
Commentaire de PCPT le 30/12/2007 21:24:19 administrateur CS

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

signaler à un administrateur
Commentaire de le pro masterchief le 04/01/2008 22:49:16 10/10

À 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+

signaler à un administrateur
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 :)

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

[aide] Morpion IA en VBA (spécifique à mon prg) [ par zubbys ] Bonjour,Je suis en ce moment entrain de coder mon premier programme en VBA sous excel et c'est un morpion (pour ne pas faire comme tout le monde...).J Event inactif [ par OneHacker ] Bonjour à tous. J'ai créer une classe IA avec Public Class IAPublic Event LogChanged()   Public Sub New()RaiseEvent LogChanged()        End SubEnd Cla Canal Alpha/ Transparence [ par GimliDotnet ] Bonjour,je cherche à détecter dans une image son canal alpha. Sachant que je ne connais pas l'image. Si elle possede un canal alpha, je voudrai connai "Tronquer le vide" d'un PNG en fonction de son canal alpha [ par Pym Corp ] Bonjour tout le monde =)Je viens chercher de l'aide de la part de personnes compétentes pour mon problème qui n'est je pense, pas solvable facilement. Besoin d'aide sur un algaritme [ par supergl ] Bonjour a tous,Voici le morceau de fonction qui me pose problème :Function crypter(acrypt As String, code As String) As Stringalpha = "azertyuiop^$qsd Livre pour apprendre les algo MinMax et Alpha/beta [ par fdiedler2000 ] 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éf Tableau a variable [ par themasterofthescripts ] Je ne suis qu'un programmeur débutant/amateur, et j'ai de grandes lacunes concernant la manipulation des variables, constantes etc...et tout par touner un picturebox de alpha degre [ par argentin7 ] bonjour a  toute la comunautéSVP je veux savoir comment faire tourner un picturebox d'un angle alphaet merci d'avance items pour selectionner tout une colonne [ par bousselhamothmane ] bnjour , jai une listbox avec des items (qui sont en fait les mots se trouvant sur les celulles de la 1ere ligne) , je voudrais faire en sorte que cha Créer une pseudo IA [ par DiabloduNord ] Bonjour tout le monde, Alors je vous rassure je suis loin d'ètre notre chers amie BILL GATES je suis un petit développeur à mes heures perdu. Mon


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version

Photothèque Nouveau !



Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés
Temps d'éxécution de la page : 4,540 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.