Discussion :

[CactO_o's]

Bonjour à tous,

Je suis dans l'optique de créer un joueur d'échecs en C++, mais avant de me lancé dans le code je suis en train de m'occuper de la partie théorique.

Voici les premières informations théoriques :

- Je ne veux surtout pas donnée à cette IA une façon de jouer et des techniques spéciales. Je vais juste lui expliqué et les règles et le faire jouer de nombreuses fois contre lui même.

- Le programme enregistrera les positions des différentes parties dans une base de connaissance afin d'évolué et de connaitre les meilleures coups à faire.

- Lorsque l'IA va devoir joué il va étudié les positions des pièces, regardé dans sa base de connaissance afin de voir le coup le plus intéressant, puis en déduire le meilleur coup.
C'est en fin de partie qu'il rajoute les coups qu'il vient de jouer avec le résultat de la partie (gagner ou perdu).

- Le programme aura plusieurs types de jeux, un mode d'essai plus ou moins aléatoire, ou le programme essai des coups et permet de remplir la base de connaissance en bon et mauvais coup. L'autre mode de coup sera du jeux normal ou le joueur essaye d'utilisé ces meilleurs coups pour gagner.

Maintenant j'ai plusieurs petites questions :

- Est-il vraiment plus intéressant (aussi au niveau de la complexité, si c'est pas trop dure) de ne vraiment apprendre aucune technique au joueur, mais uniquement grasse à sa base de connaissance, ou je vais devoir aussi apprendre au joueur certaine technique de jeux ??
Si oui, comment je vais devoir m'y prendre... ???

- J'arrive à voir quasiment toute la conception du projet juste à ce point près : la reconnaissance de la position actuelle.
J'ai d'abord pensé à enregistrer exactement la position actuelle des pièces, et de regardé les coups déjà fait qui ont fait gagné le plus souvent le joueur afin de les reproduites de maximisé les chances de réussite.

Mais après mure réflexions je me suis dit qu'il y a énormément de position possible et que si je veux quelque chose d'intéressant il me fait vraiment plusieurs coups jouer après cette même position ! Ce qui prendrai un temps impossible à mettre en place et une base de connaissance bien trop grosse.

Je me dis donc qu'une études des pièces importantes serais plus intéressante mais je ne sais pas trop comment m'y prendre.. Un simple pion posé dans un coin peut être inutile et peut être carrément la pièces la plus importante si elle est bien placé.. :s



Voilà je pense que j'en ai dis assez pour être bien compris, j'espère recevoir de votre part un maximum d'aide

Toutes informations est bonne à prendre donc n'hésitez pas !

Un grand merci d'avance à tous !

[seeme]

Bonjour,

Je pense qu'il y a plusieurs choses à prendre en compte.

L'idée d'un système à apprentissage n'est peut-être pas la plus simple des solutions. En effet, il faudrait probablement utiliser des réseaux de neurones, ce qui demande un travail théorique non négligeable (voir les neurones de Hebb), le jeu d'échec ne se prête pas trop à ça (pour débuter en tout cas..).

Quand on résous un problème semblable, le mieux est de prendre autant de temps que nécessaire sur la représentation des données:

* Comment vas tu représenter une pièce?
* Comment va tu représenter le plateau?
* Comment va tu représenter un coup?

Les échecs ont un très grand nombre de combinaisons différentes, c'est ce qui a rendu le challenge intéressent.

Ce qui se fait souvent, c'est de commencer par donner une valeur discrète aux pièces (cette valeur devrait être constante pour simplifier, mais tu pourras la rendre dynamique en fonctions de certains facteurs: un pion à une case de la promotion n'a pas la même valeur qu'un pion isolé).

Ensuite, il faut trouver comment représenter le plateau. Une approche simple serait de définir une matrice avec X(i,j) un lien (identifiant, pointeur...) vers la pièce qui l'occupe. Un problème est que la plupart des cases sont vides, il faut que tu réfléchisses, est-il plus payant de simplement retenir les cases occupées (vecteur)? D'utiliser une matrice carrée? De simplement dire qu'une pièce à une position?

Note qu'il n'y a pas vraiment de bonne réponse, les solutions possibles vont faire jouer la complexité (et donc le temps de traitement), l'espace mémoire...

Ensuite, il faut définir un pas d'itération maximum (en coups ou en demi coups) qui sera le nombre maximum de situations envisagées par l'IA. Note qu'il faut aussi se poser la question de l'utilité de regarder TOUS les déplacements possibles de TOUTES les pièces (il existe des statistiques sur les capacités de joueurs en fonctions de leur niveau; il me semble que la moyenne pour le joueur lambda est de 3 demi coups).

Il faut ensuite construire un graph avec à la racine la position courante, et comme fils les nouvelles configurations envisageables à partir de l'état courant, en se limitant à un certains nombre de générations/pièces/mouvements. Il faut maintenant chiffrer ces nœuds (c'est ce que l'on appel l'heuristique), pour déterminer quel position sera plus avantageuse. A toi de déterminer une fonctions de calcul d'heuristique. Une approche est de regarder combien de points tu gagnes. Il peut être aussi intéressent de regarder combien de points tu n'as pas perdu (ce qui n'est pas la même chose). Il existe beaucoup de solutions, mais seule une bonne heuristique rendra ton IA intéressante.

Je pense que le plus simple est ensuite d'effectuer un élagage alpha-beta, pour ensuite lancer un algorithme Min-Max sur ton arbre, et déterminer le meilleur coup à jouer pour avoir la meilleur heuristique le plus longtemps possible.

J'espère avoir pu t'aider un peu, si tu as des questions, n'hésites pas.

[CactO_o's]

Dans un premier temps, un grand merci à toi pour toutes ces réponses.

Ce qui se fait souvent, c'est de commencer par donner une valeur discrète aux pièces (cette valeur devrait être constante pour simplifier, mais tu pourras la rendre dynamique en fonctions de certains facteurs: un pion à une case de la promotion n'a pas la même valeur qu'un pion isolé).

Les pièces

Je penses faire dans un premier temps un système de permettant de 'noté' une partie en cour.
Chaque pièces possèdera un coup en point grasse à de nombreux critère (bien sur les points sont donné à titre d'exemple):
- Type de la pièce (pion [+100] / tour [+500] ...).
- Nombre de possibilité de la pièce (juste une case [+1] / 15 case [+15] ).
- Si la pièce attaque une pièce adverse (pion [+10] / tour [+50] )
- Si la pièce défend une autre pièce (pion [+10] ... ).

Les cases

Je pense même qu'il serai intéressant de calculer le nombre de cases que possède mon équipe et celle de l'adversaire (et leurs données des points en fonction de leurs importances). Par exemple je suis les Blancs, le roi Noir se trouve à côté d'une case avec un pion noir, celui-ci est défendu par X pions Noir et attaquer par X+1 pions Blancs.
De cette façon je pourrais augmenté considérablement la note de l'équipe Blanche si j'arrive à attaquer avec une pièce de plus cette case (qui permettrai de mettre gravement en danger le roi adverse)

Le plateau

Ensuite, il faut trouver comment représenter le plateau. Une approche simple serait de définir une matrice avec X(i,j) un lien (identifiant, pointeur...) vers la pièce qui l'occupe. Un problème est que la plupart des cases sont vides, il faut que tu réfléchisses, est-il plus payant de simplement retenir les cases occupées (vecteur)? D'utiliser une matrice carrée? De simplement dire qu'une pièce à une position?

Pour le plateau je pensais faire une simple matrice (i,j) avec pour chaque un objet 'case' qui possèderai :
- un attribue 'position' (exemple : a5 / d3 ...)
- un attribue 'pièce'
- un boolean 'vide'
- et pourquoi pas des valeurs permettant de noté la case pour les blanc et les noirs (pour en revenir à ce que je disais avant)

Les algorithmes

Pour les algorithmes j'ai déjà commencé à me renseigné et plusieurs personnes (dont toi) mon proposé d'utiliser les algorithmes MinMax ou Alpha-Beta.
J'ai même eu des idées comme quoi il serait possible d'utilisé un algorithme génétique ..

Pour le moment je ne sais pas trop comment me débrouillé exactement mais grasse au système de notation je pourrais facilement trouvé une des meilleures solutions dans une liste de solutions possibles.

Un chose me chagrine juste est que j'aurais vraiment aimé mettre au points par dessus ce système un apprentissage autonome (plus dur mais carrément plus intéressant), le principe serait d'utilisé des algorithmes complètement différent ou il n'y a qu'un "couche" supplémentaire à ajouter ??


Merci de ton aide !

[seeme]

Bonjour,

Quelques remarques en passant....

Je penses faire dans un premier temps un système de permettant de 'noté' une partie en cour.
Chaque pièces possèdera un coup en point grasse à de nombreux critère (bien sur les points sont donné à titre d'exemple):
- Type de la pièce (pion [+100] / tour [+500] ...).
- Nombre de possibilité de la pièce (juste une case [+1] / 15 case [+15] ).
- Si la pièce attaque une pièce adverse (pion [+10] / tour [+50] )
- Si la pièce défend une autre pièce (pion [+10] ... ).

On prend en général des écart plus petits... (à quoi sert que la valeur d'une tour soit en 10^2?) le but c'est juste de voir la différence (bon, après je chipote là..).

Pour le plateau je pensais faire une simple matrice (i,j) avec pour chaque un objet 'case' qui possèderai :
- un attribue 'position' (exemple : a5 / d3 ...)
- un attribue 'pièce'
- un boolean 'vide'
- et pourquoi pas des valeurs permettant de noté la case pour les blanc et les noirs (pour en revenir à ce que je disais avant)

Le booléen vide est inutile (s'il y a une pièce sur la case, à priori, il n'est pas vide..). Ta case est déjà en (i,j) dans ta matrice. Elle n'a pas à savoir où elle se situe.

Avec le temps, tu apprendras à faire des choses plus simples (champs de bits..) qui permettent d'utiliser des formules d'heuristiques très rapides. Mais bon, il faut bien commencer :p

Pour les algorithmes j'ai déjà commencé à me renseigné et plusieurs personnes (dont toi) mon proposé d'utiliser les algorithmes MinMax ou Alpha-Beta.
J'ai même eu des idées comme quoi il serait possible d'utilisé un algorithme génétique ..

Un algorithme génétique n'est pas le plus adapté. L'objectif d'un algorithme génétique est de partir d'un ensemble de départ de solution à ton problème et à le faire évoluer (par croisements, mutation, combats) pour atteindre une nouvelle population qui soit meilleur (tout en conservant des individus faibles pour garder une bonne hétérogènéité de la population).

Or là, tu as une unique solution de départ qui doit te servir à générer une unique solution (bon, ok on peut juste prendre la meilleur des solutions d'un génétique, mais ça change rien au fait que tu n'as qu'une solution en entrée...).
Autre remarque, l'utilisation d'un génétique "as is" ne te permet pas de prendre en compte le coup de l'adversaire. Ainsi, si une solution est qualifiée de très bonne (bonne heuristique) par l'algorithme génétique à un demi coup N, rien ne permet de dire que tu vas pas te retrouver dans les choux au demi coup N+2.

Si tu veux faire du génétique (qui au passage est un algorithme de la famille des méta heuristiques et de la recherche opérationnelle plus que de l'IA) commence par les problèmes "cas d'école" comme le voyageur de commerce par exemple.

Un chose me chagrine juste est que j'aurais vraiment aimé mettre au points par dessus ce système un apprentissage autonome (plus dur mais carrément plus intéressant), le principe serait d'utilisé des algorithmes complètement différent ou il n'y a qu'un "couche" supplémentaire à ajouter ??

Le truc, c'est que pour faire évoluer ton IA, il faudra d'abord avoir une IA qui marche.Il faudra ensuite mettre en place un réseau de neurone (il doit y avoir d'autres systèmes d'apprentissage, mais j'avoue que je ne connais que celui là). Mais là, il faudra déjà concevoir le réseau (quels neurones? Combien de couches? Bipolaire? Binaire? Continu? Quelle fonction? Cos? aTan?...) et le faire travailler (avec quoi? Comment? Comment mettre en valeur les "bon coups"? Les mauvais?...)

Si tu veux évoluer, commence par ne pas griller les étapes (de même, pour les RdN, commence par des cas d'école pour lesquels tu auras de la documentation).

Il existe pléthore d'algorithme très intéressants (recuit, colonies de fourmis, tabou, RdN, génétique....) de la recherche opérationnel, des méta heuristiques et de l'IA. Le tout est de savoir lesquels utiliser, comment, pourquoi.

Fais moi confiance. Attaque ton problème par une bonne modélisation, applique un AlphaBeta puis un MinMax sur 3 ou 4 demi coups (en essayant que l'IA ne mette pas 3/4 d'heure...) et tu pourras fièrement dire que tu as progressé en IA.

Les RdN, c'est le niveau d'après

[medchok]

Bonjour,

Je vous pire de bien vouloir excuser cette intervention tardive.
Il me semble que différentes techniques pourraient être utiles à la seule condition de bien définir sa fonction objective ou le système à optimiser ainsi que le système de "notation" ou "pondération" et surtout la représentation du problème.

Bien à Vous