Derivative Evaluation Function Learning Using Genetic Operators

David Lorenz and Shaul Markovitch. Derivative Evaluation Function Learning Using Genetic Operators. In Proceedings of The AAAI Fall Symposium on Games: Planing and Learning, 106-114 New Carolina, 1993.

Abstract

We introduce a new framework for applying genetic algorithms to game evaluation-function learning. The evaluation function is learned by its derivatives rather than learning the function itself. We define a new genetic operator, called derivative crossover, that accelerates the search for static evaluation functions. The operator performs cross-over on the derivatives of the chromosomes. The traditional crossover and mutation are special cases of this new operator. We demonstrate experimentally the advantage of the derivative crossover for learning an evaluation function. More generally, this work is also a study of the application of genetic algorithms to the domain of game playing, with the emphasis on learning a static evaluation function. Learning involves experience generation, hypothesis generation and hypothesis evaluation. Most learning systems use preclassified examples to guide the search in the hypothesis space and to evaluate current hypotheses. In game learning, it is very difficult to get classified examples. Genetic Algorithms provide an alternative approach. Competing hypotheses are evaluated by tournaments. New hypotheses are generated by combining promising hypotheses using genetic operators.

Keywords: Genetic Algorithms, Learning in Games, Games

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Lorenz:1993:DEF,
  Author = {David Lorenz and Shaul Markovitch},
  Title = {Derivative Evaluation Function Learning Using Genetic Operators},
  Year = {1993},
  Booktitle = {Proceedings of The AAAI Fall Symposium on Games: Planing and Learning},
  Pages = {106--114},
  Address = {New Carolina},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Lorenz-Markovitch-FSS1993.pdf},
  Keywords = {Genetic Algorithms, Learning in Games, Games},
  Secondary-keywords = {Adversary Search},
  Abstract = {
    We introduce a new framework for applying genetic algorithms to
    game evaluation-function learning. The evaluation function is
    learned by its derivatives rather than learning the function
    itself. We define a new genetic operator, called derivative
    crossover, that accelerates the search for static evaluation
    functions. The operator performs cross-over on the derivatives of
    the chromosomes. The traditional crossover and mutation are
    special cases of this new operator. We demonstrate experimentally
    the advantage of the derivative crossover for learning an
    evaluation function. More generally, this work is also a study of
    the application of genetic algorithms to the domain of game
    playing, with the emphasis on learning a static evaluation
    function. Learning involves experience generation, hypothesis
    generation and hypothesis evaluation. Most learning systems use
    preclassified examples to guide the search in the hypothesis space
    and to evaluate current hypotheses. In game learning, it is very
    difficult to get classified examples. Genetic Algorithms provide
    an alternative approach. Competing hypotheses are evaluated by
    tournaments. New hypotheses are generated by combining promising
    hypotheses using genetic operators.
  }

  }