Morpion avec ia minimax ou génétique

Soyez le premier à donner votre avis sur cette source.

Vue 8 767 fois - Téléchargée 754 fois

Description

J'ai fais deux morpions : un ayant une IA classique, un minimax sans limite de profondeur, il ne vous apportera surement pas grand chose, l'autre morpion est un peu plus interessant, c'est en quelque sorte un jeu de la vie : on prend un certain nombre d'IA, (testé avec 10), chaqune de ces IA sont codés par un fichier qui détermine une certaine forme de mémoire. la mémoire leur permet de rejouer le coup sans y réfléchir, quand elles ne savent pas quoi jouer, elles jouent au hazard.
Avec ces 10 IA, on organise un tournoi :
make
./morpion -IA ai0 ia1 ia2 ia3 ia4 ia5 ia6 ia7 ia8 ia9

et on regarde les différents rounds qui défilent
à la fin du tournois, on a un classement qui s'affiche, les meilleurs IA muttent, et les plus nulles meurent (les fichiers sont remplacés)

ce qui fait que seul les meilleurs restent et que finalement, elles évoluent grace aux mutations, et aux coups au hazard...

Pour un morpion, je ne fais que montrer le principe, mais en appliquant ça à de meilleurs jeux, comme le puissance4 par exemple, on peut avoir des résultats satisfaisants, et battre un minimax... surtout si on applique un minimax à la place des coups aléatoires, et si on fait mutter un des coups joué lors d'une partie perdue, en lui appliquant lui aussi un minimax (dans mon morpion, les mutations sont aléatoires)

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
540
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
lol le 42! heu pour le P4 c'est pas super utile mais un jeu ou faut choisir un nombre
de points par piece ( echec .. ), la ca peut etre utile...
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
42
le principe ce cette IA génétique, c'est simple

-on doit jouer :

--on vérifie que la partie en cours correspond à une partie enregistrée
--si elle correspond alors
----on extrait le coup
----on le joue
--sinon
--on prend un coup au hazard (mais valide sur la partie)
--on mémorise ce coup
--on joue ce coup

donc, tout les coups sont mémorisés...

cette IA légèrement améliorée donne :

--on vérifie que la partie en cours correspond à une partie enregistrée
--on tient compte des différents sens de la grille (une partie peut avoir 4 représentations en mémoires, en appliquant des roations...)
--si elle correspond alors
----on extrait le coup
----on replace le coup dans le bon sens (pour l'appliquer à la partie en cours)
----on le joue
--sinon
--on prend un coup en réfléchissant (coup valide et intelligent sur la partie, par exemple un minimax de profondeur n)
--on mémorise ce coup
--on joue ce coup

dans ce cas, les mutations devront être intelligentes, mais avoir une intelligence "meilleur" que le minimax de profondeur n... sinon, ça n'a aucun interet

Donc, on enregistre toutes les parties possibles.... enfin, on tient compte des rotations ou autres transformations, donc, ça fait un peu moins...

d'ailleur le nombre de parties possibles n'est pas 42!... mais pas du tout... il est bien inferieur, puisqu'on choisit une colone parmie 4... mais quand une colone est pleine, on ne peut pas y jouer... bref, j'ai trop la flème de calculer ça, mais ça doit être inferieur à 7^42...
voici une ligne de puissance 4
|O| | | | | | |
est la même chose que
| | | | | | |O|
donc, on peut y appliquer une transformation...
donc, 7^42/2 au max...
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

42!, c'est beau :) N'importe quel PC qui se respecte doit pouvoir gérer ce nombre ^_^.

Je ne comprends pas bien pourquoi tu as besoin d'enregistrer toutes les parties.
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
42
Kirua> Je peux optimiser quelquechose sur un morpion: diriger les mutations vers les parties perdues, et le faire choisir un endroit de mutation stratégique (là encore, c'est pour le moment aléatoire). Je peux aussi ajouter un champ nombre de pions joués, pour éviter une réplication complète du plateau avant la comparaison, surtout avec les rotations (la fonction is_similaire détermine si on peut par une rotation retrouver la partie), Mais pour le reste, c'est ridicul de l'optimiser à fond, pour un morpion... y ajouter un minimax pour déterminer le coup qu'une IA jouerait lorsqu'elle n'a pas mémorisé la partie, reviendrait à en faire une IA imbatable dès le départ... faudrait mettre ça sur un puissance 4...

Pour un puissance 4, on ne pourrait pas stoquer toute l'IA en mémoire, c'est pas possible, faudrait ruser, en se connectant à MYSQL (ou tout autre dysteme de base de donnée) je penses... enfin bon, on a (6*7)! possibilitées de grilles terminées... je vous laisse calculer le nombre de possibilitées de parties non terminées... je penses qu'une table MYISAM saturerait très très vite surtout si on y met un id_IA... (une table MYISAM peut contennir 2^32 lignes). Bref, je réfléchis encore à comment élargire ce programme...
Messages postés
540
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
Genial meme si je pense que devra t'y prendre differement pour stocker ton IA dans un P4...
Afficher les 6 commentaires

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.