Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A genetic algorithm to improve an Othello program

Abstract : Let a computer program learn to play a game has been for long a subject of studies. It probably began in 1959 with A. Samuel's program [Sam59], and similar methods are still used on the most advanced computer programs, such as Deep Thought ; however, in chess, the different methods used are mainly linear regression on parameters of the evaluation function. Othello was, from the start, a game where learning proved to be very useful. The BILL program used Bayesian learning [LM90] to improve parameters of the evaluation function. Similar methods are still applied for the best Othello programs (such as LOCISTELL0[Bur94]). However, these methods require large databases of games, and are very efficient only on Othello game playing, because the game always terminates in a fixed number of moves, with perfect end-games up to 15 moves. Such methods would be very difficult to use on chess playing algorithms. Other techniques used include co-evolution [SG94], use of neural networks trained by GA to focus minimax-search [MM94], evolving strategies with GA [MM93]. However, [SG94] did not lead to world class Othello program, [MM94] was unable to improve search as soon as the evaluation function was good enough to correctly predict the move, and [MM93] was apparently not able to improve the classical (positional+mobility) strategy. In this article, we show how genetic algorithms can be used to evolve the parameters of the evaluation function of an Othello program. We must stress that our method can be used on any algorithm using an evaluation function, for any two players game. In the first part of the article, we explain the structure of the Othello program. In the second part, we explain the structure of our genetic algorithm, the operators (crossover, mutation) used, and our method to compute fitness. In the third part, results are presented and, in the last part, possible improvements and generalization of this method are discussed
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : vendredi 25 avril 2014 - 16:53:23
Dernière modification le : mardi 19 octobre 2021 - 11:02:49
Archivage à long terme le : : vendredi 25 juillet 2014 - 10:41:01


Fichiers produits par l'(les) auteur(s)




Jean-Marc Alliot, Nicolas Durand. A genetic algorithm to improve an Othello program. EA 1995, Evolution Artificielle, Sep 1995, Brest, France. pp 307-319, ⟨10.1007/3-540-61108-8_46⟩. ⟨hal-00937682⟩



Consultations de la notice


Téléchargements de fichiers