文章合集引擎基礎設施策略專案
文章/套利

從零認識 RICH：用色彩編碼找出短獲利循環

套利課程第 8 課。為什麼機器人想找步數有限的循環、RICH 演算法（VLDB 2025）背後的色彩編碼技巧、一個小型可執行 Python 版本，以及誠實說明哪些部分被簡化了。

10 分鐘閱讀套利 課程 初學者

課程「建立自己的套利機器人」第 8 課。Bellman-Ford 和 SPFA 會找出任何獲利的圈。今天你會認識一種最近研究演算法背後的想法，它能找到好的短圈。

為什麼「任何圈」都不夠

假設 Bellman-Ford 回傳一個有九步的獲利圈。每一步都是一筆交易，而每筆交易都有手續費、延遲，以及你完成前價格移動的機會。在區塊鏈交易所，每一步還可能有網路手續費。實務上，九步的圈幾乎總是比利潤空間稍低的三步圈更差。

所以機器人需要問不同的問題：找出步數最多為 k 的獲利圈。電腦科學家稱這為 k-hop 負環問題。機器人決定 k（常見是 3、4 或 5）。

本課背後的研究論文是「RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage」（Luo、Jiang 與共同作者，PVLDB volume 18，VLDB 2025）。作者報告，在加密貨幣和外匯資料上，RICH 最多比早期方法快 32.7 倍。他們的方法建立在一個叫做色彩編碼的老技巧上，加上一些減少工作量的工程做法。今天我們建立核心技巧，省略工程部分。本課的簡化版本不是他們的程式碼。

正面做法，以及它在哪裡失效

若要從一個起始節點找出步數最多為 k 的最佳圈，你可以嘗試每一條長度最多為 k 的路徑。有 300 種貨幣、每種各有 6 個配對時，長度 4 的路徑每個起始節點大約有 6⁴ = 1296 條，這還可以。有 300 種貨幣、每種和 100 種其他貨幣交易時，則是每個起始節點 100⁴ = 100 million 條，這就不行了。

更聰明的方法是動態規劃：對每個節點和每個步數，記住到達那裡最便宜的路。這正是把輪數限制為 k 的 Bellman-Ford。問題是，最便宜的 k 步走法可能重複經過某種貨幣。四步的「圈」USD、EUR、USD、EUR、USD 不是真正的新機會：它只是把兩步圈做了兩次。你想要的是每種貨幣只經過一次的圈，叫做簡單環。強迫一條路徑沒有重複節點，正是這個問題困難的地方。

色彩編碼技巧

這個技巧聽起來很傻，卻很有效。

  1. 從 k 種顏色中，隨機給每種貨幣一種顏色。（如果 k = 3，每種貨幣隨機是紅、綠或藍。）
  2. 現在只找每一步顏色都不同的圈：一個紅、一個綠、一個藍。這種圈不可能重複經過同一種貨幣，因為重複的貨幣會重複它的顏色。
  3. 這個受限的搜尋很容易，因為你只需要記住已經使用哪些顏色，不需要記住哪些貨幣。有 k 種顏色時，已使用顏色的集合只有 2ᵏ 種。k = 3 時是 8，k = 5 時是 32。
  4. 真正能獲利的圈可能因為其中兩種貨幣拿到相同顏色而被漏掉。但如果隨機重新上色並重複，它就會被抓到。某一個有 k 種貨幣的圈剛好得到 k 種不同顏色的機率是 k!/kᵏ（k = 3 時：6/27，約 22%；k = 4 時：24/256，約 9%）。重複 50 或 100 次，漏掉它的機率就非常低。

打個比方：用三種隨機顏色替人群中的每個人上色，然後找一組剛好有三種不同顏色的三個人。換新顏色再做一次，又做一次。每一組真正的三位朋友遲早都會同時拿到三種不同顏色。

用一個很小的例子走一次

貨幣：USD、EUR、GBP、JPY。找出經過 USD、最多 3 步的最佳圈。

假設這一輪的隨機顏色是：USD 紅色、EUR 綠色、GBP 藍色、JPY 綠色。

搜尋會保留一張表。每一列表示：「我在這個節點，已使用這些顏色，到目前為止最便宜的成本是這個，而路徑是這個。」

  • 開始：在 USD，已使用 {紅色}，成本 0。
  • 第 1 步：從 USD 到 EUR（綠色，尚未使用）：在 EUR，已使用 {紅色，綠色}，成本 +0.1054。從 USD 到 GBP（藍色）：在 GBP，已使用 {紅色，藍色}，成本 +0.2877（0.75 的權重）。
  • 第 2 步：從 EUR 到 GBP（藍色，尚未使用）：在 GBP，已使用 {紅色，綠色，藍色}，成本 0.1054 + 0.1278 = 0.2332。從 EUR 到 JPY（綠色）：綠色已被使用，跳過。
  • 關閉這一圈：從 GBP 回 USD 的成本是 −0.2624。總和是 0.2332 − 0.2624 = −0.0292。總和是負數，因此 USD、EUR、GBP、USD 是一個獲利的簡單環。

如果顏色是 USD 紅色、EUR 綠色、GBP 綠色，這個圈在這一輪會被跳過（EUR 和 GBP 都是綠色），但之後顏色不同的一輪會找到它。

程式

import math, random

random.seed(7)
rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75,
         ("USD", "JPY"): 150.0, ("JPY", "USD"): 0.0066,
         ("EUR", "JPY"): 160.0, ("JPY", "EUR"): 0.0062}
nodes = sorted({n for edge in rates for n in edge})
w = {edge: -math.log(r) for edge, r in rates.items()}

def best_cycle_through(start, k, rounds=200):
    """Cheapest cycle through `start` with at most k steps, by colour-coding."""
    best = (math.inf, None)
    for _ in range(rounds):
        colour = {n: random.randrange(k) for n in nodes}
        # table[(node, 已使用顏色的集合)] = (cost, path); 這個集合是位元遮罩
        table = {(start, 1 << colour[start]): (0.0, [start])}
        for _step in range(k - 1):
            for (node, used), (cost, path) in list(table.items()):
                for (a, b), wt in w.items():
                    if a != node or b == start:
                        continue
                    bit = 1 << colour[b]
                    if used & bit:
                        continue                      # 這個顏色已經使用過
                    key = (b, used | bit)
                    if key not in table or cost + wt < table[key][0]:
                        table[key] = (cost + wt, path + [b])
        for (node, used), (cost, path) in table.items():
            if (node, start) in w and cost + w[(node, start)] < best[0]:
                best = (cost + w[(node, start)], path + [start])
    return best

cost, path = best_cycle_through("USD", 3)
print(path, "cost", round(cost, 4), "money x", round(math.exp(-cost), 4))

輸出：

['USD', 'EUR', 'GBP', 'USD'] cost -0.0292 money x 1.0296

程式找到獲利的三步圈，以及它的倍數 1.0296。

這個簡化版本省略了什麼

  • 它在內層迴圈掃描所有邊，這很慢。真正的實作會為每個節點儲存向外的道路。
  • 它沒有先縮減圖。論文描述了圖縮減和緊湊編碼，這些正是大部分加速效果的來源。
  • 它給出機率性的答案：隨機顏色有很小機率漏掉一個圈，輪數越多，機率越低。
  • 它處理一個起始節點。機器人會對所有起始節點做迴圈，或對所有節點使用同一張表。

把這堂課當成理解色彩編碼為何讓搜尋維持很小的方法（只有 2ᵏ 個顏色集合），工程部分請閱讀論文。

什麼時候值得用？

若你只需要知道是否存在任何獲利圈，使用 Bellman-Ford 或 SPFA。當許多步的圈對你沒用時（手續費、延遲、Gas 費），使用色彩編碼這類有限步數的搜尋，這幾乎總是如此。對很小的 k 和有幾百種貨幣的圖來說，搜尋成本夠小，可以在每次價格更新時執行。

讓 AI 代理人寫它並測試

一個模糊的要求：

實作 RICH。

一個包含範圍和檢查方式的要求：

不要實作完整的 RICH 論文。寫 colour_cycle.py，加入 best_cycle_through(start, k, rounds) 函式，以色彩編碼找出經過起始貨幣、最多 k 步的最便宜簡單環：每種貨幣隨機一種顏色、以 (node, 已使用顏色的位元遮罩) 為鍵的表，重複許多次隨機上色。使用匯率的負自然對數作為權重。測試：使用本課的十個匯率，起點 USD、k = 3 時，它必須回傳 USD、EUR、GBP、USD，資金倍數為 1.0296。測試 2：把所有匯率乘上 0.95，它必須不回傳負成本。儲存每個節點的向外邊，而不是掃描所有邊。

接著問代理人：「和論文相比，你省略了什麼？」好的代理人會列出省略部分。如果它聲稱已實作完整論文，不要相信它。

你的練習

  1. 執行程式。你應該看到倍數 1.0296。
  2. 把 rounds 從 200 改成 3、5、10，每個設定使用不同的隨機種子執行 20 次。有幾次漏掉這個圈？和 k = 3 時每輪機率 k!/kᵏ = 6/27 比較。
  3. 手算三種貨幣的圈在 10 輪後被漏掉的機率：(1 − 6/27)¹⁰ ≈ 0.08。
  4. 手算 USD、JPY、EUR、USD 的匯率乘積（150 × 0.0062 × 1.10）。它是 1.023，是第二個獲利圈，比第一個小。以 k = 3 和 rounds = 200 執行程式，確認程式偏好第一個圈，然後從權重解釋為什麼。

接下來

世界 2 到這裡結束。你的階段 1 現在能在匯率圖中找出獲利的圈。但所有這些匯率都是委託簿最上層的價格，只對很小的數量有效。世界 3 打開委託簿，問一個圈真正能承載多少資金。第 9 課會從閱讀和走過委託簿開始。

繼續閱讀