headlogo

Othello, les échecs et les jeux que j'ai programmés

Si vous cherchez mon travail consacré au problème de l'évaluation et du classement des joueurs d'échecs (résumé rapide, draft de l'article de la revue de l'ICGA en html et en pdf, base de données de 26000 partie en PGN) c'est ici qu'il faut aller.

On trouvera sur cette page tout un ensemble d'informations que j'ai pu accumulé au fil des années concernant la programmation des jeux, et les programmes que j'ai moi-même écrits (pour un cours plus complet, voir ma page sur la programmation des jeux).
La programmation des jeux a toujours été un de mes hobbies. J'ai écrit mon premier programme de jeu en 1979 sur un TRS-80, en assembleur Z80, quand j'avais 17 ans. C'est ainsi qu'est né OTAGE, mon programme d'Othello/Reversi.

OTAGE

La première version de mon programme d'Othello était plutôt faible. Elle utilisait un algorithme alpha-béta simple, que j'avais découvert dans la revue "l'Ordinateur Individuel", à la suite d'une série d'articles écrits par David Levy, un des pionniers de la programmation des jeux. La fonction d'évaluation était mauvaise, exclusivement basé sur des facteurs positionnels statiques.

J'ai repris mon programme en 1984, à l'X, où je l'ai réécrit en Fortran sur VAX-8600. La fonction d'évaluation était déjà meilleure (elle commençait à prendre en compte un certain nombre d'aspects dynamiques des positions). Le programme fut testé par un grand nombre d'élèves et remporta beaucoup plus de victoires qu'il ne connut de défaites. Cependant, il n'était pas de taille face aux meilleurs programmes et aux meilleurs joueurs d'Othello.

En 1987, le programme fut ré-écrit une troisième fois, cette fois-ci pour partie en C (l'algorithme de recherche) et pour partie en assembleur 68000 (la fonction d'évaluation), pour fonctionner sur Amiga et sur stations SUN-3. Cette nouvelle version avait un algorithme alpha-beta amélioré, une fonction d'évaluation plus rapide. Il fut testé par un des meilleurs joueurs français de l'époque et était déjà devenu un assez fort adversaire.

Après quelques années de pause, le programme connut de nouvelles évolutions en 1995. A cette époque, nous travaillions sur l'utilisation des algorithmes génétiques, et sur le développement de fonctions de fitness probabiliste. OTAGE semblait un candidat parfait pour ce type de tests, et un certain nombre d'évolutions furent faites, et le programme fut totalement ré-écrit en C. Les résultats ne furent pas forcément trés probants concernant Othello (voir cet article), mais permit de traiter certains problèmes comme l'optimisation de matrices de turbo-codes (voir cet autre article).

En 1996, le programme connut ses dernières évolutions (à ce jour). L'algorithme de recherche fut modifié (on passa d'un alpha-béta à un algorithme de type mtd(f)). La fonction d'évaluation fut totalement redéveloppée pour devenir une fonction auto-réalisée par apprentissage et co-évolution (voir ce rapport de DEA pour plus de détails).
Cette version d'OTAGE fut testé sur le serveur IOS, qui regroupait la quasi-totalité des meilleurs programmes d'Othello, et il arriva, au temps de sa splendeur, au cinquième rang (ce qui en faisait un programme imbattable pour n'importe quel joueur humain). Il resta cependant en deça des meilleurs programmes, comme Logistello ou Hannibal. Il lui manquait en particulier une bibliothèque d'ouverture de bonne qualité.

Je ne distribue pas le code source d'OTAGE. Il est écrit en C, et le code n'est pas particulièrement de bonne qualité... Il est peu probable que le programme connaisse de nouvelles évolutions, même si, de temps en temps, je sens des fourmillements dans les doigts pour le faire évoluer, et pour en faire en particulier un programme utilisant le parallélisme des nouveaux processeurs multi-coeurs. Hélas, c'est le temps qui manque...

Aujourd'hui la recherche sur Othello est au ralenti, voire à l'arrêt. La victoire de Logistello en 1997 contre Takeshi Murakami (alors champion du monde) sur un score sans appel de 6-0 a grandement éteint les travaux sur la programmation de ce jeu. Le code source de Logistello est disponible sur la page Web de son auteur, Michael Buro.

Les échecs

J'ai été un assez bon joueur d'échecs (classé dans mes "teens"), et les échecs restent mon jeu préféré. J'ai commencé à jouer contre les premiers programmes d'échecs sur les machines spécialisées des années 70, comme le Fidelity Chess Challenger, qui disposait d'un programme écrit par Dan et Kathe Spracklen.
Quelques années plus tard, j'ai acheté sur Apple II un autre programme des Spracklen, Sargon III, qui était pour l'époque un programme remarquable, écrit en assembleur 6502. Une longue série a suivi (mychess, mephisto, chess challenger, chessmaster, Fritz, Schredder, Rybka, etc...)

Il est aujourd'hui facile de trouver sur Internet d'excellents programmes d'échec gratuits, y compris les codes sources. Ainsi Crafty et Fruit sont tous les deux disponibles sous forme de code source.

J'ai moi-même écrit un programme d'échecs, à la suite d'un défi qui m'avait été lancé par certains de mes étudiants. Ils prétendaient qu'il était impossible d'écrire en ADA un programme d'échecs avec des fonctions de génération de coups aussi rapides qu'en C. C'est ainsi qu'est né le programme LOVELACE. LOVELACE est écrit intégralement en ADA, à l'exception d'une vingtaine de lignes d'assembleurs. Il est, comme Crafty, basé sur le système des bitboards pour la génération de coups. LOVELACE a été écrit en moins d'un mois pendant mes fins de soirée, et il ne faut donc pas en attendre des performances exceptionnelles (il passe tout de même les 2300 ELO). En revanche, le programme peut avoir un intérêt pour les gens qui apprennent à utiliser le langage ADA. Il respecte le protocole xboard et peut donc être utilisé avec de nombreuses IHM. Le code source de LOVELACE est disponible ici.

Les dames chinoises

Il s'agit là aussi d'un programme que j'ai écrit à la suite d'un challenge lancé par certains de mes amis. Il s'agissait d'écrire un programme de dames chinoises, et de faire un tournoi de programmes. Là aussi j'ai décidé de tenir le pari en écrivant le programme en OCAML, afin de prouver que ce langage permettait de programmer extrêmement vite. Au final, je fus le seul à terminer le programme... Le code source est disponible ici.

L'Awélé

L'Awélé est un jeu d'origine africaine que certains de mes élèves avaient choisi comme projet. J'ai pour habitude d'essayer de réaliser aussi moi-même les projets que choisissent mes élèves, et j'ai donc écrit un programme d'Awélé. Le code source (en Ocaml) est disponible ici. Il y a également deux versions écrites en Haskell, une de 70 lignes qui implante seulement l'algorithme, et une autre de 170 lignes avec les graphismes.

Le Quarto

Le quarto est un jeu intéressant à programmer car la fonction d'évaluation n'est pas symétrique. Le code source de mon programme est disponible ici.

L'Abalone

Un autre jeu fort intéressant dont le code source est disponible ici.


Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 03:01, 13/02/2017 xhtml validation