Sans l'aide d'un réseau de neurones, le développement d'une Intelligence Artificielle (IA) pour Abak s'est avéré être un défi de taille et, avec le temps, a atteint une limite apparente. Cependant, ce fut un processus amusant à développer, et elle est toujours en service pour jouer aux niveaux « facile », « normal » et « avancé ». Ceci est un article sur son fonctionnement et sa création.

Phase 1, GOFAI PHP

La première version de l'IA d'Abak a été écrite en PHP et était vouée à faire planter le système avec des erreurs de « mémoire insuffisante », mais elle a ouvert la voie à une version C++. C'était le terrain de prototypage pour que je comprenne comment diable on crée une IA. La première fois que je l'ai lancée connectée au serveur web (je jouais donc effectivement contre elle), elle a eu besoin de 15 très longues secondes pour sélectionner un coup, et quand j'ai vu le serveur bouger tout seul, je suis devenu fou de joie et j'ai peut-être fait une petite danse. Pas sûr.

Phase 2, GOFAI C

Ainsi, la version C/C++ de l'IA, la première à passer en environnement de production, mon cher moteur GOFAI, est née des cendres de PHP. Elle exécute 29 algorithmes d'analyse sur des milliers de positions en nanosecondes, et fonctionne comme suit :

• Étant donné une position de plateau et un ensemble de dés.
• Calculer un état
• Obtenir chaque mouvement possible.
• Analyser chaque mouvement et lui attribuer un score.
• Sélectionner le « meilleur » score.

Voici un diagramme du processus.

Il est composé de quatre fonctions principales :

• Obtenir les actions (Calculer les mouvements valides) :

  Étant donné une position de plateau et un lancer de dés, il calcule chaque mouvement valide.

  Les mouvements valides peuvent aller de 0 à des dizaines de milliers.

  Dans chaque langage où j'ai écrit cela, j'ai adopté une approche récursive inutile qui rend le code si difficile à déboguer, mais c'est tellement beau. Il compte quelques centaines de lignes de code mais m'a pris des semaines à écrire, puis encore des semaines à traduire en C.

• Obtenir l'état (Calculer l'état du plateau) :

  Étant donné une position de plateau, il calcule un état sémantique, ils sont assez explicites :

  • Début
  • Milieu de partie
  • Course sans espoir
  • Course avec espoir
  • Fin de partie
  • Entrée au jan intérieur

• Analyser le mouvement (Calculer les scores pour une position de plateau) :

  C'est de loin l'algorithme le plus étendu de tous. Il analyse les caractéristiques du plateau, chacune renvoyant un score, puis, en fonction de l'état calculé précédemment, applique des facteurs à ceux-ci, afin de pouvoir donner de l'importance à différents aspects de l'analyse en fonction de l'état du jeu.

  L'IA a commencé avec 8 algorithmes et a fini avec 29, un aperçu :

  • Hauteur des colonnes
  • Risque d'être frappé
  • Risque d'être piégé
  • Force du jan intérieur
  • Pivots d'échappée
  • Pions à la barre
  • Pions en sécurité

  Beaucoup de ces algorithmes étaient très basiques au début ou n'existaient tout simplement pas.

  Au fil du temps, j'ai travaillé dessus, ajoutant des fonctionnalités et affinant les facteurs.

• Sélectionner l'action (Sélectionner le « meilleur » mouvement) :

  Cet algorithme est relativement trivial si vous voulez juste le score le plus élevé (comme le fait le niveau Avancé).

  Pour les niveaux Normal et Facile, il sélectionne un mouvement aléatoirement parmi une liste des meilleures actions ; la taille de celle-ci (ou sa tolérance aux mauvais mouvements) est déterminée par le niveau.

Grâce au C, ce moteur est extrêmement rapide, je l'utiliserai donc toujours comme fonction principale d'obtention des actions.

Phase 3, Réglage du GOFAI C

Pour déboguer, dépanner et affiner ce moteur, j'ai dû construire de nombreux outils pour surveiller le processus de prise de décision. Contrairement au réseau de neurones, chaque décision ici est auditable, donc on avait au moins ça.

Le processus était amusant mais douloureusement lent. J'ai beaucoup joué contre le CPU, et chaque fois que je voyais un mauvais coup, je venais sur ces outils pour vérifier ce qui n'allait pas. Parfois, cela m'envoyait sur la voie de la correction d'un algorithme, du réglage d'un facteur ou de la construction d'un nouveau modèle d'analyse. Parfois, et c'était magnifique, cela m'amenait à reconsidérer mes stratégies d'Abak Evolution.

Avec le temps, j'avais une IA assez solide, mais la perfectionner davantage devenait de plus en plus difficile. Il y avait tellement de lignes de code, tellement de scénarios, des opérations si massives, que le débogage au niveau du code était une tâche lourde, et l'affinage manuel des facteurs ne donnait plus de résultats.

Phase 4, Désespoir

Mais j'en voulais plus parce que je joue à Abak, et j'avais besoin d'un joueur solide pour m'amuser, et il n'y avait pas beaucoup d'humains qui y jouaient à l'époque (et même au moment où j'écris ces lignes).

Et cette approche a beaucoup d'inconvénients :

• Elle calcule l'état du plateau en fonction de sa position actuelle, et cet état est utilisé pour modifier les facteurs des algorithmes d'analyse pour chaque action valide. Cette action, cependant, aurait pu modifier l'état, mais le moteur ne prend pas cela en compte.
• L'affinage manuel des facteurs nécessitait une quantité de temps considérable. Des moments amusants certes, mais énormément de temps néanmoins.
• L'état est brutalement difficile à calculer, étant donné le nombre de scénarios possibles. Cela a toujours été un algorithme imparfait.
• L'équité du jeu est impossible à calculer avec précision, car ce moteur a un système de score arbitraire pour chaque algorithme d'analyse, et le score final ne reflète pas une probabilité de victoire, il fonctionne simplement comme un score comparable entre différentes positions de plateau. On peut dire qu'il a une valeur relative plutôt qu'absolue.

Phase 5, L'éveil

Et puis, un jour, en 2018, Google a battu le champion de GO avec son réseau de neurones AlphaGo, et il y a eu tellement d'agitation, et de nouvelles bibliothèques d'apprentissage automatique open source sont devenues disponibles, utilisant des GPU domestiques pour accélérer le processus d'entraînement.

Bien sûr, je connaissais déjà un peu les réseaux de neurones, mais je n'en avais jamais construit un, et honnêtement, je les voyais comme une tâche au-delà de mes capacités.

Je n'ai donc pas pu résister, et le niveau expert ne fonctionne plus sur le moteur GOFAI, sauf pour la partie obtention des actions.

Mais cette histoire s'arrête ici.

Si vous avez lu tout ça jusqu'ici, je suis impressionné.

Ce texte a été écrit à des fins de référencement par l'honnête équipe d'Abak Evolution,
Alias Samy Garib.