Discussion :

[Enalde]

Bonjour à tous,

Dans le cadre d'un projet pour mes études, je dois développer en C la machine MENACE, une IA capable d'apprendre à jouer au morpion. Voilà un site qui explique tout bien.

Je suis en train de me poser la question de la bonne structure de donnée à utiliser pour stocker les "boîtes d'allumettes" (sur le site il est indiqué qu'il n'y a besoin que de 304 allumettes car c'est tout le temps la machine qui joue en premier. Sauf que dans mon cas, c'est au joueur de décider qui commence, ce qui fait exploser les différents cas possibles).


Première idée : un tableau de 3^9 cases

Si on code chaque format possible au morpion en base 3 (rien = 0 * 3^i, X = 1 * 3^i, O = 2 * 3^i, avec i le numéro de la case du plateau), le nombre donné, nous donne l'indice d'une case du tableau. Dès lors chaque case du tableau est une "boîte d'allumettes".
Avantage : il est facile d'accéder à une case du tableau. Cela rend la recherche de symétrie très facile.
Inconvénient : Beaucoup trop de mémoire gâchée à mon avis, car il existe indice qui ne correspondent pas à des cas possibles au morpion.


Deuxième idée : une table de hachage

Toujours en base 3, si on arrive à faire une fonction de hachage potable, on peut faire en sorte de supprimer l'inconvénient évoqué plus haut. En effet, à ce moment lorsque MENACE arrive sur un cas qu'il ne connait pas encore, il peut le créer en le rajoutant à une liste de la table de hachage.
Avantage : Facilité de recherche de symétrie + le fait d'avoir le strict nécessaire en termes de mémoire.
Inconvénient : trouver la bonne fonction de hachage, ce qui est loin d'être faisable x)


Troisième idée : un arbre

Cette structure de donnée se construirait au fur et à mesure que MENACE apprend. Un père aurait comme fils, tous les différents coups possibles en étant dans la position de jeu du père. Nous aurons alors toujours le strict nécessaire en termes de mémoire.
Avantage : Pas de mémoire "en trop".
Inconvénients : La recherche de symétrie devient beaucoup plus ardues, et lentes, comparée aux autres méthodes...


Quatrième idée : une simple liste chainée

C'est la méthode qui me convainc le moins, car la recherche serait trop lente dans ce type de structure de donnée. Mais je la mets quand même pour savoir ce que vous en pensait.



Voilà voilà sur quoi j'hésite, que mon conseillerez-vous, ou avez-vous d'autres idées ? Je suis preneur de toutes propositions !

[Matthieu76]

Pour le morpion il y a 9! combinaisons possible soit 362 880 (9*8*7*6*...).
300 000 est un petit nombre tu peux juste calculer toutes les combinaisons et retirer celle qui te font perdre, ensuite l'IA choisi un chemin au hasard dans l'arbre.