IA Morpion besoin d'aide

Bonjour,
J'ai réalisé le début du Jeu le morpion avec quelques particularités :

-Nécessiter de 5 alignements pour marquer un point
-Taille de la grille aléatoire (fixer par le joueur au début de la partie)
-La partie ce termine lorsque la grille est complète

Voici ce que j'ai déjà réalisé :

J'ai codé tout en C++, une classe Grille qui gère l'application des différents symboles (X,O), avec une méthode obtenirResultat qui à tout moment de la partie restitue le résultat de chaque symboles en calculant tout les alignements de 5 sur la grille.

Voila mais maintenant j'aimerais mettre en place un joueur virtuel.
Eh je ne sais vraiment pas du tout d'où partir et ce qu'il faut que je fasse...
En cherchant sur internet, j'ai trouvé qu'il existait différents algorithmes comme min-max ou alphabeta.
Mais je ne vois pas du tout comment mettre un tel algorithme en place.

Pourriez vous me donnez des pistes, pour m'aider à mettre tout ça en place ?

Merci de votre aide. :ccool:

Les algos min-max, alpha béta sont des algos exhaustifs c'est à dire qu'ils calculent tous les cas possibles. Donc à un instant T du jeu (quand c'est à l'IA de jouer), tu récupères l'état du jeu (la position des pions sur le plateau) tu calcules les coups suivants jusqu'a la profondeur N (fixée par toi) et tu évalues les arbres de façon à choisir le meilleur selon tes critères (nombre de "pions" alignés, nombre de pions que l'ennemie peut aligner au prochain coup, .....) puis tu joues le 1er coup qui a permi la construction de cet arbre. Ensuite au joueur de jouer puis on recommence (plateau, calcul, jouer).

PS.
l'algo Min-Max et Alpha Beta ont un même principe, sauf l'Alpha Beta c'est le version optimisé de Min-Max.

Ok mais concrètement je fait comment ?
Récupérer l'Etat de ma grille pas de soucis mais par contre comment calculer les coups suivant et évaluer les arbres ?

Personne ?

Comment appliquer une fonction Max et Min qui calcul tout les coups possible de ma grille ?
Il faudrait que je calcul un maximum de coups possible, puis voir à partir de quel emplacement, le score de fin est le plus élevé...

Citation:

---

Envoyé par Suefou

Personne ?

Comment appliquer une fonction Max et Min qui calcul tout les coups possible de ma grille ?
Il faudrait que je calcul un maximum de coups possible, puis voir à partir de quel emplacement, le score de fin est le plus élevé...

---

C'est l'idée.

Tu récupères ton plateau, tu simules un coup du joueur, le coup en réponse que ton IA va jouer jusqu'à une profondeur N , et ceci pour chaque coup que le joueur peut faire.

A là fin (quand tu as construit ton arbre), tu regardes quel position est la meilleure pour toi et tu joues le coup qui a permis de la construire.

Attention a ne pas oublier. Ce genre d'algorithme est exponentiel en temps de calcul. Avec une trop grande profondeur et une grande grille tu va vite avoir besoin d'un deep blue si tu veux jouer correctement.
Commence avec des petites grilles et des petites profondeur.

Salut,

Tu peux déjà regarder ça:
http://fr.wikipedia.org/wiki/Algorithme_MinMax
http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta
http://www.ffothello.org/info/algos.php
Ca te donnera les bases pour faire une IA minimum.
Après, la route est longue...

Arnaud