Solving Rubik's Cube with Deep Reinforcement Learning and A*.

Table of Contents

1. Overview
2. Motivation
3. Installation
4. Running Via Docker
5. Usage
6. Technologies Used
7. Results
8. Technical Aspect
9. Bug / Feature Request
10. To Do
11. Lıcense
12. References

Overview

This project aimed to solve Rubik's Cube succesfully, using only AI methods.

For any question, please don't hesitate to contact me ([email protected])

Back to top

Motivation

The Rubik's Cube has 43,252,003,274,489,856,000 different state spaces. Only one of them is the solved state. So this is an NP problem.

The motivation of this project is to solve a puzzle with such a large state space with the help of Neural Networks.

Back to top

Installation

This project is written in Python 3.9.

To download this repository, run this command in git bash.

  git clone https://github.com/yakupbilen/drl-rubiks-cube

To install the required packages and libraries, run this command in the project directory after cloning the repository.

  pip install -r requirements.txt 

Back to top

Running Via Docker

  docker build -t drl-rubiks-cube .

Windows

Install VcXsrv Windows X Server. After you install X Server, launch X Server. In Extra Settings set checked 'Disable access control'.

  docker run --rm -it -e DISPLAY=YourIpAdress:0.0 drl-rubiks-cube

Lınux

  docker run --rm -e DISPLAY -v /tmp/.X11-unix:/tmp/.X11-unix drl-rubiks-cube

Mac

Install xQuartz. Launch xQuartz, preferences->security set checked "Allow connections from network clients".

  xhost + YourIpAddress

  docker run --rm -e DISPLAY=YourIpAddress:0 -v /tmp/.X11-unix:/tmp/.X11-unix drl-rubiks-cube

Back to top

Usage

Before training the model, you can make changes in the config(.ini) file that you will send to the program as a parameter or you can add new model architecture to models file.

You must to run all of the below codes in this section from project directory.

To train the neural network, you need to run the "run_train.py" file. To avoid long hours running: after each run, trained neural network is saved to models/modelname/tmp/model_last.dat. In each run, program read the trained neural network model and continue to train the model. This process provide us to train the neural network multiple times with short times.

To train neural network model

  python run_train.py -p "path/train_config.ini"

To analyze checkpoints

  python run_checkpoints_evaluate.py -p "path/analysis_config.ini"

To find best parameter for A*

  python run_search_tune.py -p "path/analysis_config.ini"

To solve Rubik's cube.

  python run_solve.py -p "path/solve_config.ini"

Back to top

Technologies Used

PyTorch	NumPy

Back to top

Technical Aspect

This project is divided into three part:

• Rubik's Cube
  • Defining Rubik's Cube with numpy.
  • Defining moves with numpy indexing.
• Neural Network Model
  • Training Neural Network.
  • Analyzing and Finding best model among the checkpoints.
• Solve
  • Solving Rubik's Cube with A*

Back to top

Results

Neural network trained on Colab with free Tesla GPUs.

Scrambled cubes are solved with i5-8250u.

Back to top

Bug / Feature Request

If you find a bug kindly open an issue here by the expected result.

If you'd like to request a new function, feel free to do so by opening an issue here.

Back to top

To Do

• Train neural network with more data.
• Try different neural network architecture and parameters for better results.
• Implement 3D rubik's cube input from webcam

Back to top

License

Distributed under the MIT License. See LICENSE.txt for more information.

Back to top

References

• McAleer, S., Agostinelli, F., Shmakov, A., & Baldi, P. (2018). Solving the Rubik's cube without human knowledge. arXiv preprint arXiv:1805.07470
• Agostinelli, F., McAleer, S., Shmakov, A., & Baldi, P.(2019). Solving The Rubik’s Cube With Deep Reinforcement Learning And Search. Nature Machine Intelligence Vol 1 August 2019 356-363