Chasing the Golden Snitch

在 Harry Potter 里面，Quidditch 是一种受到了几乎全世界巫师喜爱的扫帚运动。而 Golden Snitch 则是这种扫帚运动最有趣的一种比赛用球。不仅因为它快如闪电，更因为抓住它的球队可以赢得额外的 150 分，这很有可能扭转胜负的局势。

关于详细的规则参见：Quidditch。
那么我们关注的重点就是在这场 magic game 里，搜寻手如何在一个不断变化的环境中追踪一个随机移动目标？

Table of contents

Brute-force Search

最简单和朴素的想法就是把场地的任何一个位置都搜寻一遍，这样我们总是可以找到对吧？但问题在于在一个三维空间进行这种搜寻方式需要损耗的时间和精力是无法接受的，效率过低。而且 Golden Snitch 还在高速移动，所以对于比赛而言，这是下策。

Greedy Search

暴力搜索的问题就在于这种方式会忽略种种对于提高搜寻概率的条件置若罔闻，原著中这样写道：

And then he saw it. A spearing flash of gold, a flutter of tiny wings — the Snitch.

这告诉我们一个信息，Golden Snitch 经过的地方会留下 a flash of gold。这对我们来说非常重要，那么我们在看到光芒之后会优先选择前往它出现的地方，这是一个很自然的想法。但问题在于 Golden Snitch 会高速移动，那么等到搜寻手赶到上一次 Golden Snitch 出现的位置，可能它已经逃之夭夭了。所以这种方法也被否决了。

Bayesian Search

所以真正聪明的搜寻手会选择去看哪里 Golden Snitch 出现的概率最高，然后前往那个位置。也就是基于目前掌握的所有信息，来推理计算此时哪里出现 Golden Snitch 的概率最高，这才是一种真正聪明的做法。因此，让我们来探索和解释如何利用这种方式去完成高效的搜寻吧！

Derivation

我们可以把整个 Quidditch 球场看作一个三维空间，并为每一个位置赋予一个概率：$P(x,y,z)$，用于表示 Golden Snitch 出现在坐标 $(x,y,z)$ 的可能性。
一开始，由于搜寻手没有任何信息。我们假设 Golden Snitch 出现在任何位置的概率相同，即服从均匀分布。

设：当 Golden Snitch 经过 $(x_0,y_0,z_0)$ 时，会在该位置留下一道强度为 $I_0$ 的光芒。残光随着时间 $t$ 指数衰减：

其中 $\lambda$ 是衰减系数，我们在时间 $t$ 观察到光芒的强度为 $I(t)$。
所以我们可以通过贝叶斯定理来更新 Golden Snitch 出现在 $(x_0,y_0,z_0)$ 的概率：

其中：

• $P(I(t)|x_0,y_0,z_0)$ 是当Golden Snitch经过 $(x_0,y_0,z_0)$时 我们观察到光芒强度为 $I(t)$ 的概率。我们可以假设这个概率与光芒强度成正比，即：

• $P(x_0,y_0,z_0)$ 是在没有任何观测信息时，Golden Snitch 出现在 $(x_0,y_0,z_0)$ 的先验概率。由于我们假设 Golden Snitch 出现在任何位置的概率相同，所以：

其中 $V$ 是球场的体积。

• $P(I(t))$ 是在时间 $t$ 观察到光芒强度为 $I(t)$ 的总概率，可以通过对所有可能位置的积分计算得到：

通过以上公式，我们可以不断更新每个位置的概率分布，从而指导搜寻手前往最有可能出现 Golden Snitch 的位置进行搜寻。

From Search to Tracking

但是我们也说过，Golden Snitch 是一个高速移动的目标，所以我们不能仅仅依赖于当前的概率分布来进行搜寻，不然和 Greedy Search 好像没什么差别。我们需要考虑到 Golden Snitch 的运动轨迹和速度，从而进行动态追踪。
为了描述 Golden Snitch 的运动，我们需要引入一个状态，它在 $t$ 时刻的位置

但是，仅仅知道位置是不够的。例如，如果我们知道 Golden Snitch 当前位于某个位置：

我们仍然无法预测它下一秒会出现在哪里，因为它可能向任意方向移动。
因此，我们还需要考虑它的速度：

其中 $\mathbf{v}_{t-1}$ 表示 Golden Snitch 在上一时刻的运动速度。
在一个简单的运动模型中，我们假设 Golden Snitch 下一时刻的位置由当前的位置、速度以及随机扰动共同决定，满足马尔科夫性质：

其中：

• $\mathbf{x}_{t-1}$ 表示上一时刻的位置；
• $\mathbf{v}_{t-1}\Delta t$ 表示根据当前速度预测的位置变化；
• $\boldsymbol{\epsilon}_t$ 表示运动过程中无法预测的随机变化。

由于 Golden Snitch 的飞行并不是完全规则的，它可能突然改变方向或者速度，因此我们将这种随机扰动建模为高斯噪声：

其中 $\sigma$ 控制随机扰动的大小。

Prediction Step

有了 Golden Snitch 的运动模型后，我们就可以根据过去的信息预测它下一时刻可能出现的位置。
假设在 $t-1$ 时刻，我们已经根据之前所有观测得到 Golden Snitch 的概率分布：

其中：

• $I_{1:t-1}$ 表示从开始到 $t-1$ 时刻观察到的所有光芒信息；
• $P(\mathbf{x}_{t-1}|I_{1:t-1})$ 表示结合历史观测后，Golden Snitch 在上一时刻各个位置出现的概率。

当时间推进到 $t$ 时刻时，Golden Snitch 会根据运动模型移动，因此原来的概率分布也会随之变化。
新的预测分布为：

只看这个公式可能有点抽象，我们这样理解：$P(\mathbf{x}_{t-1}|I_{1:t-1})$ 表示在上一时刻，Golden Snitch 在各个位置出现的概率分布。$P(\mathbf{x}_t|\mathbf{x}_{t-1})$ 表示从上一时刻的位置 $\mathbf{x}_{t-1}$ 移动到当前时刻位置 $\mathbf{x}_t$ 的概率分布。通过对所有可能的上一时刻位置进行积分，我们就得到了当前时刻 Golden Snitch 可能出现的位置的预测分布。

Measurement Update

然而，仅仅依靠运动模型进行预测是不够的。
因为 Golden Snitch 的运动包含随机性，我们无法准确知道它下一秒的位置。
因此，当搜寻手再次观察到新的金色闪光 $I_t$ 时，需要利用新的观测信息修正预测结果。
根据 Bayes 定理，当我们根据前 $t-1$ 个时刻的观测信息预测 Golden Snitch 在 $t$ 时刻可能出现的位置后，又获得了新的观测信息 $I_t$，我们可以利用当前的光芒信息对原来的预测进行修正，从而更新 Golden Snitch 出现在各个位置 $\mathbf{x}_t$ 的概率分布：

其中：

• $P(\mathbf{x}_t|I_{1:t-1})$ 是 Prediction Step 得到的预测结果；
• $P(I_t|\mathbf{x}_t)$ 表示如果 Golden Snitch 位于某个位置，观察到当前光芒的可能性；
• $P(\mathbf{x}_t|I_{1:t})$ 是结合新观测后的最终估计。

这个过程不断循环，直到搜寻手成功抓住 Golden Snitch。
不过话说回来，虽然在理论上，我们完全可以通过上述公式精确地描述 Golden Snitch 的概率分布。然而，在实际计算中，由于 Quidditch 球场是一个连续的三维空间，直接计算这种高维积分往往十分困难。
因此，实际系统通常会采用粒子滤波(Particle Filter)来近似这种连续的概率分布。它不再尝试计算整个空间的精确概率，而是使用大量离散的「粒子」表示 Golden Snitch 可能出现的位置。
每一个粒子都可以看作一个可能的假设：

• 粒子越密集的区域，表示 Golden Snitch 出现的概率越高；
• 随着新的观测信息加入，不符合观测结果的粒子会被淘汰，而更可能的位置会获得更多粒子。

通过不断地移动、筛选和重新采样这些粒子，搜寻手就可以近似追踪 Golden Snitch 的运动轨迹。