[JAVA] Algorithme Min-Max
Bonjour à toutes et à tous !
J'ai un soucis avec l'algo Min-Max exécuté sur un jeu de Puissance 4.
En effet, celui-ci ne fait pas ce que j'attends d'un algo en solution complète.
J'ai appris, lors de mes nombreuses recherches sur Internet que le premier joueur qui met son pion (X dans mon programme) dans la colonne du milieu gagne à tous les coups s'il fait le meilleur coup à chaque fois.
Pour tester mon algo, je fais combattre deux IA de puissance égales (la profondeur de l'arbre est identique chez les deux ordinateurs), et j'aperçois quelques ennuis.
En profondeur 5, le X joue bien la colonne du milieu mais c'est le O qui gagne.
En profondeur 6, le X ne joue pas la colonne du milieu (il joue la colonne la plus à gauche) et le O se plante royalement, X peut gagner et O ne bouche pas le trou, ce qui fait que X fait puissance 4 au tour d'après.
J'ai testé différentes valeurs de départ pour initialiser les variables min et max. Aucun des résultats n'est convaincant.
Pire encore : je mets le X et profondeur 5 et le O en profondeur 4 et devinez quoi, c'est le O qui gagne... Je vais devenir fou ! C'est celui qui fait le moins de calculs qui gagne, je trouve ça absurde.
J'aimerai une petite aide de ceux qui se sont déjà penchés sur la question.
Voici mon code :
J'aimerai savoir premièrement si je n'ai pas fait d'erreur dans la retranscription de l'algo min-max que j'ai trouvé sur le site du zéro.Code:public final class Ordinateur extends Joueur { public static final int PROFONDEUR=5; private final int profondeur; Ordinateur(Pion pion, int profondeur) //package { super(pion); this.profondeur=profondeur; } @Override public final int jouer() { return min_max(); } private final int min_max() { int max_val=-10000; //TO_MODIFY int meilleur_coup=-1; for (int colonne=0; colonne<jeu.getPlateau().getColonnes(); ++colonne) { int ligne=jeu.getLigne(colonne); if (ligne!=-1) { jeu.jouer(colonne, pion); //WARNING int val=min(profondeur); if (val>max_val) { max_val=val; meilleur_coup=colonne; } jeu.remove(colonne); } } return meilleur_coup; } private final int min(int profondeur) { if (profondeur==0 || jeu.isFinished()) return eval(pion.getOpposite()); //WARNING int min_val=10000; //TO_MODIFY for (int colonne=0; colonne<jeu.getPlateau().getColonnes(); ++colonne) { int ligne=jeu.getLigne(colonne); if (ligne!=-1) { jeu.jouer(colonne, pion.getOpposite()); //WARNING int val=max(profondeur-1); if (val<min_val) min_val=val; jeu.remove(colonne); } } return min_val; } private final int max(int profondeur) { if (profondeur==0 || jeu.isFinished()) return eval(pion); //WARNING int max_val=-10000; //TO_MODIFY for (int colonne=0; colonne<jeu.getPlateau().getColonnes(); ++colonne) { int ligne=jeu.getLigne(colonne); if (ligne!=-1) { jeu.jouer(colonne, pion); //WARNING int val=min(profondeur-1); if (val>max_val) max_val=val; jeu.remove(colonne); } } return max_val; } }
Ensuite, j'aimerai savoir si je ne me suis pas gourré pour le passage du paramètre "pion" ou "pion.getOpposite()" là où j'ai placé des "//WARNING".
Et enfin, me donner des idées pour écrire une méthode eval qui satisferait les conditions suivantes:
- Le premier joueur met son pion au milieu
- Celui qui met son pion au milieu gagne d'office en jouant le meilleur coup à chaque fois
Cette classe fait partie d'un ensemble mais les appels de méthodes parlent d'eux-même donc, comprendre mon code ne devrait pas être fort compliqué. S'il vous faut le code des autres classes du projet, je peux vous les transmettre sans aucun problème.
En vous remerciant d'avance,
Aenonis
-----
