Pour la réalisation de mon projet de fin d'années d'IA, je recherche deds exemples d'algos de fonctions d'évaluation d'un coup pour jeu d'échec, et surtout de leur élaboration....
 
En effet j'aimerais comprendre comment on détermine un algo de fonction d'évaluation...
 
 
Mon projet portant sur un jeu d'échec hexagonal, c pkoi je veux d'abord comprendre la programmation de l'IA d'un jeu d'échec classique...
 
Merci de me conseiller vos sites/tutoriaux et ouvrages  

Si je me souviens bien, l'algo porte un nom.Je crois que c'est Alpha-Bêta, mais je ne suis pas sûr. De plus il y a des mots clés en rapport, comme backtrack par exemple. Fait une recherche sur google.

En effet il s'agit de l'algo alpha-béta... Mais moi ce que je veux savoir c commetn on détermine la fonction d'évaluation utilisé par alpha-béta...
 
 
Merci pour le mot clé je vais essayer...

Euh... vous confondez pas avec l'algo mini-max ?

Non alpha béta est bcp plus puissant que mini-max....
 
Mais ma question ne porte pas qur le type d'algo à utiliser...
Mais sur comment détermine-t-on une méthode pour évaluer un coup ?

en cherchant : iterate deepening, tu devrais trouver d'autres trucs pour tes algos

thx
 
Et UP au cas où....

A ce que j'en sais ca fonctione selon de regles auquelles tu associe des poids, exemple :
- la reine adverse est prise = +1000  
- la colonne x est degagée = +10
- le pion est passé = +30
- la reine est enfermé dans un espace reduit = -20
...
...
 
a chaque niveau noeud de l'arbre alpha-beta, tu associes le poids estimé de la position que tu calcule avec chacune des regles.

 
les algo du min/max ou bien alpha/beta, ne sont que des algos d'optimisation de recherche dans un arbre (savoir éliminer le parcours de branche n'aboutissant qu'à une position de jeu non satisfaisante). Evaluer les feuilles d'un arbre (= fin de l'arbre) est la mise en place d'une fonction heuristique qui déterminera le coup le plus probablement avantageux à partir de l'arbre préalablement construit (de profondeur raisonnable). La difficulté de l'IA de jeux de plateaux (pb de dénombrement trop important) réside bien entendu dans la fonction d'évaluation du meilleur coup possible! c là qu'à lieu la différence fondamentale entre une bonne IA et une mauvaise !
 
bonne chance!  

"l'algo de fonction d'évaluation" comporte deux parties importantes :

• calcul des différentes possibilités en optimisant au maximum, par exemple avec l'alpha-béta ou les hash tables pour les finales
• évaluation des positions obtenues. Et là ... il faut avoir des notions aux échecs pour intégrer les facteurs positionnels à ton soft. Non seulement ça mais également les intégrer d'une manière qui s'harmonise avec ta manière de coder l'algo de recherche

l'annee derniere, login avait publiee un numero traitant largement des probleme algo. lies aux jeux d'echecs, et j'ai ce numero a la maison. J'essaierai de te filer des ref.

Bon...
MinMax = MiniMax = NegMax = NegaMax.
On est d'accord, ces quatres fonctions servent à construire l'arbre.
Alpha-Bêta est un test à ajouter dans l'un des deux algos (MinMax ou NegMax, donc) pour couper un maximum de branches inutiles lorsqu'on remonte les évaluations.  
Pour que les coupures Alpha-Bêta soient maximales, il faudra que tu généres les coups suivants dans le meilleur ordre possible, c'est-à-dire les meilleurs d'abords. Si tu ne comprends pas pkoi, essaie de potasser Alpha Bêta.
En fait, pour faire une bonne IA, il faut s'axer sur trois voies, qui sont d'ailleurs dépendantes les unes des autres :
 - Amélioration du NegaMax avec des ajouts (Alpha-Bêta évidemment, plus différentes astuces (coup nul, suppression de l'effet d'horizon, etc.))
 - Amélioration de moveGen (recherche des coups à jouer dans l'arbre) en supprimant les coups interdits par la règle de ton jeu, et en mettant à la fin les coups à priori inintéressants).
 - Enfin, le plus important, la fameuse fonction d'évaluation.
Il faut s'appliquer à ce que celle-ci reste purement STATIQUE!!!
C'est en effet un gros piège quand on débute avec MinMax ou NegMax : on essaie de savoir qui joue quoi, qui a joué quoi, qui joue en prochain, alors qu'il faut se borner (et c'est déjà pas mal...) à une évaluation du plateau de jeu. C'est bien sure MinMax (ou NegMax) qui se charge d'inverser la valeur des coup à chaque niveau de ton arbre de recherche.
Pour le problème spécifique au jeu d'échec, il ne me reste qu'à te recommander chaudement de regarder le source de GNU-Chess, la référence open-source.

J'ai l'URL du gars qui a écrit l'article (qui n'est en fait qu'une copie du site avec des images   ):
http://www.ifrance.com/jeudechecs/
 
Merci qui ?

Marrant, j'ai bossé sur un projet un peu similaire...Pas en tant que programmeur (quoique) mais en tant que conseillé "échecs". Je ne sais pas ce que c'est devenu...une fois mes conseils distillés, la fonction mise en place, il y avait encore plein de boulot et je les ai perdu de vu.
 
Schématiquement, il s'agissait de donner tous les éléments permettant de juger la position. On avait classer ca en plusieurs éléments:
- Structure de pion
- Fou (en lien avec la structure de poin -> le nombre de pion, leur case de couleur, etc. change tout)
- Cavalier (par comparaison au fou)
- Roi, sécurité du roi (par rapport à reine, aux possibilités d'attaque)
- Probabilité de gain dans une position similaire trouvé dans la base de donnée (Très important: ca fait la force d'un programme et ca "remplace" l'intuition d'un joueur humain)
- etc.
 
C'est la somme/moyenne de ses valeurs qui nous donnait l'évaluation. On ne calculait pas toutes ces valeurs à chaque noeud/variantes (dépend de la situation et de son évolution)
 
On avait aussi une fonction spéciale pour les finales de pion + pièce mineure. (parce que là la puissance brute de l'ordi suffit souvent)
 
Si tu veux plus d'info (et que t'es sérieux ), mail moi. Ca m'amuse de bosser là dessus.
A+

thx

Dans un vieux linuxmag, il y avait un articles qui expliquait l'évolution des ia pour les jeu d'échecs

je veux bien être consultant échecs aussi

Bon bah merci à vous tous... Je vais regarder tout ça... Pour ceeux que ça à l'air d'intéresser, je vous tiendrais au courant de l'évolution du projet qui n'a pour l'instant pas commencé...
 
Mais c à rendre en juin, et je sais que je dois/vais utiliser alpha-béta...
 
Willyzekid> je pense être assez sérieuse, donc je te tiendrais aussi au courant... Enfin j'essaierais...
 
 
EDIT : je sais plus si je l'ai dit ou pas... Mais mon but c dee comprendre la fonction d'évaluation d'un coup sur un échéquier classique pour déterminer la fonction d'évaluation d'un coup sur un échéquier hexagonal...

Le problème c'est que pour avoir une fonction d'évaluation fiable sur un échiquier hexagonal il faudrait un certain recul par rapport à la pratique d'un tel jeu ... qui n'existe pas !
Quelle structure de pions adopter ? L'espace est-il plus important que le temps ? Faut-il centraliser ?
Ce sera difficile de trouver une réponse.

Si si ce jeu existe dans la vie réelle, mais je ne crois pas qu'il est d'adaptation sur PC, juste au niveau de la plateforme, et aucune IA n'a jamais été faite sur ce jeu...

Bon OK il existe mais il n'est pas réellement pratiqué et les principes stratégiques de base ne sont pas établis de manière aussi approfondie que le jeu d'échecs traditionnel ...

C bien mon problème...
 
Enfin pour ceux que ça intéresse je dois m'y mettre plus sérieusement maintenant...
Donc je pourrais vous tenir au courant de mon avancement...
 
Pour ceux qui veulent une présentation du jeu c ici
 
Bon bah je repasserais plus tard  pour vous tenir au courant...