Self-Supervision is All You Need for Solving Rubik’s Cube

该论文使用NN来解魔方，耳目一新的方法。论文地址

TMLR 2023.

---

简单来说，该方法利用了组合搜索的一个基本特性：等概率的情况下路径越短，随机发生的可能性就越大。这意味着随机训练争夺的累积概率随着移动次数的减少而增加：$1/\mathbb{M}^N$，其中$\mathbb{M}$表示移动集，N表示路径长度。

训练一个DNN来获得达到某一目标状态的概率图，也就是获得最后一步，也就是倒着来。

训练DNN时，我们的方法用目标状态初始化目标问题，并应用一系列随机移动对其进行加扰。在每一步，DNN都会根据当前状态的模式来预测最后一次应用的移动。作为训练损失，我们计算最后一步的实际概率分布和预测概率分布之间的分类交叉熵。算法1概述了训练过程，上图展示了魔方上的一个示例数据点。

我们通过顺序反转DNN预测的移动来搜索追溯到目标状态的解决方案路径。我们采用最佳优先搜索算法，并对最有希望的候选路径进行优先排序，我们根据其所有组成移动的概率的累积乘积对其进行评估。累积乘积可以表示为$\prod_{i=1} \hat p_i$，其中$\prod$表示第$i$次朝向目标的反向移动的预测概率。