← Retour au blog

L'awalé est-il résolu ? Comment des chercheurs ont calculé la partie parfaite

Douze cases, quarante-huit graines, deux joueurs : l'awalé tient dans la main, et pourtant il fait partie des rares jeux traditionnels dont on connaît le résultat d'une partie parfaite. En 2002, deux chercheurs de l'université libre d'Amsterdam, John Romein et Henri Bal, ont annoncé avoir calculé la valeur exacte de toutes les positions de l'awari, la variante de l'awalé jouée dans les compétitions entre programmes. Leur conclusion : si les deux joueurs ne commettent aucune erreur, la partie se termine par un match nul.

Jouer à l'Awalé Le guide de stratégie

Ce que veut dire « résoudre » un jeu

Un jeu est dit résolu quand on sait ce que donne la partie si chaque camp joue toujours le meilleur coup : victoire du premier joueur, victoire du second, ou nul. Il existe plusieurs degrés. On peut connaître seulement le résultat de la position de départ, ou bien, ce qui est beaucoup plus fort, connaître le meilleur coup dans n'importe quelle position. C'est ce second degré que Romein et Bal ont atteint pour l'awari : leur base de données donne la valeur de chaque position possible.

Le morpion est résolu depuis longtemps (nul), le puissance 4 aussi (le premier joueur gagne en commençant au centre). Pour l'awalé, la difficulté tenait au nombre de positions à examiner.

Combien de positions ?

Une position d'awalé, c'est une répartition des graines restantes dans les douze cases, plus le trait et le compte des graines déjà prises. Rien qu'avec les 48 graines encore toutes sur le plateau, il existe près de 280 milliards de façons de les répartir dans les douze cases. En ajoutant toutes les positions où une partie des graines a déjà été prise, on dépasse le millier de milliards de répartitions.

Romein et Bal indiquent avoir évalué environ 889 milliards de positions. Pour un ordinateur de l'époque, c'était un travail impossible sur une seule machine : ils ont réparti le calcul sur une grappe de plusieurs dizaines d'ordinateurs travaillant en parallèle, et la base finale occupait une place considérable sur disque.

L'astuce : les graines ne reviennent jamais

Examiner toutes les parties possibles depuis le début serait sans fin : une partie d'awalé peut durer très longtemps, et les mêmes positions reviennent par des chemins différents. Les chercheurs ont utilisé une autre méthode, l'analyse rétrograde, qui part de la fin.

Elle repose sur une propriété simple de l'awalé : le nombre de graines sur le plateau ne peut que diminuer. Semer ne change pas le total, prendre le fait baisser, et rien ne le fait monter. Une position à 10 graines ne peut donc mener qu'à des positions à 10 graines ou moins. On peut alors tout calculer par étages :

  1. on calcule d'abord toutes les positions avec très peu de graines, dont l'issue est facile à établir ;
  2. puis celles à une graine de plus : chaque coup y mène soit à une position déjà calculée (s'il prend des graines), soit à une position du même étage (s'il n'en prend pas) ;
  3. à l'intérieur d'un étage, on propage les résultats connus de proche en proche, jusqu'à ce que plus rien ne change ;
  4. et ainsi de suite jusqu'à 48 graines, la position de départ.

Les positions qui tournent en rond, où les graines circulent sans que personne ne puisse rien prendre, sont réglées par la règle de fin de partie prévue dans ce cas : dans la règle des chercheurs, une position répétée arrête la partie et les graines restantes sont partagées. C'est la même méthode que celle des « tables de finales » aux échecs, qui donnent le résultat parfait de toutes les positions avec peu de pièces. La différence est qu'à l'awalé, elle a pu aller jusqu'à la position initiale.

Le résultat : un nul, mais pas une partie facile

La position de départ vaut un match nul : aucun des deux joueurs ne peut forcer la victoire, et chacun peut forcer au moins le partage, à condition de ne jamais se tromper. Ce résultat ne dit rien de la difficulté de jouer ces coups : la base contient la réponse à chaque position, mais pas d'explication. Elle ne fournit ni règle simple ni plan à retenir.

À la même époque, un site permettait de jouer contre cette base complète, qu'on surnommait « l'oracle » : il n'est plus en ligne aujourd'hui. Un passionné a par ailleurs affirmé que quelques finales avaient été mal analysées ; faute de pouvoir rejouer le calcul, la question n'a jamais été tranchée publiquement.

Attention : l'awari des chercheurs n'est pas tout à fait ton awalé

L'awalé se joue selon des règles qui varient d'un pays et d'un village à l'autre, et le résultat de 2002 ne vaut que pour la règle étudiée. Le cas du grand chelem, le coup qui prendrait toutes les graines de l'adversaire, en est un bon exemple. Dans la règle utilisée par les informaticiens, un coup qui laisse l'adversaire sans rien à jouer est en principe interdit, sauf s'il n'existe aucun autre coup. Sur ce site, comme dans la règle des tournois humains (l'abapa), ce coup se joue mais ne prend rien. Une différence de ce genre suffit en principe à changer la valeur de certaines positions, et rien ne garantit que la partie parfaite reste nulle avec toutes les variantes.

Les règles exactes jouées ici, grand chelem et obligation de nourrir comprises, sont détaillées dans les règles de l'awalé. Les noms et les cousins du jeu (awélé, oware, wari, kalah) sont présentés dans le guide awalé, awélé, oware et mancala.

Ce que ça change pour toi

Concrètement, pas grand-chose à ton échelle, et c'est une bonne nouvelle. Savoir qu'une partie parfaite est nulle ne t'aide pas à trouver le bon coup : comme aux dames ou aux échecs, les parties entre humains se gagnent sur des erreurs, et elles sont nombreuses dans un jeu où un seul semis change la moitié du plateau. Trois idées tirées de ce travail restent utiles :

Pour mettre ça en pratique, le guide stratégie de l'awalé rassemble les principes qui comptent, et l'analyse proposée après chaque partie contre l'ordinateur te montre jusqu'à trois coups qui t'ont le plus coûté.

À lire aussi

← Retour au blog Jouer à l'Awalé
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →