7.3 L'Awele
145
Pour les É checs et les Dames anglaises, les bases de données consistent en des tableaux associant à chaque indice le résultat de la position représentée par cet indice. Pour
les Dames anglaises, un résultat est représenté par deux bits ; il peut avoir une des trois
valeurs : GAGNEE, PERDUE ou NULLE. Pour les É checs, en plus de cette information,
d' autres bits sont utilisés pour donner le nombre de coups minimum au gain d' une position gagnée, le nombre de coups maximum avant la perte d' une position perdue. Cette
information permet de jouer optimalement les finales de la base de données, en jouant
tous les coups possibles à partir de la position courante, et en choisissant celui qui amène
à la position qui maximise ou minimise la distance à la fin de la partie, suivant qu' on est
en train de perdre ou de gagner.
Les bases de données de finales aux Dames anglaises prennent beaucoup de place mémoire. Pour les stocker efficacement, elles sont compressées et décompressées dynamiquement lorsqu' on en a besoin. L' algorithme de compression est le run -length encoding :
une suite de mêmes caractères est remplacée par le caractère suivi du nombre de caractères de la suite. Les taux de compression en utilisant cet algorithme varient entre 18 et
52 sur ces bases de données.
7.3 L'Awele
L' Awele est un jeu africain. Un plateau d' Awele comporte deux rangées de 6 trous
contenant des graines. Chaque joueur contrôle la rangée qui est de son coté du plateau.
Un trou supplémentaire est utilisé par chaque joueur pour garder ses prisonniers. Au début
du jeu, chaque trou contient quatre graines, il y a donc 48 graines sur le plateau.
A chaque coup un joueur choisit un trou de sa rangée contenant des graines. En commençant avec le voisin de ce trou, il sème alors toutes les graines du trou, une par une,
dans le sens contraire des aiguilles d ' une montre. Si le trou contient 12 graines ou plus,
le trou d' origine est passé et le semage continue ensuite normalement. Après un coup,
le trou auquel on a enlevé les graines est donc toujours vide. Après la fin du semage, les
prisonniers sont retirés du jeu. Des graines sont prisonnières si la dernière graine semée se
retrouve dans un trou ennemi, qui après le semage contient 2 ou 3 graines. Si une capture
est effectuée et que le trou précédent contient aussi 2 ou 3 graines, ces graines sont aussi
capturées. Cette procédure est répétée pour les autre trous qui précèdent, et elle s ' arrête
lorsqu' un trou contient un nombre de graines différent de 2 ou 3, ou lorsque le bout de la
rangée adverse est atteint.
Le but du jeu est de capturer plus de graines que l' adversaire. Le jeu se termine dès
qu'un adversaire a gagné 25 graines ou plus. Le jeu se termine aussi lorsqu ' un joueur ne
peut plus jouer ; toutes les graines restantes sur le plateau sont alors capturées par son
adversaire. Si une même position est rencontrée pour la troisième de fois, avec le même
joueur ayant la main, les graines restantes sont divisées également entre les deux joueurs.
Si les deux joueurs ont 24 graines, le jeu est déclaré nul.
L' Awele a été complètement résolu grâce à l ' analyse rétrograde en 2002 [70] . To utes
145
Pour les É checs et les Dames anglaises, les bases de données consistent en des tableaux associant à chaque indice le résultat de la position représentée par cet indice. Pour
les Dames anglaises, un résultat est représenté par deux bits ; il peut avoir une des trois
valeurs : GAGNEE, PERDUE ou NULLE. Pour les É checs, en plus de cette information,
d' autres bits sont utilisés pour donner le nombre de coups minimum au gain d' une position gagnée, le nombre de coups maximum avant la perte d' une position perdue. Cette
information permet de jouer optimalement les finales de la base de données, en jouant
tous les coups possibles à partir de la position courante, et en choisissant celui qui amène
à la position qui maximise ou minimise la distance à la fin de la partie, suivant qu' on est
en train de perdre ou de gagner.
Les bases de données de finales aux Dames anglaises prennent beaucoup de place mémoire. Pour les stocker efficacement, elles sont compressées et décompressées dynamiquement lorsqu' on en a besoin. L' algorithme de compression est le run -length encoding :
une suite de mêmes caractères est remplacée par le caractère suivi du nombre de caractères de la suite. Les taux de compression en utilisant cet algorithme varient entre 18 et
52 sur ces bases de données.
7.3 L'Awele
L' Awele est un jeu africain. Un plateau d' Awele comporte deux rangées de 6 trous
contenant des graines. Chaque joueur contrôle la rangée qui est de son coté du plateau.
Un trou supplémentaire est utilisé par chaque joueur pour garder ses prisonniers. Au début
du jeu, chaque trou contient quatre graines, il y a donc 48 graines sur le plateau.
A chaque coup un joueur choisit un trou de sa rangée contenant des graines. En commençant avec le voisin de ce trou, il sème alors toutes les graines du trou, une par une,
dans le sens contraire des aiguilles d ' une montre. Si le trou contient 12 graines ou plus,
le trou d' origine est passé et le semage continue ensuite normalement. Après un coup,
le trou auquel on a enlevé les graines est donc toujours vide. Après la fin du semage, les
prisonniers sont retirés du jeu. Des graines sont prisonnières si la dernière graine semée se
retrouve dans un trou ennemi, qui après le semage contient 2 ou 3 graines. Si une capture
est effectuée et que le trou précédent contient aussi 2 ou 3 graines, ces graines sont aussi
capturées. Cette procédure est répétée pour les autre trous qui précèdent, et elle s ' arrête
lorsqu' un trou contient un nombre de graines différent de 2 ou 3, ou lorsque le bout de la
rangée adverse est atteint.
Le but du jeu est de capturer plus de graines que l' adversaire. Le jeu se termine dès
qu'un adversaire a gagné 25 graines ou plus. Le jeu se termine aussi lorsqu ' un joueur ne
peut plus jouer ; toutes les graines restantes sur le plateau sont alors capturées par son
adversaire. Si une même position est rencontrée pour la troisième de fois, avec le même
joueur ayant la main, les graines restantes sont divisées également entre les deux joueurs.
Si les deux joueurs ont 24 graines, le jeu est déclaré nul.
L' Awele a été complètement résolu grâce à l ' analyse rétrograde en 2002 [70] . To utes