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
EA 1995, Evolution Artificielle, Sep 1995, Brest, France. 1063, pp 307-319, 1995, 〈10.1007/3-540-61108-8_46〉
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-00937682
Contributeur : Laurence Porte <>
Soumis le : vendredi 25 avril 2014 - 16:53:23
Dernière modification le : lundi 21 mars 2016 - 11:30:45
Document(s) archivé(s) le : vendredi 25 juillet 2014 - 10:41:01

Fichier

306.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

333

Téléchargements de fichiers

106