A genetic algorithm to improve an Othello program - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 1995

A genetic algorithm to improve an Othello program

Jean-Marc Alliot
Nicolas Durand

Résumé

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
Fichier principal
Vignette du fichier
306.pdf (203.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00937682 , version 1 (25-04-2014)

Identifiants

Citer

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⟩
310 Consultations
305 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More