Evolution for automatic assessment of the difficulty of sokoban boards

Created by W.Langdon from gp-bibliography.bib Revision:1.4333

  author =       "Daniel Ashlock and Justin Schonfeld",
  title =        "Evolution for automatic assessment of the difficulty
                 of sokoban boards",
  booktitle =    "IEEE Congress on Evolutionary Computation (CEC 2010)",
  year =         "2010",
  address =      "Barcelona, Spain",
  month =        "18-23 " # jul,
  publisher =    "IEEE Press",
  keywords =     "genetic algorithms, genetic programming",
  isbn13 =       "978-1-4244-6910-9",
  abstract =     "Many games have a collection of boards with the
                 difficulty of an instance of the game determined by the
                 starting configuration of the board. Correctly rating
                 the difficulty of the boards is somewhat haphazard and
                 required either a remarkable level of understanding of
                 the game or a good deal of play-testing. In this study
                 we explore evolutionary algorithms as a tool to
                 automatically grade the difficulty of boards for a
                 version of the game sokoban. Mean time-to-solution by
                 an evolutionary algorithm and number of failures to
                 solve a board are used as a surrogate for the
                 difficulty of a board. Initial testing with a simple
                 string-based representation, giving a sequence of moves
                 for the Sokoban agent, provided very little signal; it
                 usually failed. Two other representations, based on a
                 reactive linear genetic programming structure called an
                 ISAc list, generated useful hardness-classification
                 information for both hardness surrogates. These two
                 representations differ in that one uses a randomly
                 initialised population of ISAc lists while the other
                 initialises populations with competent agents
                 pre-trained on random collections of sokoban boards.
                 The study encompasses four hardness surrogates:
                 probability-of-failure and mean time-to-solution for
                 each of these two representations. All four are found
                 to generate similar information about board hardness,
                 but probability-of-failure with pre-evolved agents is
                 found to be faster to compute and to have a clearer
                 meaning than the other three board-hardness
  DOI =          "doi:10.1109/CEC.2010.5586239",
  notes =        "WCCI 2010. Also known as \cite{5586239}",

Genetic Programming entries for Daniel Ashlock Justin Schonfeld