Réseaux de neurones vs algorithmes génétiques dans des jeux comme Tic Tac Toe?

9

Actuellement, je fais un projet qui consiste à créer une IA pour jouer au jeu Gomoku (c'est comme le tic tac toe, mais joué sur un tableau 15 * 15 et nécessite 5 d'affilée pour gagner). J'ai déjà réussi à mettre en œuvre une IA tic tac toe parfaite en utilisant l'apprentissage Q et en stockant les états / actions de jeu dans une table, mais pour un tableau 15 * 15, les états de jeu possibles deviennent trop grands pour mettre en œuvre ce projet.

Ma question est, dois-je utiliser des réseaux de neurones ou des algorithmes génétiques pour ce problème? Et plus précisément, comment dois-je implémenter cela?

Conway
la source
2
Bienvenue chez AI! Excellente question à mon humble avis.
DukeZhou

Réponses:

7

Pour Gomoku, il semble un peu exagéré d'utiliser les réseaux de neurones ou l'algorithme génétique, car les deux prennent un certain temps et le plus souvent, n'allez pas comme vous le souhaitez. L'arbre de jeu de gomoku est assez grand, mais vous pouvez obtenir une IA décente de minimax, l'élagage de l'arbre de jeu et une bonne fonction heuristique (qui comprend le comptage des 2s, 3s, 4s, etc.) à moitié et à moitié, par opposition à la cartographie sur tout l'espace.

Si vous n'êtes pas familier avec l'élagage alpha beta et minimax, voir https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

Si vous voulez vraiment utiliser des réseaux de neurones ou des algorithmes génétiques, vous pouvez le faire pour l'expérience d'apprentissage. Concernant les réseaux de neurones, une façon de le faire est la suivante:

  • Définissez une fonction heuristique qui reçoit une entrée d'état de la carte (séquence de 0,1,2 pour vide, noir, blanc) et génère une valeur de «qualité» de l'état de la carte. Le réseau neuronal est notre fonction heuristique.
  • En supposant que les mouvements dans ces jeux sont optimaux, entraînez-vous sur la différence entre le meilleur mouvement actuellement (par vos paramètres actuels) et le mouvement que vos données disent être le meilleur. C'est ainsi que nous définissons notre fonction d'erreur! Ainsi, vous minimisez cette différence afin que ce que votre réseau de neurones dit le plus fort soit idéalement ce que vos données de jeu disent le plus fort (l'optimisation de cette fonction d'erreur peut se faire via une rétropropagation ou un algorithme génétique).
  • Idéalement, à ce stade, vous pouvez maintenant utiliser votre fonction d'évaluation basée sur un réseau neuronal («fort») pour vos évaluations de déplacement d'arbre de jeu au lieu d'heuristiques codées en dur.

Bien sûr, ce n'est qu'une façon, et vous devez d'abord trouver les données du jeu.

Une remarque latérale, l'application d'un algorithme génétique peut se produire de plusieurs manières, telles que l'optimisation des paramètres dans un réseau neuronal comme mentionné ci-dessus ou la recherche dans l'arbre de jeu, alors assurez-vous que vous définissez clairement comment définir le problème avec! Il en va de même pour d'autres façons d'appliquer un réseau de neurones.

Enfin, il est utile de savoir que gomuku est résolu. Voir /programming/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe pour les pensées et les idées des autres.

sma
la source
2
Joli point sur Gomoku en tant que jeu résolu. Cela permet de valider facilement la force de l'IA (c'est-à-dire que cela résout le jeu et exprime un jeu parfait, ou joue-t-il simplement de manière plus optimale qu'un adversaire, comme dans le cas d'AlphaGo.)
DukeZhou