按年被提到
20182018 · 4 次2026
强化学习与智能体›博弈与游戏 AI·arXiv:1805.07470 · cs.AI

Solving the Rubik's Cube Without Human Knowledge

无需人类知识解魔方
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, Pierre Baldi · 2018

自我对弈式强化学习 Autodidactic Iteration,自学解魔方

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2018-05-23 · 最近 2019-10-20
6不同的人
4活跃月份
6讨论串
28被引(OpenAlex)

论文提出 Autodidactic Iteration,一种让智能体在没有人类协助的情况下自学解魔方的强化学习算法,针对魔方这类奖励稀疏、回合不一定终止的组合优化环境。结果是能解开 100% 的随机打乱魔方,解法步数中位数为 30 步,不超过使用人类领域知识的求解器。

HN 为什么提它

评论者讨论魔方求解时引用它,说明深度网络配合蒙特卡洛树搜索可以不靠人类知识解魔方,并拿它的结果与 Kociemba、Korf 等已知最优算法对照。

方法难度 3 / 5约 35 分钟经得起时间
读之前最好知道
1强化学习基础
2价值网络与策略网络
3蒙特卡洛树搜索(MCTS)
4组合优化

学习路径

读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先看深度强化学习的起点 DQN,再看把搜索与神经网络结合的 ExIt 和 AlphaZero,最后读如何把自我对弈式方法迁移到只有终局奖励的魔方。

  1. 1
    Playing Atari with Deep Reinforcement Learning用深度强化学习玩 Atari 游戏 · 2013

    深度强化学习的基础,理解价值函数用神经网络近似。

    读理解 Q 学习与用网络近似价值函数的基本想法。

  2. 2

    提出用树搜索生成专家、神经网络模仿并迭代改进,与本文的迭代思想相近。

    读抓住专家迭代(搜索作为专家、网络作为学徒)的循环。

  3. 3
    Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm用通用强化学习算法通过自我对弈精通国际象棋和将棋(AlphaZero) · 2017

    本文明确以 AlphaZero 的自我对弈加搜索范式作为出发点,并改造它以适应魔方。

    读理解自我对弈、策略价值网络和蒙特卡洛树搜索的组合,以及它依赖终局奖励这一前提。

  4. 4
    Solving the Rubik's Cube Without Human Knowledge无需人类知识解魔方 · 2018 · 就是这篇

    目标论文:提出 Autodidactic Iteration,在奖励稀疏的魔方上自学求解。

    读看如何从目标状态反向生成训练样本、价值与策略的联合训练,以及用 MCTS 求解。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用partycoder · 2018-06

“Results are compared with known optimal algorithms for the Rubik's cube: Kociemba's algorithm, Korf's algorithm.”

指出结果与 Kociemba、Korf 的已知最优算法作了比较
New deep learning technique solves Rubik's Cube without assistance原评论 ↗
引用sytelus · 2019-10

“Solving steps are not generated by RL (but could be[1])”

指出求解步骤并非 RL 生成,但可以用 RL 做
Solving the Rubik’s cube with a robot hand原评论 ↗
引用MrQuincle · 2019-10

“Solving it analytically seems to use deep nets and Monte Carlo tree search [1].”

说明解魔方似乎用到深度网络与蒙特卡洛树搜索
OpenAI's blog post about "solving the Rubik's cube" and what they actually did原评论 ↗
被提交为 story · 3 次