pour programmer une intelligence artificielle d un jeu sur damier.
 
quelle sont les grandes etapes ?

en gros :
 
1. definir une fonction cout pour chaque position
2. appliquer l'algo du minmax sur l'arbre des possibilitées (elagage alpha/beta pour accelerer un peu)

je ne connais rien en intelligence artificielle mais a mon avis il faut que ton programme analyse (avec la prevision de plusieur coups futurs...) toutes les possibilités de jeu et qu'il détermine la meilleure... tu peux peut etre établir une "cote" si tu "manges" un adversaire cette possibilité de jeu gagne 10 points mais si le coup d'apres, l'adversaire t'en mange un a son tour elle perd alors 10 points... fois tous les coups analysés, tu optes pour la solution qui a obtenu les plus de points...

le principe de l'algo du min max :
 
les conditions d'utilisation de cet algotyhme :  
- il te faut tu as une fonction qui établit un score pour une configuration  du jeu donnée.
- il faut que tu puisse déterminer l'ensemble des configurations de jeu possibles en partant d'une configuration et en jouant une fois.
 
ca correspond bien au jeu de dammier.
 
le principe c'est que tu construit un arbre d'une certaine profondeur.
La racine de l'arbre est la configuration initiale. Tu fais ensuite un fils à la racine pour chaque configuration de jeu possible. Tu fais ca jusqu'à arriver à la pronfondeur voulue.
 
ensuite tu applique la fonction à chacune des feuilles de l'arbre. Ca te permet d'avoir un "score" pour chaque configuration de jeu au bout de n tours.
 
ensuite tu applique le min-max. chaque étage correspond à un tour de jeu. Par exemple, les étages pairs corresponderont à tes tours de jeu et les étages impaires aux tours ennemis.
Il faut donc minimiser les scores de l'ennemi et maximiser les tiens.
 
Donc en partant des feuilles, tu détermine le score de l'étage du dessus en prenant le min ou le max des scores des feuilles suivant le fait que ce soit ton tour de jeu ou celui de l'ennemi.
 
En fesant comme ca et en emontant jusqu'à la racine, tu sauras quel chemin prendre dans l'arbre pour maximiser ton score.
 
pour le damier, une bonne fonction d'évaluation c'est la somme, pour chaque dalles, de la distance séparant la dalle de sa position normale.

l'alpha-béta c'est une optimisation de l'ago du min-max.
 
Le principe c'est qu'il y a certaines branches de l'arbres qu'ils ne sers à rien d'explorer parce qu'un branche voisine est plus avantageuse. Ca permet donc de "couper" certaines branche de l'arbre, et donc de limiter le nombre de fonction d'évaluation à executer.
 
bha oui. l'ago min-max c'est quand même bien lourd à executer si le nombre de possibilité à chaque tour est élevé.
 
Pour le damier, ca va : y a que 4 possibilité au maximum à chaque fois.
 
Si tu choisis une pronfondeur de 5, tu auras environ 4 puissance 5 fonction d'évaluation à executer => 1024 fonction (sans compter le calcul des configurations de jeux)
 
avec une profondeur de 10 ca feras plus d'un millions de fonctions d'évalution.

en plus tu peut ajouter une intelligence qui apprends des joueurs (je dit peut etre des conneries j'y connait rien). tu augmente le poids d'une branche si c'est celle emprunté par un jouer qui a gagner la partie... l'homme a peut etre des truc a apprendre a la machine .
 
En fait ca peut etre interessant par exmple par ce moyen de faire apprendre des "strategies" un peu plus elaboré

la ca devient quand même netteemnt plus compliqué !
 
un min-max ca se fait super facilement !

speedyop> moi je dirais ke dans des jeux simples (allant jusqu'aux echecs, echecs presque y compris), la machine bien programmé mettra un patté monumentale à tout pauv cervo humain .  
 
Dans les jeux à forte explosion combinatoire (je pense au go par exemple), ta remarque est valable. On peut par exemple "aider" le minmax par un petit rez de neurones à la place de l'heuristique qui permet d'evaluer chaque pos et reduire grace à une meilleure notation la profondeur de recherche...

mmmmmm,  
alors, difficile d etablir une "cote" car le jeu n etablit pas de score
 
un coup mal placé suffit a perdre, faut plutot voir la stratégie je pense.
 
j ai fait mon TIPE sur les reseaux de neurones, mais vu que y a pas moyen de faire de "cote", je vois pas comment appliqué d algo d apprentissage

j'connais pas bien les regles de ton jeu mais à priori aucun jeu ne possede une fonction cout predefinie, aux echecs, othelo, go etc..., cette fonction est une approximation de la valeur qu'un joueur veut bien donner à une position (c'est en gros lors de la definition de cette fonction que l'imagination peut s'exprimer). C'est une heuristique donc pas besoin d'avoir une super fonction qui te donne un cout exact (qui n'existe sans doute jamais), ca doit etre une fonction qui doit introduire une hierarchie entre les differentes positions. Le fait que dans deux ou trois coups une position jugée forte puisse parraitre catastrophique, importe peu, c'est le min/max qui va faire le boulot de recherche en profondeur.

pis ca peut avoir des limites : par ex, aux echecs, un sacrifice de la dame peut etre payant...
 
Une dame aux échecs c "10 points" ...mais faut prendre en compte la position qu'occupe la dame : si elle controle le centre, et qu'elle peut jouer de ses 2 diagonales et de sa colonne et de sa  rangée, elle vaut bien plus...si jamais elle est enfermée, voir clouée, elle vaudra tt juste 10...
 
Si tu fais ce que tu appelles le alpha/beta, l'algo aura tendence à couper la branche du sacrifice dame, parce que ca fait du -10 pour toi +10 pour l'ennemis...c le pire rapport possible aux échecs si on se base uniquement sur le sys des points communément admis...
 
alors qu'un sacrifice peut permettre un échange, ou une prise de position clé...déjà faut au moins intedire le coupage de branches avant 2 coups, ne serait-ce que pour tester si un échange est possible, ou si c juste un coup foireux
 
 
-->pour othello, tu dois pouvoir faire une machine de guerre avec des heuristiques qui cherchent juste le domination des bords...tu rends très désirables pour l'ordi le périmètre du plateau de jeu...

[jfdsdjhfuetppo]--Message édité par Jubijub--[/jfdsdjhfuetppo]

Perso je vois pas en quoi un alpha beta c de l'intelligence artificielle c "juste un bete algo" et pour moi ya po d'IA la dedans.

Bah, et t'espères programmer avec autre chose que des algo !? jusqu'a aujourd'hui, les ordi savent uniquement appliquer des "bêtes algos" comme tu dis. Des trucs qui simulent un raisonnement logique quoi. Après, si t'as une idée pour faire réfléchir réellement un ordi, 'faut en parler !

[jfdsdjhfuetppo]--Message édité par El_Gringo--[/jfdsdjhfuetppo]

El_Gringo a écrit a écrit : Bah, et t'espères programmer avec autre chose que des algo !? jusqu'a aujourd'hui, les ordi savent uniquement appliquer des "bêtes algos" comme tu dis. Des trucs qui simulent un raisonnement logique quoi. Après, si t'as une idée pour faire réfléchir réellement un ordi, 'faut en parler !

tu c ce ke c ke des reseaux de neurones???????
non parce que ca c de l'intelligence artificielle un truc capable d'apprendre par lui meme  
Voila ce ke c de l'IA ca a rien a voir avec de l'algorithmie pure et dure comme l'est un alpha beta

 
  apprendre par lui meme, mais bien sur    
 
si tu le prends comme ca, l'apprentissage d'un rez de neurones, c'est rien de plus que la retropropagation du gradient (ou un rafinement de cet algo). De plus, avec la puissance de calcul actuelle, on est loin de pouvoir simuler un rez de neurones qui puisse tenir tete à celui d'un etre humain. Les ordis sont inteligents à leur facon, pas à la notre

 
les réseaux de neurone, c'est des algos à la con aussi !
c'est juste parce que c'est pas une machine de vonneuman ('scuse pour l'ortographe) que ca te semble plus "inteligent" ...
 
et puis c'est quand même la mort à mettre en place un réseau de neurone !

on s'éloigne du sujet, lui pourrissez pas son topic

bha on a déjà répondu ... on a bien le droit d'utiliser son topic : il s'en sert plus !
 
c'est pour pas gacher

nan nan, vous pourrissez pas mon topic
serieusement, vos remarques sont interessantes.
 
pour ma part le reseau de neuronnes, n est pas de l IA (car dans IA, y a artificielle),
l idée que je m en fait, c est que l IA = algo "statique" qui a des "deductions" pregrogrammée sur lesquels il se base pour jouer.
 
alors qu avec les reseaux de neurones, la strategie de l ordinateur "evolue" au cours de son apprentissage. le but, etant de lui faire apprendre beaucoup pour qu il soit tres fort

ben un réseau de neurone, c'est vachement artificiel quand même ...
c'est sorte de base de données executable qui s'automodifie ...
 
et puis c'est pas seulement en fonction du nombre d'exemple gournit que le réseau devient efficace. Ca dépend aussi beaucoup de l'implémentation même du réseau (la façon dont il construit au départ et dont il mutte) et de la qualité du jeu d'exemple

ben pour ton IA on avait répondu au début...

vi, d ailleurs je vous remercie      
 
ps: je n 'ai pas donné volontairement le nom jeu dont il est question, car c est quand meme un projet "scolaire"  et que je souhaite faire normallement  
j en ai juste parlé pour avoir des qq pistes où m orienter

ha merde ... je croyais que tu parlais du jeu où on doit reconstituer un puzzle en déplaçant une case vide ...  
 
comment ca s'appelle ce jeu ???

wpk a écrit a écrit :       apprendre par lui meme, mais bien sur       si tu le prends comme ca, l'apprentissage d'un rez de neurones, c'est rien de plus que la retropropagation du gradient (ou un rafinement de cet algo). De plus, avec la puissance de calcul actuelle, on est loin de pouvoir simuler un rez de neurones qui puisse tenir tete à celui d'un etre humain. Les ordis sont inteligents à leur facon, pas à la notre

g jamai parlé de tenir tete a un etre humain on en est tres tres loin et j'espere quon i arrivera pas de si tot.
le truc c kun rez de neurones ou un SE (systeme experts) deduits des trucs de sa propre xp donc il "apprend" par lui meme et pour moi ca c de l'IA pace ke excuse moi mais un alpha beta c rien d'autre kun calcul d'explosion combinatoires de solutions...

benou a écrit a écrit : ha merde ... je croyais que tu parlais du jeu où on doit reconstituer un puzzle en déplaçant une case vide ...     comment ca s'appelle ce jeu ???

 
tu cois vraiment kil programmerais un alpha beta pour un jeu de taquin ??? o non ca seré tellement surprenant c pas l'exemple choisi  d'habitude...  
ou alors il faudrait pitet utiliser un A* ou encore un ptit SSS* si je ne m'abuse???
 
Merde g dit le nom de taquin j'espere que cété pas ca le jeu sinon je t grillé  

 
il n'apprend rien du tout, y'a rien de "magique" dans l'apprentissage d'un rez de neurones, c'est un simple algo qui essaye de minimiser l'erreur entre la sortie et l'entrée et qui stocke ses resultats dans un pauv tablo (c'est les poids "synaptiques" ). C'est du meme niveau de difficulté que le min/max (on appelle alpha beta l'amelioration du min/max par l'elagage des branche initeressantes et c'est pas du tout un "calcul de l'explosion combinatoire"...).

Dj_jim a écrit a écrit :   tu cois vraiment kil programmerais un alpha beta pour un jeu de taquin ??? o non ca seré tellement surprenant c pas l'exemple choisi  d'habitude...

remarque, ce serait pas évident un jeu de taquin dans lequel t'as pas le droit de te tromper une fois ...

benou a écrit a écrit :   remarque, ce serait pas évident un jeu de taquin dans lequel t'as pas le droit de te tromper une fois ...

 
Bah, avec un bon vieux mini max, la solution la meilleur est surement vite trouvée !

Si tu veux chui pas d'accord mais bon...
En tout cas pour la difficulte la chui anti-d'accord un alpha beta c tout con a programmer pour un jeu c juste l'heuristique a trouver qui est baleze, apres c rien a programmer mais un rez de neurones c plus casse couilles a mettre en place kan meme....

 
Et bien là je ne suis pas trop d'accord quand à la difficulté d'un réseau de neurones.
J'ai bossé dessus pendant un an complet et je peux te dire que programmer un réseau de neurones c'est assez compliqué.
Ecrire le code ça va c'est pas ça le plus dur. Le plus compliqué c'est de lui faire apprendre. C'est a dire ne pas faire de l'overfitting et donc le faire "trop apprendre" ce qui veut dire qu'il sera incapable de se demerder avec un cas nouveau ni de faire le contraire non plus.
Le plus gros problème avec RdN c'est l'apprentissage ET le jeu d'essai a effectuer après. Après tu l'essayes sur des exemples aléatoires et généralement.... tu recommences...
 
Bonhomme

bonhomme> entierement d'accord, à l'utilisation, ca peut etre tres compliqué, en tout cas ca demande des nombreux essais et une bonne definition de la taille de la base d'apprentissage pour ne pas apprendre justement le bruit (en plus, y'a des details non negligeables comme le nb de couches, le nb de noeuds, le choix d'une fonction non lineaire pour la reponse...) Par contre, pour ce qui est de la programmation du truc, c'est tres facile, aussi facile que la prog du minmax (et dans bien de cas, la def d'une heuristique satisfaisante pour evaluer une pos est aussi compliqué que de mettre en place un rdn)

Totalement d'accord la programmation doit pas etre le plus casse couille c clair que c pas ca le plus dur comme dans bien des cas, mais c plutot la conception  le + cho.
Pour reussir a faire "apprendre kk chose a un RdN" c pas gagné et pour peter une heuristique capable de battre Kasparov aux echecs c pas evident, la programmation c loin d'etre le + dur on est bien d'accord la dessus.

une heuristique capable de battre n'importe quel joueur d'échec oui, mais pour kasparov, ils avaient programmé le calculateur avec ses coups préférés, et son style de jeu...de sorte que le rézo anticipait avec un finesse bcp plus grande la profondeur de coups de kasparov...