PlayAwale : les algorithmes derrière les IA

Un trou à 2 graines juste avant le tour de l’adversaire. Une réserve qu’on garde un peu trop longtemps. Un coup qui capture peu mais qui coupe toute retraite. Si vous jouez sérieusement à l’awale, ces réflexes vous parlent déjà : ce sont exactement ceux qu’il a fallu coder, un par un, dans les huit intelligences artificielles de PlayAwale.com, le jeu d’awale gratuit que je développe depuis 2025.

Je voulais raconter ce qui tourne réellement sous le capot de ces IA : les algorithmes classiques qui portent la majorité des niveaux, et les deux détours plus inhabituels tentés pour les deux derniers. Je ne donne pas la recette exacte (les poids, les seuils, le contenu des livres d’ouverture restent maison), mais la mécanique se raconte très bien, et coder ces réflexes m’a forcé à les rendre explicites. Il devrait donc y avoir, en plus du récit, quelques idées à emporter sur le plateau.

• La règle qui change tout : la famine
• Minimax et l’élagage alpha-bêta
• Comment j’ai adapté ça à l’awale
• Techniques de compétition
• Niveau 7, jeter minimax à la poubelle
• Pourquoi ce niveau m’a pris tant de temps
• Niveau 8, retour aux fondamentaux
• La suite : Stockfish, Python, et après

Une règle simple qui rend les évaluations naïves inutiles

L’awale se joue sur deux rangées de six trous. À son tour, un joueur vide un trou de son camp et sème une graine dans chaque trou suivant, dans le sens antihoraire. Si la dernière graine posée tombe dans un trou adverse qui contient alors 2 ou 3 graines, on capture, et on remonte la chaîne tant que la règle se vérifie sur les trous adverses précédents.

La règle qui complique tout, pour une IA, s’appelle la famine. Si l’adversaire n’a plus aucune graine de son côté, on est obligé de jouer un coup qui lui en donne, quand un tel coup existe. Un algorithme qui évalue une position uniquement sur le score et les captures immédiates va systématiquement rater les coups qui préparent un assèchement du plateau, ou les pièges qui forcent à nourrir l’adversaire au pire moment.

Minimax et l’élagage alpha-bêta

Sur PlayAwale, seuls les deux tout premiers niveaux n’utilisent pas de vraie recherche. Semeur Novice joue à peu près au hasard, en évitant simplement d’affamer l’adversaire quand un autre coup est possible. Gardien des Graines regarde un seul coup à l’avance : il capture le maximum de graines possible, ou à défaut choisit le coup qui expose le moins de graines à une capture adverse. Aucun des deux ne regarde ce qui se passe ensuite.

À partir du niveau 3, avec Esprit Ancestral, Voyageur des Sillons, Sage Immuable ZAK et Sage Immuable SIR, on entre dans la vraie recherche, avec le même algorithme qui fait tourner la plupart des IA de jeux de plateau depuis les années 1950 : minimax.

L’idée est simple à énoncer. On construit un arbre de tous les coups possibles : mon coup, puis toutes les réponses possibles de l’adversaire, puis tous mes coups suivants, et ainsi de suite jusqu’à une certaine profondeur. On évalue ensuite les positions tout en bas de l’arbre avec une fonction qui donne un score, plus il est haut, mieux c’est pour l’IA. Puis on remonte l’arbre niveau par niveau : à chaque niveau qui correspond à mon tour, je garde le score maximum parmi mes coups, puisque je veux le meilleur résultat. À chaque niveau qui correspond au tour de l’adversaire, je garde le score minimum, puisque je suppose qu’il choisira le coup qui me fait le plus de mal. Le coup réellement joué, à la racine de l’arbre, est celui qui garantit le meilleur résultat dans ce scénario où l’adversaire joue toujours au mieux contre moi.

Le problème, c’est que cet arbre grossit très vite. À l’awale, un joueur a en moyenne autour de six coups possibles à chaque tour. Chercher huit coups à l’avance représente déjà un nombre impressionnant de positions à évaluer. C’est là qu’intervient l’élagage alpha-bêta. Il ne change rien au résultat final : le coup choisi est rigoureusement le même qu’avec un minimax complet. Il change seulement le nombre de positions qu’on doit réellement calculer pour y arriver. Le principe : pendant l’exploration, on garde en mémoire deux bornes, le meilleur score que l’IA est déjà sûre de pouvoir obtenir, et le pire score que l’adversaire est déjà sûr de pouvoir lui infliger. Dès qu’une branche ne peut plus, mathématiquement, changer ces bornes, on sait qu’elle ne changera jamais le choix final, alors on arrête de l’explorer.

Comment j’ai adapté ça à l’awale

Minimax et alpha-bêta, tels quels, ne savent rien jouer du tout : ce sont des mécanismes de recherche vides. Toute l’intelligence réelle est dans la fonction d’évaluation, celle qui donne un score à une position quand on arrête de creuser. C’est là qu’il a fallu mettre ce que je savais du jeu.

Ces quatre niveaux tournent sur exactement le même moteur de recherche, minimax et son élagage alpha-bêta, à l’identique. Seule change, d’un niveau à l’autre, la fonction d’évaluation, et elle se complexifie réellement, pas juste en empilant des bonus au hasard.

Esprit Ancestral (niveau 3) pose la base : la différence de graines déjà capturées, la différence de mobilité (qui a le plus de coups légaux disponibles), le contrôle du plateau (qui a le plus de graines de son côté), et la vulnérabilité, c’est-à-dire combien de mes trous contiennent exactement 2 ou 3 graines et sont donc prêts à être capturés. Un bonus supplémentaire le rend plus agressif quand l’adversaire se retrouve avec très peu de coups possibles.

Voyageur des Sillons (niveau 4) garde cette base et l’étoffe nettement : une pénalité contre l’accumulation excessive de graines dans un seul trou, pour éviter de laisser l’adversaire construire une grosse réserve qu’il ferait exploser au bon moment ; un score de tempo, qui regarde combien de graines chaque joueur pourrait capturer dès le coup suivant ; une pénalité si l’IA reste bloquée à zéro capture trop longtemps ; une reconnaissance de motifs tactiques et stratégiques propres à l’awale (pièges, contrôle des coins, formations défensives) ; des poids qui changent selon la phase de la partie ; et une détection du style de l’adversaire, agressif ou défensif, qui ajuste la prise de risque en réponse.

Sage Immuable ZAK (niveau 5) repart de la base du niveau 3 et introduit un raisonnement différent, par « marches » : il compte, de son côté, les trous vides (des cases prêtes à recevoir une attaque) et, en face, les trous à 2 ou 3 graines (des cibles). Si le décompte penche en sa faveur, un gros bonus anticipe une capture qui devient presque inévitable ; sinon, une pénalité symétrique le pousse à corriger le tir.

Sage Immuable SIR (niveau 6) garde ce système de marches et ajoute deux réflexes de fin de partie : une consolidation volontaire des graines dans les derniers trous quand le plateau se vide, tant que l’adversaire garde un coup jouable, et un mode entièrement reparamétré, plus offensif et plus défensif à la fois, dès qu’il reste peu de graines en jeu.

Ce n’est donc pas une simple accumulation de tout ce qui précède : chaque niveau explore une piste différente plutôt que d’empiler mécaniquement les idées du précédent.

Il a aussi fallu coller précisément aux règles réelles du site plutôt qu’aux règles génériques de l’awalé. Par exemple, quand un joueur se retrouve bloqué, ce n’est pas l’adversaire qui rafle toutes les graines restantes : chaque camp récupère les siennes, et c’est le score final qui départage. Une IA qui chercherait à affamer l’adversaire en pensant rafler tout le plateau se tromperait de calcul, il a fallu coder la règle exacte du projet, pas une règle générique supposée.

Pour les joueurs : ces critères ne sont pas que du code, ce sont des réflexes que les bons joueurs appliquent déjà à l’instinct. Les rendre explicites pour l’IA m’a au moins permis de les vérifier noir sur blanc.

Un trou à 2 ou 3 graines juste avant le tour adverse est une cible : ça vaut le coup de vérifier, avant de jouer, combien des vôtres se retrouvent à cette hauteur après votre coup. La mobilité se paie cash : se retrouver avec un seul coup légal rend votre prochain coup devinable, même sans perte immédiate de graines. Un gros tas construit patiemment n’est une menace que s’il finit par se vider au bon moment ; laissé sans plan, il devient une cible immobile. Une capture immédiate n’est pas toujours le meilleur choix : un coup qui prépare une capture plus grosse au tour suivant, tout en limitant celle de l’adversaire, vaut souvent mieux. Et rester longtemps à zéro capture est un signal d’alarme pour un humain comme pour une IA : ça veut dire qu’on subit la partie plus qu’on ne la dirige.

Quelques techniques, telles que le code les définit

Si vous jouez en compétition, ces définitions devraient parler directement. Ce ne sont pas des figures de style : ce sont les seuils numériques exacts que ces IA utilisent pour reconnaître chaque situation.

Le gardien. Un trou de son propre camp contenant entre 4 et 8 graines. Ni vide (inutile), ni surchargé (immobile), c’est une réserve souple, capable à la fois de menacer l’adversaire et de se reconstituer. Le perdre sans contrepartie coûte cher dans l’évaluation ; en construire un, sans augmenter sa propre vulnérabilité au passage, rapporte gros.

La pince. Un trou adverse à 2 ou 3 graines qui peut être atteint par au moins deux de mes trous en même temps. L’adversaire ne peut défendre les deux cases à la fois : quoi qu’il joue, une capture reste possible au tour suivant.

Les marches. Vu plus haut au niveau 5 : compter, de son côté, les trous vides (des attaques en préparation) contre, en face, les trous à 2 ou 3 graines (des cibles). Le camp qui a le plus de marches disponibles a l’avantage.

Le krou. Un trou qui accumule beaucoup de graines, au-delà d’une dizaine, est une arme à double tranchant. C’est une réserve impressionnante pour son propriétaire, mais elle devra un jour être jouée, et à ce moment-là sa distribution complète autour du plateau devient calculable à l’avance par l’adversaire. Le moteur encode donc deux techniques opposées : nourrir volontairement le krou adverse pour le pousser encore plus loin, ou au contraire couper toutes les sources qui l’alimentent pour l’empêcher de grossir.

L’ouverture. Sur le tout premier coup, une des IA (le Stratège Probabiliste) porte un bonus explicite aux trous 4, 5 et 6, et une pénalité au trou 1. Les trous 2 et 3 figurent dans la liste des coups « conseillés » du code, mais aussi dans celle des coups « déconseillés » : les deux bonus se annulent presque, si bien qu’en pratique ils finissent légèrement pénalisés plutôt que favorisés. Que ce chevauchement soit voulu ou qu’il vienne d’un reliquat de code non nettoyé, je ne peux pas trancher avec certitude, mais le résultat net est clair.

Stratège Probabiliste : jeter minimax à la poubelle

Pour le septième niveau, j’ai posé une règle dès le départ dans le code, en commentaire, presque comme un interdit : aucun appel à minimax ou à alpha-bêta. Le raisonnement exhaustif, même optimisé, même très profond, finit par devenir prévisible et surtout trop lent pour rester redoutable tout en répondant en quelques secondes. Le Stratège Probabiliste repose sur une famille d’algorithmes complètement différente, le Monte Carlo Tree Search (MCTS), la même famille d’idées qui a porté AlphaGo face aux meilleurs joueurs de go. En beaucoup plus modeste bien sûr, sans réseau de neurones, mais avec le même principe statistique, d’où son nom.

Plutôt que de calculer méthodiquement toutes les conséquences d’un coup, l’IA joue un grand nombre de parties fictives jusqu’à leur terme, en partant de chaque coup candidat, et regarde quel coup a le plus souvent mené à une victoire. Quatre étapes se répètent en boucle pendant les quelques secondes de réflexion :

Quelques mécanismes complètent cette boucle. L’IA garde en mémoire l’arbre déjà construit d’un coup à l’autre plutôt que de tout recalculer. Elle partage l’information entre positions apparentées pour apprendre plus vite de chaque simulation. Et elle conserve une petite mémoire persistante des positions déjà rencontrées pour orienter ses futures parties. Les parties fictives, surtout, ne sont pas jouées au hasard : elles sont guidées par une lecture stratégique du plateau, capable de reconnaître une construction de réserve, d’anticiper un assèchement du camp adverse, ou de repérer un coup qui protège une case sensible, pour éviter de laisser échapper des coups évidents pour un joueur humain mais invisibles à un pur comptage statistique.

Pourquoi ce niveau m’a pris tant de temps

Les niveaux basés sur minimax se sont écrits, réglés et validés en quelques jours chacun. L’algorithme est connu, les optimisations sont documentées depuis longtemps, et il suffit de les assembler correctement. Le Stratège Probabiliste a demandé un temps disproportionné, pour des raisons assez différentes les unes des autres.

Changer d’algorithme, ce n’est pas régler un curseur

Passer de minimax à MCTS n’est pas une variante du même moteur avec un paramètre en plus. C’est reconstruire un moteur de jeu entier sur des bases mathématiques différentes, avec un vocabulaire (sélection, exploration contre exploitation, rétropropagation) qui n’a aucun équivalent direct dans ce qui existait avant. Rien du code précédent n’était réutilisable tel quel.

Régler MCTS est empirique, pas théorique

Là où alpha-bêta se prouve mathématiquement (le résultat est optimal, point final), les bons réglages d’une recherche Monte-Carlo ne se calculent pas, ils se mesurent : l’équilibre entre explorer de nouveaux coups et approfondir les coups déjà prometteurs, le nombre de parties fictives jouées, jusqu’où les pousser. Chaque changement de réglage demande de faire rejouer l’IA de nombreuses fois contre elle-même ou contre d’anciennes versions, pour voir si elle progresse réellement ou si elle s’est seulement mise à jouer différemment.

Ce que la théorie ne dit pas : une recherche Monte-Carlo pure, sans aucune connaissance du jeu, finit par bien jouer, mais très lentement à l’échelle humaine : il lui faut un nombre de simulations énorme pour distinguer, par exemple, un coup qui construit patiemment une réserve d’un coup qui la gâche. Sur l’awale, ces idées ont un nom précis pour les joueurs expérimentés : la construction de gros tas, la maîtrise de l’approvisionnement adverse, les coups de gardien qui protègent une case sensible. Il a fallu coder cette connaissance du jeu à la main et l’injecter dans les simulations, pour que l’IA les intègre sans avoir à les redécouvrir seule à chaque partie.

Des parties réelles ont révélé des angles morts

Une version qui semblait très solide en interne s’est parfois révélée contournable une fois exposée à de vrais joueurs. Certaines lignes de jeu exploitaient finement la règle de famine, ou laissaient volontairement une grosse réserve pour la faire exploser plus tard, et passaient à travers les simulations sans être suffisamment pénalisées. Il a fallu observer des parties rejouées, identifier précisément ce qui se passait, puis ajouter des correctifs ciblés dans l’évaluation pour combler ces angles morts.

Rester rapide sans devenir prévisible

Un niveau censé être redoutable qui met trente secondes à répondre, ou qui fige le navigateur pendant qu’il réfléchit, est un échec de produit même s’il est un succès algorithmique. Il a fallu découper le calcul en petites tranches non bloquantes pour que l’interface reste fluide pendant que l’IA réfléchit, et fixer un budget de temps strict par coup.

En clair : le Stratège Probabiliste n’a pas pris du temps parce qu’il était difficile à coder au sens littéral. L’implémentation d’un MCTS tient sur quelques centaines de lignes. Il a pris du temps parce qu’il fallait, en plus, lui enseigner à la main tout ce qu’un bon joueur d’awale sait sans savoir qu’il le sait.

Maître Awalé : retour aux fondamentaux, poussés à leur maximum

Le Stratège Probabiliste n’a pas été le dernier mot. Le huitième niveau, Maître Awalé, revient à minimax et alpha-bêta, abandonnés au niveau précédent. Ce n’était pas un retour à zéro : alpha-bêta n’avait jamais vraiment disparu du projet, il tournait déjà depuis le niveau 3. Ce qui change ici, c’est l’ampleur. Les mêmes bases, poussées avec des techniques de moteur d’échecs modernes que les niveaux précédents n’avaient pas :

Technique	À quoi ça sert
Coups tueurs	Retenir les coups qui ont provoqué une coupure ailleurs dans l’arbre, et les ré-essayer en priorité : plus on coupe tôt, plus on va vite.
Historique heuristique	Un score qui s’accumule pour chaque coup au fil de la recherche, pour trier les coups à examiner sans attendre de les avoir déjà vus jouer.
Réduction des coups tardifs	Les coups classés peu prometteurs sont d’abord regardés en surface ; on ne les recreuse à fond que s’ils se révèlent meilleurs que prévu.
Élagage de futilité	Si même dans le meilleur des cas un coup ne peut pas remonter au niveau déjà atteint, on l’abandonne sans le calculer davantage.
Extensions sur capture	Les enchaînements de grosses captures méritent d’être creusés plus profondément que le reste, c’est souvent là que tout se joue.
Livres d’ouverture & de fin de partie	Sur les tout premiers coups et les toutes dernières graines, l’IA consulte une base déjà validée hors ligne plutôt que de recalculer à chaque fois.

Revenir à un algorithme exact après être passé par une approche statistique n’a rien d’un aveu d’échec. C’est plutôt la preuve que les deux familles d’algorithmes ont chacune leur terrain de prédilection, et que le bon choix dépend de ce qu’on est prêt à sacrifier : la garantie mathématique d’un côté, la robustesse face à l’imprévu de l’autre.

Huit esprits, une même règle du jeu

Niveau	Nom	Algorithme
1	Semeur Novice	aléatoire
2	Gardien des Graines	glouton, 1 coup
3	Esprit Ancestral	minimax
4	Voyageur des Sillons	minimax
5	Sage Immuable ZAK	minimax
6	Sage Immuable SIR	minimax
7	Stratège Probabiliste	MCTS
8	Maître Awalé	alpha-bêta renforcé

Ce qui me plaît, avec le recul, c’est que ces huit niveaux ne sont pas huit variations de la même idée avec un curseur de difficulté. Ce sont plusieurs réponses différentes à la même contrainte : douze trous, une règle de famine, un temps de réflexion limité. Minimax et son élagage restent une base d’une élégance redoutable pour la majorité des cas. Mais à mesure qu’on grimpe l’échelle, il y a un point où il faut accepter d’abandonner la certitude mathématique d’un algorithme exhaustif pour la robustesse statistique d’un algorithme qui apprend en jouant, quitte ensuite à revenir au calcul exact une fois qu’on a appris de cette parenthèse.

Vous pouvez tester les huit sur PlayAwale.com : le Semeur Novice pour débuter, ou directement le Maître Awalé si vous cherchez un vrai défi.

Stockfish, Python et une base de parties qui grossit

Je n’en ai pas fini avec ce sujet. Mon prochain chantier tourne autour de Python, que je peux maintenant faire tourner sur mon serveur personnel, et ça ouvre des perspectives assez évidentes côté temps de calcul. Une bonne partie des limites actuelles vient du fait que tout tourne côté navigateur, avec un budget de quelques secondes par coup. Déporter le calcul sur un serveur change la donne.

Stockfish, le moteur d’échecs open source, m’intéresse beaucoup de ce point de vue. Son approche, une évaluation apprise plutôt qu’écrite à la main, combinée à un alpha-bêta extrêmement optimisé, représente clairement le niveau au-dessus de ce que j’ai construit ici. Je ne me fais pas d’illusions sur la marche à franchir : ça demande un niveau de compétence que je n’ai pas encore, et je préfère le dire plutôt que de prétendre le contraire. C’est une direction qui m’intéresse, pas un projet prêt à démarrer demain.

Plus concrètement et plus à ma portée, il y a la piste des livres d’ouverture et de fin de partie : les rendre plus complets, mieux couvrir les positions réellement rencontrées. Et surtout, la base de données de parties du site continue de grossir chaque jour, avec des joueurs venus d’horizons très différents. Cette matière première, des dizaines de milliers de parties réelles jouées par de vraies personnes, est exactement ce qu’il me manquait pour retravailler sérieusement l’évaluation d’une future IA, et peut-être un jour reprendre ce chantier avec une approche encore plus solide que celles que je viens de décrire.

Merci aux joueurs, et un petit mot sur la suite

Ce projet ne me rapporte rien, et je ne peux pas y consacrer tout mon temps libre. Je refuse d’intégrer de la publicité dans mon jeu d’awalé afin de ne pas dénaturer l’expérience. Ce modèle économique ne correspond pas à l’esprit du jeu. Ce qui me donne vraiment envie de continuer, ce sont les retours des joueurs : des habitués reviennent jour après jour, certains prennent le temps de m’écrire pour signaler un bug, proposer une idée, ou simplement dire qu’ils aiment le jeu. Ce projet grandit, avec des joueurs venus de nombreux pays différents, et plus de 24 000 parties déjà enregistrées. Ce sont ces retours là, très concrètement, qui me donnent envie de continuer à améliorer le jeu plutôt que de le laisser tourner tel quel.

Si vous voulez donner un coup de main pour l’hébergement, les mises à jour ou simplement soutenir le projet, un petit don est toujours possible ici : revolut.me/nlion. Ce n’est jamais demandé, juste proposé pour ceux qui en ont envie.