Rapport de PIR première année
Jeu d'Awélé

Nicolas Chapon
Charles Girard

sous la direction de

M. Jean-Marc Alliot

Dans le cadre d'un Projet d'Initiation à la Recherche à SUPAERO, nous avons voulu créer un jeu d'Awélé, jeu africain très ancien. Pour que tous puissent y jouer nous avons voulu ce jeu portable sur toutes les plateformes actuelles. (Windows, Linux, Mac OS, Solaris, ...). Nous présentons ici, brièvement notre programme qui répond à nos attentes.

1 Une brève présentation du Jeu d'awélé

L'Awele est un jeu très ancien originaire d'Afrique. De très nombreuses légendes circulent sur son origine. On dit que certains hommes ayant marché à travers le désert de nombreux mois arrivèrent enfin à la mer. Ils y trouvèrent de superbes coquillages qu'ils emportèrent comme souvenirs. Durant leur longue marche de retour, ils auraient inventé l'awélé afin de gagner le plus de ses trésors aquatiques. L'awele était né.

1.1 Le plateau de jeu

En général, un plateau d'awélé est une planche de bois, souvent de l'ébène, percée de douze trous ou cases, six d'un coté et six de l'autre. Bien souvent, viennent s'adjoindre au deux extrémités du plateau de trous plus gros ou greniers. On dépose dans ses cases les fruits du Caesalpinia bonduc.

Figure 1 : Fruits du Caesalpina

Figure 2 : Un plateau d'awélé

Ces fruits ressemblent étrangement à des graines et sont parfois remplacés par des cailloux.

1.2 Les règles

Les différentes règles de l'awélé sont aussi nombreuses que les légendes sur son origine. Les règles présentées ci-dessous ne sont que celles les plus utilisées en Occident et que nous avons décidé d'utiliser avec M.Alliot. L'Awélé se joue à deux joueurs. Nous avons vu que le plateau de jeu se divise en deux camps, nord (en haut) et sud (en bas) et de deux greniers. Chaque joueur possède ainsi un grenier et six cases. Au début du jeu, chaque case du jeu contient 4 graines et les greniers sont vides.

1.3 Déroulement du jeu

Le jeu se joue au tour par tour. Le but du jeu est de ramasser le plus de graines, et les graines amassées pour chaque joueur sont stockées dans son grenier.
Chaque joueur joue en effectuant deux choses:la semaille puis la récolte: Pour semer,il faut choisir une case, prendre les graines qui sont dedans et déposer exactement une graine dans chacune des cases suivantes, en tournant dans le sens contraire des aiguilles d'une montre. Cela signifie qu'on dépose les graines dans son camp en allant vers la droite, et dans le camp adverse en allant vers la gauche. On commence par semer dans la case qui suit la case choisie, non pas dans la case choisie elle-même. Et si le nombre de graines est suffisant pour que la semaille conduise à faire un tour complet (le joueur repasse sur la case choisie), on passe la case choisie sans placer de graine dedans. Cela signifie que quoi qu'il en soit, la case choisie sera vide à la fin du tour. Bien évidemment, La semaille ne concerne pas les greniers.
Après avoir semé, le joueur récolte. La récolte est éventuelle, et s'effectue uniquement chez le joueur adverse. Il y a récolte lorsque la dernière case où l'on a semé se trouve chez l'adversaire et comporte exactement 2 ou 3 graines (après semaille). Dans ce cas, le joueur qui récolte prend ces deux ou trois graines, il continue sa récolte dans les cases précédentes si celles-ci contiennent de même deux ou trois graines. La récolte s'arrête dès qu'on cherche à récolter sur une case non recoltage. Le joueur arrête donc la récolte soit lorsqu'il rencontre une case n'ayant pas deux ou trois graines, soit lorsqu'il arrive à la fin des cases de l'adversaire. On récolte dans le sens inverse de la semaille, c'est-à-dire en allant vers la droite (on reste chez l'adversaire). Les graines ainsi empochées sont mises dans le grenier du joueur qui récolte, et c'est la fin du tour.

1.4 la fin de partie

Il arrivera forcément un moment où un joueur ne pourra plus jouer faute de graines. Le joueur adverse se doit alors de prévenir cela, et doit toujours jouer de manière à ce que son adversaire soit nourri au tour prochain, c'est-à-dire qu'il ait au moins une graine dans son camp au tour suivant. Si un joueur n'a plus de graine, et que l'adversaire ne peut pas le nourrir, alors le jeu s'arrête et chaque joueur ajoute à son grenier toutes les graines qu'il avait dans son camp. Le gagnant est bien sûr celui ayant le plus de graines. Il peut aussi arriver qu'une situation ne mène à aucune solution, les deux joueurs décident d'un commun accord de s'arrêter à ce point. Les points sont alors décomptés comme précédemment.

1.5 L'awélé en informatique

Le premier portage informatique de l'awélé a été réalisé par Roland Silver en 1961, le jeu portait alors le nom de Kalah. L'algorithme mis en oeuvre était alors un algorithme assez proche du notre. Cependant, les régles adoptées étaient bien différentes des notres.

2 Les principes du jeu

Notre jeu d'awélé se joue à deux: Un joueur humain au Sud et un joueur ordinateur au Nord. Le sud commence. Le jeu se décompose en deux modules principaux :

Le module algorithmique
Le module graphique

Le module algorithmique, Alphabeta

C'est un programme qui reçoit le coup joué par le joueur humain et renvoie le coup à jouer par l'ordinateur. La stratégie de l'ordinateur est la suivante : Il crée un arbre des possibles de profondeur 6 et recherche grâce à l'algorithme Alphabeta le meilleur coup à jouer.

l'Alphabeta

C'est un algorithme dérivé du très célèbre algorithme Minimax, qui cherche à maximiser le gain du joueur ordinateur tout en minimisant le gain du joueur humain. Cependant, l'Alphabeta est théoriquement supérieur au Minimax car il permet d'éviter des recherches inutiles. Nos tests de rapidité ont montré que dans la pratique l'Alphabeta jouait bien plus rapidement que le Négamax.
Il est bien plus important de constater que le jeu joue correctement, nous n'avons jamais été capable de battre l'ordinateur.

Le module Graphique

C'est à proprement parlé le jeu; Il présente le plateau, les billes, diverses options dont celle de jouer à deux joueurs humains. Nous aurions pu faire jouer l'ordinateur contre lui même. Cependant l'issue de la partie serait toujours la même et trop rapide à suivre. Un tel mode de jeu ne présente donc aucun intérêt et nous ne l'avons pas implémenté.

Figure 3 :Capture d'écran du jeu tournant sous Debian GNU/Linux

Notre développement du jeu permet une grande souplesse. Souplesse dans le graphisme, le titre, le plateau ne sont que des images au format GIF donc facilement modifiable malgré le caractère non-libre de la licence GIF. Et souplesse dans son portage sous différentes plateformes très aisé grâce à la bibliothèque Labltk. Toutefois on pourra regretter une qualité graphique médiocre du jeu, notre maîtrise des outils infographiques étant trop limité.

Quoiqu'il en soit, nous avons réussi à atteindre nos objectifs: Un jeu d'awélé performant dont le portage est très aisé.

3 Obtenir le jeu

Pour obtenir le jeu :

Version Windows

Télécharger le fichier awele-PIR-Girard-Chapon.zip. Décompressez l'archive et suivez les instructions du fichier LISEZMOI

Linux, Unix, Mac OS

Vous devez posseder la version 3.08 d'O'Caml ainsi que la bibliothèque Labltk
Télécharger les archives

Compilez chacun d'elle grâce au script compil.sh. Et mettez les deux programmes awele et alphabeta dans le même repertoire.
Pour jouer lancer awele

4 Informations légales

Ce jeu a été totalement développé par Nicolas Chapon et Charles Girard sous le patronage de M. J-M Alliot. Il a été codé grâce au langage O'Caml version 3.08 distribué sous la licence GNU Gpl et utilisant la bibliothèque Labltk, portage des librairies Tcl/Tk version 8.3 sous O'Caml. La licence d'utilisation de Tcl/Tk est disponible à l'adresse http://www.tcl.tk/software/tcltk/license_terms.html .

Vous pouvez distribuer librement ce logiciel en faisant référence aux auteurs.

Ce document a été traduit de L^AT_EX par H^EV^EA. retravaillé par Charles Girard

Rapport de PIR première année Jeu d'Awélé

Nicolas Chapon Charles Girard