Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata
Contributor : Laurence Porte Connect in order to contact the contributor
Submitted on : Friday, April 25, 2014 - 4:53:23 PM
Last modification on : Tuesday, October 19, 2021 - 11:02:49 AM
Long-term archiving on: : Friday, July 25, 2014 - 10:41:01 AM


Files produced by the author(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⟩



Les métriques sont temporairement indisponibles