----- Entry for the 2010 "Humies" Awards for Human-Competitive Results ----- ---------------------------------------------------------------------------- (1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result: 1st: "An Evolutionary Approach for Solving the Rubik’s Cube Incorporating Exact Methods" 2nd: "Empirical Benchmarks of a Genetic Algorithm Incorporating Human Strategies" 3rd "Design and Comparison of two Evolutionary Approaches for Solving the Rubik's Cube" ---------------------------------------------------------------------------- (2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper: 1st: Nail El Sourani, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany sourani@fhdw.de +492202 9527387 FAX +492202 9527200 Sascha Hauke, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany sascha.hauke@fhdw.de +492202 9527387 FAX +492202 9527200 Markus Borschbach, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany Markus.Borschbach@fhdw.de +492202 9527369 FAX +492202 9527200 2nd: Markus Borschbach, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany Markus.Borschbach@fhdw.de +492202 9527369 FAX +492202 9527200 Christian Grelle, University of Münster, Ludwig-Wolker Str. 27 48157 Münster Germany Chistian.Grelle@uni-muenster.de +492511321258 Sascha Hauke, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany sascha.hauke@fhdw.de +492202 9527387 FAX +492202 9527200 3rd: Nail El Sourani, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany sourani@fhdw.de +492202 9527387 FAX +492202 9527200 Markus Borschbach, Faculty of Computer Science, University of Applied Sciences Hauptstr. 2, 51465 Bergisch Gladbach, Germany Markus.Borschbach@fhdw.de +492202 9527369 FAX +492202 9527200 ---------------------------------------------------------------------------- (3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition): Markus Borschbach ---------------------------------------------------------------------------- (4) the abstract of the paper(s): 1st: Solutions calculated by Evolutionary Algorithms have come to surpass exact methods for solving various problems. The Rubik’s Cube multiobjective optimization problem is one such area. In this work we present an evolutionary approach to solve the Rubik’s Cube with a low number of moves by building upon the classic Thistlethwaite’s approach. We provide a group theoretic analysis of the subproblem complexity induced by Thistlethwaite’s group transitions and design an Evolutionary Algorithm from the ground up including detailed derivation of our custom fitness functions. The implementation resulting from these observations is thoroughly tested for integrity and random scrambles, revealing performance that is competitive with exact methods without the need for pre-calculated lookup-tables. 2nd: This work outlines the incorporation of human strategies in a genetic algorithm. Human competence and machine intelligence are merged creating symbiotic human-machine intelligence, which is called HuGO!, the Human strategy based Genetic Optimizer. HuGO! emerged from and is applied to the restoration problem of Rubik’s Cube and successfully solves this task. A competition between HuGO! and human Rubik’s Cube contestants demonstrates that the incorporated human strategies improved the genetic solver’s performance to become human-competitive. 3rd: Solutions calculated by Evolutionary Algorithms have come to surpass exact methods for solving various problems. The Rubik's Cube multiobjective optimization problem is one such area. In this paper we design, benchmark and compare two di erent evolutionary approaches to solve the Rubiks Cube. One being based on the work of Michael Herdy using prede ned swapping and ipping algorithms, the other adapting the Thistlethwaites Algorithm. The latter is based on group theory, transforming the problem of solving the cube into four subproblems. We give detailed information about realizing those Evolutionary Algorithms regarding selection method, quality function and mutation operators. Finally, both methods are benchmarked and compared to enable an interesting view of solution space size and exploration/eploitation in regard to the Rubik's Cube. ---------------------------------------------------------------------------- (5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria that the author claims that the work satisfies: A, B, D, E, F, G, H ---------------------------------------------------------------------------- (6) a statement stating why the result satisfies the criteria that the contestant claims: This work vividly shows, how a human strategy can be incorporated in a genetic algorithm and can be approved by using elementary knowledge from computable complex solutions. The goal was on one hand not to develop an outstanding fast or efficient algorithm, but to demonstrate the advantageous adaptation of genetic algorithms to human induced strategies and on the other hand to explore the nimprovement by using structure taken from exeact solutions. While an external strategy guides the algorithm, the evolutionary process produces solutions no human had thought of. The approach and procedure fulfill (A), while the results of the algorithm outperform the evolutionary approach of "Herdy, M.; Patone, G.: Evolution Strategy in Action – 10 ES-Demonstrations. 1994." in terms of solution lengths, which is an important factor in the field of Rubik's Cube (B,F). The result as scientific approach is publishable (D) and is equal to the results of human performance, which have improved over time in a long history of competitions (E). The application of evolutionary strategies in the field of Rubik's Cube is considered of indisputable difficulty among experts (G) and the entry holds its own competition involving real human players to demonstrate its human-competitiveness (H). A: The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention. B: The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. D: The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created. E: The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. F: The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. G: The result solves a problem of indisputable difficulty in its field. H: The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs). ---------------------------------------------------------------------------- (7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); 1st: Nail El Sourani, S. Hauke, M. Borschbach, "An Evolutionary Approach for Solving the Rubik’s Cube Incorporating Exact Methods", In C. Di Chio et al. (Eds.): EvoApplications 2010, Part I, LNCS 6024, pp. 80–89, 2010, Springer-Verlag Berlin Heidelberg 2010. 2nd: Markus Borschbach, Christian Grelle, "Empirical Benchmarks of a Genetic Algorithm Incorporating Human Strategies", Technical Report no. 2009/01, University of Applied Sciences Bergisch Gladbach, April 2009. http://www.fhdw.de/Borschbach.aspx 3rd: Nail El Sourani, M. Borschbach, "Design and Comparison of two Evolutionary Approaches for Solving the Rubik's Cube", submitted PPSN 2010. ---------------------------------------------------------------------------- (8) a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors: C. Grelle: 25 % N. Sourani: 30 % S. Hauke: 10 % M. Borschbach 35 % ---------------------------------------------------------------------------- (9) a statement stating why the judges should consider the entry as "best" in comparison to other entries that may also be "human-competitive." Since the introduction of the ideas of evolutionary problem solving, the focus of applications has been on either so far not solvable scaled problem sizes or problems which are not solveable in an analytical way. The incorporating of human strategies in real life is often much similar. Examples are decision strategies based on a "rule of thumb" and expert knowledge for certain problems which are often in a descriptive form. In the work filed for the award, the evolution of such a strategy is considered, which has been proven to be successful in many human competitions. Therefore, the approach qualifies for a new research direction within Evolutionary Computation, which is outlined and inspired by human achievements. This can be considered as one of the major goals of the “HUMIES” AWARDS FOR HUMAN-COMPETITIVE RESULTS. The evolutionary implementation resulting from the strategy filed for the award is thoroughly tested for integrity and random scrambles, revealing performance that is competitive with exact methods without the need for pre-calculated lookup-tables.