skip to main content
10.1145/2908812.2908887acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article
Open access

Discovering Rubik's Cube Subgroups using Coevolutionary GP: A Five Twist Experiment

Published: 20 July 2016 Publication History

Abstract

This work reports on an approach to direct policy discovery (a form of reinforcement learning) using genetic programming (GP) for the 3 by 3 by 3 Rubik's Cube. Specifically, a synthesis of two approaches is proposed: 1) a previous group theoretic formulation is used to suggest a sequence of objectives for developing solutions to different stages of the overall task; and 2) a hierarchical formulation of GP policy search is utilized in which policies adapted for an earlier objective are explicitly transferred to aid the construction of policies for the next objective. The resulting hierarchical organization of policies explicitly demonstrates task decomposition and policy reuse. Algorithmically, the process makes use of a recursive call to a common approach for maintaining a diverse population of GP individuals and then learns how to reuse subsets of programs (policies) developed against the earlier objective. Other than the two objectives, we do not explicitly identify how to decompose the task or mark specific policies for reuse. Moreover, at the end of evolution we return a population solving 100% of 17,675,698 different initial Cubes for the two objectives currently in use.

References

[1]
E. B. Baum and I. Durdanovic. Evolution of cooperative problem solving in an artificial economy. Neural Computation, 12:2743--2775, 2000.
[2]
J. Bongard. Behavior chaining -- Incremental behaviour integration for evolutionary robotics. In Proceedings of the International Conference on the Synthesis and Simulation of Living Systems. MIT, 2008.
[3]
E. D. de Jong. A monotonic archive for pareto-coevolution. Evolutionary Computation, 15(1):61--93, 2007.
[4]
E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, and A. Winslow. Algorithms for solving Rubik's Cubes. In ESA, volume 6942 of LNCS, pages 589--700, 2011.
[5]
J. A. Doucette, P. Lichodzijewski, and M. I. Heywood. Hierarchical task decomposition through symbiosis in reinforcement learning. In Proceedings of the ACM Genetic and Evolutionary Computation Conference, pages 97--104, 2012.
[6]
J. A. Doucette, P. Lichodzijewski, and M. I. Heywood. Symbiotic coevolutionary genetic programming. Genetic Programming and Evolvable Machines, 13:71--101, 2012.
[7]
N. El-Sourani, S. Hauke, and M. Borschbach. An evolutionary approach for solving the Rubik's Cube incorporating exact methods. In EvoApplications: Part I, volume 6024 of LNCS, pages 80--89, 2010.
[8]
R. M. F. Gomez, J. Schmidhuber. Accelerated neural evolution through cooperatively coevolved synapses. Journal of Machine Learning Research, 9:937--965, 2008.
[9]
F. Gomez and R. Miikkulainen. Incremental evolution of complex general behavior. Adaptive Behavior, 5(3--4):317--342, 1997.
[10]
W. Jaskowski, M. Szubert, P. Liskowski, and K. Krawiec. High-dimensional function approximation for knowledge-free reinforcement learning: A case study in SZ-Tetris. In Proceedings of the ACM Genetic and Evolutionary Computation Conference, pages 567--574, 2015.
[11]
L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey. Journal of Machine Learning Research, 4:237--285, 1996.
[12]
S. Kelly and M. I. Heywood. Genotypic versus behavioural diversity for teams of programs under the 4-v-3 keepaway soccer task. In Proceedings of the AAAI Conference on Artificial Intelligence, 2014.
[13]
S. Kelly and M. I. Heywood. On diversity, teaming, and hierarchical policies: Observations from the keepaway soccer task. In European Conference on Genetic Programming, volume 8599 of LNCS, pages 75--86. Springer, 2014.
[14]
S. Kelly and M. I. Heywood. Knowledge transfer from keepaway soccer to half-field offense through program symbiosis. In ACM Genetic and Evolutionary Computation Conference, pages 1143--1150, 2015.
[15]
S. Kelly, P. Lichodzijewski, and M. I. Heywood. On run time libraries and hierarchical symbiosis. In IEEE Congress on Evolutionary Computation, pages 3245--3252, 2012.
[16]
R. Korf. Finding optimal solutions to Rubik's Cube using pattern databases. In Proceedings of the Workshop on Computer Games (IJCAI), pages 21--26, 1997.
[17]
D. Kunkle and G. Cooperman. Solving the Rubik's Cube: Disk is the new RAM. Communications of the ACM, 51(4):31--33, 2008.
[18]
P. Lichodzijewski and M. Heywood. Managing team-based problem solving with symbiotic bid-based genetic programming. In ACM Genetic and Evolutionary Computation Conference, pages 363--370, 2008.
[19]
P. Lichodzijewski and M. Heywood. The Rubic's Cube and GP temporal sequence learning: An initial study. In Genetic Programming Theory and Practice VIII, chapter 3, pages 35--54. Springer, 2010.
[20]
D. Moriarty, A. C. Schultz, and J. J. Grefenstette. Evolutionary algorithms for reinforcement learning. Journal of Machine Learning Research, 11:241--276, 1999.
[21]
T. Rokicki, H. Kociemba, M. Davidson, and J. Dethridge. God's number is 20. http://cube20.org, 2010.
[22]
C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Evolutionary Computation, 5:1--29, 1997.
[23]
D. G. Shapiro, H. Munoz-Avila, and D. Stracuzzi. Special issue on structured knowledge transfer. AI Magazine, 32(1), 2011.
[24]
K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2):99--127, 2002.
[25]
P. Stone. Layered learning in multiagent systems. MIT Press, 2000.
[26]
R. R. Sutton and A. G. Barto. Reinforcement Learning: An introduction. MIT Press, 1998.
[27]
M. E. Taylor, P. Stone, and Y. Liu. Transfer learning via inter-task mappings for temporal difference learning. Journal of Machine Learning Research, 8:2125--2167, 2007.
[28]
S. Whiteson, M. E. Taylor, and P. Stone. Critical factors in the empirical performance of temporal difference and evolutionary methods for reinforcement learning. Journal of Autonomous Agents and Multi-Agent Systems, 21(1):1--27, 2009.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016
July 2016
1196 pages
ISBN:9781450342063
DOI:10.1145/2908812
This work is licensed under a Creative Commons Attribution-ShareAlike International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. coevolution
  2. games
  3. genetic programming
  4. reinforcement learning
  5. task transfer

Qualifiers

  • Research-article

Funding Sources

  • NSERC

Conference

GECCO '16
Sponsor:
GECCO '16: Genetic and Evolutionary Computation Conference
July 20 - 24, 2016
Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)108
  • Downloads (Last 6 weeks)18
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)W. B. Langdon “Jaws 30”Genetic Programming and Evolvable Machines10.1007/s10710-023-09473-z24:2Online publication date: 22-Nov-2023
  • (2023)Evolutionary Ensemble LearningHandbook of Evolutionary Machine Learning10.1007/978-981-99-3814-8_8(205-243)Online publication date: 2-Nov-2023
  • (2022)Q-learning and traditional methods on solving the pocket Rubik’s cubeComputers and Industrial Engineering10.1016/j.cie.2022.108452171:COnline publication date: 1-Sep-2022
  • (2019)Solving complex problems with coevolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323384(975-1001)Online publication date: 13-Jul-2019
  • (2019)Solving the Rubik’s cube with deep reinforcement learning and searchNature Machine Intelligence10.1038/s42256-019-0070-z1:8(356-363)Online publication date: 15-Jul-2019
  • (2018)Solving complex problems with coevolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207888(880-906)Online publication date: 6-Jul-2018
  • (2017)Coevolving deep hierarchies of programs to solve complex tasksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071316(1009-1016)Online publication date: 1-Jul-2017
  • (2017)Solving complex problems with coevolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067705(782-806)Online publication date: 15-Jul-2017
  • (2017)Observations on exploration and exploitation effects on solving Rubik's cube using evolutionary strategies2017 13th International Computer Engineering Conference (ICENCO)10.1109/ICENCO.2017.8289770(95-99)Online publication date: Dec-2017
  • (2016)On Synergies between Diversity and Task Decomposition in Constructing Complex Systems with GPProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931655(969-976)Online publication date: 20-Jul-2016
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media