Solving the Rubik's cube with stepwise deep learning

Johnson, Colin G.

Abstract

This paper explores a novel technique for learning the fitness function for search algorithms such as evolutionary strategies and hillclimbing. The aim of the new technique is to learn a fitness function (called a Learned Guidance Function) from a set of sample solutions to the problem. These functions are learned using a supervised learning approach based on deep neural network learning, that is, neural networks with a number of hidden layers. This is applied to a test problem: unscrambling the Rubik's Cube using evolutionary and hillclimbing algorithms. Comparisons are made with a previous LGF approach based on random forests, with a baseline approach based on traditional error-based fitness, and with other approaches in the literature. This demonstrates how a fitness function can be learned from existing solutions, rather than being provided by the user, increasing the autonomy of AI search processes.

Citation

Johnson, C. G. (2021). Solving the Rubik's cube with stepwise deep learning. Expert Systems, 38(3), Article e12665. https://doi.org/10.1111/exsy.12665

• Journal Article Type: Article
• Acceptance Date: Nov 6, 2020
• Online Publication Date: Jan 24, 2021
• Publication Date: May 1, 2021
• Deposit Date: Jan 30, 2021
• Publicly Available Date: Feb 1, 2021
• Journal: Expert Systems
• Print ISSN: 0266-4720
• Electronic ISSN: 1468-0394
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 38
• Issue: 3
• Article Number: e12665
• DOI: https://doi.org/10.1111/exsy.12665
• Keywords: artificial intelligence, human-like AI, fitness functions, loss functions, evolutionary computation
• Public URL: https://nottingham-repository.worktribe.com/output/5021464
• Publisher URL: https://onlinelibrary.wiley.com/doi/full/10.1111/exsy.12665
• Additional Information: Received: 2020-05-11; Accepted: 2020-11-06; Published: 2021-01-24