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

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 !

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

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 !

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».

"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).

Moi, perso, ça m'intéresse pour le fun (parce que j'ai vu vite fait les algos génétiques et réseaux de neurones dans un domaine légèrement différent)

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)

Parce que ! 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.

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.

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.}