Algorithmique génétique et jeu de société

Je préfère faire bosser mon code plutôt que bosser dessus !

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bien le bonsoir, cher-ère-s ami-e-s du zeste !

Les cours ont repris, une nouvelle année commence, et paf, mon premier projet de l'école tombe : ça s'agit de développer une petite IA qui joue à l'awalé (dans une variante décidée par le prof), afin d'organiser un petit concours au sein de la promo ; et ce en Ruby.

Tout le monde ou presque ayant décidé de partir sur une approche minimax que je trouve absolument dégueulasse et facile, j'ai convaincu mon binôme que nous nous lancions dans un algo génétique avec apprentissage et tutti quanti. Parce que c'est rigolo, que c'est original et que si on se plante, on le fera en beauté (et le projet n'est pas noté, étant juste un avant-goût de l'année).

Donc. Je voudrais éventuellement vos avis d'experts sur l'approche à envisager (sachant que j'ai déjà quelques idées sous le coude et derrière le crâne), et surtout, si certains ont de quoi me rediriger, de la doc' de qualité (english allowed ofc) pour une introduction efficace au sujet — efficace, parce que le projet est à rendre mercredi soir prochain !

Bonne soirée à vous, en attendant vos réponses ! :)

Édité par firm1

ZdS : un palimpzeste pour le savoir. | Les codes correcteurs, c'est bien.

+1 -0

Je ne suis pas sur d'avoir bien compris les règles de ce jeu, mais il me semble qu'une approche rigolote serait celle des algorithmes d'apprentissage semi-supervisé, parce que tu ne devrais pas avoir de mal à simuler les réactions des IA des autres, surtout si ils utilisent tous la méthode MinMax.

Malheureusement, c'est un domaine que je commence tout juste à explorer, donc je ne suis pas sur de pouvoir en dire quoi que ce soit sans faire de grosse bêtise ^^' Poste donc ton avancement ici, je suis intéressé par le déroulement de ce petit projet :)

+0 -0
Auteur du sujet

Merci pour la piste, je m'en vais l'explorer et je fais suivre. :)

Edit : après avoir lu quelques pages Wikipédia, il semble que les idées que j'ai déjà rassemblées correspondraient à un algorithme génétique implémentant un apprentissage semi-supervisé non probabiliste. Je détaillerai ici plus tard !

Édité par Alkareth

ZdS : un palimpzeste pour le savoir. | Les codes correcteurs, c'est bien.

+0 -0

En fait, l’awalé c'est un jeu combinatoire presque sans explosion, je ne suis pas sur que les méta-heuristique soit le meilleur choix pour ce faire.

A priori, c'est le genre de cas ou un élagage α-β bien fait sera très bon, j'ai du mal a imaginé le gain d'une fonction d'évaluation construite par un algorithme génétique sachant que la difficulté de conception de ces algorithme est justement de choisir les critères pertinent… ce qui revient a comprendre le jeu (et donc a être capable d'écrire une fonction d'évaluation :-° )

Après, ça peut être amusant, mais probablement pas «utile».

Édité par anonyme

+0 -0
Auteur du sujet

"Sans explosion" ? 6 fils par nœud parent, c'est quand même pas mal…

Mais ceci dit, voici l'état de l'art : on est parti pas seulement sur un algo génétique, mais en plus de cela sur un réseau de neurones. Du coup, non-supervisé total et pas besoin de comprendre le jeu (juste d'être capable d'encoder l'environnement).

En gros, l'environnement (plateau, coup précédent de l'adversaire et gains du tour) est encodé sur 81 bits d'entrée qui sont avalés par 81 neurones de couche 1 (par convention), qui redirigent sur 40 neurones de couche 2 puis 3 neurones de couche 3, qui eux donnent directement la sortie nous intéressant : le coup à jouer, encodé donc sur trois bits. C'est vraiment simple comme bonjour, et ça marche ! On en fait combattre une génération aléatoire, on applique l'algo génétique sur les ADNs scorés (ce qui donne une fitness-based selection en cross-over avec une mutation gaussienne par ADN) pour obtenir une nouvelle génération, et ainsi de suite.

Tout n'est pas fini, l'algo de tournoi reste à optimiser pour pouvoir générer notre petit cerveau de manière un peu plus efficace. Si ça intéresse, je peux filer les sources, une bonne partie est réutilisable (et à défaut, amusante à lire). :)

ZdS : un palimpzeste pour le savoir. | Les codes correcteurs, c'est bien.

+0 -0

En gros, l'environnement (plateau, coup précédent de l'adversaire et gains du tour) est encodé sur 81 bits d'entrée qui sont avalés par 81 neurones de couche 1 (par convention), qui redirigent sur 40 neurones de couche 2 puis 3 neurones de couche 3, qui eux donnent directement la sortie nous intéressant : le coup à jouer, encodé donc sur trois bits.

Alkareth

Donc 81 -> 40 -> 3 : pourquoi cette progression, passer de 40 à 3 après avoir diviser par 2 ? (Je ne m'y connais absolument pas en reseaux de neurones mais ca m'intéresse)

http://nodraak.fr/ – Dictateur bienveillant de l'iTeam, logiciel libre et sécurité à l'ECE Paris

+0 -0
Auteur du sujet

Parce que ! :D En fait, il s'agit de conventions dont l'efficacité est en partie démontrée, en partie empirique (d'après ce que j'ai pu lire çà et là). Il est prouvé que trois couches suffisent et équivalent à autant de couches que possible. La taille de la couche d'entrée et de la couche de sortie est fixée par les besoins de l'IA à générer, par convention on prend une taille intermédiaire pour la couche du milieu.

Édité par Alkareth

ZdS : un palimpzeste pour le savoir. | Les codes correcteurs, c'est bien.

+0 -0

"Sans explosion" ? 6 fils par nœud parent, c'est quand même pas mal…

Alkareth

Va voir du côté du jeu de go (ou des échecs dans une moindre mesure) si tu veux voir un jeu avec des explosions :) Effectivement, l'approche des réseaux de neurones me semble un peu violente pour ce genre de problème ^^ En tout cas c'est rigolo.

+0 -0
Auteur du sujet

Je suis d'accord. M'enfin, pour utiliser un arbre et que ça soit intéressant, il faut bien une dizaine de niveaux de profondeur (au moins) et le temps de calcul s'en ressent beaucoup…

Ceci dit c'est jamais comparable au go, et c'est en grande partie pour le fun qu'on s'est lancé dans cette approche. :-°

Édité par Alkareth

ZdS : un palimpzeste pour le savoir. | Les codes correcteurs, c'est bien.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte