Version imprimable
Bonjour a tous je suis étudiant,
je dois programmer un jeu de go en java, j'aimerais programmer une ia mais pour le jeu de go c'est particulier j'ai lu qu'il faut utiliser l'algorithme minmax ,mais je ne comprend pas comment programmer la fonction d'évaluation merci de prendre de votre temps pour m'expliquer
Salut,
As tu regardé les tutoriels sur le minmax, et sur le alpha-beta, une optimisation du minmax ? Les exemples de code sont en c, mais se traduisent aisément en java.
Euuh, tout comme aux dames, aux échecs, au puissance 4, au backgammon, au shôgi...Citation:
Envoyé par kevin254kl
Les meilleurs programmes actuels utilisent une fonction d'évaluation "Monte-Carlo", genre ils jouent des coups au hasard et terminent un maximum de parties, le résultat de l'évaluation du coup est le nombre de parties aléatoires gagnées. Doit y avoir des sources qui traînent...
De mémoire le jeu de Go est d'ailleurs encore plus difficile à mettre en IA que le jeu d'échecs. Alors qu'au jeu d'échec le nombre de pieces par rapport à ton adversaire peut aider à indiquer si ta position est bonne, au jeu de go, tu peux retourner presque tout le jeu en un coup :)
Il y a eu une percée relativement récente, avec justement l'utilisation d'un algo MC. Avant ça les meilleurs programmes, basés sur des fonctions d'évaluation (qui "connaissaient" davantage que les règles du jeu) étaient d'un niveau très moyen, maintenant ils battent la plupart des amateurs, s'ils ont des ressources suffisantes. Même si on y a réinjecté quelques "connaissances" supplémentaires.
Il n'y a pas la fonction d'évaluation.
Tu peux trouver une heuristique par toi-même ou chercher sur le net les idées de chercheurs ou thésard. Dans tous les cas, ça reste une heuristique.
Tu peux en trouver des triviales (par exemple le nombre de pierres blanches moins le nombre de pierres noires) qui fonctionnent plus ou moins, tu peux en combiner plusieurs.
Quoi qu'il en soit, l'heuristique est une fonction empirique qui permet de donner une "note" (un genre de nombre magique) à une position sur un plateau afin de sortir une bonne position (ou la moins pire si l'heuristique est un peu naze) parmi toutes celles calculées.
Je t'encourage vivement à commencer par une heuristique très simple (même simpliste genre stupide comme le simple comptage des pierres), avec une méthode de monté-carlo sur un tirage aléatoire de position avec une profondeur raisonnable pour commencer. Ce sera relativement simple à implémenter. Une fois tout mis en place, tu pourras améliorer les différents modules : l'heuristique, le tirage aléatoire (en privilégiant certains coups intéressants) et la profondeur de recherche.
Mais tu peux préférer aussi une recherche arborescente (min-max avec ou sans élagage par exemple). Même dans ce cas, tu dois trouver une heuristique.
Le minimax est heuristique, et nécessite une fonction d'évaluation de la position. Les algos récents de go sont plutôt simples et utilisent le pourcentage de parties gagnées à partir de la position, en jouant des coups légaux au hasard jusqu'à la fin de la partie. Les pierres noires moins les pierres blanches, c'est absurde comme évaluation : tant qu'il n'y a aucune prise c'est stable, genre 0 si c'est à Noir de jouer, et 1 si c'est à Blanc.
Ou alors je ne sais pas ce que tu appelle "une heuristique".
Oui, c'est simple et absurde, je l'ai précisé. Mais ça permet de ne pas être bloqué dans l'avancement du projet ;-)Citation:
Envoyé par JoeChip
Car de ce que j'ai compris, l'IA est optionnelle, c'est un plus. Présenter un jeu fonctionnel avec une IA nulle à cause de l'heuristique un peu naze, c'est facilement défendable. Par contre présenter un projet pas fini en expliquant que tout le temps a été passé sur la recherche d'une heuristique, le gars ne part pas vainqueur... Mais c'est juste un point de vue sur le peu d'info donnée :ccool:
je vous remercie je vais regarder le minmax et aussi commencer par programmer pour des joueur avant l'ia et m'inspirer de vos conseil.