課程「建立自己的套利機器人」第 5 課。階段 1 變得更聰明：我們不再比較兩個價格，而是看貨幣形成的圈。
問題
在同一間交易所，你可以把 USD 換成 EUR、EUR 換成 GBP、GBP 換成 USD，還有許多其他交易對。第 2 課說過，USD 到 EUR 到 GBP 再回到 USD 這一圈，最後的錢可能比一開始更多。只有三種貨幣時，你可以在腦中檢查；有五十種貨幣時，卻有數千個圈。你需要一種不必逐一嘗試的方法。
本課會打好基礎，還不會開始搜尋。第 6、7、8 課才會進行搜尋。
直接硬做的方法，以及它的極限
直接的方法是：列出每一個圈並把它們的匯率相乘。只有 3 種貨幣時，圈並不多，你可以像第 2 課那樣在腦中計算。有 50 種貨幣時，3 步的圈有 50 × 49 × 48 = 117 600 個，4 步的圈有 5 527 200 個，而且每多一步，數量大約就乘上 50。程式仍可對幾步的情況這樣做，但對真正的交易所來說成長得太快。第 6 課會用程式執行這種直接搜尋，並測量它在哪裡失效。本課先準備一種更好的表示方式。
第 1 步：畫出來
圖是由箭頭連起來的一組點。這裡的點是貨幣，叫做節點。從 A 指向 B 的箭頭表示「你可以把 A 換成 B」，箭頭上的數字是匯率：一單位 A 能換到多少單位 B。箭頭叫做邊。
我們的小市場：
USD --0.90--> EUR
EUR --0.88--> GBP
GBP --1.30--> USD
EUR --1.10--> USD
一個圈是最後回到起點的路徑。USD、EUR、GBP、USD 是一個有三條邊的圈。
第 2 步：跟著錢走
從 100 USD 開始，走過這一圈：
- USD 換 EUR 後：100 × 0.90 = 90 EUR
- EUR 換 GBP 後：90 × 0.88 = 79.2 GBP
- GBP 換 USD 後：79.2 × 1.30 = 102.96 USD
這一圈讓你的錢乘上 0.90 × 0.88 × 1.30 = 1.0296。乘積大於 1 表示獲利，小於 1 表示虧損，剛好等於 1 表示什麼都沒發生。
因此問題是：有沒有一個圈的匯率乘積大於 1？
第 3 步：乘法的問題
搜尋圖的程式擅長沿著路徑把數字相加（「這條路是 3 km，接著是 5 km，總共 8」），它們不是為乘法設計的。我們可以把乘法轉成加法嗎？
可以，用對數。這門課只需要知道自然對數（寫成 ln）的三個事實：
- ln(a × b) = ln(a) + ln(b)。乘法變成加法。
- ln(1) = 0。
- 如果 x 大於 1，ln(x) 是正數；如果 x 在 0 和 1 之間，ln(x) 是負數。
你可以用任何計算機驗證。例如，ln(2) = 0.693、ln(3) = 1.099，而 ln(6) = 1.792，也就是 0.693 + 1.099。
把事實 1 套用到我們的圈：
ln(0.90 × 0.88 × 1.30) = ln(0.90) + ln(0.88) + ln(1.30)
數字是：−0.1054 − 0.1278 + 0.2624 = +0.0292。
這個圈的總和是 +0.0292。大於 1 的乘積變成大於 0 的總和。我們已經把「相乘」轉成「相加」。
第 4 步：翻轉符號
圖論演算法通常尋找短或便宜的路徑，所以較小的數字對它們較好，負數更是最好。我們希望利潤對它們來說是小且負的，因此翻轉符號。定義一條邊的權重：
weight = −ln(rate)
那麼，我們這一圈是：
- USD 到 EUR：−ln(0.90) = +0.1054
- EUR 到 GBP：−ln(0.88) = +0.1278
- GBP 到 USD：−ln(1.30) = −0.2624
總權重 = −0.0292，低於零。
獲利的一圈，是權重加總小於零的一圈，叫做負環。
兩行規則：
- 匯率乘積大於 1，和權重總和小於 0 是同一件事；
- 這一圈的資金倍數是 e 的負總權重次方（這裡 e^0.0292 = 1.0296）。
第 5 步：在程式中看它
import math
rates = {
("USD", "EUR"): 0.90,
("EUR", "GBP"): 0.88,
("GBP", "USD"): 1.30,
("EUR", "USD"): 1.10,
}
money = 100.0
for a, b in [("USD", "EUR"), ("EUR", "GBP"), ("GBP", "USD")]:
money *= rates[(a, b)]
print(a, "->", b, "money =", round(money, 4))
print("product of rates:", round(0.90 * 0.88 * 1.30, 4))
weights = {edge: -math.log(rate) for edge, rate in rates.items()}
for edge, w in weights.items():
print(edge, round(w, 4))
cycle = [("USD", "EUR"), ("EUR", "GBP"), ("GBP", "USD")]
total = sum(weights[e] for e in cycle)
print("sum of weights:", round(total, 4))
print("money multiplier:", round(math.exp(-total), 4))
輸出：
USD -> EUR money = 90.0
EUR -> GBP money = 79.2
GBP -> USD money = 102.96
product of rates: 1.0296
('USD', 'EUR') 0.1054
('EUR', 'GBP') 0.1278
('GBP', 'USD') -0.2624
('EUR', 'USD') -0.0953
sum of weights: -0.0292
money multiplier: 1.0296
兩種檢查結果一致：資金從 100 變成 102.96，權重總和是 −0.0292，而 e 的 0.0292 次方是同樣的 1.0296。
手續費放在哪裡
每筆交易收 0.1% 手續費，表示你只能得到匯率所說金額的 0.999。先把每個匯率 r 改成 r × 0.999，再取對數。對有三條邊的圈來說，倍數會少大約 0.3%，我們的圈還撐得住：1.0296 × 0.999 × 0.999 × 0.999 ≈ 1.0265，也就是 2.96% 變成大約 2.65%。但利潤空間只有 0.2% 的圈就會消失：手續費吃掉的比它賺的還多。這就是為什麼真正機器人的第一個篩選器，是把手續費放進權重裡；第 10 課會這樣做。
讓 AI 代理人寫它
一個模糊的要求：
在貨幣圖中找套利。
一個剛好建立這一步的要求：
寫 graph.py。接受一個匯率字典 {("USD","EUR"): 0.90, ...}，以匯率的負自然對數建立權重，並加入一個 cycle_gain(cycle) 函式，回傳指定圈的資金倍數，也就是 e 的負權重總和次方。用 USD、EUR、GBP、USD 測試，匯率是 0.90、0.88、1.30，並印出結果。它必須印出 1.0296。還不要搜尋圈。
如果代理人印出其他結果，檢查就失敗了，你要請它修正。這就是使用你能手算驗證的數字。
你的練習
- 執行上面的程式。五個印出的數字和我的一致嗎？
- 自己做一個有三個匯率的新市場：A 到 B 是 2.0、B 到 C 是 0.6、C 到 A 是 0.9。先手算乘積，再算權重和總和。它是獲利的一圈嗎？（乘積 = 1.08，所以是。）接著用程式檢查。
- 改一個匯率，讓乘積剛好變成 1.0，並檢查權重總和是 0。
- 用相反方向走同一個圈。證明如果一個方向的乘積是 p，另一個方向大約是 1/p（每條箭頭使用反向匯率 1/r 時）。因此兩個方向最多只有一個能獲利。
接下來
現在整個問題是：怎樣才能不逐一嘗試所有圈，找出有許多節點的圖中的負環？第 6 課會介紹經典答案 Bellman-Ford。
