Discussion :

[Leinhardt]

Bonjour à tous.

Je suis actuellement en dernière année de licence informatique et ce semestre, nous avons un projet à faire. Mes collègues et moi avons choisi de faire un jeu d'échec.

Aussi, le problème le plus épineux de ce projet nous semble être l'IA puisqu'elle devra être cohérente (et si possible performante). Seulement nous ne savons pas trop comment aborder la problématique qui se pose.

Aussi, j'aurais aimé savoir s'il existe des types d'algorithme particuliers pour aborder la chose ou avoir votre point de vue sur la question (savoir comment vous aborderiez le problème).

Je vous remercie d'avance pour votre aide et j'essaierai au possible de poster mes avancées sur la question.

[zoonel]

Bonjour,

As-tu déjà eu des cours d'IA?

Je penses qu'il faut d'abord choisir quelle type d'IA on souhaite faire.
Souhaite tu une plutot une IA d'apprentissage automatique qui apprends au fur et a mesure des parties, ou alors plutot une IA planificatrice qui en fonction des coups joués calculera quelle direction prendre pour augmenter ses chances de victoire.

JE conseille de te renseigner sur l'algorithme MinMax et non pas l'algorithme A* (dit "a star") pour la planification, et sur le Q-learning et/ou réseaux de neurones pour l'apprentissage. Sachant que pour l'apprentissage stocker les données peut poser problème (gros volume).

[Davidbrcz]

Hum.
zoonel >> A* c'est pour de la recherche de chemin dans un graph

[Jedai]

Renseigne toi en tout premier lieu sur l'algorithme MinMax et son optimisation Alpha-beta, ça te donnera les bases, ensuite tu pourras te poser des questions sur les banques d'ouvertures, l'amélioration de la fonction d'évaluation, l'apprentissage, etc.

--
Jedaï

[zoonel]

zoonel >> A* c'est pour de la recherche de chemin dans un graph

ok, vu le post ci dessus j'ai confondu MinMax et A*; Donc c'est bien min max que je voulais dire

[totaliou]

Bonjour,
Réseaux de neurones pour l'apprentissage.

Efficacité plus que douteuse...

Sinon pas de quoi avoir peur pour l'IA. Vous porurez même en présenter plusieurs, ce sont des problèmes bien documentés...

[jobherzt]

J'avais aussi programmé un logiciel d'echec ya un petit moment, et j'etais arrivé sans trop de difficulté à pondre un truc très largement plus fort que moi (ce qui n'est pas dur, mais c'est tout de même amusant ). Je l'avais interfacé avec winboard, pour ne pas avoir a realiser l'interface graphique.

Tu trouveras plein de tutos sur le net, donc je ne vais pas tout te refaire, mais en gros une IA de jeux d'echecs se compose de deux parties essentielles :

- une fonction d'évaluation. C'est elle qui va juger la qualité d'une position. En gros tu lui donne le plateau de jeux, et elle retourne un score, basé sur différent critères. Basiquement, tu peux compter les pièces (en comptant 1 pour un pion, 3 pour un fou, 9 pour une dame, etc.. si mes souvenirs sont bons). Rien que ca te donne deja un truc honnete, mais il vaut mieux raffiner en tenant compte des positions des pieces (cavaliers au centre, tour et fou devant des lignes ouvertes, ...) A priori c'est le coeur de l'intelligence, c'est ca qui determine la "personnalité" de ton programme, et toute sa capacité tactique. Perso, j'avais piqué quelques tables de score pour la position des pieces dans le code source de Crafty (moteur d'echec open source très fort).

- Une fonction qui va rechercher le meilleur coup. Basiquement, tu listes les coups possibles, puis tu explore recursivement les possibilités jusqu'a une certaine profondeur, et la tu evalues les positions grace a la fonction precedente, puis tu "remontes" en selectionnant a chaque fois le meilleur coup. C'est ce qu'on appelle le MinMax. Il en existe beaucoup de raffinement, par exemple :

- Alpha Beta : Permet d'obtenir le meme resultat que MinMax mais sans traiter tous les coups. En gros, il est possible dans certain cas de savoir qu'un sous arbre ne contient pas de meilleur coup que le meilleur qu'on a trouvé j.a. présent. Des variantes existent (genre negaMax/nega alpha beta)

- On peut remarquer aussi que l'elagage alpha beta est d'autant plus efficaces qu'on traite les meilleurs coups en premier. Donc une astuce non debile consiste à : faire un alpha beta de profondeur 1 ; trier les coups de tel sorte que les coups jugés les meilleurs soient en premier. faire un alpha-beta profondeur 2. Re trier, puis profondeur 3.. etc..

Ca n'a l'air de rien, mais cette methode accelere de maniere hallucinante la recherche des coups. Un autre de ses avantages, est que tu n'as pas a fixer a l'avance la profondeur a laquelle tu vas chercher, ce qui a 2 consequences :

- tu peux jouer en te basant sur un chronometre (tant qu'on a du temps, on approfondit)
- pour un temps fixé, si tes choix sont plus limité (moins de coups a traiter) alors l'algo va automatiquement aller chercher plus profond (typiquement : fin de partie, plus bcp de pieces en jeu, bcp de positions bloquées, il va aller te chercher un mat en 10 ou 15 coups...)

Cette methode s'appelle l'iterative deepening.

Voila, ce ne sont que quelques pistes mais elles sont "classiques". Et meme si ca ne semble pas relever de l'IA, n'oublie pas que la maniere dont tu stocke le plateau de jeu va avoir une grande imprtance, tout comme la maniere dont tu detecte un mat, un echec, etablit la liste des coups... Bref, n'oublie pas que quand elle fonction, l'IA "joue" virtuellement, un très grand nombre de fois.

[strayyy]

Yo! Leinhart, tu serais pas à Limoges, par hasard? xD

Pasque nous, c'est la même, on a le même projet... Ca va etre dur, mais on va tenter de faire comme jobhertz le conseille, et si possible, de s'appuyer sur du code déjà existant...

EDIT: j'ai rien dit