Урок 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", а число у стрелки — курс: сколько единиц B вы получите за одну единицу A. Стрелки называют ребрами.
Небольшой рынок:
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 км, потом 5 км — всего 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.
Попросим ИИ-агента написать код
Расплывчатый запрос:
Найди арбитраж в графе валют.
Запрос, в котором задан именно этот шаг:
Напиши файл 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 мы разберем классический способ — алгоритм Беллмана-Форда.
