La description de Cyrano.

L'applet se divise en trois grandes parties, l'interface graphique, les mécanismes de base, et le centre de décision Othellistique.

Peu de chose sur l'interface graphique, écrit avec l'AWT elle ne demande qu'a être améliorée. En attente d'actions, elle lance en réponse les taches appropriées.

Les mécanismes de bases, véritable squelette de l'application, gèrent et contrôlent tous les mouvements sur l'othellier. De la rapidité a exécuter ces taches dépend une partie non négligeable des performances de Cyrano.

Attardons nous sur le centre de décisions Othellistique. Véritable cerveau de Cyrano, il intègre la plupart des derniers développements sur ce type de produit. Une petite dissection s'impose.

Le centre de décision travaille en permanence et s'exécute dans son propre Thread (comme une tache de fond), l'IHM peut l'interroger à tout moment. Une requête de l'IHM est simplement la transmission d'une position. Il détermine alors en fonction du temps restant et du niveau jeu, le temps accordé à trouver une réponse, puis vérifie que la position correspond à la recherche en cours (réflexion sur temps adverse) et si nécessaire relance une étude . Le temps accordé n'est pas systématiquement utilisé, par exemple si une étude plus profonde n'a que peu de chance de se terminer.

La prise de décision:

L'ouverture : Cyrano emprunte a Cassio une mini bibliothèque d'ouverture, les lignes les plus courantes avec les réponses les plus fréquentes, le hasard (pondéré) permet de varié les plaisirs. Cette partie est embryonnaire car gourmande en mémoire (les meilleurs programme ont une bibliothèque de plusieurs Mo, voire plusieurs dizaines de Mo).

Le milieu de partie : Cyrano, comme tous les autres, utilise une variante de l'algorithme alpha-beta, le Negascout. Plusieurs améliorations sont implementées, l'iterative deepening qui offre en autre l'avantage de trouver rapidement une réponse, l'Aspiration search reduit la fenêtre de recherche, le tri des coups grâce a une recherche courte (généralement 1), une table de transposition de type TWODEEP avec l'anticipation ETC évitent d'analyser plusieurs fois la même position et ProbCut qui réfute les coups les moins probables. Mais tous ces développements ne servent a rien sans une bonne évaluation des positions.

La fonction d'évaluation : Deux critères entrent dans l'évaluation de la position, la mobilité et la structure. Le premier est évalué de façon approché, le second grâce a une étude statistique sur des bases de données de parties [Wthor][Edax][logistello]. Ils sont pondérés en fonction de l'avancement de la partie. M Buro, auteur de Logistello, a largement commenté le sujet.

Pour sa part Cyrano utilise 3 patterns dynamiques (stages 10-54),

et un pattern statique pour la structure.

La fin de partie : Une autre variante alpha-beta est implementé, MTD(f) qui, il me semble, est légèrement supérieure pour la résolution d'une position a Aspiration Negascout, un ProbCut dans sa version EndCut accélére la prise de decision. Ici la fonction d'évaluation est triviale.

Cyrano et ses ressources sont encapsulés dans une archive JAR dont la taille est un peu moins de 128Ko.



Cyrano version 4.2.5 (19/01/2005).
Copyright © 2002-2005 Bruno Causse.
Tous droits réservés.
Othello ® est une marque déposée de Tsukuda-Original, licenciée par Anjar et distribuée en France par Mattel.