Le Grand Maître : les coulisses d’une nouvelle IA d’awalé

Un nouveau niveau arrive sur PlayAwale : le Grand Maître. Voici, aussi simplement que possible, comment il réfléchit, comment je l’ai entraîné, et ce qu’il me reste à apprendre.

L’awalé en deux mots

L’awalé est un jeu de semailles venu d’Afrique de l’Ouest, de la grande famille des mancalas. Deux joueurs, douze trous, quarante-huit graines. À son tour, on prend toutes les graines d’un de ses trous et on les sème une à une dans les trous suivants. Si la dernière graine tombe chez l’adversaire et y forme un trou de 2 ou 3 graines, on les prend, ainsi que celles des trous précédents dans le même cas. Le premier à 25 graines gagne.

Les règles tiennent en quelques lignes, mais le jeu est d’une grande profondeur : chaque coup déplace des graines partout sur le plateau, et une position calme peut basculer en trois coups. L’Afrique nous a fait un très beau cadeau avec ce jeu, qui mérite sa place aux côtés des échecs et du jeu de go.

Pourquoi un nouveau niveau ?

Jusqu’ici, le niveau le plus fort de PlayAwale était le Maître. Je suis arrivé au bout de ce que je savais en tirer : sa façon de juger une position ne progressait plus, et chaque retouche l’aidait sur un point pour le gêner sur un autre. J’ai donc repris ses bases dans un nouveau moteur, en y ajoutant ce que j’ai appris en route, souvent auprès des autres.

Comment une IA « réfléchit » à un jeu

Imaginez que vous essayez tous vos coups possibles, puis, pour chacun, toutes les réponses de l’adversaire, puis toutes vos réponses à ses réponses, et ainsi de suite. Vous obtenez un arbre : une branche par coup, qui se divise à chaque étage. Au bout des branches, on juge la position obtenue (« j’ai 3 graines d’avance, mon camp est solide »), puis on remonte en supposant que chacun joue au mieux pour lui. C’est le principe du minimax : je choisis le coup qui me laisse la meilleure position, en sachant que l’adversaire choisira ce qui est le pire pour moi.

La difficulté, c’est la taille de cet arbre. À l’awalé, il y a jusqu’à six coups possibles à chaque tour. À dix coups de profondeur, cela fait déjà des dizaines de millions de positions, et bien plus au-delà.

Le remède classique s’appelle l’élagage alpha-bêta. Dès qu’une réponse de l’adversaire rend un coup moins bon qu’un autre déjà examiné, inutile d’étudier ses autres réponses : ce coup est déjà écarté. On voit ainsi bien plus loin pour le même effort. Le Maître reposait déjà sur ce principe, connu depuis les années 1950.

Ce que j’ai appris de Stockfish

Stockfish est un célèbre moteur d’échecs dont le code est ouvert. Des centaines de passionnés y ont mis au point des astuces pour chercher plus vite et plus loin. J’en ai essayé une dizaine sur l’awalé, et cinq se sont révélées utiles :

• La fenêtre d’aspiration : à chaque nouvel étage de réflexion, on parie que la valeur de la position restera proche de celle trouvée juste avant. Si le pari tient, la recherche va plus vite.
• La futilité inversée : près du bout des branches, une position déjà largement gagnante ne sera pas rattrapée en un ou deux coups. Inutile de creuser.
• Les réductions des coups tardifs : les coups qui semblent mauvais sont d’abord regardés moins loin. S’ils se révèlent intéressants, on les reprend sérieusement.
• La réduction sans piste : une position jamais rencontrée, loin dans l’arbre, est sans doute peu importante. On y passe un peu moins de temps.
• La singularité : à l’inverse, quand un seul coup tient et que les autres perdent, on le creuse plus loin. Bien des positions d’awalé n’ont qu’un bon coup.

Ensemble, ces techniques permettent d’atteindre la même profondeur de réflexion en examinant beaucoup moins de positions, et donc de voir plus loin dans le même temps.

Les autres idées n’ont rien donné à l’awalé. Aux échecs, il y a trente ou quarante coups possibles par position, et l’on gagne à en ignorer beaucoup. À l’awalé, il n’y en a que six au plus, et en ignorer un à tort coûte cher.

Juger une position : apprendre des joueurs

Au bout des branches, il faut donner une note à la position. Pour le Maître, j’avais choisi les critères à la main. Pour le Grand Maître, ce sont vos parties qui ont parlé : 236 000 positions tirées des parties jouées sur PlayAwale. La méthode, elle aussi venue du monde des échecs, consiste à régler les critères pour que la note prédise le mieux possible qui a fini par gagner.

Vos parties m’ont appris des choses que je n’aurais pas devinées :

• Avoir le trait est souvent un handicap. À l’awalé, on est fréquemment obligé de jouer un coup qui offre une prise.
• Avoir des petits trous chez soi n’est pas forcément une faiblesse : ce sont des coups souples, qui permettent d’attendre.
• Une grosse réserve de graines dans un trou (douze ou plus) vaut cher : elle prépare un tour complet du plateau et une belle prise.
• Les trous vides de l’adversaire lui retirent des coups, et le rapprochent de l’impasse.

Un grand merci à tous les joueurs : sans vos parties, ce travail n’aurait pas été possible.

La fin de partie : calculer plutôt que deviner

Quand il reste peu de graines sur le plateau, on peut tout calculer. Le Grand Maître construit une base de finales : le résultat exact des positions qui ont 13 graines ou moins sur le plateau, en partant de la fin et en remontant. Dans ces positions-là, il n’a plus besoin de deviner.

Cette base n’est pas téléchargée : elle est calculée dans votre navigateur, en arrière-plan, pendant que la partie commence.

Le piège des parties qui tournent en rond

Une partie d’awalé peut tourner en rond : les deux joueurs déplacent leurs graines sans jamais rien prendre. La règle de PlayAwale arrête alors la partie quand la même position revient pour la troisième fois, et chacun ramasse les graines de son camp.

C’est un vrai casse-tête pour une IA, car la valeur d’une position dépend alors de ce qui s’est passé avant. En étudiant ses défaites, j’ai trouvé une erreur de ma part : le Grand Maître garde en mémoire, d’un coup à l’autre, ce qu’il a déjà calculé, mais cette mémoire ne tenait pas compte des positions déjà vues deux fois. Dans une finale serrée, il jouait le mauvais coup. C’est corrigé, et c’est une bonne leçon : ce sont les défaites qui font progresser.

L’ouverture, et un peu de variété

Pour les premiers coups, le Grand Maître dispose d’un livre d’ouverture : plus de 800 positions de début de partie étudiées à l’avance. S’y ajoute un livre de leçons : les positions de parties qu’il n’a pas gagnées, recalculées longuement.

Pour ne pas être prévisible, il choisit parfois au hasard, en début de partie, entre des coups de valeur presque égale.

Il réfléchit aussi pendant votre tour

Le Grand Maître dispose de 8 secondes par coup sur ordinateur, 6 sur téléphone. Il profite aussi du temps où vous cherchez votre coup pour commencer à réfléchir. Selon les positions, il voit ainsi de 25 à 30 demi-coups à l’avance en milieu de partie, et davantage en fin de partie, quand il reste moins de graines.

L’entraînement, et beaucoup de prudence

Je l’ai fait jouer des centaines de parties contre d’autres IA, notamment Aalina, le moteur open source de Joan Sala Soler. Sans son travail, publié librement, je n’aurais pas eu de partenaire d’entraînement aussi exigeant : un immense merci à lui. Chaque partie perdue était étudiée coup par coup.

J’ai aussi appris à me méfier de mes propres idées. Une correction qui aide dans une situation peut nuire dans dix autres. Je me suis donc fixé une règle : chaque changement doit affronter la version en ligne, sur au moins 40 parties, et s’il fait moins bien, on revient en arrière.

Le hasard, en plus, pèse plus qu’on ne croit. J’ai fait jouer la version en ligne contre elle-même : sur 20 parties, l’une des deux copies a obtenu 75 % des points ! Sur si peu de parties, un résultat ne prouve pas grand-chose. Beaucoup de mes idées ont d’ailleurs été écartées : ces derniers jours encore, sur six essais, deux seulement ont été gardés.

Quelques résultats, à prendre avec prudence

Adversaire	Conditions	Victoires · nulles · défaites
Aalina (Joan Sala Soler)	8 s par coup chacun, 40 parties	36 · 0 · 4
Le Maître de PlayAwale	départs égaux, 40 parties	40 · 0 · 0
Un alpha-bêta classique	1 s par coup chacun, 40 parties	38 · 0 · 2

Ces chiffres viennent de mes propres essais, sur ma machine, et contre les quelques IA que j’ai pu faire jouer. Il existe d’autres programmes d’awalé très forts que le Grand Maître n’a jamais affrontés : je ne sais donc pas où il se situe vraiment. C’est l’une des raisons de cet article.

Imbattable ? Non.

En 2002, des chercheurs néerlandais, ont entièrement calculé l’awalé, soit près de 900 milliards de positions. Leur verdict : bien joué des deux côtés, la partie se termine par une égalité.

Le Grand Maître, lui, ne connaît pas le jeu entier : il réfléchit, et il peut se tromper. Un très bon joueur peut lui arracher une égalité, voire une victoire. Et je serai très heureux de voir ça.

Tout tourne dans votre navigateur

Le Grand Maître est écrit en JavaScript et tourne directement dans votre navigateur, sur ordinateur comme sur téléphone, sans serveur de calcul. C’était une contrainte que je m’étais donnée dès le départ, et elle m’a obligé à chercher des solutions simples.

À vous de jouer

Je cherche des joueurs, et des développeurs d’IA d’awalé, pour le mettre à l’épreuve et m’aider à le faire progresser.

• ♟️ Vous êtes joueur, en club, en tournoi ou par passion ? Venez l’affronter. Si vous gagnez ou obtenez une égalité, partagez votre partie avec l’option prévue dans le jeu.
  
• 🤖 Vous avez développé votre propre IA d’awalé ? Confrontez-la au Grand Maître. Des développeurs l’ont déjà fait avec le Maître, et leurs retours m’ont beaucoup appris.

Un gagnant, c’est un nouveau défi pour moi 🙂 Chaque partie gagnée contre lui m’aidera à le rendre meilleur.

Et rassurez-vous : il y a des niveaux pour tout le monde sur PlayAwale, du débutant au Grand Maître.

Merci à tous pour votre fidélité, et excellentes parties d’awalé !

👉 Jouer sur PlayAwale