Ne cherchez pas trop, à ce jour il n'existe qu'un seul programme !

Il s'agit de MGounki, commis par l'auteur de ces lignes :-)

MGounki est programmé en C++, et est capable d'explorer quelques dizaines de milliers de positions par seconde, assez pour résister dignement à un joueur moyen et permettre à un joueur débutant de s'initier au jeu.

Le code source de MGounki, développé sous Linux/GNU, est distribué sous licence GNU GPL. Vous pouvez le télécharger en cliquant ici.

Merci à Bruce Moreland, pour son excellente série d'articles sur la programmation du jeu d'échecs, qui m'a été d'une aide plus que précieuse pour écrire MGounki.

• Jeu à 2, seul contre l'ordinateur, ou en autoplay ;
• 10 niveaux de difficultés, caractérisés par le temps de réponse moyen de l'ordinateur ;
• mode « smart » : l'ordinateur continue à réfléchir, même quand c'est à votre tour de jouer ;
• possibilités de revenir en arrière, de reprendre une partie depuis une position antérieure, ou de commencer une partie depuis une position saisie manuellement ;
• possibilité de sauvegarder / recharger la partie ;
• bibliothèque d'ouvertures (expérimentale !).

• Interface en mode texte uniquement ;
• distribué sous forme de code source uniquement (c'est parfois un avantage, mais seulement pour des informaticiens !), donc soyez prêt à le compiler vous-même !
• et tant d'autres encore...

MGounki a été réalisé principalement à titre d'exercice, sans autre ambition que de réaliser un prototype crédible, capable de se défendre honorablement face à un joueur débutant ou moyen. Cet objectif est atteint puisque MGounki me bat régulièrement !

Cependant, il convient de garder à l'esprit que MGounki n'est qu'un simple prototype, que ce soit en termes de fonctionnalités que d'interface, ou même de finesse d'analyse. C'est bien davantage un programme de type « proof of concept » qu'un logiciel abouti.

En ce qui concerne l'avenir de MGounki, à moyen terme je n'ai pas l'intention de consacrer davantage de temps à son développement. La conception et la mise au point des algorithmes de recherche est une vraie spécialité (qui, je l'avoue, me dépasse un peu), et à titre personnel j'ai d'autres plans.

C'est l'une des raisons pour lesquelles le code source est distribué sous license GNU GPL : si la programmation du jeu de Gounki vous intéresse et si vous souhaitez améliorer et/ou enrichir ce programme, considérez que vous y êtes très vivement encouragé !

• Performance : de NPS > 50000 (Athlon K7 550 Mhz), à NPS > 200000 (Athlon XP 2100+). Your mileage may vary...
• algorithme de recherche : alpha-beta (negamax avec extraction de la variante principale) + table de transposition + iterative deepening + quiescence search ;
• aspiration window : utilisée mais sans grand effet (la fenêtre doit rester très large en raison de l'instabilité de la recherche) ;
• table de transposition : une seule table (replacement policy : always replace), 12 octets par entrée, hachage sur 64 bits. Idéalement, la table contient 8 millions d'entrées ou plus. L'expérience confirme qu'une table à 16 millions d'entrées (soit 192 Mo) permet de diviser par 2 la durée de certaines recherches, par comparaison à une table contenant seulement 65000 entrées.
• réfléxion sur le temps de l'adversaire : en anticipant que l'adversaire joue suivant la variante principale (pondering en mode « smarter »), ou sans anticipation (mode « smart », activé par défaut) ;
• profondeur d'analyse : insuffisante ! La profondeur d'analyse, très sensible aux conditions d'exécution (vitesse CPU, temps imparti, taille de la table de transposition, etc.), est typiquement de 5 ou 6 demi-coups seulement au niveau 4 (25 secondes par coup en moyenne). Cette faiblesse rend MGounki très vulnérable à l'effet d'horizon, d'où l'importance du mode « smart » qui permet parfois de gagner 1 voire 2 demi-coups supplémentaires...
• représentation des positions : à base de bit-maps sur 64 bits.

• Makefile pour GNU Make ;
• langage de programmation : C++ (ISO 98 + entiers longs sur 64 bits), développé pour gcc 3.2 ;
• appels systèmes Unix standards : pipe, fork, sigaction, etc. ;
• threads POSIX ;
• assembleur IA-32 (gas) : utilisé pour quelques fonctions critiques. Les fonctions équivalentes en C++ sont fournies et utilisables en option (leurs performances sont à peine légèrement inférieures) ;
• base de données des ouvertures sous Berkeley DB v4.0 ou supérieure (*) ;
• compilé et testé sous Linux Mandrake 9.1.

(*) Si la librairie Berkeley DB n'est pas installée sur votre système, vous pouvez désactiver la bibliothèque d'ouvertures lors de la compilation (cf. fichier MANUAL.fr).

Code source de la dernière version (v1.03) : MGounki-1.03.tar.gz

Hash MD5 : 695405126adc687ddcbc8b934da8eb48

Deux questions fréquentes à propos de Gounki intéressent directement les programmeurs de jeux :

• Gounki est-il plus difficile ou plus simple à programmer que le jeu d'échecs ?
• Comment la complexité de Gounki se compare-t-elle à celle du jeu d'échecs ?

Je me garderai bien d'affirmer la moindre certitude sur ces questions, ne serait-ce parce que je n'ai jamais programmé un jeu d'échecs. Cependant la comparaison, qui pourrait sembler prétentieuse à première vue, ne me paraît pas absurde.

Un critère très important concernant la complexité du jeu est le fameux facteur de branchement, qui correspond au nombre de coups que l'on peut jouer dans une position donnée.

Un calcul théorique élémentaire montre que ce facteur peut être très élevé, la position la plus complexe (8 combinaisons rond-carré) pouvant engendrer 40 déplacements et 96 déploiements, soit un total de 136 possibilités ! Cependant une telle position est assez improbable.

En pratique, l'exploration de l'arbre de recherche, à partir de la position initiale du jeu, donne un facteur de branchement moyen de 43,5 en début de partie (*). Cette valeur est à comparer avec celle fréquemment citée de 35 pour le jeu d'échecs (**).

(*) Calcul effectué sur toutes les positions atteintes jusqu'à la profondeur de 4 demi-coups, l'arbre de recherche étant construit exhaustivement, avec détection des transpositions.

(**) Cette valeur, qui revient dans de nombreux articles, est malheureusement souvent citée en dehors de tout contexte, et j'ignore à quoi elle correspond exactement : s'agit-il de l'ouverture, ou d'une moyenne plus globale ? Comment ce facteur évolue-t-il au cours de la partie ?

Par ailleurs, une expérience rapide sur l'espace de recherche de MGounki indique un facteur de branchement moyen typiquement situé entre 40 et 50 pour les coups du début de partie, avant le premier échange. Un échange de pièces composées se traduit en général par une baisse significative du facteur de branchement. Cependant, étant donnée la vitesse du jeu, une partie typique courte (environ 15 coups) peut être entièrement résolue dans un espace de recherche dont le facteur de branchement moyen reste supérieur à 40.

Un autre aspect du jeu de Gounki à prendre en considération est l'impossibilité de reculer. Il s'agit là d'une caractéristique déterminante, qui explique largement que les parties de Gounki soient en moyenne nettement plus courtes que les parties d'échecs (où seuls les pions ne peuvent pas reculer). Une partie de Gounki dure ainsi typiquement entre 15 et 25 coups, et dépasse très rarement 30 coups.

Une conséquence majeure de cette impossibilité est que toute avancée imprudente d'une pièce est irréparable. D'où il découle que le problème, plutôt complexe au départ, est susceptible de se simplifier nettement, soit par élimination de pièces capturées, soit en raison des brêches laissées dans la défense par les pièces trop vites exposées...

Pas de conclusion, le sujet étant à peine effleuré !

Ou plutôt, à vous de jouer maintenant ! Si le jeu de Gounki vous intéresse, si la programmation de ce type de jeux vous passionne, n'hésitez pas, voilà un terrain d'expérimentation tout neuf !