Git Product home page Git Product logo

alphacube's Introduction

AlphaCube

AlphaCube is a powerful & flexible Rubik's Cube solver that extends EfficientCube. It uses a Deep Neural Network (DNN) to find optimal/near-optimal solutions for a given scrambled state.

Note

๐ŸŽฎ Try the interactive demo: alphacube.dev

Use Cases

  • Solve any scrambled Rubik's Cube configuration with ease
  • Find efficient algorithms/solutions, optimizing for either computation speed or ergonomics of the move sequence
  • Incorporate into Rubik's Cube apps and tools to provide solving capabilities
  • Analyze and study the statistical properties and solution space of the Rubik's Cube puzzle
  • Illustrate AI/ML concepts to students. Topics include:
    • discrete diffusion model
    • self-supervised learning
    • combinatorial search with probabilities

Table of Contents

Installation

Open a terminal and execute the following command:

pip install -U alphacube

Usage

Basic

import alphacube

# Load a trained DNN (default: "small" on cpu, "large" on GPU)
alphacube.load()

# Solve the cube using a given scramble sequence
result = alphacube.solve(
    scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2",
    beam_width=1024, # Number of candidate solutions to consider at each depth of search
)
print(result)

Output

{
    'solutions': [
        "D L D2 R' U2 D B' D' U2 B U2 B' U' B2 D B2 D' B2 F2 U2 F2"
    ],
    'num_nodes': 19744, # Total search nodes explored
    'time': 1.4068585219999659 # Wall-clock time in seconds
}

Better Solutions

Increasing beam_width explores more candidate solutions, producing shorter (better) solve sequences at the cost of increased computation:

result = alphacube.solve(
    scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2",
    beam_width=65536,
)
print(result)

Output

{
    'solutions': [
        "D' R' D2 F' L2 F' U B F D L D' L B D2 R2 F2 R2 F'",
        "D2 L2 R' D' B D2 B' D B2 R2 U2 L' U L' D' U2 R' F2 R'"
    ],
    'num_nodes': 968984,
    'time': 45.690575091997744
}

beam_width values between 1024-65536 typically offer a good trade-off between solution quality and speed. Tune according to your needs.

Applying Ergonomic Bias

The ergonomic_bias parameter lets you specify the desirability of each move type, influencing the solver to favor certain moves over others:

# Desirability scale: 0 (lowest) to 1 (highest)
ergonomic_bias = {
    "U": 0.9,   "U'": 0.9,  "U2": 0.8,
    "R": 0.8,   "R'": 0.8,  "R2": 0.75,
    "L": 0.55,  "L'": 0.4,  "L2": 0.3,
    "F": 0.7,   "F'": 0.6,  "F2": 0.6,
    "D": 0.3,   "D'": 0.3,  "D2": 0.2,
    "B": 0.05,  "B'": 0.05, "B2": 0.01,
    "u": 0.45,  "u'": 0.45, "u2": 0.4,
    "r": 0.3,   "r'": 0.3,  "r2": 0.25,
    "l": 0.2,   "l'": 0.2,  "l2": 0.15,
    "f": 0.35,  "f'": 0.3,  "f2": 0.25,
    "d": 0.15,  "d'": 0.15, "d2": 0.1,
    "b": 0.03,  "b'": 0.03, "b2": 0.01
}

result = alphacube.solve(
    scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2",
    beam_width=65536,
    ergonomic_bias=ergonomic_bias
)
print(result)

Output

{
    'solutions': [
        "u' U' f' R2 U2 R' L' F' R D2 f2 R2 U2 R U L' U R L",
        "u' U' f' R2 U2 R' L' F' R D2 f2 R2 U2 R d F' U f F",
        "u' U' f' R2 U2 R' L' F' R u2 F2 R2 D2 R u f' l u U"
    ],
    'num_nodes': 1078054,
    'time': 56.13087955299852
}

GPU Acceleration

For maximum performance, use the "large" model on a CUDA-enabled GPU (requires PyTorch):

alphacube.load("large")
result = alphacube.solve(
    scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2",
    beam_width=65536,
)
print(result)

Output

{
    'solutions': ["D F L' F' U2 B2 U F' L R2 B2 U D' F2 U2 R D'"],
    'num_nodes': 903448,
    'time': 20.46845487099995
}

Using a GPU provides an order of magnitude speedup over CPUs, especially for larger models.

Important

When running AlphaCube on a CPU, it's generally recommended to stick with the "small" model, as the larger "base" and "large" models would take considerably more time to find solutions.

Please refer to our documentation for more, especially "Getting Started"

How It Works

At the heart of AlphaCube lies a deep learning method described in "Self-Supervision is All You Need for Solving Rubik's Cube" (TMLR'23), the official code of which is also available as EfficientCube.

The 3 provided models ("small", "base", and "large") are compute-optimally trained in the Half-Turn Metric, This means the model sizes are scaled in tandem with the amount of training data to maximize prediction accuracy for a given computational budget. See Section 7 of the above-mentioned paper for details.

Note

๐Ÿ“– Read more: "How It Works"

Contributing

You are more than welcome to collaborate on AlphaCube. Please read our Contributing Guide to get started.

License

AlphaCube is open source under the MIT License.

alphacube's People

Contributors

kyo-takano avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar

Forkers

m-a-t-h-e-u-s

alphacube's Issues

Error when running AlphaCube

So when I try to run the following code

import alphacube

alphacube.load(model_id="small") # the default model

result = alphacube.solve(
    scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2",
    beam_width=1024,
)
print(result)

the output would give me these errors

Traceback (most recent call last): File "/Users/vincent/Rubik Cube Solver/main.py", line 4, in <module> alphacube.load(model_id="small") # the default model ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/alphacube/__init__.py", line 58, in load _solver.load(*args, **kwargs) File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/alphacube/solver.py", line 55, in load self.model = load_model(*args, **kwargs) ^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/alphacube/model.py", line 55, in load_model state_dict = torch.load(model_path, map_location=torch.device("cpu")) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/torch/serialization.py", line 993, in load with _open_zipfile_reader(opened_file) as opened_zipfile: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/torch/serialization.py", line 447, in __init__ super().__init__(torch._C.PyTorchFileReader(name_or_buffer)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ RuntimeError: PytorchStreamReader failed reading zip archive: failed finding central directory

I did pip install alphacube already

Symbolic Regression

Hi there!

It is me again...

First of all, thank you very much for listening to my ideas and being so patient and nice with me.

I'm attempting Symbolic Regression on your model. However, managing 54 entries and 18 outputs is quite overwhelming. I'm considering training another model to predict the number of moves required for the AlphaCube to solve a given scramble, possibly with a small beam width to expedite data collection (I remember you did something like this, but I'm unsure if you have the model saved). For every solution with a length N, I would generate N data points, capturing the state after the scramble and the number of moves required to solve from the start to the end of the solution. Then, I'll utilize it as an evaluation function, like chess engines, and proceed with symbolic regression on this model, which involves 54 entries and 1 output. My intuition suggests it might contain some information on solving a Rubik's Cube within its weights. Additionally, it would be interesting to observe from the Symbolic Regression whether redundancies emerge, such as knowing two colors of a corner piece being sufficient to determine the entire piece.

Thank you!

A process to find new solutions

Hi there, I'm testing a way to implement a FMC technique to search others solutions based on a single one. It is called NISS. From the example solve you put in "usage" here are the outputs:

scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2"
beam_width=1024

Original output: [21] D L D2 R' U2 D B' D' U2 B U2 B' U' B2 D B2 D' B2 F2 U2 F2

New output:
[20] U2 R L' U2 F2 L' U2 F2 D' L U R2 F2 D' R D' B' R B' R'
[21] D R2 D B' D' B L' B' R F L2 R F' D' R B D2 R L2 U' D

With a higher beam width:

scramble="D U F2 L2 U' B2 F2 D L2 U R' F' D R' F' U L D' F' D R2"
beam_width=11024

Original output: [20] R' F L2 D R2 U' B' L' U2 F2 U L D U2 B2 D2 R2 U2 B2 R2

New output:
[19] R' F R B2 F2 R2 D2 F2 D2 B2 R' D B R L U2 R' D U
[19] D2 R U' F U2 F' U F2 R2 D2 R2 L U L' U2 D' R' F2 R'
[18] D2 L F' D F2 D' F D2 R2 B2 R' U L' U2 D' R' F2 R'

I did it by applying NISS with gradually increasing sequence of the original solution, from the beginning to the end, and finding a new solution on the inverse scramble, like we usually do in FMC.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.