Algorithme d'apprentissage automatique pour jouer à Connect Four

14

Je lis actuellement sur l'apprentissage automatique et je me suis demandé comment l'appliquer à la lecture de Connect Four .

Ma tentative actuelle est un classifieur multiclasse simple utilisant un modèle de fonction sigmoïde et la méthode one-vs-all.

À mon avis, les caractéristiques d'entrée doivent être l'état (disque du lecteur 1, disque du lecteur 2, vide) des champs de grille 7x6 = 42.

La sortie serait le numéro de la ligne dans laquelle mettre le disque. Parce que c'est un nombre discret entre 1 et 7, je suppose que cela peut être traité comme un problème de classification multiclasse.

Mais comment générer des exemples de formation utilisables en apprentissage supervisé?

L'objectif principal est de gagner la partie mais le résultat n'est évidemment pas connu lors de tous les tours sauf le dernier. Si je laisse juste deux joueurs qui décident au hasard quoi faire jouer des milliers de fois l'un contre l'autre, sera-t-il suffisant de simplement prendre tous les tours faits par le vainqueur de chaque manche comme exemples d'entraînement? Ou dois-je le faire d'une manière complètement différente?

Edit: Comme suggéré dans les commentaires, j'ai lu un peu sur l'apprentissage par renforcement. D'après ce que je sais comprendre, Q-Learning devrait faire l'affaire, c'est-à-dire que je dois approximer une fonction Q de l'état actuel et l'action à prendre pour être la récompense cumulative maximale commençant dans cet état. Ensuite, chaque étape serait de choisir l'action qui aboutit à la valeur maximale de Q. Cependant, ce jeu a beaucoup trop d'états pour le faire, par exemple comme une table de recherche. Alors, quel est un moyen efficace de modéliser cette fonction Q?

À M
la source
2
Google "Apprentissage par renforcement"
George
D'accord, je suppose que cela s'applique vraiment exactement à ce problème. Il semble qu'il y ait beaucoup de lecture à venir. Des conseils ou des recommandations plus spécifiques?
Tom
1
Si j'en savais plus, je la posterais comme réponse :) Malheureusement, je n'ai aucune expérience de l'apprentissage par renforcement. Je commencerais par le livre "Machine Learning" de Tom Mitchell. C'est un très bon livre d'introduction et contient également un chapitre sur l'apprentissage par renforcement.
George
1
Ce dernier, je suis juste curieux de savoir l'apprentissage automatique et d'essayer de le connaître.
Tom
1
@Tom, il existe de meilleures façons d'apprendre à connaître les techniques d'apprentissage automatique. Je commencerais par des techniques de classification et de régression plus basiques et j'irais de l'avant. Vous pouvez récupérer des ensembles de données à partir du référentiel de données d'apprentissage automatique de l'UCI, consulter les notes de cours d'apprentissage automatique d'Andrew Ng (Stanford) et obtenir la mise en œuvre. Passer directement à essayer de résoudre Connect 4 en utilisant l'apprentissage par renforcement semble assez maladroit et trop compliqué.
Nick

Réponses:

8

Juste pour offrir une alternative plus simple à l'apprentissage par renforcement, vous pouvez utiliser l'algorithme de base minimax pour rechercher de bons mouvements et utiliser l'apprentissage automatique pour évaluer les positions de la planche.

Pour clarifier, minimax construit un arbre de jeu où chaque nœud est étiqueté avec le résultat des feuilles (1 = le joueur A gagne, 0 = le joueur B gagne), en supposant que A choisit les coups qui maximisent ce nombre, et B choisit les coups qui le minimisent.

À moins que le jeu ne soit très simple, vous ne pourrez pas construire l'arborescence de jeu complète jusqu'aux terminaux. Vous devrez plutôt vous arrêter à des positions de plateau inachevées et évaluer les feuilles avec une certaine heuristique (essentiellement la probabilité que le joueur A gagne à la position donnée). Vous pouvez laisser un algorithme d'apprentissage automatique comme un réseau de neurones essayer d'apprendre cette probabilité en connectant quatre positions avec des résultats connus.

Pour générer des exemples de formation, vous pouvez créer votre lecteur minimax avec une simple heuristique, le laisser jouer mille fois, utiliser ces jeux pour former votre premier réseau de neurones, puis le laisser payer mille jeux et ainsi de suite. Avec un peu de chance, votre système s'améliorera à chaque génération.

Peter
la source
2

J'ai écrit un blogpost sur l' utilisation de Minimax pour jouer connecter quatre il y a un certain temps. Vous pouvez voir le code en action ici . Si vous avez besoin de former vos modèles, vous pouvez peut-être le laisser jouer quelques milliers de jeux contre mon implémentation minimax.

Lukas Vermeer
la source
N'hésitez pas à bifurquer mon code sur Github. github.com/lukasvermeer/minimax
Lukas Vermeer
Bienvenue sur Stack Exchange. Ceci est un site de questions et réponses . Veuillez lire notre FAQ , en particulier comment y répondre . En particulier, nous ne voulons pas de messages qui consistent uniquement en un lien vers une réponse. Merci pour votre contribution, mais pourriez-vous résumer les points principaux de votre article de blog dans votre article ici?
Gilles 'SO- arrête d'être méchant'
Je suis désolé, mais la question initiale était "comment générer des exemples de formation utilisables en apprentissage supervisé?" J'ai fourni des liens vers du code de travail qui peut être utilisé pour les générer. Je ne vois pas comment l'écriture de plus de texte ci-dessus aiderait à répondre au besoin d'origine.
Lukas Vermeer
"Un lien vers une solution potentielle est toujours le bienvenu, mais veuillez ajouter du contexte autour du lien afin que vos collègues utilisateurs aient une idée de ce que c'est et pourquoi il est là. Citez toujours la partie la plus pertinente d'un lien important, dans le cas où le site cible est inaccessible ou se déconnecte de façon permanente. " Je pense que j'ai fait le premier. Ce dernier ne serait pas pertinent. La question d'origine a besoin d'exemples de jeux, pas d'explication sur la façon de mettre en œuvre une solution.
Lukas Vermeer