我解开了华容道
I Solved Klotski
频道:2swap · 时长:12:19 · 发布:2025-08-22 · 播放:2081728
简介
2swap 解释了他如何通过将华容道的完整状态空间映射为图并可视化来解决这个滑块拼图。视频包含吉尼斯世界纪录解法的片段,并链接到交互式图。
HN 为什么推荐
HN 用户指出它有助于直观理解为什么某些游戏难以导航,以及它的 Rush Hour 和图可视化。
游戏的状态空间可以产生一些直觉,解释为什么某些游戏很难 — HN, 2025
数据可视化与信息设计 · 算法与数据结构 · 国际象棋、桌游与解谜
中文字幕节选
这是一个随机智能体在探索滑块拼图的状态空间。 这个拼图叫做Klotski。 这类滑块拼图相当常见, 但除了作为拼图之外,这些滑块还定义了图, 用它们的局部子结构来建模复杂的拓扑, 以及它们的全局超结构。 通常,它是一个6x6的网格,目标是 将这个方块从右侧的洞中移出。 我们还做不到,因为这块挡住了…… 让我们把拼图的当前位置表示为一个节点。 如果我们在拼图上走一步,就会到达另一个节点。 由于这些位置只差一步, 我们画一条边连接这两个节点。 每个节点又连接着几个其他节点,形成一座路径的迷宫。 你可能会想——如果我们把所有节点都加进去,这个图会是什么样子? 也许它有一些总体的结构…… 比如一个网格,或者可能完全是一团乱麻! 为了建立一些直觉,先来看几个刻意构造的拼图。 只有一个方块时,只有一个自由度。 有两个时,你得到它们坐标的笛卡尔积,形成一个网格。 每个方块定义了一个不同的运动轴。 三个方块构成一个3D晶格, 而有4个自由度时,图自然扩展成一个超立方体! 但当方块可以相交时,就变得更有趣了。 拿我们的双方块拼图,但让方块相互阻挡, 2D结构的一部分就不再有效,代表方块重叠。 当两个方块在同一条轨道上时,我们得到这个三角形。 无论上面的方块在哪里,它都成为下方方块的边界。 对于这样的拼图,我们隐含地创造了一个想象的对偶结构, 对应于那些有效但无法到达的状态, 除非一个方块穿过另一个。 3个相交的方块仍然形成一个立方体,只是有些区域被挖空了。 但随着方块数量增加,图的维度与方块数量的关系越来越小, 而与空格数量的关系越来越大。 举个例子,这个拼图有一些很酷的行为。 如果我把它完全展开,注意它有一些总体的超结构, 但同样,在图的很小一部分中, 局部行为也呈现出相当漂亮的模式。 它就像一个可爱的局部欧几里得流形, 有两个维度——两个自由度。 这是因为在拼图上,有两个洞允许移动。 一个轴以移动上面的洞为特征, 一个轴对应下面的洞。 在极端情况下,不是方块在移动,而是 空格定义了自由度。 所以,在满板和空板之间的某个地方,我们得到 方块之间纠缠交错的复杂结构。 这是我们开始时的一个拼图。 它的超结构相当简单。 暂停一下,想想它可能是什么样子。你 也许能从方块的排列猜出它的形状! 准备好了吗? 从这个角度看,拼图几乎是对称的。 关键在于认识到这两个方块会卡在两个位置之一。 它们要么在垂直红条的左边, 要么在它的右边。 一次只能有一个过渡。 当红条在上方时,橙色方块可以过渡。 但当它放下时,绿色方块可以过渡。 这就是图超结构的决定性特征。 这是一个连接4个角的方形。 我们可以根据拼图的位置给图上的节点着色。 这一半的节点中,绿色方块在横条的右侧, 而另一半的节点中,橙色方块在横条的右侧。 让我们在这个图上转一圈。 现在,从这里,我们可以高亮所有解,其中绿色方块在 洞的旁边——
HN 上的讨论
这看起来和“2swap”[1] 上的图表很相似。如果你还没看过,值得一看。[1] [VIDEO] — sublinear, 2026-02
很棒的文章,能解决整个游戏而不仅仅是单个谜题,非常令人印象深刻。PS:如果你正在读这些评论,你很有可能也会喜欢 2swap 的这个视频,它用 3D 可视化了 Rush Hour 的解法:[VIDEO] — ohc, 2025-12
这让我想起一个很棒的视频:[VIDEO] 基本上,游戏的状态空间可以让人直观理解为什么某些游戏很难,视频中展示了各种状态的聚类,而这些状态只通过极少数边与获胜状态相连。因此玩家很容易在迷宫中“迷路”。 — chii, 2025-09
这是一个包含更多信息的视频的交互式配套内容:[VIDEO](之前在[LINK]有过一些讨论) — dzaima, 2025-09
相关视频
- 量子纠缠与幽灵般的超距作用 · Veritasium · 9:15
- AI 安全是帕斯卡的赌注吗? · Robert Miles AI Safety · 13:41
- 光环驱动器 · Cool Worlds · 17:33
- 美国的财富不平等 · politizane · 6:23
- 租房 vs. 买房:5% 规则 · Ben Felix · 10:36
- 我尝试使用AI。它吓到了我。 · Tom Scott · 15:49
- 费曼:如何思考 1 of 2 FUN TO IMAGINE 11 · Christopher Sykes · 6:24
- TUN:让 MMO 不再被毁 · MrBtongue · 14:05
- 核聚变发电还有多远? · Sabine Hossenfelder · 12:49
- Larynx 演示 · synesthesiam · 6:39
- 在没有科学和数学的情况下建造大教堂:工程方法解析 · engineerguy · 11:54
- Matplotlib 更好的默认颜色映射 | SciPy 2015 | Nathaniel Smith 和 Stéfan van der Walt · Enthought · 19:08
- Hans Rosling 的 200 个国家,200 年,4 分钟 - 统计的乐趣 - BBC · BBC · 4:47
- AlphaGo - 电影 | 完整获奖纪录片 · Google DeepMind · 1:30:28
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- 学会玩经典 NES 游戏的计算机程序 · suckerpinch · 16:17