Marcel Julien

Vous êtes ici : Les échecs et échiquiers électroniques

Presentation

Bigre, ça donne du travail de faire un jeu d'échecs! Voilà que maintenant il faut en plus répondre aux interviews.

Je ne suis pas un programmeur professionnel, mais un simple dilettante, étant en réalité juriste et professeur de droit. Si j'ai également fais un DESS en Génie Logiciel, c'était plus pour colorer ma vocation juridique d'une teinte "newtech" que l'inverse.

Magiques Années 80

Je viens d’entrer dans la trentaine, et ai donc vécu la fantastique période des années 80 quand les micros 8 bits sont arrivés. Il était hors de question pour mes parents que j'acquière ce qui ne pouvait qu'obligatoirement me distraire de l'école. Aussi me suis-je contenté de rêver, et de bouquiner. J’ai lu ainsi pas mal de livres de programmation (en basic à l'époque) et étais donc familiarisé avec la programmation sans doute dès mes 6-7 ans. Un souvenir qui me marqua, cependant fut, en primaire, un professeur qui nous fit une démonstration de son TO7 Thomson. Les jolies couleurs pures (bleu, vert) et le son synthétique m’impressionnèrent beaucoup.

Les années 80 ont aussi été les années des grandes joutes entre les "2K", Kasparov et Karpov, qui me fascinaient. Je passais également beaucoup de temps devant les vitrines des magasins à contempler ces merveilles hors de prix qu'étaient les jeux d'échecs électronique, alors très à la mode mais fort coûteux pour une bourse d'enfant.

Enfin, arrivé au collège, je fréquentais le club informatique et bavais devant cette Rolls qu'était alors l'Amiga 500. Pensez donc ! Pendant que les PC de l'époque affichaient du texte en monochrome vert et poussaient de lamentables bip-bips l'Amiga affichait 4096 couleurs et disposait d'un son HIFI sur 4 voies stéréo. Sans parler de son système d'exploitation graphique et multitâche, à des années-lumière de MS-DOS et même de MacOs. Je commençais alors discrètement à économiser...

Premières armes et premier jeu d'échecs

... et l'occasion vint en 1991, quand mon meilleur ami soutint qu'il était impossible de programmer un jeu d'échecs en Amiga Basic, le langage n'étant pas assez perfectionné selon lui. Qu'à cela ne tienne, la chose me semblait fort réalisable et je relevai le pari.

J'achetais alors un Amiga 500 (ils étaient bradés pour faire place nette à la nouvelle gamme de Commodore), mettant mes parents devant le fait accompli, et me mis aussitôt à la tâche... au détriment certes du travail scolaire. Hum. Après deux mois d'un travail acharné et passionnant, je conviais mon ami, qui assista d'abord dubitatif puis ensommeillé et enfin intrigué, à la démonstration. Dubitatif devant le sac de spaghettis qu'était mon programme en basic. Ensommeillé ensuite quand il fallut attendre vingt minutes que le jeu réagisse au coup qu'il avait entré, et intrigué enfin quand le programme se décida enfin à répondre un coup ma foi fort légal mais aussi bien peu orthodoxe (ce devait être Ca6 ou quelque chose comme ça). Enfin, cela fonctionnait ! Il ne me reste aujourd'hui de ce programme, pour l’essentiel disparu dans les méandres de disquettes démagnétisées, que quatre pages de cahier sur lesquelles j’avais recopié mon générateur de coups.

D'un point de vue purement technique, le jeu ne cherchait que sur deux coups (plies) de profondeur, et la recherche était codée "en dur" dans le programme, c'est à dire sans routine récurrente. Je ne disposais d'aucune documentation et n'avais aucune idée de ce qu'était le minimax, même si mon programme en reprenait bien s r le principe évident. Je n'avais guère pour me guider que l'observation du comportement des jeux présents sur mon ordinateur (en particulier le fantastique Sargon III).

Ce fut là ma première expérience avec la programmation d'un jeu d'échecs, et la dernière avant longtemps. L'Amiga était en effet une machine bien plus passionnante à programmer pour ses capacités graphiques que pour son processeur 68000 délivrant à peine un MIPS... surtout en basic. Je fis cependant toutes sortes de petits jeux que je distribuais sur disquette à mes amis au collège. Si cela était éloigné de la programmation des échecs ça a en tout cas été une excellente école de programmation et de créativité !

Au lycée, j'abandonnais cependant la programmation pour consacrer mon temps libre à la pratique des échecs de compétition.

Verhelst et ALPHA-BETA

Vinrent alors les années d’études. Et les études de droit laissent fort peu de place à toute activité non estudiantine (non, les soirées étudiantes n’en font pas partie !). Ce fut cependant l'époque de l'arrivée d'Internet, et je découvris le site (qui existe toujours, plus de dix ans après, quoi qu'un peu remanié) de Verhelst.

J'y appris les joies de l'alpha beta et de l'approfondissement itératif et me mis à écrire le squelette d'un jeu d'échecs en pascal, langage que j'ai toujours trouvé infiniment plus élégant que le C. Je testais en fait ces routines avec un jeu de morpion, plus rapide à écrire dans le peu de temps libre que j'avais qu'un jeu d'échecs entier. Puis ces sources restèrent dormir sur mon disque dur. En fait, je continuais à programmer pendant mes loisirs quand j’en avais le temps, mais je m'intéressais plus à la compression de données qu'à la programmation des échecs, en ce temps-là. C'est ainsi que j'ai réalisé un archiveur/ compresseur de fichiers à la Winzip.

Viennent ensuite encore d'autres années d'études, puis à l'étranger, puis des stages et des années de travail, tout ceci plein d'une vie personnelle riche et animée, mais qui ne concernent en rien le sujet de cet article : la naissance de Prédateur.

La naissance de Prédateur

Prédateur est né l’été dernier, en ao t 2007. Pour la première fois depuis des années j’ai enfin disposé d’un vrai mois de vraies vacances. Je le passais au bord de la mer, dans la résidence familiale, sans internet ni media, avec la ferme intention de bouquiner et de profiter du bon air. Sans Internet, certes, mais j’avais commis l’imprudence d’emmener avec moi mon ordinateur portable, sur lequel trônait entre autres choses l’IDE Lazarus accompagné de son Free Pascal Compiler. Bientôt une pulsion créatrice longtemps refoulée me pris et je me mis au travail pour la purger : oui, il était temps de voir si je pouvais moi aussi créer de toutes pièces un jeu d’échecs.

Etonnamment, tout s’assembla très vite dans mon esprit et il fallut un temps très court pour obtenir des résultats. Au bout de deux jours, j’avais écrit l’interface UCI et le générateur de coups. Encore trois jours et j’avais un minimax avec alpha-beta et recherche quiescente. Prédateur 0.0.3 cherchait encore à des profondeurs fixes. La Version 0.0.4 introduisit l’approfondissement itératif et la fenêtre d’aspiration. Quatre jours plus tard, première version entièrement fonctionnelle de Prédateur, alors âgé de neuf jours : la version 0.1.0 implémentait enfin l’intégralité des règles en détectant les répétitions de positions (via l’indexation des positions par des clés de Zobrist). Il était également capable de gérer son temps et n’avait donc plus besoin de profondeur de recherche fixe. Enfin, sa fonction d’évaluation devenait plus complexe, incluant, en plus de la balance matérielle, la mobilité des pièces, leur activité, la sécurité du roi, pions doublés et avancement des pions.

Deux jours plus tard, la version 0.1.1 fut une évolution majeure. J’avais cette fois fait un gros travail sur l’ordonnancement des coups afin de rendre l’alpha-beta plus efficace. La recherche quiescente bénéficiait aussi de son propre générateur de coups, ne générant que les captures et les échecs, ce qui l’accélérait notablement. Par ailleurs, Prédateur connaissait enfin la nulle par insuffisance de matériel, ce qui lui permettait de l’éviter ou de la rechercher, selon les cas. La première ligne de code de prédateur avait alors 13 jours seulement !

Suivit la version 0.1.2, qui introduisit principalement des tables de transposition : une pour l’alpha-beta et une pour la recherche quiescente. Cette dernière table n’apportant finalement pas grand-chose sera supprimée avec la version suivante.

Mes vacances s’achevèrent sur cette version, et ce fut donc la dernière de l’été 2007. Cela s’en ressenti sur la croissance de Prédateur puisqu’il n’y a eu ensuite que quelques révisions mineures, sans beaucoup d’évolutions. J’ai surtout corrigé un bogue rémanent qui empêchait Prédateur de mater dans certains cas.

Je n’ai jamais eu l’intention de diffuser ces versions de Prédateur, encore un peu vertes et bien faibles, mais mon blog a rendu un certain nombre de gens curieux, ce qui m’a poussé à les rendre publiques. D’une part pour ne plus faire l’objet d’une certaine pression, et d’autre part parce qu’il n’y avait finalement pas beaucoup d’arguments à opposer à la publication de Prédateur, si ce n’est l’orgueil mal placé d’un programmeur qui aurait aimé que le bébé fut plus joli. Mais l’orgueil est la source de la plupart de nos mauvais comportements.

L'Avenir

Mes tests m’ont permis de me convaincre de ce qu’il faudrait réécrire mon générateur de coups, trop lent, pour utiliser les bitboards de Robert Hyatt. J’ai également suivi avec intérêt la mode nouvelle des magic bitboards, mais je ne l’essayerai pas avant d’avoir réussi un générateur de coups utilisant les bitboards classiques. Mon envie de réécrire Prédateur à partir de rien tient aussi au fait que je l’ai jusqu’ici écrit sans plan aucun, tapant directement le code au fur et à mesure de ce que mon imagination me dictait, et que, inévitablement, le programme ressemble maintenant à son tour au joli plat de spaghettis de son ancêtre en Amiga Basic.

Cela rend très difficile l’implémentation de nouveaux algorithmes, tels que le null-move. Par ailleurs, j’aimerais threader le parcours de l’arbre pour faire bénéficier Prédateur des processeurs multi-cœurs dont nous disposons maintenant. Enfin, ces futures versions seront publiées en 32 et 64 bits, puisque les architectures 64 bits sont maintenant bien répandues et bien plus profitables aux échecs. Ma propre machine de développement est un portable Samsung avec un Core 2 Duo.

Je ne peux pas dire cependant que ma motivation soit maximale en ce moment, car la programmation d’un jeu d’échecs est une activité extrêmement consommatrice de temps, alors qu’il y a tant de choses passionnantes à faire dans la vie et de temps à passer avec ses proches. Il est probable que Prédateur ne continuera à évoluer qu’au gré du temps que je lui consacrerai chaque été. Ceci étant dit, les réactions positives à la sortie de Prédateur m’ont fait plaisir et incité à reprendre le travail.

Dernière version : Prédateur 2.2.1

Retrouver Julien sur son blog

Direkt-Navigation öffnen oder schließen

Ce site Web utilise des cookies pour vous offrir la meilleure expérience possible.