Bonjour à tous,

Je suis depuis peu entrain de m'intéresser au langage Java et je viens vers vous parce que j'ai un problème avec l'IA d'un puissance4 que je suis entrain de créer.

J'ai déjà réalisé un algorithme minmax (que j'ai attribué à l'IAfacile) et je voudrais réalisé un algorithme de Monte Carlo pour l'IAdifficile. Je pense avoir plus ou moins réussi à installer les bases mais l'IA me laissait gagner (de manière triviale) quelque fois. Pour moi, c'était dû au caractère entièrement aléatoire de mon algorithme. Pour minimiser celui-là, j'ai créer une nouvelle méthode 'winningMove()' qui renvoie la colonne à choisir si il y a un coup gagnant, -1 sinon.

Je pensais avoir réussi mais l'IA me laisse toujours gagner et là j'avoue que je sèche complètement. Je pense qu'il y a une erreur dans mon algorithme mais je n'arrive pas à trouver lequel.

Je vous mets le code de l'IA correspondante. Je débute en Java donc excusez moi d'avance si le code n'est pas bien écrit et/ou optimisé. Les méthodes appartenant aux autres classes ont toutes été vérifiées et marchent parfaitement. Je pourrais néanmoins vous mettre le code des autres classes si vous le souhaitez !

Merci d'avance

package core;

import java.util.Random;
import java.util.ArrayList;

public class IAdifficile extends AlgoIA {

	
	/* Nombre de parties simulés aléatoirement 
	 * pour chaque coup possible 
	 */
	private static int nbSimulation;

	
	public IAdifficile(){
		nbSimulation=10000; 
	}

	/* Méthode abstract de la classe AlgoIA
	 * Méthode appelé quand c'est au tour de L'IA de choisir une colonne (de 0 à 6)
	 */
	public int chooseColumn(Grid grid, Color color) {
		return monteCarlo(grid, color);
	}

	/* Le choix de la colonne se fait par la méthode de Monte Carlo :
	 * On simule un grand nombre de parties pour chaque coup possible et le meilleur coup est celui qui a généré le plus de victoires
	 */
	private int monteCarlo(Grid grid, Color color) {
		//Raccourci, si il y a un coup gagnant, renvoie la colonne correspondante
		if (grid.winningMove(color)!=-1)  
			return grid.winningMove(color);
		
		boolean win;
		int count=0, colmax=0, countmax=0;
		for (int col=0; col<grid.getBoard()[0].length; col++){ //Pour chaque colonne du tableau
			if (grid.columnFull(col)) 						   //Si la colonne est pleine on passe à la prochaine
				continue;
			else{
				for (int k=0; k<nbSimulation; k++){			   //Sinon on simule 'nbSimulation' parties aléatoires
					count=0; win=false;
					grid.addPion(color, col);					//Ajout d'un Pion de couleur 'color' à la colonne 'col'
					if (!grid.isFull() && grid.gameFinished()==0)//Si la partie n'est pas finie (grille non pleine et pas encore de gagnant)
						win = simulRandom(grid, color, false);   //cf. simulRandom()
					else 
						win = grid.gameFinished()==color.numPlayer();//Si la partie est finie, on renvoie vraie si le gagnant possède la couleur en entrée
					grid.removePion(col);
					if (win) count++; 							//On compte le nombre de parties gagnées
				}
			}
			if (count>countmax){								//On stocke la colonne où il y a le plus de parties gagnées
				countmax=count;
				colmax=col;	
			}
		}
		return colmax;
	}
	

	/* Simule une partie aléatoire à partir d'une position donnée de la grille
	 * return true si la partie est gagné par le joueur ayant la couleur color
	 */
	private boolean simulRandom(Grid grid, Color color, boolean turnIA){
		//Raccourci, si il a un coup gagnant et que c'est le tour de l'IA, renvoie true
		//coup gagnant et tour de l'adversaire, renvoie false
		Color colorturn = turnIA ? color : Color.getOther(color);
		if (grid.winningMove(colorturn)!=-1){
			return turnIA;
		}
		
		boolean win;
		int colrandom=randomCol(grid); 						//cf. randomCol()
		grid.addPion(colorturn, colrandom);					//Ajout d'un Pion dans la couleur aléatoire
		if (grid.gameFinished()!=0 || grid.isFull()) 		//Check si la partie est finie
			win = grid.gameFinished()==color.numPlayer();	//Si oui, win=true si l'IA a gagné
		else 
			win = simulRandom(grid,color,!turnIA);			//Sinon, on simule un tour de plus
		grid.removePion(colrandom);
		
		return win;
	}
	

	/* Renvoie une colonne aléatoire parmi celles de la grille qui ne sont pas pleines
	 */
	private int randomCol(Grid grid){
		Random rand = new Random();
		ArrayList<Integer> colAvailable = new ArrayList<Integer>();
		for (int col=0; col<grid.getBoard()[0].length; col++){
			if (!grid.columnFull(col))
				colAvailable.add(colAvailable.size(), col);;
		}
		return colAvailable.get(rand.nextInt(colAvailable.size()));
	}
}

-
Edité par BaptisteTRUCHET 22 août 2015 à 0:57:05

Salut,

est-ce que tu as essayé d'augmenter le nombre de simulation? 10k par coup ça me paraît peu pour un jeu comme le puissance 4, au final ça fait 70k simulations parmi plusieurs millions, voir milliards, et parmi ces simulations, beaucoup seront peut-être gagnante parce que l'IA considérera que son coup était bon, alors qu'il aura été bon contre un adversaire qui joue de manière stupide (aléatoire).

Essaie d'afficher le nombre de victoires par coup pour voir les tendances, peut-être aussi afficher les grilles gagnantes générées aléatoirement, pour voir si elles sont réellement cohérentes.

Est-ce que l'algorithme de Monte-Carlo est vraiment celui qui rendra l'IA la plus difficile? Un algo qui évalue un arbre des possibilités de manière plus (IA difficile) ou moins (IA facile) profonde avec des heuristiques ne serait pas meilleur?

J'ai pas trop réfléchis à la question, mais c'est ce qui me vient en tête en premier.

++