Intelligence artificielle pour puissance 4 [Résolu/Fermé]

Signaler
Messages postés
22
Date d'inscription
dimanche 25 septembre 2011
Statut
Membre
Dernière intervention
5 mai 2014
-
Messages postés
22
Date d'inscription
dimanche 25 septembre 2011
Statut
Membre
Dernière intervention
5 mai 2014
-
Bonjour,
En ce moment je programme un puissance 4 sur java's cool.
Il s'agit d'un projet en spécialité isn et tout marche correctement pour l'instant.
Le professeur nous a demandé de créer une version intelligente pour l'ordinateur lorsque c'est à son tour de jouer.
J'aimerais créer une intelligence artificielle toute basique. Et c'est pour ça que je sollicite l'aide des internautes sur ce forum.

J'ai cherché un peu partout sur internet, on me dit d'utiliser l'algorithme min-max mais ça me semble très compliqué. C'est pour ça, j'aimerais savoir s'il y a un moyen beaucoup plus facile pour créer une IA très basique.

Par basique je veux dire une version qui n'est pas tout le temps intelligente et qui se laisse faire parfois.

J'ai déjà essayé des trucs, c'est-à-dire, j'ai fait analysé chaque case du plateau de jeu et que si le joueur principal aligne 3 pions dans n'importe quel sens, l'ordi joue la colonne où le 4eme pion est censé être placé. Sauf que l'analyse ne fonctionne pas du tout.

Merci d'avance. :D

1 réponse

Messages postés
16066
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 octobre 2020
2 699
Bonjour,

Tu peux y aller par force brute. Tu choisis un niveau d'anticipation et tu calcules toutes les combinaisons possibles pour l'ordinateur et l'humain.

Sachant que tu peux mettre ton jeton dans 7 colonnes, ça fait 7^n calculs maximum, si n est ton niveau d'anticipation. Pour n=7 par exemple, c'est à dire 4 tours ordinateur et 3 tours humain, tu aurais donc moins d'un million de calculs. Ça se fait bien.

Le vrai problème, c'est d'estimer quelle sera la meilleure solution parmi les 7^n, il faut prendre plusieurs critères en compte.
D'une part il faut gagner le plus tôt possible, c'est à dire mettre son premier jeton là où on a le plus de chances de gagner par la suite, c'est à dire où les chemins mènent vers une ou plusieurs possibilités de gain (idéalement vers une combinaison où l'on est sûr de gagner).
D'autre part, il faut perdre le plus tard possible, si l'ordinateur met le jeton à une position qui offre une possibilité de victoire à l'humain, il faut faire en sorte que cela arrive tard, de manière à ce que l'adversaire humain puisse se tromper.
Le plus délicat va donc être de pondérer les 7^n informations que tu auras obtenu, afin de faire le meilleur choix de colonne.

Remarque : il n'y a qu'un choix sur 7 à faire. Au tour suivant tu recommences les calculs avec le nouvel état, tu pourras éventuellement récupérer les calculs déjà effectués, mais vu que cela ne représente que 2% des calculs (1/7^2) et qu'il faudra de toute façon les prolonger sur 2 niveaux supplémentaires, tu peux même carrément tout oublier entre chaque tour.

Par contre l'intelligence artificielle ne doit pas se laisser faire. Il faut toujours qu'elle choisisse le meilleur choix sinon ça ne sert à rien. Par contre on pourra faire varier la difficulté selon la valeur de n.
En théorie, si on prenait un n maximum (n=7*7), l'ordinateur devrait déjà avoir gagné avant même de commencer sa partie. Mais comme cela fait 256 sextilliards de calculs, en pratique on ne pourra évidement pas le faire. Je doute que tu puisses raisonnablement dépasser n=10 avec de la force brute, ou alors en fin de partie lorsque le nombre de coups est plus restreints. Dans ce cas il faudra prévoir un mode "bonus" où l'intelligence artificielle décide d'elle même d'anticiper de 1 ou 2 niveaux de plus lorsqu'elle n'a pas suffisamment de visibilité pour décider.
Messages postés
22
Date d'inscription
dimanche 25 septembre 2011
Statut
Membre
Dernière intervention
5 mai 2014
>
Messages postés
16066
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 octobre 2020

Le but ici est donc d'analyser les cases et d'attribuer des probabilité pour chaque colonne? Merci pour la reponse, c'est complet mais j'ai un peu de mal à comprendre. :/
Messages postés
16066
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 octobre 2020
2 699
Il ne s'agit pas vraiment de probabilité.

Dans l'intelligence artificielle, tu dois toujours trouver un moyen d'évaluer la qualité d'une solution. Il faut donc que tu puisses convertir toute une grille en un seul nombre, qui doit te permettre d'évaluer si elle meilleur qu'une autre.

Je t'ai donné un exemple de comment on pourrait obtenir ce nombre, en faisant la somme des k^2 pour chaque joueur, et la différence entre l'adversaire et toi.
Mais ce n'était qu'un exemple, tu peux trouver une autre manière de faire, peut-être plus simple, peut-être meilleur. Mais le principe doit toujours être le même. Il faut pouvoir comparer deux grilles et savoir laquelle est la plus à notre avantage.

Ensuite vient l'algorithme de recherche en lui même, qui va parcourir les différentes grilles possibles, ce que je t'ai proposé est le plus simple, tu considères toutes les solutions possibles et tu ne gardes que la meilleure. D'autres algorithmes sont plus intelligents, il se dirigeront vers une première solution un peu meilleure et par différentes méthodes, se diriger vers une autre solution encore meilleure, jusqu'à obtenir la meilleure, ou au moins une des meilleurs solutions.

Concrètement, il te faut donc deux méthodes indépendantes :

// détermine quelle est la valeur de la grille
double valeur(Grille g);

// trouve la meilleur colonne où jouer à partir de la grille g
int meilleur(Grille g);

Evidemment la deuxième méthode utilisera la première afin de trouver la valeur maximale.
Messages postés
22
Date d'inscription
dimanche 25 septembre 2011
Statut
Membre
Dernière intervention
5 mai 2014

Aaah oui! Je vois mieux maintenant! :D
En fait, dans votre exemple, si l'ordi est jaune, il est dans une position avantageuse puisque la différence est positive. Par contre si l'ordi est rouge, il est désavantagé, il doit donc trouver un moyen de rendre la différence positive ou nulle en essayant de couvrir la colonne où le joueur adversaire a plus de chance de gagner. Et ce moyen là est, dans votre cas, la fonction meilleur() si j'ai bien compris.
Je vais tester ça, et je vous tiendrais au courant. Merci pour les explications.
Messages postés
16066
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 octobre 2020
2 699
Pas tout à fait.

Au départ on a une grille, qui est l'état courant du jeu.

Puis l'ordinateur va simuler un ensemble de prochains tours possibles.
Par exemple si on anticipe sur n=3 tours on pourrait avoir une combinaison (5, 2, 6) qui signifie "je joue 5, l'adversaire joue 2, je joue 6".
Ce qui nous intéresse c'est la valeur de la grille après que ces n coups aient été joués.
Si la valeur maximale de la grille est obtenue avec une combinaison (x, y, z), alors l'ordinateur devrait jouer x (cela vient du fait que l'on choisit justement le calcul de la valeur pour ça).

Tout ça c'est le principe de l'intelligence artificielle. Après il y a deux choix à faire :
1) comment calculer la valeur de la grille de manière à avoir le meilleur coup à jouer quand on aura trouvé le maximum
2) comment sélectionner les combinaisons possibles à calculer de manière à trouver le maximum.

Le principe de la force brute, c'est qu'on va faire toutes les combinaisons possibles sans exception. Par exemple sur n=3 tours, on va avoir 7^3 combinaisons à tester que sont :
(1,1,1), (1,1,2) ... (1,1,7), (1,2,1), (1,2, 2) ... (1, 7, 7), (2, 1, 1), ... (7,7,7)

Malheureusement si cette technique est infaillible pour trouver le maximum, elle est coûteuse pour de trop grandes valeurs de n. C'est pour cela que d'autres techniques plus sophistiquées existent, mais dans ton cas la force brute devrait suffire si tu te limites à de petites valeurs de n.
Messages postés
22
Date d'inscription
dimanche 25 septembre 2011
Statut
Membre
Dernière intervention
5 mai 2014

Je vois a peu près ce que c'est. Je vais y travailler à fond.
En tout cas merci beaucoup pour votre disponibilité. C'est très rare de voir des gens expliquer et répondre aussi clairement aux questions posées. C'est très gentil de votre part.
Je vais suivre vos conseils et essayer de faire fonctionner le programme.
Merci encore, passez une bonne fête de Pâques! :D