使用分形思想，通过图灵完备的机器赛跑关卡，并获得小机快跑成就

本文作者：Wyu-Cnk

前言

最近在玩
图灵完备(Turing Complete)
一路过关斩将，来到
机器赛跑(Robot Racing)
这一关的时候，一看地图

对于选修过分形几何的我来说，这不就是熟悉的
希尔伯特曲线
嘛！老朋友了！于是我复活已经死去的和分形几何有关的记忆，用
分形
的思想初步实现了对应的汇编代码并通过了这一关。正当我沾沾自喜并在网上查看其他人解决这一关的思路的时候，我看到了这一篇文章:
图灵完备(Turing Complete)机器赛跑(Robot Racing)关卡纯汇编60字节达成成就纪念
，我才知道原来有个成就是要求汇编代码在 64 个字节内过关，并且这篇文章里用非常简洁巧妙的方法达成了这个成就。

我和我弟弟一起探讨研究了这个方法的原理，现在我们都理解了这个方法并直呼”Vocal！ “，文章里的方法本质上也是用到了分形的思想，但文章的作者只用了简单两句”容易发现，有明显的递归模式“和”注意到 r1、r2 可被合并优化“，难倒一众英雄好汉，仿佛该作者一眼看透这个方法的本质，并觉得这非常简单无需多言(这就是大佬么.jpg)。而后我在这篇文章的启发下，也获得了“小机快跑”的成就。
本文将用尽量通俗易懂的语言，为了解过和没了解过图灵完备和分形的读者讲解用分形思想来通过机器赛跑这一关并达成成就“小机快跑”的思路，同时也将给出实现该思路的汇编代码。

图灵完备

《图灵完备》是一款电路模拟器游戏，于 2021 年在 Steam 上架。在这款游戏中，玩家可以从零开始构建计算机并编程它。在解决谜题的过程中，玩家将会学习到从基础逻辑门到算术单元、存储器等复杂元件的知识，并沿着这条道路最终学习如何搭建完整的处理器架构。完成所有主线关卡后，玩家将对处理器架构、汇编语言和电子元件彼此之间的具体联系产生更加深刻的理解。玩家也会了解高级编程语言中常见的条件判断、循环、函数等概念是如何在汇编和硬件层面具体实现的。
在本文中，读者无需关注电路细节，只需要关注算法中体现的分形的思想，以及如何巧妙地简化算法即可。

机器赛跑是最后一章
汇编挑战
里的一关，它要求玩家用汇编代码输出指令控制机器人移动走出迷宫，而“小机快跑”成就则要求玩家编写的汇编代码要尽可能简短，
只有当代码字节数不超过64才可获得该成就
。

分形与希尔伯特曲线

分形通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状
^[1]
”，即具有自相似的性质，例如最常见的雪花就是一种分形。而在机器赛跑这一关里，机器人所在的迷宫路线正好是分形几何里很经典的一种分形:
希尔伯特曲线
。希尔伯特曲线一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在1891年提出。称
\(H_n\)
为一条
希尔伯特曲线
，如果
\(H_n\)
满足以下性质:

\(H_0\)
为正方形的中心点；
将
\(H_n\)
等比例缩小到原来的
\(\frac{1}{4}\)
，记为
\(H^{\prime}_n\)
。记
\(H^{\prime}_n\)
最靠近左下角的点为
\(s_n\)
，最靠近右下角的点为
\(t_n\)
。
\(H_{n+1}\)
按照以下方式连接生成:
1. 将正方形等分成
  \(2\times2\)
  个小正方形；
2. 令左下角的小正方形为顺时针旋转
  \(90\degree\)
  后的
  \(H^{\prime}_n\)
  ；
3. 令左上方和右上方的小正方形为
  \(H^{\prime}_n\)
  ；
4. 令右下方的小正方形为逆时针旋转
  \(90\degree\)
  后的
  \(H^{\prime}_n\)
  ；
5. 连接左下方的
  \(s_n\)
  与左上方的
  \(s_n\)
  ；
6. 连接左上方的
  \(t_n\)
  与右上方的
  \(s_n\)
  ；
7. 连接右上方的
  \(t_n\)
  与右下方的
  \(t_n\)
  。

可以严格证明，
当
\(n\rightarrow\infty\)
时，
\(H_n\)
会在正方形中稠密，即会填满正方形平面。

如果将正方形等分成
\(2^n\times2^n\)
个小正方形，则容易看出，
\(H_n\)
具有以下性质:

\(H_n\)
会经过所有小正方形的中心点，并且每个小正方形只会经过一次；
相邻的两个小正方形之间至多有一条连线；
不相邻的两个小正方形之间没有连线；
\(H_n\)
为一条折线，两个端点分别位于最左下角和最右下角的小正方形中心点；
\(H_n\)
是没有方向的；
\(H_n\)
是左右对称的。

正文

有向希尔伯特曲线

虽然说迷宫的路线是希尔伯特曲线，但实际上是有一点区别的，
\(H_n\)
是没有方向的，但迷宫路径是有方向的，是要从左下角的起点走到右下角的终点的。因此我们需要仿照
\(H_n\)
的定义，给出有方向的希尔伯特曲线的定义。

称
\(\hat{H}_n\)
为一条
有向希尔伯特曲线
，如果
\(\hat{H}_n\)
满足以下性质：

\(\hat{H}_0\)
为正方形的中心点；
将
\(\hat{H}_n\)
等比例缩小到原来的
\(\frac{1}{4}\)
，记为
\(\hat{H}^{\prime}_n\)
。记
\(\hat{H}^{\prime}_n\)
的起点为
\(\hat{s}_n\)
，终点为
\(\hat{t}_n\)
。
\(\hat{H}_{n+1}\)
按照以下方式连接生成:
1. 将正方形等分成
  \(2\times2\)
  个小正方形；
2. 令左下角的小正方形为路径反转并顺时针旋转
  \(90\degree\)
  后的
  \(\hat{H}^{\prime}_n\)
  ；
3. 令左上方和右上方的小正方形为
  \(\hat{H}^{\prime}_n\)
  ；
4. 令右下方的小正方形为路径反转并逆时针旋转
  \(90\degree\)
  后的
  \(\hat{H}^{\prime}_n\)
  ；
5. 连接左下方的
  \(\hat{s}_n\)
  与左上方的
  \(\hat{s}_n\)
  ，方向指向左上方的
  \(\hat{s}_n\)
  ；
6. 连接左上方的
  \(\hat{t}_n\)
  与右上方的
  \(\hat{s}_n\)
  ，方向指向右上方的
  \(\hat{s}_n\)
  ；
7. 连接右上方的
  \(\hat{t}_n\)
  与右下方的
  \(\hat{t}_n\)
  ，方向指向右下方的
  \(\hat{t}_n\)
  。

这里的路径反转指的是将路径从原本的起点走到终点改为从终点走到起点。而要进行路径反转的原因是，在拼接路径的时候，需要前一条路径的终点走到后一条路径的起点，这样构成的才是一条新的路径，而如果不进行路径反转的话，会出现“起点走到起点”或“终点走到终点”的情况，这样得到的就不是一个新的路径了。

如果将正方形等分成
\(2^n\times2^n\)
个小正方形，则容易看出，
\(\hat{H}_n\)
和
\(H_n\)
有许多相似的性质:

\(\hat{H}_n\)
从起点出发，会经过所有小正方形的中心点，并且每个小正方形只会经过一次，而后走到终点；
相邻的两个小正方形之间至多有一条路径；
不相邻的两个小正方形之间没有路径；
\(\hat{H}_n\)
的起点和终点分别位于最左下角和最右下角的小正方形中心点；
\(\hat{H}_n\)
是有方向的，从起点指向终点；
\(\hat{H}_n\)
进行路径反转等价于
\(\hat{H}_n\)
进行左右镜像翻转
。

其中性质6尤为重要，它是由
\(H_n\)
的左右对称性决定的:
如果一条路径在忽略方向的情况下是左右对称的，则这条路径进行路径反转等价于这条路径进行左右镜像翻转
。而这个性质也意味着可以用更简便的方法来处理这个操作。

生成迷宫路径

容易看出，迷宫路径实际上就是
\(\hat{H}_3\)
，如果用给定的指令来表示路径的话，
\(\hat{H}_3\)
是这样表示的:

为了更形象地表示路径，不妨记路径为指令 1
\(\rightarrow\)
指令 2
\(\rightarrow\dots\rightarrow\)
指令
\(m\)
，例如
\(1\rightarrow2\rightarrow3\)
。设
\(h(n)\)
为
\(\hat{H}_n\)
的路径表示，则
由
\(\hat{H}_n\)
的生成方式 2~7
，我们可以得到
\(h(n)\)
的生成方式（这里需要注意路径的先后顺序，以方便后面按顺序输出路径）:

\(h(1)=3\rightarrow0\rightarrow1\)
；
\(h(n+1)=f(h(n))\rightarrow3\rightarrow h(n)\rightarrow0\rightarrow h(n)\rightarrow1\rightarrow g(h(n))\)
，

其中
\(f\)
为将路径左右翻转后顺时针旋转
\(90\degree\)
的操作，
\(g\)
为将路径左右翻转后逆时针旋转
\(90\degree\)
的操作。而要给出对路径的整体操作的定义，实际上只需要给出对路径每一步的具体操作的定义即可。因此这里只给出
\(f\)
和
\(g\)
针对每一步的具体定义：

\[f(x)=\begin{cases}
3, & x=0 \\
2, & x=1 \\
1, & x=2 \\
0, & x=3
\end{cases} \quad
,g(x)=\begin{cases}
1, & x=0 \\
0,& x=1 \\
3, & x=2 \\
2, & x=3
\end{cases} \quad.
\]

举例说明，
\(f(h(1))=f(3\rightarrow0\rightarrow1)=0\rightarrow3\rightarrow2\)
，
\(g(h(1))=g(3\rightarrow0\rightarrow1)=2\rightarrow1\rightarrow0\)
。于是对于任意给定的正整数
\(n\)
，我们都可以迭代生成对应的
\(h(n)\)
，即
不管希尔伯特迷宫有多少级，我们都可以用一条公式给它秒了！

汇编代码实现及优化

在用代码实现之前，需要先简单了解一下什么是汇编语言。
汇编语言是一种低级编程语言，用于与计算机硬件直接交互。它是计算机指令集架构的一种表现形式，使用符号代表计算机的机器指令。在汇编语言中，用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址。汇编语言与计算机硬件的关系密切，每一条汇编语句都对应着底层的机器指令，直接操作计算机的寄存器和内存。

而《图灵完备》很形象地展示了汇编语言是如何操作寄存器和内存的，不过这不是本节的重点，本节只会摘取相关原理进行讲解。

语法

条件跳转操作码 参数 1  参数 2 跳转地址

含义

如果参数 1 和参数 2 按照条件跳转操作码对应的条件判断为真，则跳转到跳转地址对应的指令

例子

label test
// 其他代码
equl re0 re1 test

表示如果
re0==re1
则跳转到
test
对应的指令处，这里
label
会将当前指令的地址赋值给
test

equl

语法

equl 参数1  参数2 跳转地址

含义

如果
参数1 == 参数2
则跳转到跳转地址对应的指令

例子

equl re0 re1 test

表示如果
re0==re1
则跳转到 test 对应的指令处

call

语法

call 函数地址 _ _

含义

调用函数，跳转到函数地址对应的指令

例子

label fun
# 其他代码
call fun 0 0

表示调用 fun 函数，跳转到 fun 对应的指令处

return

语法

return _ _ _

含义

跳转到上一次执行的 call 语句的下一句指令

例子

call fun 0 0
add re0 re1 re2
// 其他代码
label fun
// 其他代码
return 0 0 0

在执行
call
语句后会跳转到
fun
对应的指令处，当执行到
return
指令的时候，会跳转到上一次执行
call
语句的下一句指令，也就是
add
这一句

代码实现

本节的目标是以尽可能短的代码、尽可能少的寄存器数量和尽可能短的运行时间来输出
\(h(n)\)
，为此首先要对
\(f\)
和
\(g\)
进行处理。容易验证
\(f(x)=(\sim x)\&3\)
，
\(g(x)=x\textasciicircum1\)
，这里要用到按位与“&”、按位取反“~”、按位异或“^“运算，均为简单的逻辑门运算，代码简单，运行速度快，而且”
\(\&3\)
“本质上就是对 4 取余，可以在不破坏值与指令一一对应关系的前提下将值限制在值的范围内。

下面给出的 Python 代码参考了:
图灵完备(Turing Complete)机器赛跑(Robot Racing)关卡纯汇编60字节达成成就纪念
:

n = 3 
r0 = 0 # 第几层递归， h(r0) 为第 n-r0 层递归
r1 = 0 # 当前路径方向

def fill():
  global r0, r1
  if r0 is not n:
    r0 += 1
    r1 = ~r1 # f
    fill() # f(h(n))
    print(r1 & 3, end='') # 对于当前层 n 的指令 3
    r1 = ~r1 # 回溯
    fill() # h(n)
    print(r1 & 3, end='') # 对于当前层 n 的指令 0
    fill() # h(n)
    r1 ^= 1 #g
    print(r1 & 3, end='') # 对于当前层 n 的指令 1
    fill() # g(h(n))
    r1 ^= 1 # 回溯
    r0 -= 1 # 回溯

fill()

fill() 实现的功能是输出以 r1 为起点朝向的 h(n-r0)，并且从终点出来后机器人的朝向仍为 r1。注意到
\(f(f(x))=x,g(g(x))=x\)
，因此递归的回溯只需要再调用一次
\(f\)
或
\(g\)
即可。

将其翻译为汇编语言如下:

label fill
equl|imme2 re0 3 end
add|imme2 re0 1 re0
not|imme2 re1 0 re1 
call fill 0 0
and|imme2 re1 3 out
not|imme2 re1 0 re1
call fill 0 0
and|imme2 re1 3 out 
call fill 0 0
xor|imme2 re1 1 re1 
and|imme2 re1 3 out
call fill 0 0
xor|imme2 re1 1 re1
sub|imme2 re0 1 re0
label end
return 0 0 0

只需要 60 个字节，达成成就”小机快跑“！而且只用到两个寄存器，并且运行时间也很短，非常优雅~

结语

汇编作为较底层的编程语言，其直接操作内存的方式赋予了这门语言独特的魅力。在优化
\(f\)
和
\(g\)
的过程中，我发现缺乏一定的 ”汇编直觉“ 或 ”逻辑门直觉'“是很难一眼看出优化方案的。一开始，我采用了较为笨拙的方法来实现这两个映射，直到阅读了那篇”容易看出“的文章后，我才豁然开朗，原来还能以这样的方式操作！

与此同时，分形是一门令人着迷的学科，其美丽和奇妙之处让人为之倾倒。通过这篇文章，我希望能够激发更多人发现这枚数学瑰宝的美丽。同时，我也鼓励图灵完备的玩家们努力实现 ”小机快跑“ 的成就！

参考文献

Mandelbrot Benoit B. 1983. The Fractal Geometry of Nature. [New edition] ed. New York: Freeman.
↩︎

使用分形思想，通过图灵完备的机器赛跑关卡，并获得小机快跑成就

前言

图灵完备

分形与希尔伯特曲线

正文

有向希尔伯特曲线

生成迷宫路径

汇编代码实现及优化

位和字节

寄存器

指令

add

语法

含义

例子

imme1

语法

含义

例子

imme2

语法

含义

例子

sub

语法

含义

例子

and

语法

含义

例子

xor

语法

含义

例子

not

语法

含义

例子

条件跳转

语法

含义

例子

equl

语法

含义

例子

call

语法

含义

例子

return

语法

含义

例子

代码实现

结语

参考文献

添加新评论

最新文章

最近回复

分类

归档

其它