Solving a Rubik's Cube Using its Local Graph Structure
<|reference_start|>Solving a Rubik's Cube Using its Local Graph Structure: The Rubix Cube is a 3-dimensional single-player combination puzzle attracting attention in the reinforcement learning community. A Rubix Cube has six faces and twelve possible actions, leading to a small and unconstrained action space and a very large state space with only one goal state. Modeling such a large state space and storing the information of each state requires exceptional computational resources, which makes it challenging to find the shortest solution to a scrambled Rubix cube with limited resources. The Rubix Cube can be represented as a graph, where states of the cube are nodes and actions are edges. Drawing on graph convolutional networks, we design a new heuristic, weighted convolutional distance, for A star search algorithm to find the solution to a scrambled Rubix Cube. This heuristic utilizes the information of neighboring nodes and convolves them with attention-like weights, which creates a deeper search for the shortest path to the solved state.<|reference_end|>
@article{yao2024solving,
    title={Solving a Rubik's Cube Using its Local Graph Structure},
    author={Shunyu Yao, Mitchy Lee},
    journal={arXiv preprint arXiv:2408.07945},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.07945},
    primaryClass={cs.AI}
}